Szyfrowanie RSA: krok 4

Mamy już zapadkę do wyznaczania wartości funkcji φ. Znając rozkład N na czynniki pierwsze, wartość φ wyznaczycie bez trudu. Np. rozkład liczby 77 na czynniki pierwsze to 7 razy 11, więc wartość funkcji φ dla 77 wynosi 6 razy 10, czyli 60. Krok trzeci: jak powiązać funkcję φ z potęgowaniem modularnym? Cocks posiłkował się twierdzeniem Eulera, które właśnie opisuje związek między funkcją φ a potęgowaniem modularnym: Mamy: m do potęgi φ policzonej dla n jest przystające do 1 mod n. To znaczy, że możemy wybrać dwie dowolne liczby, byle nie miały wspólnych dzielników… Nazwijmy je „m” i „n”. Powiedzmy, że m = 5, a n = 8. Gdy podniesiemy m do potęgi φ od n, czyli 4, i podzielimy to przez n, to zawsze zostanie 1. Musimy tylko zmodyfikować to równanie z pomocą dwu prostych reguł. Po pierwsze, jeśli podniesiecie 1 do dowolnej potęgi, k, to zawsze uzyskacie 1. Tak samo, możemy pomnożyć wykładnik φ od n przez dowolną liczbę k, a wynik zawsze będzie wynosił 1. Po drugie, jeśli pomnożycie 1 przez dowolną liczbę, np. m, zawsze wyjdzie m. Zatem możemy pomnożyć lewą stronę przez m, żeby uzyskać m po stronie prawej. A to można uprościć do postaci: m do potęgi (k razy φ od n) plus 1. I to jest przełom. Mamy teraz równanie do wyznaczenia e razy d, które zależy od φ od n. Zatem obliczyć d jest łatwo tylko wtedy, gdy znamy rozkład n na czynniki pierwsze. Czyli d powinno być prywatnym kluczem Alicji. To zapadka, która pozwoli jej odwrócić efekt e. Na prostym przykładzie zobaczmy, jak to wszystko działa. Bob ma wiadomość, którą przekształcił w liczbę z pomocą schematu dopełnienia. Nazwijmy ją „m”. Później Alicja generuje swoje klucze, publiczny i prywatny: najpierw generuje dwie losowe liczby pierwsze podobnej wielkości i mnoży je, żeby uzyskać n: 3127. Potem łatwo oblicza wartość φ od n, bo zna rozkład n na czynniki pierwsze. Uzyskuje 3016. Teraz wybiera mały wykładnik publiczny, e, przy czym musi to być liczba nieparzysta niemająca wspólnego dzielnika z φ od n. Wybiera e równe 3. W końcu znajduje wartość prywatnego wykładnika, d, który w tym przypadku wynosi 2 razy φ od n, plus 1, podzielone przez 3, czyli 2011. Teraz ukrywa wszystko poza wartościami n oraz e, bo n oraz e tworzą jej klucz publiczny. To jakby otwarty zamek. Wysyła to Bobowi, żeby zamknął swoją wiadomość. Bob zamyka wiadomość, obliczając m do potęgi e mod n. Nazwijmy to „c”, jego zaszyfrowaną wiadomością, którą wysyła do Alicji. W końcu Alicja deszyfruje wiadomość używając prywatnego klucza, d, do którego dostała się przez swoją zapadkę. C do potęgi d mod n jest przystające do oryginalnej wiadomości Boba, m. Zauważcie, że Ewa lub ktoś inny, mając c, n oraz e, wyznaczy wykładnik d tylko wtedy, gdy może obliczyć wartość φ od n, a w tym celu musi znać rozkład n na czynniki pierwsze. Przy dostatecznie dużym n Alicja jest pewna, że szukanie potrwa setki lat, nawet za pomocą najpotężniejszej sieci komputerowej. Ta metoda została utajniona od razu po publikacji, jednak w 1977 r. niezależnie odkryli ją Ron Rivest, Adi Shamir i Len Adleman, dlatego teraz jest w kryptografii znana pod nazwą RSA. RSA to najczęściej na świecie używany algorytm z kluczem publicznym. I najczęściej kopiowane oprogramowanie w historii. Każdy użytkownik Internetu na świecie używa RSA lub jakiegoś wariantu tej metody, świadomie czy nie. Siła algorytmu opiera się o trudność rozkładu na czynniki pierwsze. To zaś wynika z trudnego zagadnienia dystrybucji liczb pierwszych. Kwestia przez tysiące lat nie doczekała się rozwiązania!