RSA Verschlüsselung - ggt Berechnung
Zurück zum Hauptartikel über RSA
Der (erweiterte) euklidische Algorithmus
Dieser spezielle Algorithmus dient eigentlich der Berechnung des größten gemeinsamen Teilers (ggT) zweier Zahlen a und b. Mit einem Beispiel möchte ich Ihnen das Verfahren im Folgenden vorstellen:
a = 105, b = 1001
1001 mod 105 = 56 (1001 = 9 · 105 + 56)
105 mod 56 = 49 (105 = 1 · 56 + 49)
56 mod 49 = 7 (56 = 1 · 49 + 7)
49 mod 7 = 0 (49 = 7 · 7)
Der ggT von 105 und 1001 ist demnach 7. Man könnte den Algorithmus auch folgendermaßen beschreiben:
r0 = a
r1 = b
r0 = q1 · r1 + r2
r1 = q2 · r2 + r3
r2 = q3 · r3 + r4
...
rn − 2 = qn − 1 · rn − 1 + rn
rn − 1 = qn · rn
Diese Darstellung entspricht den oben in Klammern durchgeführten Berechnungen. rn ist der größte gemeinsame Teiler.
Auf dem Computer geht's noch einfacher. Hier ein Beispiel in C:
int a, b;
/* Lese zwei Zahlen a und b ein */
while (b != 0)
{
int r = a % b;
a = b;
b = r;
}
/* Gebe a als ggT aus */
Der größte gemeinsame Teiler kann auch als Summe von zwei Produkten dargestellt werden (Vielfachsummendarstellung); dies ist für unsere Zwecke von großer Wichtigkeit:
d = xa + yb
Um x und y zu berechnen, müssen wir die oben aufgeführte euklidische Gleichungskette von unten nach oben durchgehen; dies nennt man auch den erweiterten euklidischen Algorithmus.
Und so sieht das mit unserem Beispiel 105 und 1001 aus:
d = 7 = 56 − 1 · 49
= 56 - 1 · (105 − 1 · 56)
= (−1) · 105 + (1 + 1 · 1) · 56
= 2 · (1001 − 9 · 105) − 1 · 105
= 2 · 1001 − (2 · 9 + 1) · 105
= 2 · 1001 − 19 · 105
Sie sehen also, dass die Gleichungskette soweit umgeformt wurde, bis die Darstellung der Art x · a und y · b, also x · 1001 bzw. y · 105, war. So konnten wir x = 2 und y = −19 berechnen.
Sind a und b zueinander teilerfremd, d. h. ihr größter gemeinsamer Teiler ist 1, dann gibt es eine ganze Zahl c mit der Eigenschaft
b · c mod a = 1
Man sagt in diesem Fall, dass b modulo a invertierbar ist. Warum ist das so? Nun, da a und b teilerfremd ist, gilt
xa + yb = d = 1
Da xa ein Vielfaches von a ist, ist xa modulo a 0 – es lässt sich ohne Rest durch a teilen. c ist also gleich y.
Jetzt wissen wir auch, wie wir mit Hilfe des willkürlich gewählten e und des bekannten Phi(n) die Zahl d berechnen können. Wie wir bereits gesehen haben, soll gelten:
ed mod Phi(n) = 1 oder anders ausgedrückt:
x · Phi(n) + y · e = 1
y (bzw. c) stellt das gesuchte d dar.
Neben dieser Berechnung nach dem euklidischen Algorithmus existiert noch eine weitere Berechnungsart, die auf dem Satz von Euler beruht, allerdings nicht immer funktioniert.
Zurück zum Hauptartikel über RSA
