Berechnung privater Schlüssel im RSA-Kryptosystem

  • Als Basis für eine Implementierung des RSA-Systems wurde die Zahl $ 43733 $ gewählt. $ M = 19985 $ ist die Nachricht, die mit einem öffentlichen Schlüssel $ K = 53 verschlüsselt wurde $.

    Was ist der Klartext? Was ist der private Schlüssel?

    Bisher sind meine Berechnungen:

    1. $ n = pq $
    2. $ n = 101 * 433 $
    3. $ \ phi (43733) = (101 - 1) * (433 - 1) = 43200 $.
    4. Der öffentliche Schlüssel ist $ (n = 43733, e = 53) $. < / li>
    5. Der private Schlüssel lautet $ (n = 43733, d = 12343) $.

    Allerdings bin ich nicht sicher, ob das richtig ist? Wohin gehe ich falsch?

    21 January 2012
1 answer
  • Der öffentliche Schlüssel ist $ K = e = 53 $, bereits vergeben. $ n $ (der Modulus) muss ebenfalls angegeben werden. Sie können also sagen, dass $ (e, n) $ der eigentliche Schlüssel ist.

    Der private Schlüssel ist $ d $ welcher muss $ d * e = 1 \ mod \ phi (n) $ erfüllen. Sie suchen also nach $ d $, für den $ (53 * d) \ mod 43200 == 1 $. Eine schnelle Brute-Force-Suche (mit so kleinen Zahlen ist kein Problem) zeigt, dass $ 17117 $ diese Gleichung erfüllt.

    Nun ist $ N = 43733 $, und das ist garantiert $ (M ^ e) ^ d = (M ^ d) ^ e = M \ mod n $.

    Ihre Nachricht lautet $ M = 19985 $:

    • $ 19985 ^ {53} \ äquiv. 17195 \ mod 43733 $

    • $ 17195 ^ {17117 } \ equiv 19985 \ mod 43733 $

    Dies zeigt, dass Sie mit dem öffentlichen Schlüssel verschlüsseln und mit dem privaten Schlüssel entschlüsseln können. Das Gegenteil funktioniert auch (zum Signieren der Nachricht):

    • $ 19985 ^ {17117} \ equiv 125 \ mod 43733 $

    • $ 125 ^ {53} \ equiv 19985 \ mod 43733 $

    Es gibt bessere Möglichkeiten, $ d $ von $ e $ zu finden, wenn Sie $ \ phi (n) $ kennen. Wenn Sie dies nicht tun, haben Sie Schwierigkeiten, weil Sie $ n $ dafür einkalkulieren müssen.

    21 January 2012