W kryptografii z kluczem publicznym używane są dwa klucze: klucz publiczny i klucz tajny. Klucze publiczne może znać każdy, zaś klucze tajne są utajnione.
Zakładając, że osoba B chciałaby wysłać wiadomość osobie A, można by było wyróżnić następujące etapy:
- Osoba B znajduje (np. w jakimś specjalnym katalogu lub dostaje osobiście) klucz publiczny osoby A.
- Osoba B korzystając z klucza publicznego osoby A szyfruje tekst jawny. Co można ująć wzorem: x = FP(t).
- Osoba B wysyła zaszyfrowany tekst do osoby A.
- Osoba A korzystając z klucza tajnego odszyfrowuje wiadomość, czyli wykonuje operację t = FS(x).
Aby funkcja FP przy bardzo długich tekstach była łatwa do obliczenia dla każdego, a funkcja FS tylko dla osoby do niej przypisanej należy zastosować szyfr blokowy.
Kryptosystem RSA należy do kryptosystemów z kluczem publicznym. Zasadę zastosowania tego kryptosystemu można by ująć w następujący sposób:
- Losowo wybieramy dwie bardzo duże liczby pierwsze p i q.
- Obliczamy n = pq
- Obliczamy r = (p-1)(q-1)
- Wybieramy małą liczbę e, przy czym musi być ona nie parzysta i jedynym wspólnym dzielnikiem e i r powinno być 1.
- Obliczamy d = e mod r tzn. ed mod r = 1
- Kluczem publicznym czynimy parę P = (e, n), a tajnym S = (d, n)
- Definiujemy funkcje FP (x) = xe mod n i FS (x) = xd mod n. Mogą one działać na blokach tekstu jawnego lub zaszyfrowanego.
Szyfrując tekst za pomocą algorytmu RSA już w pierwszym kroku musimy użyć dwóch dużych liczb pierwszych. Aby tego dokonać można skorzystać z twierdzenia o liczbach pierwszych, które można ująć w następujący sposób: jeśli m dąży do nieskończoności, to liczba liczb pierwszych równych lub mniejszych m prowadzi do m/ln m. Jeśli wybierzemy losowo m to szansa, iż jest to liczba pierwsza wynosi: jeden na ln m. W praktyce jednak prostsze jest twierdzenie Fermata, mówi ono, że jeśli m to liczba pierwsza, to xm-1 mod m = 1, przy czym x to dowolna liczba z przedziału od 1 do m – 1. Czyli m jest liczbą pierwszą, jeśli wyżej przytoczony warunek jest spełniony.