Das RSA-Verfahren ist wohl das bekannteste unter den hier vorgestellten Verfahren. Er funktioniert so:

Zwei möglichst große Primzahlen werden sich ausgedacht (p und q). Daraus wird das Modul n mit n = p * q gebildet. Dies ist ein ÖFFENTLICHER Schlüssel, d.h. auch ein Angreifer kann ihn ruhig erfahren. Nun wird eine teilerfremde Zahl zu (p-1)*(q-1) gesucht. Das ist der zweite öffentliche Schlüssel (e für encrypt), mit dem verschlüsselt wird. Nun muss die modulare Inverse von e im Modul (p-1)*(q-1) gefunden werden, d.h. die Zahl d (decrypt, mit der entschlüsselt wird), für die gilt:

c^d mod n = Klartext, entsclüsselt wird so: Klartext^e mod n. Die modulare Inverse kann mit dem euklidischen Algorithmus ermittelt werden.

Um diesen Code zu knacken müsste man das bekannte Modul n in seine Primfaktoren zerlegen, was sich bei großen Zahlen als sehr schwierig erweist. Dann könnte man mit (p-1)*(q-1) als Modul die Inverse von e berechen (d) und damit hätte man den geheimen Schlüssel. Dieses Programm arbeitet mit relativ kleinen Zahlen, ist also nur für Demonstrationszwecke gedacht.
Außerdem ist der RSA-Algorithmus relativ langsam, da z.T. mit sehr hohen Zahlen potenziert werden muss.


Beispiel:

p = 17;
q = 31;
n = p*q = 17*31 = 527;
(p-1)*(q-1) = 480 -> eine teilerfremde Zahl e = 7;
inv e im Modul n (527) = d = 343

2 ist der zu verschlüsselnde Code.
Verschlüsseln: 2^e mod n = 2^7 mod 527 = 128 mod 527 = 128 = c (Ciphertext - verschl. Code)
Entschlüsseln: 128^d mod n = 128^343 mod 527 = 128^256 * 128^64 * 128^16 * 128^4* 128^2 * 128^1 mod 527
= 35 * 256 * 35 * 101 * 47 * 128 mod 527 = 2 mod 527 = 2 (Klartext).