Zusatzaufgaben zur Sicherheit der RSA-Verschlüsselung

Zusatzaufgaben

zur interaktiven Flash-Animation
RSA-Verschlüsselung

Worauf gründet sich die Sicherheit der RSA-Verschlüsselung?

Überlegen wir uns das anhand der Animation: Ein unbefugter Lauscher kann im Prinzip alle (rot dargestellten) Zahlen, die durch den öffentlichen Bereich übertragen werden, in Erfahrung bringen. Das sind:

Alices öffentlicher Schlüssel, d.h. die Zahlen n und a (die ja ganz offen bekannt gegeben werden), und
alle übermittelten Geheimtexte (d.h. im Falle von Bobs Nachricht die Zahl y, die über elektronische Abhörmethoden beschafft werden kann, in diesem Sinn also auch "öffentlich" ist).

Was nützt ihm das? Alice ermittelt den Klartext von an sie gerichteten Nachrichten (d.h. in Bobs Fall die Zahl x) mit der Formel
x = y^b mod n.
Der Lauscher müsste also zunächst den Wert von b in Erfahrung bringen, bevor er Nachrichten an Alice nicht nur abfangen, sondern auch entschlüsseln kann.

Aufgabe 1: Falls der Lauscher tatsächlich b herausfindet - wie schwer ist es dann für ihn, auch m zu ermitteln?
Tipp: Beachte, dass b die Inverse von a modulo m ist, d.h. eine Zahl, die die Gleichung
ab mod m = 1
erfüllt. Was weißt du über m, wenn a und b bekannt sind?

Wenn du Aufgabe 1 gelöst hast, siehst du, dass es mit einem heutigen Computer ganz einfach ist, m zu berechnen, wenn b einmal bekannt ist.

Aufgabe 2: Falls der Lauscher m kennt - wie schwer ist es dann für ihn, auch Alices geheime Primzahlen p und q zu ermitteln?
Tipp: Beachte, dass in diesem Fall sowohl pq also auch (p - 1)(q - 1) bekannt sind!

Wenn du Aufgabe 2 gelöst hast, siehst du, dass es ganz einfach ist, die Primfaktoren von n zu ermitteln, wenn m einmal bekannt ist. Von diesem Problem wird aber allgemein angenommen, dass es nur schwer zu lösen ist! Um ein n mit 300 Dezimalstellen in seine beiden Primfaktoren zu zerlegen, müsste auch ein schneller Computer Hunderte von Jahren rechnen!

Die Hürde, die ein Lauscher also überwinden muss, ist - egal, wie er es anstellt - genauso hoch wie die Faktorisierung von n. Darauf gründet sich die Sicherheit der RSA-Verschlüsselung. Sollte eines Tages eine Möglichkeit gefunden werden, große Zahlen sehr schnell zu faktorisieren, wäre das Verfahren mit einem Schlag unsicher.

Dass ein "klassischer" Faktorisierungs-Algorithmus, der auf einem konventionellen Computer laufen könnte, gefunden wird, halten die meisten ZahlentheoretikerInnen für eher unwahrscheinlich. Vielleicht kann sogar eines Tages bewiesen werden, dass ein solcher Algorithmus nicht existiert. Allerdings droht der RSA-Verschlüsselung von einer anderen Seite Gefahr: Auf einem geeigneten Quantencomputer (der bisher aber experimentell noch nicht realisiert wurde) wäre die schnelle Faktorisierung großer Zahlen - dank eines im Jahr 1994 von Peter Shor gefundenen Verfahrens - kein Problem mehr.

Weitere Seiten zur RSA-Verschlüsselung: