Erweiterter Euklid

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 das Inverse d = x = 23

Quelltext ein-/ausblenden