Sicherheit des RSA-Verfahrens

Arbeitsgrundlage: Krypto Skript 23 - Sicherheit RSA.docx

Einwegfunktionen mit Falltür

Die Sicherheit des RSA-Verfahrens beruht auf einer Einwegfunktion: Die eine Richtung ist leicht zu berechnen, die Umkehrung nicht. Die leichte Richtung ist die Multiplikation zweier großer Primzahlen. Der schwere Rückweg ist die Faktorisierung – aus dem Produkt die beiden Primzahlen zurückzugewinnen.

Werden zusätzliche Informationen bekannt – etwa einer der beiden Primfaktoren oder der private Schlüssel –, besitzt diese Einwegfunktion eine Falltür: Die Berechnung wird wieder einfach.

Das Schnappschloss

Ein geöffnetes Schnappschloss kann jeder schließen – einfach zudrücken. Wieder öffnen kann es in kurzer Zeit und ohne Gewalt nur, wer den Schlüssel besitzt. Der private Schlüssel ist in diesem Bild die Falltür.

Das Skript führt diesen Gedanken mit einem Comic aus dem „Taschenbuch der Algorithmen“ von Vöcking u. a. vor (Seite 140–141): Eine Figur springt über eine Kante und kommt nicht zurück – es sei denn, sie kennt die Falltür. Die Zeichnungen selbst liegen dem gedruckten Skript bei.

Werkzeug

Beide Richtungen selbst ausprobieren

Rechne dieselbe Zahl einmal vorwärts und einmal rückwärts. Achte darauf, wie viele Rechenschritte jede Richtung braucht.

Beispiel laden:

1 Der leichte Hinweg

Zwei Primzahlen multiplizieren – ein einziger Rechenschritt.

p q

2 Der schwere Rückweg

Aus N die beiden Primzahlen zurückgewinnen – durch Probedivision.

N

3 Die Falltür

Wer p kennt, bekommt q, φ(N) und den privaten Schlüssel d sofort.

N p e

Wie lange dauert der Rückweg wirklich?

Angenommen, ein Rechner schafft eine Milliarde Probedivisionen je Sekunde.

N hat Dezimalstellen

Aufgabe 1: Einen echten Schlüssel brechen

Ein Bote fängt eine verschlüsselte PIN ab. Der öffentliche Schlüssel steht offen im Netz: e = 5 und N = 5141. Der abgefangene Geheimtext lautet 4449.

Brich den Schlüssel: Zerlege N mit dem Werkzeug oben, bestimme daraus φ(N) und den privaten Schlüssel d – und lies damit die PIN.

Rechenaufgabe

Aufgabe 1: Schlüssel brechen und PIN lesen

Jede Lücke wird einzeln geprüft. Das ? neben einer Lücke zeigt die Berechnungsvorschrift.

N 5141 e 5 Geheimtext c 4449

Rechner

Rechner zum Entschlüsseln der PIN

Stelle auf „Entschlüsseln“, trage dein d und N = 5141 ein und gib die abgefangene Zahl 4449 ein.

Verschlüsseln Entschlüsseln

Schlüssel k N

Klartextzahl m Geheimzahl c

Freitext

Aufgabe 2: Versuche dasselbe mit dem 31-stelligen N aus dem vorigen Kapitel (N = 1062646162893167618721054113099, e = 5). Beschreibe, woran das Werkzeug scheitert, und erkläre daran die Sicherheit des RSA-Verfahrens.

💡 Zum Speichern deiner Antwort bitte einloggen.

Rechenaufgabe

Aufgabe 3: Die Falltür benutzen

Ein Mitarbeiter plaudert einen der beiden Primfaktoren des 31-stelligen Moduls aus: p = 993124637809243. Wie weit kommst du damit? Nutze Panel 3 des Werkzeugs.

N 1062646162893167618721054113099 e 5 verratenes p 993124637809243

Lückentext

Merke: Die Sicherheit des RSA-Verfahrens beruht auf einer . Die leichte Richtung ist das zweier Primzahlen, die schwere Richtung ihre . Wer p, q oder φ(N) kennt, besitzt die und kann den privaten Schlüssel wieder leicht berechnen.