Podręcznik

5. Szyfry i kryptografia

5.11. Algorytm szyfrowania szyfrem RSA

Szyfr RSA jest typowym, najczęściej stosowanym szyfrem z kluczem publicznym. Nazwa RSA pochodzi od nazwisk 3 profesorów z MIT (Massachussets Institute of Technology) R.L.Rivesta, A.Shamira i L.M.Adlemana, którzy w roku 1978 opracowali koncepcję tego szyfru. Szyfr RSA uważany jest za jeden z najbezpieczniejszych, najpewniejszych szyfrów. Używany jest do szyfrowania wiadomości, do tworzenia podpisów cyfrowych oraz dystrybucji kluczy kryptograficznych.

Opiszemy teraz, jak tworzymy system kryptograficzny RSA. Potrzebne nam będzie przy omawianiu szyfru RSA pojęcie funkcji Eulera. Dla danej liczby naturalnej n symbolem  (n) oznaczamy liczbę liczb naturalnych względnie pierwszych z n i mniejszych od n, tzn.  (n)  card{m  N; m  n, NWD(m, n)  1}. W ten sposób definiujemy funkcję  : N  N , która nazywa się funkcją Eulera. Łatwo można wykazać, że jeśli p jest liczbą pierwszą to  ( p)  p  1 i dla każdego k  N , mamy

 ( p^k )  p^k ^¹( p  1) $\qquad$ (1)

Jeśli m i n są względnie pierwszymi liczbami naturalnymi to mamy

 (mn)   (m) (n) $\qquad$ (2)

Z (1) i (2) dostajemy, że jeśli n  p₁^k¹p₂^k² ...  p_r^k^r, gdzie p₁, p₂ ,..., p_r są parami różnymi liczbami pierwszymi to

 (n)  p₁^k¹^¹( p₁  1)  p₂^k²^¹( p₂  1)  ...  p_r^k^r^¹( p_r  1) $\qquad$ (3)

Wybieramy teraz dwie duże liczby pierwsze p i q obliczamy iloczyn n=pq oraz wartość funkcji Eulera  (n)  ( p  1)(q  1) . Wybieramy następnie losowo dowolną taką liczbę (n) d  Z_(n), dla której istnieje element odwrotny e  d ^¹ w pierścieniu Z_{ (n)} czyli takie e  Z_{ (n)} by d _{ (n)}e  1 w pierścieniu Z_{ (n)}(oczywiście jest to równoważne temu by znaleźć takie e  Z_{ (n)}, żeby d  e  1 (mod (n)) ). Warunkiem koniecznym i dostatecznym na to by istniał taki element odwrotny jest by NWD( (n), d )  1 . Obliczamy e  d ^¹ i ujawniamy parę uporządkowaną (e,n) jako klucz publiczny. Kluczem prywatnym będzie para uporządkowana (d,n).

Tekst szyfrowany, czyli tekst jawny m V₁ ^ np. "ala ma kota" zamieniamy na liczbę całkowitą x np. 10982398.

Podnosimy tę liczbę do ustalonej potęgi e w pierścieniu Z_n ((e,n) jest znane i stanowi klucz publiczny) lub co na jedno wychodzi podnosimy tę liczbę do potęgi e w pierścieniu Z i bierzemy resztę z dzielenia tej liczby przez liczbę n. Tę resztę wysyłamy do adresata.

c  x^e

Adresat podnosi (w pierścieniu Z_n) uzyskaną liczbę do pewnej potęgi d będącej kluczem tajnym czyli kluczem prywatnym uzyskując wiadomość jawną x.

x  c^d

Algorytmy RSA mające klucz o długości do 512 bitów, są stosunkowo proste do złamania. Adi Shamir opracował w 1999 r. specjalizowany równoległy komputer łamiący 512 bitowe RSA w ciągu 2 dni. Obecnie stosuje się już klucze 1024 bitowe a nawet 2048 i 4096 bitowe praktycznie całkowicie bezpieczne (w 2003 r.) tzn. nie do złamania przy współczesnym stanie wiedzy o algorytmach komputerowych i przy współczesnych możliwościach obliczeniowych systemów cyfrowych.

Rivest, Shamir i Adleman w słynnej słynnej zagadce zamieszczonej w 1977 roku w czasopiśmie "Scientific American" zamieścili szyfrogram pewnego tekstu jawnego, proponując czytelnikom odtworzenie tego tekstu z szyfrogramu. Użyli przy tym szyfru nazwanego później RSA-129. Liczba 129 w oznaczeniu bierze się od 129 cyfrowej liczby (cyfry dziesiętne), którą trzeba rozłożyć na czynniki pierwsze by uzyskać klucz i funkcję odwrotną deszyfrującą szyfrogram. Zadanie przed którym stanęli czytelnicy było więc typowym problemem przed którym staje kryptoanalityk. Szyfr RSA-129 został w końcu złamany w 1994 roku dzięki równoległej pracy wielu komputerów w sieci komputerowej i superkomputerów równoległych.

