Das Verfahren beruht auf der mathematischen Tatsache, dass eine sehr große natürliche Zahl nur sehr schwer faktorisiert werden kann. Im Wesentlichen beruht es auf folgenden Überlegungen:

Es sei

n = p * q

das Produkt zweier großer verschiedener Primzahlen ("groß" soll bedeuten, dass der zu erwartende Gegner unter Computer-Einsatz nicht in zumutbarer Zeit in der Lage ist, n in die Primfaktoren zu zerlegen). Dann ist

j (n) = (p-1) * (q-1).

Sei nun e so gewählt, dass

ggT(e, j (n)) = 1,

d.h.

ggT(e, p-1) = ggT(e, q-1) = 1.

Dann existiert

d = e^-1 in Zj _(n)

und kann etwa durch Umkehrung des euklidschen Algorithmus praktisch berechnet werden.

Die Nachrichten mögen als Elemente von Z_n vorliegen. Dann verschlüsseln wir x Î Z_n durch die Funktion

E(x) = x^e(n).

Diese Abbildung E: Z_n ® Z_n ist bijektiv: Die Funktion D: Z_n ®  Z_n mit D(x) = x^d(n) ist nämlich invers, und kann daher zum Entschlüsseln verwendet werden:

D(E(x)) = (x^e)^d(n) = x^ed(n) = x^{1+k * j (n)} = (xj ⁽ⁿ⁾)^k * x º x(n),

da n quadratfrei ist.

Für die praktische Anwendung mit r Benutzern verwendet man entsprechend r Werte e₁, ..., e_r mit ggT(e_i,j (n)) = 1 und die dazu inversen d₁, ..., d_r in Zj _(n).

Öffentlich bekanntgegeben werden n, sowie e₁, ..., e_r (in einer Art "Telefonbuch"). Geheimgehalten werden p, q, d₁, ..., d_r. Nur der i-te Benutzer erfährt d_i.

Will nun Benutzer i an Benutzer j eine Botschaft senden, so verschlüsselt er sie als

y = E_j(x) = x^ej(n).

Nur Benutzer j kennt dj und erhält daher mit

D_j(y) = y^dj(n)

den Klartext.

Das System kann auch dazu verwendet werden, um die geheime Nachricht mit einer Unterschrift zu versehen, die dem j-ten Benutzer garantieren soll, dass die Nachricht vom i-ten Benutzer stammt. Dazu sendet i an j die Nachricht

E_j(D_i(x)) = x^{di * ej}(n).

Benutzer j wendet das nur ihm bekannte D_j an:

D_j(E_j(D_i(x)) = D_i(x).

Anschließend überprüft er mit der im Telefonbuch vorhandenen Funktion Ei, ob

E_i(D_i(x)) = x

einen sinnvollen Text und damit den Klartext ergibt, so dass die Nachricht vom Benutzer i stammen muss, da nur dieser D_i kennt.

Um das System direkt zu brechen, d.h. die Funktion Di berechnen zu können, ist die sehr große Zahl n in Primfaktoren zu zerlegen, wofür bis heute kein in polynomialer Zeit arbeitender Algorithmus bekannt ist. Dessen ungeachtet kann bei der Wahl von p, q, e und d nach den obigen Vorschriften dennoch ein sehr leicht zu brechendes System entstehen, wenn die Abbildung E(x) in Z_n viele Fixpunkte besitzt, d.h. für viele x Î Z_n gilt:

x_e º x(n).

Wie wir wissen, kann die maximale Ordnung l(n) eine Elements in E(Z_n) wesentlich kleiner als j(n) sein, so dass im Extremfall E(x) sogar die identische Abbildung sein kann.

Abschließend ein Auszug eines Artikel aus dem Jahr 1999:

Zum Knacken des Codes benötigten die Forscher allerdings eine Cray 900-16 und 300 PCs/Workstations im Wert von mehreren Millionen Dollar. Benötigt wurde insgesamt eine Rechenzeit von 35 Jahren - bei Einführung des RSA vor 25 Jahren schätzte man die benötigte Rechenzeit auf 50 Milliarden Jahre."