Das 1977 von den drei Mathematikern Rivest, Shamir und Adleman entwickelte RSA galt damals als erstes asymmetrisches Verschlüsselungs-Verfahren. Es basiert auf dem aktuellen Wissensstand, dass die Faktorisierung einer grossen Zahl, also ihre Zerlegung in ihre Primfaktoren, eine sehr aufwändige Angelegenheit ist, während das Erzeugen einer Zahl durch Multiplikation zweier Primzahlen recht einfach ist.

Die eigentliche Ver- und Entschlüsselungs-Funktion ist sehr einfach. Einzig das Erzeugen der Schlüssel ist etwas komplizierter. Der öffentliche Schlüssel besteht aus zwei Zahlen: dem RSA-Modul und dem Verschlüssel­ungsexponent . Der private Schlüssel besteht ebenfalls aus zwei Zahlen: dem RSA-Modul und dem Entschlüsselungsexponent .

Verschlüsseln

Um eine Nachricht zu verschlüsseln, verwendet der Absender die Formel

und erhält so aus dem Klartext den Geheimtext .

Entschlüsseln

Der Geheimtext kann durch modulare Exponentation wieder zum Klartext entschlüsselt werden. Der Empfänger benutzt die Formel

mit dem nur ihm bekannten Wert sowie .

Schlüssel generieren

Das komplette Schlüsselpaar besteht aus den drei Zahlen , und , wobei den privaten und den öffentlichen Schlüssel bilden. Diese Zahlen werden durch das folgende Verfahren erzeugt:

1. Wähle zufällig zwei Primzahlen und so dass .
2. Berechne den RSA-Modul
3. Berechne die Eulersche -Funktion von :
   
4. Wähle eine zu teilerfremde Zahl , für die gilt
5. Berechne den Entschlüsselungsexponenten als Multiplikativ Inverses von bezüglich des Modulus . Es soll also die folgende Kongruenz gelten:

Die Zahlen , und werden nicht mehr benötigt und sollten nach der Schlüsselerstellung auf sichere Weise gelöscht werden.

Beispiel:

1. Wir wählen und für die beiden Primzahlen.
2. Der RSA-Modul ist
3. Die Eulersche -Funktion nimmt damit den Wert an.
4. Die Zahl muss zu teilerfremd sein. Wir wählen .
   Damit bilden und den öffentlichen Schlüssel.
5. Berechnung der Inversen zu :
   Es gilt:
   bzw. im konkreten Beispiel:
   Mit dem erweiterten euklidischen Algorithmus berechnet man nun die Faktoren und , so dass die Gleichung aus dem Beispiel wie folgt aussieht:
   bildet zusammen mit dem schon berechneten den privaten Schlüssel, während nicht weiter benötigt wird.