Fakt praktyczny: żeby złamać szyfr RSA musimy umieć rozkładać duże liczby na czynniki pierwsze. Do określenia funkcji odwrotnej do funkcji szyfrującej czyli funkcji deszyfrującej potrzebna jest znajomość 2 liczb pierwszych, p i q, których iloczyn daje n.

Wykażemy teraz poprawność RSA. Skorzystamy z następującego lematu będącego konsekwencją chińskiego twierdzenia o resztach.

Lemat: Niech m₁, m₂,..., m_n N będą parami względnie pierwsze (tzn. NWD(m_i, m _j)  1 dla każdego i, j  1, n ,i  j ) i m_i 2 dla każdego i=1,2,...,n oraz niech a, b będą dowolnymi liczbami całkowitymi czyli a, b  Z .

a  b(mod m_i) dla każdego i=1,2,...,n wtedy i tylko wtedy gdy a  b(mod m₁ m₂... m_n)

Dowód poprawności algorytmu RSA: Z założenia ed  1 (mod  (n)), zatem istnieje takie k  Z , że

ed  1  k  (n) $\qquad$ (*)

Załóżmy teraz, że wiadomość jawna m  Z_n jest względnie pierwsza z p, czyli NWD(m, p)  1 . Z małego twierdzenia Fermata mamy wówczas:

m ^p^¹ 1 (mod p) $\qquad$ (**)

Podnosząc obie strony kongruencji (**) do potęgi k  (q  1) i mnożąc przez m dostajemy:

m^{1k ( p1)(q1)}  m(mod p)

a więc korzystając z (*) mamy:

m^ed m(mod p) .

Jeżeli NWD(m, p)  1 , to NWD(m, p)  p . Zatem również mamy wówczas:

m^ed m(mod p) $\qquad$ (***)

Istotnie, ponieważ m jest podzielna przez p, więc m^ed 0(mod p) i m  0(mod p), i kongruencja (***) zachodzi.

Zatem niezależnie od tego czy NWD(m, p)  1 , czy NWD(m, p)  1 , zawsze mamy

m^ed m(mod p) .

Podobnie możemy rozumować dla liczby pierwszej q otrzymując

m^ed m(mod q)

Z lematu dostajemy ostatecznie, że m^ed m(mod pq) .

Probabilistyczne uzasadnienie algorytmu RSA: Warto zwrócić uwagę na to, że nie wymagamy w założeniach powyższego twierdzenia by tak jak w założeniach twierdzenia Eulera. Próba uzasadniania kongruencji NWD(a, n)  1, m^ed m(mod pq) twierdzeniem Eulera byłaby więc zręcznym korzystaniem z nieuwagi Czytelnika.

Jednak przy n  p₁ p₂ (gdzie czynniki są liczbami pierwszymi) i założeniu równomiernego rozkładu prawdopodobieństwa na zbiorze Z_n prawdopodobieństwo tego, że NWD(a, n)  1 maleje do 0 wraz ze wzrostem p₁i p₂ . Istotnie z definicji funkcji Eulera mamy, że:

P({a  Z ; NWD(a, n)  1})  $\frac{n - \phi (n) }{n} = \frac{n - (p_1-1)\cdot(p_2-1) }{n} = \frac{(p_1 + p_2 -1) }{p_1\cdot p_2} = \frac{1}{p_1} + \frac{1}{p_1} - \frac{1}{n}$

a więc P({a  Zn ; NWD(a, n)  1})  0 jeśli p₁  i p₂ 

zatem sytuacja, że NWD(a, n)  1 nie zachodzi staje się bardzo mało prawdopodobna.

Uwagi końcowe o algorytmie RSA: Szyfr RSA jako algorytm z kluczem publicznym może być wykorzystywany zarówno do zwykłego szyfrowania jak również do dystrybucji tzw. kluczy sesyjnych oraz realizacji algorytmów podpisów cyfrowych.

Bezpieczeństwo szyfru RSA jest zależne od tego czy istnieje efektywny algorytm rozkładu dużej liczby n na czynniki pierwsze (dotychczas nie jest znany taki efektywny algorytm). Dokładniej, gdyby taki algorytm istniał to moglibyśmy łatwo obliczyć wartość funkcji Eulera  (n) , n jest ogólnie znanym parametrem sytemu kryptograficznego. Odtworzenie klucza prywatnego z klucza publicznego sprowadzałoby się w tej sytuacji do znalezienia elementu odwrotnego do klucza publicznego w pierścieniu ^Z (n) co sprowadza się z kolei do realizacji rozszerzonego algorytmu Euklidesa (istnieją szybkie efektywne wersje tego algorytmu np. algorytm Stein'a).

Główną wadą algorytmu RSA jest jego znacznie większa złożoność obliczeniowa w porównaniu z innymi algorytmami szyfrowania jak np. algorytmem DES. Okazuje się to specjalnie kłopotliwe, gdy zależy nam na szyfrowaniu w czasie rzeczywistym, np. gdy szyfrujemy próbki sygnału mowy w systemie telekomunikacyjnym.