Folgendes Problem:

der geheime Schlüssel d wird aus dem öffentlichen Schlüssel c und dem Produkt zweier Primzahlen n wie folgt gebildet

d = (1 + k * Phi[n]) / c

wobei k eine beliebige Konstante ist, die aber vorraussetzt, dass die Division ohne Nachkommastellen vollzogen werden kann. Eine solche Konstante zu finden, ist irgendwie recht schwierig, da 1 + k * Phi[n] eine Zahl mit um die 60 Stellen ist. Gibt es eine schnellere und effizientere Methode als stupides ausprobieren?

MFG jelleton


Moderiert von Christian S.: Topic aus Sonstiges verschoben am Do 28.04.2005 um 16:56

Da gilt d * e mod p == 1 kannst Du d = e^-1 mod p setzen und damit sehr effizient d berechnen.

Anyone who is capable of being elected president should on no account be allowed to do the job.
Ich code EdgeMonkey - In dubio pro Setting.

BenBE hat folgendes geschrieben:

Da gilt d * e mod p kannst Du d = e^-1 mod p setzen und damit sehr effizient d berechnen.

(e^-1) mod p ?
da würde doch immer (e^-1) rauskommen, weil das dann eine sehr kleine Zahl ist, sozusagen "ein e-tel"..
Die Methode verstehe ich noch net so ganz.

jelleton hat folgendes geschrieben:

(e^-1) mod p ? da würde doch immer (e^-1) rauskommen, weil das dann eine sehr kleine Zahl ist, sozusagen "ein e-tel".. Die Methode verstehe ich noch net so ganz.

Stimmt so nicht ganz, weil Du mit Restklassen rechnest. Dort ist die Division so definiert, dass du immer Integerzahlen rausbekommst.

Für den Fall von oben wäre dies:

da a ^ (p - 1) mod p == 1


Und zweiteres sieht stark nach der Ausgangsgleichung aus ^^

Anyone who is capable of being elected president should on no account be allowed to do the job.
Ich code EdgeMonkey - In dubio pro Setting.

Auf www.manuel-poeter.de findest du meine Fachbereichsarbeit zum Thema Public-Key-Kryptographie speziell RSA. Schaus dir mal an, vielleicht hilft dir das weiter...