Erweiterter Euklid - Die modular Inverse
Mit dem erweiterten Euklid wird die modular Inverse berechnet. In diesem speziellem Fall
d für den privaten Schlüssel. Dies ist möglich, weil folgendes gilt:
Für zwei Zahlen a, b ∈ ℤ gibt es immer Zahlen x, y ∈ ℤ so daß
ggT(a, b) = x * a + y * b.
Die Berechnung kann in zwei Varianten ausgeführt werden. Hier händisch die
rekursive. Das Programm nutzt die iterative.
Solange der Rest ≠ 0 ist, wird a durch b und b durch Rest = a mod b ersetzt.
Außerdem werden die Koeffizienten neu berechnet.
e * d = 1 mod Phi(N) im Beispiel 47 * d = 1 mod 60
47 * x + 60 * y = 1 ist zu lösen.
g = ganzzahliger Teil von a/b
a b g Rest x=d y
---------------------------
47 60 0 47 47 < 60 ->Argumente tauschen
60 47 1 13 abwärts immer a mod b
47 13 3 8
13 8 1 5
8 5 1 3
5 3 1 2
3 2 1 1
2 1 2 0 Bei Rest = 0 abbrechen und von unten
aufwärts x und y ausrechnen.
47 60 0 47 23 -18 Schema für jede Zeile bis auf die unterste:
60 47 1 13 -18 23 x = y(zeile darunter)
47 13 3 8 5 -18 y = x(zeile darunter) -
13 8 1 5 -3 5 g(aktuelleZeile) * y(zeile darunter)
8 5 1 3 2 -3
5 3 1 2 -1 2
3 2 1 1 1 -1
2 1 2 0 0 1 x = Rest * a, y = 1 * b
Probe
(e * d) mod Phi(N) = 1
(47 * 23) mod 60 = 1081 mod 60 = 1;
damit ist die Inverse d = x = 23
