RSA Algorithmus

RSA wurde 1977 von Ron Rivest, Adi Shamir und Leonard Adleman entwickelt. Das Verfahren verwendet große Primzahlen; seine Sicherheit basiert auf der Schwierigkeit, große Zahlen zu faktorisieren. Dieser Algorithmus benutzt die Modulo-Funktion. Die RSA-Verschlüsselung mit 1024 Bit Schlüssellänge gilt zurzeit als sicher. Allerdings wenn man einen neuen, schnellen mathematischen Algorithmus zur Faktorisierung erfinden würde, dann wäre RSA nicht mehr so sicher. Auch die Entwicklungen im Quantenrechnerbereich können dazu führen, dass die RSA-Verschlüsselung nicht mehr als "sehr sicher" eingestuft wird.

Die Schlüsselerzeugung mit RSA-Algorithmus könnte man wie folgt darstellen:

I. Man nehme zwei Primzahlen, nennen wir sie hier einmal p und q, z.B. p = 11 und q = 29.

II. Diese beiden Primzahlen werden nun miteinander multipliziert, das Ergebnis wird n genannt: n = p * q,

hier: n = 11 * 29 = 319

III. Als nächstes wird eine kleine ungerade natürliche Zahl benötigt, die zu: (p-1) * (q-1) nur den größten gemeinsamen Teiler (ggT) 1 besitzt. (p-1) * (q-1) wird n0 genannt, die soeben definierte Zahl heißt ab jetzt e. In diesem Beispiel hier könnte z.B. e = 9 sein.

IV. Zu diesen ganzen Zahlen kommt jetzt noch eine weitere, und zwar d. Für d soll Folgendes gelten: e * d = 1 mod n0 (Lösung der Gleichung siehe unten)

V. Das Zahlenpaar e, n wird der öffentliche Schlüssel

VI. Die Zahl d wird der private Schlüssel.

Die Punkte "I" bis "III" sind recht harmlos, hier werden lediglich einige Zahlen festgelegt. Gleiches gilt für die Punkte "V" und "VI".

Was bleibt ist "IV". Rechnen wir "d" doch einfach an unserem Beispiel aus. e war festgelegt mit e = 9, für n₀ gilt: n₀ = (p-1) * (q-1) = (11 - 1) * (29 - 1) = 10 * 28 = 280.

Damit sieht die Gleichung in IV wie folgt aus:

9 * d = 1 mod 280

9 * d ist ja der Rest der Divisionsaufgabe 1 : 280.

Oder, wenn wir das Ganze umschreiben 1 = 280 * a + r = 280 * a + (9 * d).

Der Rest sollte immer eine ganze Zahl sein, ebenso a.

Das geht sie aber gar nicht, und das Tolle an der Mathematik ist nun, dass das unserer Formel (1 = 280 * a + (9 * d)) "egal" ist. a bleibt eine ganze Zahl, nur ist sie negativ.

Lösen können wir die Gleichung, indem wir nun eine Zahl nach der anderen ausprobieren.

So z.B. a = (-1). In diesem Falle erhalten wir: 1 = 280 * (-1) + (9 * d). Durch Umstellen (zuerst + (280 * 1), dann durch 9 teilen) erhalten wir 31,222..., dies ist keine ganze Zahl, somit ist a = (-1) nicht unsere Lösung. Also: a = (-2). d = 62,333... - wieder nichts. Also, a = (-3), dann (-4), (-5), ..., (-8), (-9) doch halt! a = (-8).

Der Taschenrechner beantwortet die Frage (280 * 8 + 1) : 9 = d mit d = 249 und das ist eine ganze Zahl...

Somit ist die Zahl d für unser kleines Beispiel auch bekannt: d= 249. Tatsächlich wird mit viel größeren Zahlen gerechnet, und tatsächlich wird d mit dem "erweiterten Euklidischen Algorithmus" berechnet.

Das Demo Applet funktioniert genau so wie o.g. Beispiel.
Allerdings soll hier noch erwähnt werden, dass das nicht die einzige Methode ist, wie man den privaten Schlüssel berechnen kann. Z.B. es ist möglich die Bestimmung des modularen Inversen anzuwenden, obwohl die erste Methode (Ausprobieren) wohl einfacher zu verstehen ist.

Der RSA-Algorithmus ist ausführlich im Buch "Angewandte Kryptographie" von "Wolfgang Ertel" beschrieben.

Verschlüsselung und Entschlüsselung

Eine Nachricht M muss hier in Zahlen umgewandelt werden, es können nämlich nur Zahlen verschlüsselt werden.

Das stellt aber letztendlich kein unüberwindliches Problem dar, der ASCII-Code macht ja nichts anderes. Führen wir das Beispiel fort, es soll (M =) 348 verschlüsselt und entschlüsselt werden. Dies geschieht wie folgt:

Verschlüsseln: M^e mod n = E

Entschlüsseln: C^d mod n = D

"C" steht für Chiffretext, "M" für Message, E erinnert an encodieren (verschlüsseln), D an decodieren (entschlüsseln).

A wird zu 65 ASCII und damit zu:

65⁹ mod 319 = 252

252 kann wiederum zurück-verwandelt werden:

252²⁴⁹ mod 319 = 65 oder A

Eine Beschreibung, wie man große Potenzen so etwa wie 252²⁴⁹ einfach berechnet, finden Sie in der Sektion mit mathematischen Grundlagen.

Da der öffentliche Teil des Schlüssels in der Regel jedem zugänglich ist, sind die individuellen Zahlen e und n eines jeden Schlüssels bekannt. n war jedoch das Produkt der beiden Primzahlen p und q.

Aus eben jenen Primzahlen kann jedoch der geheime Schlüssel, der dem Entschlüsseln einer Nachricht dient, leicht berechnet werden. Anders formuliert, wenn es einfach wäre, von 319 auf unsere beiden Primzahlen zu schließen, dann wäre dieses Verfahren wertlos.
Es ist es aber nicht, eine Primzahlenzerlegung sehr großer Zahlen zu berechnen ist eine höchst aufwändige Aufgabe.

Die Menschheit versucht schon seit langem diese Aufgabe zu lösen, bis jetzt aber ohne Erfolg. Wenn das gelingt, wird der RSA - Algorithmus auch der Vergangenheit angehören.