Różnice między mnożeniem liczb pierwszych a procesem odwrotnym są podstawą jednego z najbardziej udanych systemów klucza publicznego, RSA, nazwanego na cześć jego wynalazców, Rona Rivesta, Adi Shamira i Leonarda Adlemana. Pełny dowód tej techniki wymaga skomplikowanej matematyki, ale zasada jest prosta. Dwie duże liczby pierwsze o w przybliżeniu równej wielkości są wybierane i mnożone razem, aby otrzymać liczbę o długości kilkuset bitów. Nazywa się to „modułem”. Dwie kolejne liczby są obliczane z dwóch liczb pierwszych. Są to tak zwane klucze publiczne i prywatne. Właściciel musi zachować w tajemnicy wybór dwóch liczb pierwszych i klucza prywatnego, ale może udostępnić moduł i klucz publiczny. Dzięki temu nie ma potrzeby skomplikowanego konfigurowania bezpiecznego kanału do przekazywania tajnych kluczy. Każdy, kto chce wysłać wiadomość, używa algorytmu opisanego poniżej do zaszyfrowania wiadomości, operując na niej za pomocą modułu i klucza publicznego. Gdy wiadomość zostanie zaszyfrowana, zadanie jej odszyfrowania jest równoważne próbie faktoryzacji n, co jest znane jako „trudne”, chyba że ktoś ma dostęp do klucza prywatnego. Znajomość tego klucza prywatnego pozwala uprawnionemu odbiorcy odszyfrować wiadomość przy użyciu podobnego algorytmu do szyfrowania, z wyjątkiem tego, że zamiast klucza publicznego używany jest klucz prywatny.
Algorytm szyfrowania RSA
Algorytm opiera się na wyborze dwóch dużych liczb pierwszych p i q, których tożsamość musi być zachowana w tajemnicy. Niech n = p x q i wybierz liczbę e, która jest mniejsza od n. e nie musi być liczbą pierwszą, ale nie może mieć żadnych wspólnych czynników ani z (p – 1) ani (q – 1) . Musimy teraz znaleźć inną liczbę, d, taką, że (ex d – 1) i podzielna przez (p – 1) (q – 1) bez reszty. Mamy więc trzy liczby: d, e, n. Upubliczniamy e i n. (Są to „klucze publiczne”). D (klucz prywatny) trzymamy w tajemnicy. Załóżmy, że Alicja chce wysłać nam wiadomość, m. Wyszukuje naszą wartość e na liście publicznej. Następnie podnosi m do potęgi e. (Oznacza to, że mnoży m przez siebie, e razy. Gdyby m było „345”, a e było „7”, obliczyłaby 345 x 345 x 345 x 345 x 345 x 345 x 345). Następnie znajduje n z listy publicznej i wielokrotnie dzieli je na poprzednie obliczenia, aż pozostanie tylko reszta R. (np. załóżmy, że m do potęgi e = 10n + R. W notacji matematycznej jest to znane jako znalezienie R = me mod n). R to zaszyfrowany tekst, który Alicja wysyła do nas przez otwarty kanał. Można wykazać, że każda technika, która pozwala znaleźć m na podstawie R i znajomości n i e, jest trudna obliczeniowo, równoważna próbie rozłożenia na czynniki iloczynu dwóch liczb pierwszych. Bierzemy zaszyfrowany tekst R i podnosimy go do potęgi d (klucz tajny). Następnie znajdujemy resztę po wielokrotnym dzieleniu przez n (tj. obliczyliśmy Rd mod n). Co zaskakujące, okazuje się, że jest to m, wiadomość tekstowa. Typowa wartość klucza publicznego, zakodowana jako ciąg alfanumeryczny, wyglądałaby mniej więcej tak
