wichtiges Verfahren der asymmetrischen Verschlüsselung, benannt nach den drei Autoren Ronald Rivest, Adi Shamir und Leonard M. Adleman, die diesen Algorithmus 1977 publizierten.

Sowohl Verschlüsselung als auch Entschlüsselung werden durch Potenzieren in einem großen Restklassenring \({{\mathbb{Z}}}_{m}\) ausgeführt. Ist n eine zu verschlüsselnde Nachricht, dann ist \begin{eqnarray}c\equiv {n}^{e}\,\mathrm{mod}\,m\end{eqnarray} der chiffrierte Text.

Durch die Wahl des Moduls m = pq als Produkt zweier großer Primzahlen kann mit einem Exponenten d, für den ed ≡ 1 mod φ(m) gilt, das Chiffrat auch wieder entschlüsselt werden. Ist ggT(m, n) = 1, dann ist \begin{eqnarray}{c}^{d}\equiv {n}^{de}\equiv {n}^{1+k\varphi (m)}\equiv n.({n}^{\varphi (m)})k\,\mathrm{mod}\, m.\end{eqnarray} Nach dem Eulerschen Satz ist \begin{eqnarray}{n}^{\varphi (m)}\equiv 1\,\mathrm{mod}\, m\end{eqnarray} und deshalb \begin{eqnarray}{c}^{d}\equiv n\,\mathrm{mod}\, m.\end{eqnarray} Dabei ist φ die Eulersche Funktion der zu m teilerfremden ganzen Zahlen zwischen 0 und m, und es gilt \begin{eqnarray}\varphi (m)=(p-1)(q-1).\end{eqnarray} Wie man leicht sieht, gilt n^de ≡ n mod m auch für n mit ggT(m, n) ≠ 1.

Es gilt als sicher (ein Beweis fehlt jedoch), daß ein unberufener Entschlüsseler trotz Kenntnis von m und e den Exponenten d nur mit einem Rechenaufwand bestimmen kann, der mit der Faktorisierung der Zahl m vergleichbar ist (die Umkehrung ist dagegen offensichtlich, ausgehend von der Zerlegung m = pq kann man d aus m und e mit Hilfe des Euklidischen Algorithmus leicht berechnen).

Deshalb kann m und e als öffentlicher Schlüssel und d als geheimer Schlüssel für ein asymmetrisches Verschlüsselungsverfahren gewählt werden. Die Berechnung der Potenzen läßt sich durch Quadrieren und Multiplizieren so beschleunigen, daß man für große Exponenten d nur O(log₂d) viele Operationen ausführen muß.

Während 1977 die Entwickler von RSA noch glaubten, daß 129-stellige Zahlen (428 Bit) m = pq nicht in realistischer Zeit faktorisierbar sind, werden durch neue algebraische Methoden (Zahlkörpersieb) gegenwärtig (2001) die ersten 512-Bit-Zahlen in ihre beiden Faktoren zerlegt. 1024-Bit-Zahlen sind noch ausreichend sicher, und durch Vergrößerung der Modullänge auf 2048 Bit kann man auch auf längere Sicht den RSA-Algorithmus noch verwenden.

Im Vergleich mit symmetrischen Verfahren ist der RSA als Verschlüsselungsverfahren um einige Größenordnungen langsamer, sodaß man ihn zweckmäßigerweise mit einer sicheren Blockchiffre kombiniert. Dabei wird die Nachricht mit einem zufällig gewählten symmetrischen Schlüssel chiffriert, und nur dieser Schlüssel allein wird zusätzlich mit RSA verschlüsselt und an die Nachricht angehängt.

Eine einzelne RSA-Verschlüsselung von 1024-Bit-Zahlen ist im Millisekundenbereich sogar auf Chipkarten möglich und kann deshalb für die Bildung digitaler Signaturen verwendet werden.