RSA: Privaten Schlüssel schneller berechnen

[negaH]

1 == e*d mod Phi(N), stellen wirs mal um ergibt dann

d = e^-1 mod Phi(N)

du musst also das Multiplikative Inverse von E berechen, also E^-1 mod X und hast dann D direkt berechnet.
Man macht dies intern fast immer mit dem Erweiterten ggT() oder in englisch dem extended GCD().

Der eggT() berechnet

D = U * A + V * B

wir benötigen

D == 1
A == E
B == Phi(N)
U == E^-1

ergibt


1 = E^-1 * E + V * Phi(N)

wobei wir V am Ende nicht benötigen.

Wir berechnen also ExtGCD(var E^-1, var V, const E, const Phi(N)) == 1, und sind daran interessiert das das Resultat == 1 sein muß (ansonsten gibts kein modulares multiplikatives Inverse), der Rückgabewert V nicht interersiert und wird unser E^-1 geliefert bekommen, da dies unser Decryption Exponent D ist.

Es kann nun sein das der Wert E^-1 vom ExtGCD() negativ ist. Halb so wild denn in diesem Falle addieren wir auf diese Variable einfach Phi(N) dazu.

E^-1 * E == 1 und somit ist V * Phi(N) == 0 mod Phi(N) da wir ja die Gleichung
1 = E^-1 * E + V * Phi(N) vorliegen haben.
1 = 1 + 0.

Dh. das multiplikative Inverse von E ist E^-1 und definiert als 1 == E * E^-1.

Gruß Hagen