Entschlüsselung von RSA
-
29-09-2020 - |
Frage
Wie können wir eine RSA-Nachricht entschlüsseln, wenn wir nur den öffentlichen Schlüssel haben?
Zum Beispiel Nachricht:21556870,12228498
Öffentlicher Schlüssel: (e = 15852553, n = 44331583)
Ich weiß, dass es diese Formeln gibt:
gcd(e, φ(n)) = 1
ed mod φ(n) = 1
Meine Idee war also, dass ich den Wert von e in die erste Formel eingeben und dann d ableiten könnte, das Teil des privaten Schlüssels ist.Ich glaube jedoch nicht, dass es mathematisch möglich ist, es zu finden φ(n)
Hier.Wie kann ich sonst eine RSA-Nachricht nur mit dem öffentlichen Schlüssel entschlüsseln?
Lösung
„Wie können wir eine RSA-Nachricht entschlüsseln, wenn wir nur den öffentlichen Schlüssel haben?“
Also, Wir müssen den privaten Schlüssel aus dem öffentlichen Schlüssel finden.Dies sollte in praktischen Situationen im Allgemeinen zu schwierig sein, da es sich bei RSA-Algorithmen um bewährte, praxiserprobte Sicherheitsalgorithmen handelt und die Leute sie im Allgemeinen vorsichtig mit ausreichend langen Bits verwenden.
Die Ihnen zugewiesene Übung dient jedoch dazu, den RSA-Algorithmus zu üben.Die verwendeten Zahlen sind nicht groß genug, um zu verhindern, dass Sie aufgrund des öffentlichen Schlüssels den privaten Schlüssel erhalten. Sie sollten in der Lage sein, alle Berechnungen durch einfaches Programmieren mit Ihrer bevorzugten Programmiersprache und Ihrem bevorzugten Computer durchzuführen.
Versuchen Sie es besser, bevor Sie sich die Antwort unten ansehen.
Öffentlicher Schlüssel: (e = 15852553, n = 44331583)
Lassen Sie uns faktorisieren n
.Hier ist ein einfaches Python-Programm.
def factor(n):
for i in range(2, n-1):
if n % i == 0:
print(str(n) + " = " + str(i) + " * " + str(n // i))
break
Läuft factor(44331583)
, das erhalten wir 44331583 = 5003 * 8861
.
Also φ(n) = (5003 - 1) * (8861 - 1) = 44317720
Finden Sie die Umkehrung von e
Modulo φ(n)
.Hier ist ein einfaches Python-Programm.
def inverse(e, phi):
""" display the inverse of e modulo phi """
for i in range(1, phi):
if i * e % phi == 1:
print(str(e) + " * " + str(i) + " = 1 (mod " + str(phi) + ")")
break
Läuft inverse(15852553, 44317720)
, das erhalten wir 15852553 * 1951097 = 1 (mod 44317720)
.Das heißt, das Gegenteil von e
Modulo φ(n)
Ist d=1951097
.
Der entsprechende private Schlüssel lautet also (d = 1951097, n = 44331583)
.
Berechnen m**d (mod n)
um eine RSA-Nachricht zu entschlüsseln (auch bekannt alsGeheimtext) m
.Hier ist die beliebte modulare Potenzierungsfunktion.
def modulo_pow(base, exponent, modulus):
""" display the result of base ** exponent % modulus """
exp = exponent
result = 1
b = base % modulus
while exp > 0:
if exp % 2 == 1:
result = (result * b) % modulus
exp = exp >> 1
b = (b * b) % modulus
print(str(base) + " ** " + str(exponent)
+ " = " + str(result) + " (mod " + str(modulus) + ")")
Läuft modulo_pow(21556870, 1951097, 44331583)
Und modulo_pow(71, 15852553, 44331583)
, wir erhielten jeweils
21556870 ** 1951097 = 71 (mod 44331583)
12228498 ** 1951097 = 111 (mod 44331583)
Daher ist die entschlüsselte Nachricht 71,111
.Können Sie herausfinden, was es bedeutet?
Andere Tipps
Sie müssen die Basis des öffentlichen RSA-Schlüssels berücksichtigen, um eine Entschlüsselung durchführen zu können.Das ist der springende Punkt:Das Knacken von RSA entspricht dem Faktorisieren, und das Faktorisieren ist (vermutlich) sehr schwierig.