RSA-Demo
Das Herzstück
Auf der vorherigen Seite wurde folgende Vermutung entwickelt:
Grundlage des RSA-Verfahrens
Man vermutet, dass die Multiplikation zweier Primzahlen eine Einwegfunktion ist. Das bedeutet:
- Es ist in sinnvoller Zeit möglich, zwei Primzahlen zu multiplizieren.
- Die Umkehrung, also aus einem Produkt die beiden Primzahlen zu rekonstruieren (Primfaktorzerlegung oder auch Faktorisierung) ist deutlich schwieriger und (bei großen Zahlen) nicht in sinnvoller Zeit machbar.
Beachte, dass es sich dabei nur um eine Vermutung handelt. Falls jemand einen effizienten Algorithmus zur Primfaktorzerlegung findet, ist diese Grundlage des RSA-Verfahrens hinfällig.
Eine RSA-Demo
Wir werden nun einmal das RSA-Verfahren Schritt für Schritt durchführen. Wir nutzen dafür ein Tool von CrypTool-Online.
Aufgabe 1
Rufe die Seite RSA Step by Step auf und lass dich Schritt für Schritt durch das RSA-Verfahren leiten. Nachfolgend siehst du Screenshots mit einigen Erklärungen.
Erst werden zwei Primzahlen festgelegt. Diese dürfen nicht veröffentlicht werden; sie werden sogar nach der Schlüsselerzeugung (folgt gleich) gelöscht. Du kannst die Primzahlen an dieser Stelle verändern.
Jetzt berechnet die Seite schrittweise die Schlüssel:
Zuerst den Modul $n$ als Produkt der beiden Primzahlen. Dieses Produkt wird später öffentlich sein. CrypTool-Online führt die Berechnung für dich aus.
Dann muss eine Hilfsgröße bestimmt werden, mit der sowohl der öffentliche als auch der private Schlüssel ausgerechnet werden. Die zahlentheoretischen Hintergründe, warum es diese Größe braucht und was sie genau bedeutet, sind an dieser Stelle zu kompliziert. Wichtig ist aber, dass das Berechnen selbst sehr einfach ist, weil wir die beiden Primzahlen kennen. CrypTool-Online führt die Berechnung für dich aus.
Jetzt kann man selbst eine Zahl $e$ wählen, die für die Verschlüsselung verwendet wird. Es gibt aber Einschränkungen an diese Zahl. Du kannst vom Vorschlag von CrypTool-Online hier abweichen und eine andere Zahl ausprobieren.
Die Zahl $d$ brauchen wir zur Entschlüsselung. Sie kann nicht einfach ausgewählt werden, sondern es muss sich um das modulare multiplikative Inverse von $e$ modulo $\phi(n)$ handeln. CrypTool-Online führt die Berechnung für dich aus. Dabei wird übrigens derselbe Algorithmus verwendet wie in Versuch 2 (e) auf der vorangegangenen Seite im Schulbuch. Im Anschluss können die SChlüssel veröffentlicht werden. Die beiden Primzahlen sowie $\phi(n)$ werden dann vernichtet.
Nun ist das System vorbereitet und man kann verschlüsseln. Dafür gibt man eine Zahl als Nachricht ein. Diese wird dann durch CrypTool-Online auf eine vorgegebene Weise verschlüsselt. Dazu ist eine modulare Potenz nötig.
Und im letzten Schritt kannst du die Geheimzahl $c$ wieder entschlüsseln lassen.
Aufgabe 2
Schau, was du an der Seite verändern kannst. Probiere andere Primzahlen und Klartexte ($m$) aus. Wenn du möchtest, überlege dir sogar eine kurze Nachricht, codiere sie mithilfe einer ASCII-Tabelle durch Zahlen und verschlüssle dann diese Zahlen.
Aufgabe 3
Wir möchten nun etwas auf das Verfahren zurückschauen:
(a) An welcher Stelle werden zwei Primzahlen multipliziert?
(b) Die Sicherheit des Verfahrens beruht darauf, dass diese Multiplikation eine Einwegfunktion ist. Doch warum eigentlich? Stell dir vor, du hättest ein Verfahren gefunden, schnell eine Zahl in ihre Primfaktoren zu zerlegen. Wie kannst du damit das RSA-Verfahren knacken?
💡 Tipp
Als Angreifer hast du folgende Informationen $n$ und $e$ (öffentlicher Schlüssel). Mit deinem Verfahren kannst du nun aus $n$ einfach $p$ und $q$ berechnen.
Doch wie kannst du damit das Verfahren knacken? Dein Ziel sollte es sein, $d$ zu berechnen. Gehe dafür so ähnlich vor, wie bei der Schlüsselerzeugung (Schritte 2.3 und 2.4).
(c) A. sagt: „Das RSA-Verfahren wurde seit Jahrzehnten nicht geknackt, also ist es bestimmt sicher.“ Nimm Stellung zu dieser Aussage.
