Dzieło Rona Rivesta, Adi Shamira i Lena Adlemana z MIT, powstało w 1977r., a zostało opublikowane rok później. Jak do tej pory jest to jedyna powszechnie akceptowana i stosowana metoda z kluczem jawnym.

Opis algorytmu:
     System RSA to szyfr blokowy, w którym tekst jawny i zaszyfrowany są liczbami całkowitymi od 0 do n-1 dla pewnego n. Korzysta on z wyrażenia potęgowego. Tekst jawny jest szyfrowany blokami, z których każdy ma wartość binarną mniejsza od pewnej liczby n. Szyfrowanie dla bloku tekstu jawnego M i zaszyfrowanego Z ma następująca postać:

C=M^e mod n

M=C^d mod n = (M^e)^d mod n = M^ed mod n

Wartość n musi być znana nadawcy i odbiorcy. Nadawca zna wartość e, a odbiorca d. Jest to algorytm z kluczem publicznym KU = {e, n} i prywatnym KR = {d, n}.

Składniki systemu RSA:
p, q - dwie liczby pierwsze
n=pq
d, przy nwd((n), d)=1; 1<d<(n)
e=d-1 mod (n)

(n) - funkcja Eulera, czyli ilość liczb dodatnich mniejszych od n i względnie pierwszych wobec n.

     Klucz prywatny składa się z {d, n}, a klucz jawny z {e, n}. Załóżmy, że użytkownik A opublikował swój klucz jawny. Natomiast B chce wysłać do A wiadomość M. B oblicza C=M^e (mod n) i przesyła C. Użytkownik A deszyfruje tekst zaszyfrowany, obliczając:

M=C^d (mod n).

Tabela obrazująca algorytm RSA (kliknij, aby zobaczyć)

     W przypadku RSA bardzo istotny jest aspekt złożoności obliczeń. Zarówno podczas generowania kluczy jak i przy szyfrowaniu deszyfrowaniu.
Aby można było zastosować system RSA każdy użytkownik musi wygenerować parę kluczy. Związane są z tym następujące zadania:

• Określenie dwu liczb pierwszych p i q.
• Wybór e lub d i obliczenie drugiego z nich.

     Pierwszy problem to znalezienie dwóch liczb pierwszych p i q. Powinniśmy wybiarać liczby p i q z dużego zbioru, aby nie możliwe było ich odkrycie, po poznaniu n=pq metodą kolejnych prób. Natomiast metoda poszukiwania liczb pierwszych musi być dostatecznie efektywna.
     Obecnie nie ma dobrych metod znajdywania dużych liczb pierwszych, dlatego stosuje się metodę polegającą na wylosowaniu liczby nie parzystej żądanego rzędu wielkości, a następnie sprawdzaniu, czy jest pierwsza.
     Jest dużo testów sprawdzających czy dana liczba jest pierwsza. Większość z nich to testy probabilistyczne. Czyli sprawdzają czy dana liczba jest prawdopodobnie pierwsza. Nie można osiągnąć pewności, ale można dojść do prawdopodobieństwa bliskiego 1,0.
     Najlepszym i najczęściej używanym testem jest test Millera-Rabina. W skrócie poszukiwanie liczby pierwszej można przedstawić następuąco:

1. Losowanie nieparzystej liczby całkowitej n (generatorem liczb pseudolosowych).
2. Losowanie liczby całkowitej a < n.
3. Wykonanie sprawdzenia czy liczba jest pierwsza np. metodą Millera-Rabina. Jeżeli n nie przejdzie testu wracamy do punktu pierwszego.
4. Jeżeli n przeszło dostateczną liczbę testów, to zaakceptować je, jeżeli nie wracamy do punktu drugiego.

     Procedura ta jest dość wyczerpująca. Jednak wykonuje się ją tylko w celu stworzenia nowej pary kluczy (KU, KR).
     Zarówno przy szyfrowaniu jak i deszyfrowaniu wykonuje się operację podniesienia liczby całkowitej do całkowitej potęgi, mod n. Gdyby potęgować na liczbach całkowitych, a następnie redukować modulo n, wartości pośrednie byłyby ogromne. Można jednak skorzystać z pewnej własności arytmetyki modulo:

[(a mod n)x(b mod n)]mod n=(axb)mod n

W ten sam sposób redukujemy wyniki pośrednie modulo n. Obliczenia są dzięki temu prostsze.

Zarządzanie kluczami:
Metody dystrybucji kluczy można podzielić na cztery grupy:

• Publiczne ogłoszenie.
• Ogólnie dostępny katalog.
• Organ zarządzający kluczami jawnymi (public-key authority).
• Certyfikaty kluczy jawnych.