RSA hat den Namen nach den Anfangsbuchstaben der Nachnamen seiner Erfindern RONALD L. RIVEST, ADI SHAMIR und LEONARD ADLEMAN bekommen. RIVEST, SHAMIR und ADLEMAN haben das Verfahren 1977 entwickelt. Es gilt bis heute als sicher. Die RSA-Verschlüsselung nutzt so genannte Einweg-Funktionen. Man kann sich diese Funktionen als mathematische Einbahnstraßen vorstellen. In die eine Richtung (Verschlüsseln) ist die Berechnung ganz einfach. Versucht man den Rechenweg jedoch rückwärts zu beschreiten (Entschlüsseln ohne Schlüssel), wird die Sache schwieriger.
Ein Beispiel für eine Einweg-Funktion ist die Multiplikation von Primzahlen. Zur Wiederholung: Eine Primzahl ist nur durch sich selbst und 1 teilbar. Es ist sehr einfach, zwei Primzahlen miteinander zu multiplizieren. Nehmen wir 3.259 und 5.431, das Ergebnises 17.699.629.
Die mathematische Einbahnstraße wurde hierbei in der einfachen (richtigen) Richtung „befahren“. Wenn die Frage nun aber lauten würde: „Gesucht sind alle Teiler der Zahl 17.699.629“ sieht die Sache sehr viel schwieriger aus. Jetzt müssen wir die Einbahnstraße in die andere Richtung zurück fahren. Das ist in der Mathematik für diese Aufgabe sehr schwierig. 17.699.629 hat nämlich nur vier Teiler: 1 und sich selbst (das gilt immer und für jede Zahl) sowie die beiden Primzahlen, die wir gerade zuvor multipliziert haben.
Das bedeutet, wenn man aus dem Produkt 17.699.629 alle Teiler, außer 1 und der Zahl selbst, findet, hat man die Ausgangswerte ermittelt. Das große Problem dabei ist, dass für das Zerlegen einer Zahl in ihre Primfaktoren auf der ganzen Welt keine wirklich guter (d. h. schneller) Algorithmus bekannt ist.
Dazu ein Beispiel: Ein 39stelliges Produkt aus zwei 20stelligen Primzahlen wird auf einem aktuellen Computer mit Hilfe einer leistungsfähigen (und übrigens teuren) Mathematik- Software in weniger als einer Sekunde in die beiden Primzahl-Faktoren zerlegt.
Für eine 41stellige Zahl dauert das Ganze schon etwas mehr als 8 Minuten. Für ein 43stelliges Produkt aus zwei 22stelligen Primzahlen benötigte der Computer fast 19 Minuten. Bei einem 44stelliges Produkt hat das Programm die Berechnung ohne Ergebnis abgebrochen.
In der Praxis wird mit 150stelligen Primfaktoren gearbeitet. Es wird schnell klar, dass auch der schnellste Computer der Welt aus dem 300stelligen Produkt die beiden Primzahl-Faktoren nicht in akzeptabeler Zeit ermitteln und damit die Verschlüsselung ohne Schlüssel knacken kann. Und sollte doch irgendwann einmal ein Computer oder ein Verbund von vielen Computern schnell genug für die Ermittlung der Primfaktoren sein, muss man nur die Anzahl der Stellen der verwendeten Primzahlen erhöhen und schon ist man wieder auf der sicheren Seite.
Im Folgenden wird Schritt für Schritt dieses mathematische Verfahren mit ganz kleinen Primzahlen und einer sehr kurzen Nachricht, die nur aus einem Zeichen besteht, erklärt. Voraussetzung für das Verständnis ist die mathematische Rechenoperation "modulo". Die Operation modulo liefert den Rest, der bei einer ganzzahligen Division entsteht. Beispiele:
20 : 6 = 3 Rest 2, denn 3 · 6 =18 -> 18 + 2 = 20 20 mod 6 = 2 43 : 5 = 8 Rest 3, denn 8 · 5 =40 -> 40 + 3 = 43 43 mod 5 = 3 48 : 5 = 9 Rest 3, denn 9 · 5 =45 -> 45 + 3 = 48 48 mod 5 = 3
(1) Alice erzeugt zuerst Ihren privaten Schlüssel
(2) Alice erzeugt nun ihren öffentlichen Schlüssel
Die Zahlen N = 187 und e = 7 sind Alice "öffentlicher Schlüssel (N,e)" - also (187,7).
(3) Als nächstes wird phi(N) bestimmt:
(4) Der geheime Schlüssel besteht aus einem d mit der Eigenschaft, dass gilt:
Hinweis: Erweiterter Euklidischer Algorithmus um d zu bestimmen! Wir wählen hier einfachheitshalber ein d.
Nun haben wir (N,e) und (N,d) mit (187,7) und (187, 23) bestimmt und können es nun zu Ver- und Entschlüsseln nutzen.
(5) Die zu verschlüsselnde Nachricht wird in eine Zahl m umgewandelt
Das kann mit dem ASCII-Code geschehen. Nehmen wir an, Bob möchte Alice den Buchstaben X als symbolisches Herz schicken. Das X hat im ASCII-Code den Dezimalwert 88. Daraus folgt m = 88.
(6) Jetzt kann Bob die Zahl m verschlüsseln und erzeugt die verschlüsselte Nachricht c
Die Verschlüsselung von m zu c erfolgt mit der Formel
Den öffentlichen Teil des Schlüssels e = 7 und N = 187 von Alice kennt Bob. Also kann er sie in die Formel einsetzen. Die umgewandelte Zahl m ist ebenfalls verfügbar, da es sich um die in eine Zahl umgewandelte Nachricht von Bob handelt.
Bob rechnet also:
Bob kann diese Nachricht selbst nicht entschlüsseln. Angenommen, er wollte noch einmal überprüfen, ob er wirklich ein X als Symbol für das Herz geschickt hat, so wäre ihm das nicht möglich. Denn für die Gleichung
gibt es unendlich viele Lösungen, z. B. x = 88, x = 275. Bob schickt nun die verschlüsselte Nachricht c = 11 an Alice. (7) Alice entschlüsselt die empfangene Nachricht c
Dazu benötigt sie ihren privaten Schlüssel d = 23 und den Teil des öffentlichen Schlüssels N = 187. Die Formel zur Berechnung der Originalnachricht lautet:
Jetzt setzen wir die Zahlen ein und erhalten:
Das Zeichen im ASCII-Code mit der Nummer 88 ist das X. Alice hat den nun das symbolische Herz erhalten. Hätte ihr Vater den Brief abgefangen, hätte er die Zahl 11 gelesen. Der Zahl 11 ist im ASCII-Code aber gar kein Zeichen zugeordnet. Das ist zwar Zufall, aber auch bei einem größeren ASCII-Dezimalwert könnte Alice’s Vater nur das verschlüsselte Zeichen erkennen. Ein Rückschluss auf die richtige Nachricht ist ohne Kenntnis von Alice's privatem Schlüssel nicht möglich. Die Wahl der Primzahlen und das Ver- und Entschlüsseln überlassen Alice und Bob ab jetzt einer Software. Das Beispiel hat ja gezeigt, dass das Verfahren funktioniert und es wurde erklärt, unter welchen Bedingungen es als sicher angesehen werden kann. Deutlich wurde aber auch, dass RSA sehr rechenintensiv ist. So benötigt RSA 1000mal mehr Zeit als das symmetrische verschlüsselungsverfahren DES. Deshalb ist es für lange Nachrichten nicht geeignet. Symmetrische Verfahren haben aber den großen Nachteil, dass der gemeinsame Schlüssel zwischen Sender und Empfänger ausgetauscht werden muss. Und genau dafür eignet sich RSA hervorragend. Die Schlüssel für die symmetrische Verschlüsselung werden mit dem asymmetrischen Verfahren RSA ausgetauscht. Denn Schlüssel sind im Vergleich zu richtigen Nachrichten sehr kurz.
Bisher ist kein Verfahren bekannt, mit dem große Primzahlen (p,q) in einer angemessenen Zeit in ihre Primfaktoren zerlegt werden können. Daher kann RSA fur hinreichend große Primzahlen als eine sehr sichere Art der Verschlusselung betrachtet werden. Sollte jedoch eine Methode entdeckt werden, mit der man aus N seine beiden Primfaktoren p und q oder phi(N) = (p−1)(q −1) relativ einfach berechnen könnte, wäre RSA kein sicheres Verschlusselungsverfahren mehr.
Veranschaulichen kann man sich ein solches Verfahren mit einer Reihe von einbruchssicheren Briefkästen. Wenn ich eine Nachricht verfasst habe, so suche ich den Briefkasten mit dem Namensschild des Empfängers und werfe den Brief dort ein. Danach kann ich die Nachricht selbst nicht mehr lesen oder verändern, da nur der legitime Empfänger im Besitz des Schlüssels für den Briefkasten ist.