Nur für Freaks: RSA exemplarisch
Der RSA-Algorithmus
Der RSA-Algorithmus greift in vollen Zügen in die Mathematik hinein, speziell in den Bereich der Zahlentheorie. Dennoch ist das Prinzip auch für einen Laien mit Schulmathematik verständlich.
Die Erzeugung der Schlüssel
Der private Schlüssel besteht aus einer natürlichen Zahl d, der öffentliche Schlüssel aus den beiden natürlichen Zahlen e und n.
Zunächst werden zwei große Primzahlen p und q gewählt und deren Produkt n = p · q als ersten Bestandteil des öffentlichen Schlüssels berechnet.
Als e wird eine Zahl festgelegt, die mit dem Produkt (p - 1)(q - 1) keinen gemeinsamen Teiler hat, also der ggT(e, (p - 1)( q - 1)) = 1.
Der private Schlüssel ist dann die Zahl d, mit:
- d ≤ (p - 1)(q - 1)
- e·d mod (p - 1)(q - 1) = 1
Die Anwendung der Schlüssel
Jeder kann nun eine Nachricht an den Teilnehmer senden. Dazu muss er den Klartext in Form einer Zahl m darstellen, die nicht größer als n ist.
Um nun die Zahl m zu verschlüsseln, rechnet der Sender c = me mod n. Diese Zahl c ist der zum Klartext m gehörende Geheimtext.
Der Empfänger entschlüsselt mit m = cd mod n.
Dass der Empfänger hier wirklich wieder m zurückerhält, beruht auf dem „Satz von Euler“, einer um 1773 entdeckten Aussage der Zahlentheorie.
Ein einfaches praktisches Beispiel
In der Praxis müssen p und q sehr groß sein, im folgenden Beispiel beschränken wir uns der Übersichtlichkeit halber auf 11stellige Primzahlen, nämlich
p = 37419669101 und q = 11110693267.
Das Produkt dieser Zahlen ist n = 415758465533848642967.Damit ist die erste Zahl des öffentlichen Schlüssels bekannt.
Die Zahl e muss zu (p - 1)(q - 1) = 415758465485318280600 teilerfremd sein.
Das geht beispielsweise mit e = 216 + 1 = 65537.
Es bleibt der private Schlüssel d zu bestimmen. Er ist die einzige Zahl zwischen 1 und (p - 1)(q - 1) mit der Eigenschaft, dass e·d mod (p - 1)(q - 1) = 1.
Um aus dieser Gleichung d zu bestimmen, verwendet man den „Erweiterten Euklidischen Algorithmus“. Das Ergebnis ist d = 16481384459631305873.
Dazu sind die Nachrichten zunächst in eine Zahlenfolge zu übersetzen. Wir wählen folgendes Verfahren: a bis z werden durch die Zahle 01 bis 26 kodiert, das Leerzeichen mit 00.
Die Nachricht "Kryptologie macht Spass" entspricht damit der Zahlenfolge: 1118251620151215070905001301030820001916011919.
Diese Zahl lässt sich nicht als Ganzes verschlüsseln, weil sie größer ist als n, die erste Zahl des öffentlichen Schlüssels. Also teilt man die Zahlenfolge der Nachricht in Blöcke auf, die jeweils einzeln kodiert werden.
Der erste dieser Blöcke ist m = 11182516201512150709.
m wird nun verschlüsselt zu c = 1118251620151215070965537 mod 415758465533848642967 = 71043117991897565951.
Entsprechend geht man mit den weiteren Blöcken um.
m = 7104311799189756595116481384459631305873 mod 415758465533848642967 = 11182516201512150709
... und erhält so den ersten Teil der Nachricht zurück.