4

WYKLAD 9

1. KRYPTOSYSTEM RSA

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ą).

Szyfrowanie korespondencji

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.

Uwierzytelnianie

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

Szyfrowanie

Szyfrowane mogą być liczby m <n:

E(m)=me mod n

Wtedy dla bloku tekstu jawnego otrzymujemy kryptogram c = E(m)

Deszyfrowanie

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ą

Algorytm opiera się na kongruencji

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.

MIPS godzinę=1.000.000...