Co to jest rsa?



Pobieranie 13.68 Kb.
Data08.05.2016
Rozmiar13.68 Kb.
Co to jest RSA?
W roku 1978 trzej informatycy i matematycy dokonali przełomu w świecie szyfrowania danych. Ronald Linn Rivest, Adi Shamir i Leonard Adleman opublikowali nowy rodzaj szyfrowania, którego nazwa jest akronimem ich nazwisk. RSA jest pierwszym szyfrem asymetrycznym tzn. algorytm deszyfrowania nie wynika z algorytmu szyfrowania (znając algorytm szyfrowania nie jesteśmy w stanie odszyfrować danych). Charakterystyczną cechą RSA są dwa klucze – publiczny i prywatny. Publiczny służy do szyfrowania danych i może go znać każdy. Klucz prywatny służy do deszyfrowania i jest chroniony.
Algorytm generowania klucza publicznego i prywatnego oparty jest na twierdzeniu Eulera, którego treść brzmi:
aφ(b) mod b=1 gdy a i b to para liczb względnie pierwszych
φ(b) to wartość funkcji Eulera dla argumentu b. Wartość tej funkcji to ilość liczb względnie pierwszych z argumentem mniejszych od niego.


Generowania kluczy

1.Wybieramy dwie duże (512 lub 1024 bitowe) liczby pierwsze p i q.

2.Znajdujemy liczbę n=pq

3.Znajdujemy φ(n)=(p-1)(q-1) (po tym kroku liczby p i q powinny zostać zniszczone)

4.Znajdujemy liczbę e taką, że φ(n) i e to para liczb względnie pierwszych i e € (1,n)

5.Znajdujemy liczbę d taką że de mod φ(n)=1

Para liczb n i e to klucz publiczny

Para liczb n i d to klucz prywatny


szyfrowania i deszyfrowanie:

w- liczba właściwa

s- liczba szyfrowana


s= wn mod e

w=sn mod d liczby 0 i 1 nie zostaną zaszyfrowane!!!


RSA na dzień dzisiejszy jest praktycznie nie do złamania. Aby złamać szyfr RSA musielibyśmy poddać faktoryzacji liczbę n, aby otrzymać liczby p i q, które umożliwią nam wygenerowanie klucza prywatnego. Sprawdźmy ile czasu zajmie złamanie RSA:
Jedyną metodą faktoryzacji liczb jest szukanie ich dzielników. Z własności liczb wiemy, że jeden z czynników pierwszych (p lub q) liczby n jest mniejszy od pierwiastka z n. . Liczba n jest 512 bitowa, zatem jej pierwiastek jest 256 bitowy. Mamy 2256 liczb do sprawdzenia, szukamy liczby nieparzystej – co druga liczba jest nieparzysta, więc mamy 2256:2=2255 liczb do sprawdzenia. Statystycznie poszukiwany czynnik pierwszy powinien znajdować się w górnej połówce zakresu od 2 do pierwiastka z n, więc mamy dwa razy mniej liczb do sprawdzenia czyli 2255:2=2254. Komputer, który ma powstać w 2011 roku na zlecenie rządu USA będzie wykonywał dwadzieścia tysięcy bilionów operacji na sekundę (2*1016 operacji na sekundę). 2254:(2*1016)=1,447401115*1060 sekund

1,447401115*1060 sekund : 60 =2,412335192*1058 minut

2,412335192*1058 minut : 60 =4,020558654*1056 godzin

4,020558654*1056 godzin : 24=1,675232773*1055 dni

1,675232773*1055 dni : 365=4,589678829*1052 lat

Nie brzmi to optymistycznie, szczególnie że liczba n może być 1024 bitowa.



Przykład generowania klucza
1. p=5 q=7

2. n=pq=5*7=35

3. φ(n)=(p-1)(q-1)=4*6=24 (niszczymy p i q)

4. Rozkładamy φ(n) na czynniki pierwsze 24=2*2*2*3 i wybieramy liczbę e względnie pierwszą z φ(n): e=7*5

5. de mod φ(n)=1

d*e- φ(n)*y=1

35d- 24y=1
Rownanie diofantyczne:

Aby wyliczyć d musimy teraz rozwiązać równanie diofantyczne (postać równania diofantycznego ax+by=c, dane mamy a,b i c – a=35 b=-24 c=1). Stosujemy rozszerzony algorytm Euklidesa.


1.a musimy przedstawić jako sumę iloczynu |b| *z i liczby całkowitej większej od zera i mniejszej od |b|:
35=24*1+11 11 jest naszą resztą.
2.Teraz liczbę, którą mnożyliśmy przedstawiamy jako sumę iloczynu reszta*z’ i liczby całkowitej większej od zera i mniejszej od reszty. (analogicznie do pierwszego kroku)
24=11*2+2
3.Postępujemy tym samym sposobem, do momentu w którym reszta jest równa 1.
11=2*5+1
Powyższe równanie przekształcamy, aby wyliczyć 1:
1=11-5*2
Równanie z kroku 2. przekształcamy tak, aby wyliczyć 2 ( 2=24-2*11) i podstawiamy do równania z jedynką 1=11-5*2=11-5(24-2*11)=11*11-5*24
Równanie z kroku 1. przekształcamy tak, aby wyliczyć 11 (11=35-24*1) i podstawiamy do równania z jedynką 1=11*11-5*24=11(35-24*1)-5*24=35*11-24*16
Porównajmy to równanie z naszym równaniem diofantycznym z niewiadomymi d i y.

1=35*11-24*16

1=35d-24y

Nasz wykładnik prywatny d=11.


Nasz klucz prywatny to n=35 i e=35, a klucz publiczny to n=35 i d=11

Aby zaszyfrować liczbę w do liczby s wykonujemy działanie



s=w35 mod 35
Deszyfrowanie:
w=s35 mod 11
Mikołaj Wawrzyniak


©absta.pl 2016
wyślij wiadomość

    Strona główna