RSA-Verschlüsselung - Privaten Schlüssel herausfinden?
Von einer Nachricht im ASCII-Code ist bekannt, dass sie mit dem RSA-Verfahren verschlüsselt ist. Der öffentliche Schlüssel ist n=133 und e=17, der private ist nicht bekannt.
Verschlüsselte Nachricht (5 Buchstaben): mlF6_ (d.h. klein M, klein L, groß F, sechs, Unterstrich)
Wie muss ich vorgehen, ums sie trotzdem zu entschlüsseln ?
2 Antworten
Du musst n in die Primfaktoren p und q zerlegen.
n = p * q = 133 = 7 * 13
p = 7
q = 13
Nun kannst Du die Euler'sche Phi-Funktion berechnen.
phi(n) = (p - 1) * (q - 1) = 6 * 12 = 72
Nun musst Du d so wählen, dass (e * d) mod phi(n) = 1, also das Multiplikativ-Inverse zu e mod phi(n) finden.
Lustigerweise ist hier d = e = 17, denn 17² mod 72 = 1.
Falls man d einmal nicht "raten" kann, muss man den erweiterten Euklidischen Algorithmus anwenden, der d bei gegebenen e und phi(n) in polynomieller Laufzeit berechnen kann.
Dann die ASCII-Zeichen in Zahlen konvertieren und für alle Zeichen x (= ASCII-Code des Zeichens) folgendes berechnen.
x^17 mod 133
Das dann jeweils wieder in ein ASCII-Zeichen konvertieren.
Der Vollständigkeit halber dann noch die Rechung für 133.
Es ist 133 = 7 * 19, also
phi(n) = 6 * 18 = 108.
Nun mit dem erweiterten euklidischen Algorithmus das Inverse des öffentlichen Schlüssel e = 17 mod 108 berechnen.
108 = 6 * 17 + 6
17 = 2 * 6 + 5
6 = 5 + 1. Der ggT ist also wirklich 1. Jetzt rückwärts:
1 = 6 - 5 = 6 - (17 - 2 * 6) = 6 - 17 + 2 * 6 = 3 * 6 - 17
=> 1 = 3 * (108 - 6 * 17) - 17 = 3 * 108 - 18 * 17 - 17
=> 1 = 3 * 108 - 19 * 17
Damit ist -19 das Inverse von 17. Als positive Zahl ist dies
108 - 19 = 89.
DIe Zahl 89 ist also der geheime Schlüssel d.
Super, danke! :-)
Da der erweiterte Euklidische Algorithmus ja numerisch nicht unbedingt einfach zu implementieren ist, wollte ich noch anmerken, dass es auch eine direkte Möglichkeit gibt, d zu berechnen.
d = e^(phi(n) - 1) mod n
Der Exponent ist zwar recht groß, aber mittels des "square-and-multiply"-Algorithmus lässt sich die Exponentiation effizient (mit einer Laufzeit, die proportional zu log(n) ist) berechnen.
d = e^(phi(n) - 1) mod n
Sorry.
Es muss heißen ...
d = e^(phi(n) - 1) mod phi(n)
Dann kommt auch 89 heraus. :-)
Vorab, das ist nicht so einfach!
Näheres aber hier: http://www.curiegymnasium.goerlitz.de/inf/scheinfo/info12/krypto/rsa.htm
Du müsstest hier also das Verfahren Rückwärts durchlaufen, um auf den Ursprung zu kommen und das mit einer Variable.
Rückschließend kannst du dann die Entschlüsslungskomponente rausfinden.
abgesehen davon, dass 133 = 7 • 19 und nicht 7 • 13 ist, ist alles okay :-)