Strona główna

Wstęp do kryptografii kwantowej


Pobieranie 24.59 Kb.
Data19.06.2016
Rozmiar24.59 Kb.
Wstęp do kryptografii kwantowej

  • Systemy kryptograficzne z kluczem publicznym wykorzystują fakt, że rozkład dużej liczby na czynniki jest trudny (czasochłonny)

  • Najszybszy obecnie algorytm wymaga czasu:

~exp[(64/9)1/3(ln ln N)2/3]

faktoryzacja liczby 400 cyfrowej wymagałaby 1010 lat



  • W 1994 r. RSA 129 został złamany na 1600 stacjach roboczych w ciągu 8 miesięcy

  • Algorytm kwantowy Petera Shora wymaga czasu:

~(ln N)2+e

komputer kwantowy, który sfaktoryzowałby liczbę 130 cyfrowa w ciągu miesiąca, sfaktoryzowałby liczbę 400 cyfrowa w czasie krótszym niż 3 lata.



Mechanizm działania algorytmu RSA, czyli jak wygląda kryptografia
z kluczem publicznym.


N = pq

  • Znajdujemy funkcję Eulera

φ(N) = N − p − q +1 = (p − 1)(q − 1)

Teraz każdy może użyć naszego klucza publicznego do zaszyfrowania informacji przesyłanej do nas.

  • Wyznaczamy d < φ(N) takie, że de = 1 mod φ(N) .

To jest nasz klucz prywatny, którego pilnie strzeżemy!

Przykład:

Weźmy: p = 11, q = 13;

N = 11 * 13 = 143;

φ(N) = 10 * 12 = 120

wybieramy: e = 7;

(120 − 1)/7 = 17 jest całkowite;

d = 120 − 17 = 103.

Weźmy: M = 31 (to jest wiadomość do zaszyfrowania)

Szyfrujemy: 317 mod 143 = 125

Rozszyfrowujemy: 125103 mod 143 = 31



Klucz publiczny: {e,N}

Klucz prywatny: {d,N}

Szyfrowanie: C = Me mod N

Deszyfrowanie: M = Cd mod N

Kwantowa faktoryzacja

Chcemy sfaktoryzować liczbę N = 15. Wybieramy liczbę losową 1 < X <

N − 1 względnie pierwszą z N, tzn. taką, że NWD(N,X) = 1, powiedzmy

X = 2.


liczb od 0 do 15

A

0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15



  • Wykonujemy operacje B = XA mod N, wykorzystując kwantowy

paralelizm. Wyniki umieszczamy w rejestrze B. Komputer kwantowy

wykonuje taką operację w jednym kroku!



A

0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

B

1

2

4

8

1

2

4

8

1

2

4

8

1

2

4

8

  • Zauważamy, że wyniki w rejestrze B są okresowe z okresem r = 4.

Komputer kwantowy potrafi szybko znajdować okres funkcji!

nowa. Jeśli r jest parzyste, obliczamy P = Xr/2 − 1 lub P = Xr/2 + 1

i sprawdzamy czy P jest dzielnikiem N. W naszym przykładzie r = 4 i

P = 24/2 − 1 = 3 lub P = 24/2 +1 = 5.

15/3 = 5


15/5 = 3


©snauka.pl 2016
wyślij wiadomość