Der RSA-Algorithmus

Bevor überhaupt ver- bzw. entschlüsselt werden kann, muss von einer Zentrale der öffentliche und private Schlüssel erzeugt werden. Der private Schlüssel besteht aus einer ganzen positiven Zahl d, der öffentliche Schlüssel aus den beiden ganzen positiven Zahlen e und n. Um diese Zahlen festzulegen, wählt die Zentrale für jeden Teilnehmer zwei große Primzahlen p und q und bildet deren Produkt n = p x q. Damit hat sie den ersten Bestandteil des öffentlichen Schlüssels. Als e, den zweiten Teil des öffentlichen Schlüssels des Teilnehmers, legt sie eine Zahl fest, die mit der Zahl (p - 1)(q - 1) keinen gemeinsamen Teiler hat. Der größte gemeinsame Teiler von e und (p - 1)( q - 1) soll also 1 sein. Der private Schlüssel des Teilnehmers ist dann die Zahl d, die folgende Bedingungen erfüllen muss:

Dem Teilnehmer werden nun die Zahl d geheim als privater Schlüssel mitgeteilt; die Zahlen n und e werden veröffentlicht und die Werte p und q sollten von der Zentrale vernichtet werden.
Jeder kann nun eine Nachricht an den Teilnehmer senden. Dazu muss er den Klartext K in Form einer Zahl K^* darstellen, die nicht größer als n ist. Um nun die Zahl K^* (z. B. die ASCII-Codierung) zu verschlüsseln, rechnet der Sender den Divisionsrest aus, der bei Division von und n entsteht, also Diese Zahl G stellt den Geheimtext dar, der dem Klartext K entspricht. Der Empfänger, der die chiffrierte Botschaft G erhält, entschlüsselt sie mit der Rechnung

Beispiel (Schneier, Angewandte Kryptografie):

Wir wählen 2 Primzahlen:

p=47 und q=71.

Anschließen bilden wir das Produkt

n=pq=3337.

Der Chiffrierschlüssel e darf keine gemeinsamen Faktoren mit

(p-1)(q-1)=3220

aufweisen. Das trifft z.B. auf die zufällig gewählte Zahl e=79 zu. Für die Entschlüsselung brauchen wir noch den Schlüssel d, der durch den erweiterten Euklidischen Algorithmus gewonnen wird:

d=79^-1 mod 3320=1019

e und n werden veröffentlicht, d bleibt geheim, p und q werden vernichtet. Unsere Nachricht, die wir übermitteln wollen sei:

K=688 232 687 966 668 3

Diese Nachricht zerlegen wir in Blöcke a 3 Ziffern, den letzten Block füllen wir von links mit Nullen auf. Demnach erhalten wir sechs Blöcke m_i wie folgt:

K₁=688

K₂=232

K₃=687

K₄=966

K₅=668

K₆=003

Der erste Block wird nach folgendem Verfahren verschlüsselt:

G₁=688⁷⁹ mod 3337=1570

Wenn wir diese Operation auch mit den anderen Blöcken durchführen, bekommen wir die vollständig verschlüsselte Nachricht:

G=1570 2756 2091 2276 2423 158

Zur Entschlüsselung der Nachricht wird eine ähnliche Potenzierung mit dem Dechiffrierschlüssel d=1019 vorgenommen:

K₁=1570¹⁰¹⁹ mod 3337=688

Der Rest funktioniert analog. Auch dieses System hat seine Schwachstellen. Wenn es dem Angreifer gelingt, den Schlüssel in seine Primfaktoren p und q zu zerlegen, so ist es ihm möglich, den privaten Schlüssel d zu berechnen. Das Verfahren dazu ist bekannt. Heutige Computer sind jedoch nicht in der Lage (eine entsprechende Schlüssellänge vorausgesetzt, n sollte momentan mindestens 300 Stellen groß sein), dies in akzeptabler Zeit zu erledigen. An der Faktorisierung einer 129stelligen Zahl arbeiteten 1994 600 Menschen (bzw. deren Computer) acht Monate lang! Die Rechenzeit für die Faktorisierung einer 160stelligen Zahl wurde 1996 auf fünf Jahre geschätzt. Daher kann jeder der beiden Schlüssel für sich betrachtet eine Einwegfunktion darstellen. Schnellere Computer sind aber nicht die Lösung zum Knacken von RSA. Gibt es Computer, welche entsprechenden Primzahlen in angemessener Zeit faktorisieren können, wird einfach die Schlüssellänge erhöht, so dass der Geschwindigkeitsvorteil aufgehoben ist.