Entschlüsselung von RSA

Question

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?

Answer 1

„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?

Answer 2

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.