4
Został przedstawiony w 1977 r. Nazwa pochodzi od nazwisk jego autorów: R.Rivesta, A. Shamira i L. Adlemana.
RSA wymaga wielu operacji arytmetycznych. Prędkość szyfrowania i deszyfrowania jest znacząco niższa niż dla DES-a (do 1000 razy).
Specyficzne zastosowania RSA: dzięki warunku
jeśli DK1(EK2(x))=x to EK1(DK2(x))=x
tej samej pary kluczy można użyć do różnych celów.
Niech klucz K1 jest kluczem prywatnym, a klucz K2 – publicznym A (nazywany tradycyjnie Alicją).
B (Bob) pragnie przesłać list M do A. W tym celu B oblicza EK2(M) i wysyła. A otrzymuje EK2(M) i oblicza DK1(EK2(M))=M. Bez znajomości K1 trudno deszyfrować EK2(M), tak więc tylko A może odczytać list od B.
A pragnie rozesłać komunikat T potwierdzając przy tym, że jest jego autorką. A koduje T jako EK1(T). Każdy odbiorca deszyfruje wiadomość za pomocą K2 jako DK2(EK1(T))=T.
Algorytm RSA.
Niech mamy pewien system z dużą liczbą użytkowników i każdy może chcieć wysłać tajną wiadomość do innego. Jednostkami m tekstu jawnego są liczby całkowite z przedziału 0£ m <N. Wiadomość mogą składać się z bloków liter alfabetu, np. łacińskiego, traktowanych jako rozwinięcia liczb całkowitych przy podstawie 10, przy czym litery pełnią rolę cyfr. W praktyce liczba N ma około od 200 do 600 znaków dziesiętnych.
Każdy użytkownik:
Wybór kluczy:
1. Losowo wybiera dwie duże liczby pierwsze p i q tak, żeby ich iloczyn n=pq>N
2. Losowo wybiera liczbę e tak, aby e było tego samego rzędu wielkości co n (e<f(n)=(p-1)(q-1)) oraz e i f(n) były względnie pierwsze (NWD(e,f(n))=1), gdzie f(n) jest funkcja Eulera. (Inaczej mówiąc eÎZ*f(n) )
3. Za pomocą algorytmu Euklidesa znajduje liczbę d:
e d º 1 (mod f(n))
e, n jest wygenerowanym kluczem publicznym
d jest wygenerowanym kluczem prywatnym
Szyfrowane mogą być liczby m <n:
E(m)=me mod n
Wtedy dla bloku tekstu jawnego otrzymujemy kryptogram c = E(m)
D(c) = cd mod n
Przykład. Niech p=53 i q=67. Wtedy n=3551 i f(n)=3432. Wybieramy e=1021. Obliczamy przy użyciu algorytmu Euklidesa NWD(1021,3432) =1. Jednocześnie obliczamy d=1021-1 mod 3432=1237. Klucze są wygenerowany: 1021, 3551 - publiczny, 1237 – prywatny.
Co robi użytkownik B, gdy pragnie przesłać A wiadomość, np. 192018050013?
1. Szuka w książce telefonicznej klucza publicznego A: e, n
2. Wiadomość składa z bloków po 4 liczby, ze względu na n: 1920 1805 0013
3. Oblicza:
19201021 mod 3551=2393
18051021 mod 3551=1788
131021 mod 3551=2188
4. Otrzymany kryptotekst 239317882188 przesyła A.
Aby odszyfrować wiadomość A posługuje się swoim tajnym kluczem d=1237:
23931237 mod 3551=1920, ...
Zasady tworzenia kluczy, szyfrowania i deszyfrowania opierają się na następujące twierdzenie, jakie wypływa z twierdzenia Eulera.
Twierdzenie 1. Niech n=pq jest iloczynem dwóch różnych pierwszych liczb. Jeśli e d º 1 (mod f(n)), to dla wszystkich xÎZn
xed º x (mod n)
W trakcie szyfrowania i deszyfrowania wykonane są operacje podnoszenia liczb do dużych potęg: ad mod n. Dla tego:
1. Przedstawimy liczbą d w postaci binarnej: d=d0 2 r + ... + dr-1 2 + d r , gdzie di jest liczbami równymi 0 czyli 1, d0=1
2. Połóżmy a0=a oraz dla i=1, 2,..., r obliczymy
3. a r jest szykaną resztą
i zawiera około 2log2 d mnożeń modulo n.
Twierdzenie 2. Niech A będzie algorytmem, który dla zadanego klucza e, n algorytmu RSA znajduje pasujący klucz d. Wtedy można skonstruować algorytm z podprocedurą A, który rozkłada n na czynniki pierwsze oraz ma podobny czas obliczeń i używa podobnej pamięci co A.
Twierdzenie oznacza, że jeśli istnieje praktyczna metoda znajdowania prywatnych kluczy, to można wskazać praktyczny algorytm rozkładu n na czynniki pierwsze. Przy tym poprzez rozkład n na czynniki pierwsze można łatwo odtworzyć obliczenie prywatnego klucza.
Problem rozkładu liczb na czynniki pierwsze jest problemem z klasy NP, ale nie wiadomo, czy jest to problem NP- zupełny, co świadczyłoby o jego trudności. Z drugiej strony najlepsze obecne znane algorytmy wymagają dość dużych czasów obliczeń. Ten czas obliczeń zależę od ilości bitów liczby n: , gdzie n jest ilość bitów.
Ilość bitów n
L(n)
Ilość MIPS lat
512
6.7´1019
2.1´106
576
1.7´1021
5.5´107
......
.........
................
960
3.7´1028
1.2´1015
1024
4.4´1029
1.4´1016
MIPS godzinę=1.000.000...
pio1281trek