Die RSA Verschlüsselung ist ein von R. Rivest, A. Shamir und L. Adleman 1977 entwickeltes asymmetrisches Verschlüsselungsverfahren, welches sowohl zum Verschlüsseln als auch zum Erstellen einer digitalen Signatur eingesetzt wird. Das RSA Verfahren basiert auf einem Schlüsselpaar aus einem öffentlichen Schlüssel zum Verschlüsseln und einem privaten Schlüssel zum Entschlüsseln.
Die Mathematiker R. Rivest, A. Shamir und L. Adleman versuchten 1976 die Annahmen einer Veröffentlichung von W. Diffie und M. Hellman im Bereich der Public-Key Kryptographie zu widerlegen. Dabei fanden sie ein Verfahren, das nach ihrer Einschätzung nicht angreifbar ist. Dieses Verfahren wurde dann nach ihren Entdeckern, RSA benannt. Das RSA Kryptosystem weist mehrere Vorteile auf. Zum einen umgeht das RSA Verfahren das Schlüsselaustauschproblem, das bei symmetrischen Verschlüsselungsverfahren auftritt. Zum anderen gibt es keinen bekannten Algorithmus mit dem aus dem öffentlichen Schlüssel, der zum Verschlüsseln eingesetzt wird, der private Schlüssel, der zum Entschlüsseln verwendet wird, berechnet werden kann.
Das RSA Verfahren ist aufgrund folgender Eigenschaften als fast sicher einzustufen:
Ein Klartextbuchstabe wird nicht immer auf den gleichen Geheimtextbuchstaben abgebildet. Es ist also nicht monoalphabetisch.
Die RSA Verschlüsselung ist ein asymmetrisches Verfahren.
Es gibt einen öffentlichen Schlüssel der zum Verschlüsseln eingesetzt wird und einen privaten Schlüssel, der zum Entschlüsseln verwendet wird. Das RSA Verfahren stellt unter anderem deshalb einen sicheren Verschlüsselungsalgorithmus dar, da aus dem öffentlichen Schlüssel nicht der private Schlüssel berechnet werden kann.
Das RSA Verfahren eignet sich zur Kommunikation mit vielen Teilnehmern, da der öffentliche Schlüssel allen bekannt sein darf und somit nicht mit jedem Kommunikationsteilnehmer ein Schlüssel geheim ausgetauscht werden muss.
Nur der Besitzer des privaten Schlüssels kann eine Nachricht wieder einfach entschlüsseln.
Im Folgenden zeigen wir dir, wie man sich beim RSA Kryptosystem ein Schlüsselpaar mit einem öffentlichen Schlüssel und einem privaten Schlüssel erzeugen kann. Zuerst wählt man sich zwei große Primzahlen p und q und berechnet anschließend die Produkte
n=p ⋅ q
φ(n) = (p-1)(q-1).
Hierbei ist φ die Eulersche Phi-Funktion. Daraufhin sucht man sich eine Zahl e ∈ ℕ die teilerfremd zu φ(n) ist, sodass der größte gemeinsame Teiler von e und φ(n) eins ist:
ggT(e,φ(n)) =1.
Wenn man ein solches e wählt, dann ist e in \mathbb{Z}/\varphi(n)\mathbb{Z} invertierbar. Somit kann man ein zu e inverses Element d ∈ ℕ mit folgender Formel berechnen:
e ⋅ d ≡ 1 mod{φ(n)}.
Damit hat man nun einen öffentlichen Schlüssel (n, e), den man für jeden frei zugänglich macht und einen privaten Schlüssel (p,q,d), den man nur selbst kennen sollte.
Um mit dem RSA Verfahren eine Nachricht verschlüsseln zu können, muss eine aus Buchstaben bestehende Nachricht zuerst in natürliche Zahlen umgewandelt werden. Hierfür wird oft der ASCII Code verwendet. Im Folgenden gehen wir davon aus, dass Bob an Alice eine geheime Nachricht senden möchte. Alice habe sich hierfür ein Schlüsselpaar mit dem öffentlichen Schlüssel (n, e) und einem privaten Schlüssel (p,q,d) erzeugt.
Sei nun x ∈ ℤ, die Nachricht, die Bob an Alice senden möchte. Diese Nachricht verschlüsselt Bob mit Hilfe des öffentlichen Schlüssels (n, e) von Alice, indem er y = xe berechnet, wobei y x ∈ ℤ. Nachdem er y berechnet hat, verschickt er y an Alice.
Damit nun Alice die Nachricht von Bob entschlüsseln kann, benötigt sie eine Zusatzinformation, die der private Schlüssel enthält. Eine Funktion, die in eine Richtung leicht zu berechnen, aber sehr schwer umzukehren ist, nennt man eine Einwegfunktion. Gibt es jedoch eine Zusatzinformation, mit der die Umkehrung leicht durchgeführt werden kann, so spricht man von einer Falltürfunktion. Bei der RSA Verschlüsselung besitzt Alice gerade eine solche Zusatzinformation, mit Hilfe der die Funktion einfach umgekehrt werden kann.
Beispiel
Im Folgenden werden wir uns an einem konkreten Beispiel anschauen, wie man einen Schlüssel erzeugt, und wie anschließend Nachrichten ausgetauscht werden können. Gehen wir wieder von Alice und Bob aus. Damit sie Nachrichten austauschen können, muss jeder von ihnen ein Schlüsselpaar aus einem öffentlichen und einem privaten Schlüssel erzeugen. Zuerst schauen wir uns an, wie Alice ein Schlüsselpaar generiert. Gehen wir davon aus, dass Alice die Primzahlen p=47 und q=59 wählt, dann kann Alice n und φ(n) berechnen
n= p ⋅ q = 47 ⋅ 59 = 2773
φ(n) = (p-1)(q-1)=46 ⋅ 58=2668.
Anschließend kann sie e und d mit folgender Formel bestimmen
e ⋅ d ≡ 1 mod{φ(n)}.
⇔ d= 1+(q-1)(p-1) / e.
Wählt Alice zum Beispiel e=17, so folgt d=157. Der öffentliche Schlüssel von Alice ist also (e,n)=(17, 2773) und der private Schlüssel ist (p,q,d)=(47, 59,157). Nun besitzt Alice ein Schlüsselpaar und ist mit der Schlüsselgenerierung fertig.
Analog erzeugt sich Bob ein Schlüsselpaar. Angenommen, Bob wählt die Primzahlen p=71 und q=83. Dann erhält er hiermit
n= p ⋅ q = 71 ⋅ 83 = 5893
φ(n) = (p-1)(q-1)= 70 \cdot 82= 5740.
Damit kann er nun e und d bestimmen mit
d= \frac{1+(q-1)(p-1)}{e}.
Wählt Bob e=17, dann erhält er d= 1013. Damit ist Bob fertig mit der Schlüsselerzeugung. Er besitzt nun ein Schlüsselpaar aus dem öffentlichen Schlüssel (e,n)=(17,5893) und dem privaten Schlüssel (p,q,d)=(71,83,1013).
Gehen wir davon aus, dass Alice nun Bob die Nachricht „super“, senden möchte. Dann müssen die Buchstaben zuerst in Zahlen umgewandelt werden. Hierfür werde folgende Tabelle verwendet:
Tabelle folgt…
Wenn man das Wort „super“ mit dieser Tabelle in Zahlen ausdrückt, erhält man „super“ =„19 21 16 05 18“. Um dies verschlüsseln zu können, benötigt Alice den öffentlichen Schlüssel von Bob. Diesen findet sie zum Beispiel frei zugänglich im Internet (e,n)=(17,5893). Zum Verschlüsseln werden diese Zahlen nun in Blöcke der Länge vier geschrieben, sodass man folgende Blöcke erhält „1921 1605 1800“.
Anschließend verschlüsselt Alice jeden Block mit
x^e = x^{17}
in \mathbb{Z}/n\mathbb{Z}, sie erhält
1921^{17}\bmod{5893} = 1172
1605^{17}\bmod{5893} = 5791
1800^{17}\bmod{5893} = 3536.
Daraufhin sendet Alice die Nachricht „1172 5791 3536“ an Bob und Bob entschlüsselt diese Nachricht mit
y^d &= (x^{e})^d \quad \quad \text{in } \mathbb{Z}/n\mathbb{Z}.
Er erhält mit seinem privaten Schlüssel (p,q,d)=(71,83,1013)
1172^{1013}\bmod{5893} = 1921
5791^{1013}\bmod{5893} = 1605
3536^{1013}\bmod{5893} = 1800.
Splittet Bob nun die vierer Blöcke „1921 1605 1800“ wieder in zweier Blöcke „19 21 16 05 18 00“ auf und übersetzt die Zahlen nach der obigen Tabelle in Buchstaben, so erhält er die Nachricht von Alice im Klartext „super“.
Die Sicherheit des RSA Verfahrens basiert darauf, dass kein effizientes Verfahren existiert, das eine Zahl in ihre Primfaktoren zerlegt. Denn zum Entschlüsseln wird lediglich die Zahl d benötigt ed \equiv 1 \mod{\varphi(n)}. Um d berechnen zu können, benötigt man jedoch die Primfaktorzerlegung von n, also p und q oder \varphi(n)=(p-1)(q-1). Zur heutigen Zeit (2019) existiert kein effizienter Algorithmus, mit dem dies möglich wäre. Deshalb stellt das RSA Verfahren heutzutage für große Primzahlen einen sicheren Verschlüsselungsalgorithmus dar.
Aufgaben
Bearbeite Aufgabe 1 und 2Nutze den RSA - Rechner, um Dir das Verfahren nochmals zu verdeutlichen.
RSA - Rechner RSA - Rechner