Gibt es mehrere Werte für d bei der Schlüsselberechnung des RSA-Algorithmus mit dem erweiterten euklidischen Algorithmus. Wie berechne ich diese?
Ich muss gerade eine Seminararbeit über den RSA-Algorithmus schreiben und habe mich heute in die Schlüsselerzeugung eingearbeitet. Aber bei dieser Aufgabe habe ich Probleme. Die Werte sind:
e = 3
n = 253
Darauf habe ich dann den erweiterten euklidischen Algorithmus angewandt und bekam für d = -84 raus. Ich habe das auch nochmal mit einem Rechner im Internet nachgeprüft. Eigentlich rauskommen müsste: d = 147, was ja auch Sinn macht, da
d > 1 sein muss. Soweit ich es verstanden habe, gibt es wohl mehrere Werte für d, allerdings verstehe ich nicht wie ich auf diese komme.
Ich danke schonmal für jede Hilfe.
1 Antwort
Also n=253=11*23
Also ist phi(n)=10*22=220
Du willst d so bestimmen, sodass e*d=1 bzgl Modulo 220 gilt.
Jedoch ist 3*(-84)=-252=-32 bzgl Modulo 220, also nicht 0, du hast somit beim Erweiterten Euklidischen Algorithmus ein Fehler gemacht.
Falls du beim Euklidischen Algorithmus eine negative Zahl bekommen solltest, kannst du einfach Vielfache von Phi(n) (also 220) auf d addieren, bis es positiv ist (da d dann immer noch in der selben Rest-Klasse bzgl Mod Phi(n) ist)
Ahhh danke, mein Fehler war, das ich den Algorithmus mit e und n und nicht mit e und phi(n) berechnet habe. Und danke für den Tipp mit dem Vielfachen von Phi