Schlüsselgenerierung RSA / Moduloarithmetik

[Dennis S. (eltio)]

Hallo zusammen,

ein Schritt bei der Generiering der RSA-Schlüssel ist ja:

$$\mbox{Bestimme: } e \cdot d \equiv 1 \mod \Phi{N}$$

Also, wenn ich das Produkt aus d und e durch die Phi-Funktion teile, 
dann soll 1 übrigbleiben. Leider fehlt mir ein bisschen der Ansatz, wie 
ich das effektiv berechnen kann. Also nach d umstellen zum Beispiel. 
Welche Rechenregeln sind da relevant?

Gruß
Dennis

[Rolf (Gast)]

Google mal anch dem erweiterten euklidischen Algorithmus.

[Cyblord -. (cyblord)]

Rolf schrieb:
> Google mal anch dem erweiterten euklidischen Algorithmus.

Korrekt:

Schaue man hier:
http://de.wikipedia.org/wiki/RSA-Kryptosystem#Erzeugung_des_.C3.B6ffentlichen_und_privaten_Schl.C3.BCssels

Das steht die Generierung Schritt für Schritt, ebenfalls mit Verweis auf 
den alten Euklid.

[Dennis S. (eltio)]

Danke für das Stichwort!

Gruß
Dennis