RSA-Verschlüsselung

379238930, 656540520, 481853065, 133754286, 95155117,
154934359, 99748360, 407787080, 257916135, 294126417,
281235777, 456611745, 130140221

 

Der Text des dritten Rätsels ist mit RSA verschlüsselt. RSA ist ein Public-Key-Verfahren. Das bedeutet, dass der Schlüssel, mit dem Nachrichten verschlüsselt werden, öffentlich bekannt sein kann, da es mit ihm nicht möglich ist, ein Chiffrat wieder zu entschlüsseln.

 

Im Beispiel ist der öffentliche Schlüssel

    e = 3
    n = 804446941

Das bedeutet, dass zum Verschlüsseln der Zahl m die folgende Berechnung durchgeführt wird:

    c = m^3 (mod 804446941)

 

Das Chiffrat c kann mit dem geheimen Schlüssel entschlüsselt werden. Den geheimen Schlüssel kann berechnen, wer die Primfaktoren der Zahl n kennt. Die Faktorisierung großer Zahlen ist ein schwieriges Problem, das sich nicht effizient lösen lässt. Für euch haben wir jedoch eine kleine Zahl verwendet, die sich sehr leicht in ihre Primfaktoren zerlegen lässt. Sind die Primfaktoren p und q bekannt, ist es ein Leichtes (p-1)*(q-1) zu berechnen:

 

Der gesuchte geheime Schlüssel d ist das multiplikativ Inverse zu e bezüglich des Moduls (p-1)*(q-1), so dass gilt:

    e * d = 1 (mod (p-1)*(q-1))

Nach der Entschlüsselung erhaltet ihr Zahlen, die ihr noch in Buchstaben übersetzten müsst. Wie das geht, findet ihr schon selbst heraus ;) Entschlüsselt wird übrigens wie folgt:

    m = c^d (mod n)


Das hier beschriebene Verfahren heißt Textbook-RSA und weist verschiedene Schwächen auf. Es werden zum Beispiel gleiche Klartexte immer auf das gleiche Chiffrat abgebildet. Daher wird in den meisten Fällen die Variante RSA-OAEP verwendet.

Warum das Entschlüsseln der RSA-Chiffrate mit dem geheimen Schlüssel funktioniert und warum es nicht möglich ist dies mit dem öffentlichen Schlüssel zu tun, könnt ihr euren Mathematiklehrer fragen. Vielleicht zeigt er euch nach dem Abi, was mathematisch hinter RSA steckt.

 

Du bist fertig oder kommst nicht weiter? Hier findest Du die Lösung.

 

Bei Fragen oder Feedback freuen wir uns über eine Nachricht an krypto∂informatik.kit.edu