Was passiert wenn das multiplikative Inverse für RSA-negativ ist?

Hallo Leute,

Ich habe gerade zum vorbereiten auf meine Abschlussarbeit, wie gelernt, den erweiterten euklidischen Algorithmus angewendet um das multiplikative Inverse für eine RSA-Verschlüsselung zu berechnen.

p=7 q=13 N=91 Phi(N) = 73

e habe ich willkürlich auf 23 bestimmt

Jetzt habe ich wie gesagt den Algorithmus angewendet und komme für das multiplikative Inverse aber auf -25, das verträgt sich aber als negative Zahl nicht mit dem RSA Algorithmus. Ich habe versucht eine Lösung zu finden, alles mehrfach nachgerechnet, aber komme einfach nicht weiter. Wie gehe ich mit der Situation um?

Anderes e? Ich dachte e muss nur größer als 1 und kleiner als Phi(N) sein? Ist eine negative Zahl doch verwendbar?

Danke im Vorraus,

Liebe Grüße Lenny :)

Answer 1

[kmkcl]

Ich bin absolut nicht in dem Thema drin... und es kann sein, dass ich total daneben liege...

aber operierst du nicht eigentlich auf einem endlichen Zahlenraum? Eigentlich sollte es doch gar keine negativen Zahlen geben, oder? Hast du vielleicht irgendwo vergessen Modulo anzuwenden?

Das Multiplikative Inverse kann doch auch gar keine negative Zahl sein, wenn die Ausgangszahl nicht negativ ist... Die Multiplikation muss ja 1 ergeben.

Comments

[Lennart2006]

Ich habe mittlerweile die Lösung gefunden. Also ich habe ja den erweiterten euklidischen Algorithmus angewendet. Da kann eine negative Zahl raus kommen, das ist völlig normal. Zur Lösung addiert man einfach nocheinmal Phi(N), dann wird die Zahl positiv und lässt sich auch für die weiteren Rechungen verwenden.

Aber ja, das multiplikative inverse ist eigentlich nicht negativ, nur mit dem euklidischen Algorithmus kommt man halt manchmal erst auf die negative Zahl.