Kryptografia z kluczem publicznym
Wobec zwiększającego się dostępu do środków łączności oraz potrzeby przesyłania różnych informacji powstała potrzeba opracowania metod szyfrowania, które zabezpieczałyby te informacje. Początkowo przesyłane szyfrowane informacje udawało się przeczytać łamiąc szyfr, który utrzymywany był w tajemnicy. W kryptografii nastąpił wielki postęp, gdy zaczęto używać systemów szyfrujących z kluczem publicznym. System taki cechuje prostota i jest niezwykle trudny do złamnania. Pomysł podali w 1976 roku W. Diffie i M.E. Hellman, a zaimplementowany efektywnie został w 1978 r. przez Ronalda Rivesta, Adi Shamira i Leonarda Adlemana, stąd system ten nazywa się systemem RSA.
Każdej literze lub innemu znakowi, włączając spację, jest przyporządkowana liczba trzycfrowa, w tzw. kodzie ASCII (American Standard Code for Information Interchange). Każdą literę lub znak w tekście zastępuje się odpowiadającą mu liczbą 3-cyfrową i w ten sposób powstaje liczba, która odpowiada temu tekstowi. Przesyłaną wiadomość można traktować więc jako pewną liczbę naturalną otrzymaną z ciągu liczb trzycyfrowych odpowiadających kolejnym literom i znakom w tej wiadomości.
Każdy użytkownik tego systemu kryptograficznego podaje do publicznej wiadomości swój klucz, który jest parą liczb naturalnych (n, k). Pierwsza z liczb jest iloczynem dwóch dowolnych liczb pierwszych p, q, (n = pq), które zachowuje się w tajemnicy. Ponadto liczba k musi być liczbą względnie pierwszą z p-1 i q-1.
Zaczynamy od dwóch dużych, losowo wybranych, rożnych liczb pierwszych p i q. Obliczamy ich iloczyn n = pq. Liczba n nie jest liczbą pierwszą, wiec nie zachodzi równość, xn-1 ≡ 1 (mod n) dla 0 < x < p. Aby użyć RSA musimy znaleĽć taki wykładnik t, aby xt ≡ 1 (mod n) dla (prawie) wszystkich x. Jeżeli zachodzi xt ≡ 1 (mod n), to zachodzi również xt ≡ 1 (mod p) oraz xt ≡ 1 (mod q). Liczby p i q są pierwsze więc równanie xt ≡ 1 (mod n) będzie zachodzić tylko wtedy gdy p-1 będzie dzielnikiem t oraz q-1 będzie dzielnikiem t. Zatem najmniejsza liczba o takiej właściwości to NWW(p-1, q-1). Mamy zatem t = NWW(p-1, q-1), wartość t możemy obliczyć również z funkcji Eulera. Funkcja ta dla liczby n = pq, gdzie p i q są pierwsze wynosi Φ(n) = (p - 1)(q - 1) i jest wielokrotnością liczby t. Użycie jej zamiast t również daje dobry rezultat.
Mając p, q, n oraz t, potrzebujemy teraz dwóch różnych wykładników k oraz l. Muszą one spełniać warunek kl ≡ 1 (mod t). Znając wykładnik k, obliczamy l jako odwrotność k modulo t. Aby zaszyfrować wiadomość w, nadawca oblicza tekst zaszyfrowany c = wk (mod n). Aby odszyfrować tekst c wystarczy obliczyć cl (mod n) co jest równe oryginalnej wiadomości w. Klucz publiczny stanowi para (n, k), kluczem tajnym są liczby (p, q, t, l)
Należy zwrócić uwagę jeszcze na to, że jeżeli liczba k będzie miała wspólny czynnik z t, to nie będzie istniał element odwrotny do k modulo t, dlatego k i t muszą być względnie pierwsze. Dla wybranej wartości k liczby należy sprawdzić czy p-1 oraz q-1 nie mają wspólnych czynników z wybranym k.
Na podstawie klucza publicznego nie da się łatwo odgadnąć liczb w kluczu prywatnym. Można by tego dokonać rozkładając n na czynniki by poznać p i q, jednak nie jest znany wydajny algorytm rozkładu liczb na czynniki liczb złożonych. Jeśli chcemy zapewnić odpowiednie bezpieczeństwo, to nasza liczba n powinna mieć kilka tysięcy bitów długości.