Erweiterter Euklidischer Algorithmus - Extended Euclidean Algorithm

Der erweiterte euklidische Algorithmus (Details siehe →hier) findet für gegebene a und b die Werte s und t, die die Gleichung s·a + tb = ggT(a,b) erfüllen.
The extended Euclidean algorithm (see →here) finds the values s and t that satisfy the equation s·a + t·b = gcd(a,b) for given a, b.

Die diophantische Gleichung s·a + t·b = c für gegebene c hat unendlich viele Lösungen, wenn der ggT(a,b) die Zahl c teilt, sonst ist sie unlösbar. Eine spezielle Lösung findet man, wenn man s₀a+t₀b=ggT(a,b) mit c/ggT(a,b) multipliziert. Wenn nun s' und t' so gewählt werden, daß s'·a = t'·b ist, dann wird eine Zunahme von s um s' durch die Zunahme von t um t' ausgeglichen. Es ist dann s'·a - t'·b = 0. Geeigneterweise wählt man kgV(a,b) = s'·a = t'·b, und erhält so s'=kgV(a,b)/a und t'=kgV(a,b)/b.

© Arndt Brünner, 16. 8. 2007 (erweitert: 23. 10. 2011)

Geheimes geheimhalten mit Euklid, Fermat und Euler

Eine wichtige Anwendung des erweiterten Euklidischen Algorithmus ist das Ermitteln des multiplikativen Inversen innerhalb eines Restklassenringes, d.h. das Finden der Zahl b zu gegebenen a und m mit ggT(a,m)=1, so daß a·b ≡ 1 mod m ist. Äquivalent zu diesem letzten Ausdruck ist a·b : m = q Rest 1, d.h. a·b/m = q + 1/m, woraus sich a·b = q·m + 1 und damit a·b - q·m = 1 ergibt.

Dieses Inverse hat bei der im Internet-Zahlungsverkehr allgegenwärtigen RSA-Verschlüsselung eine entscheidende Bedeutung. Die Verschlüsselung beruht auf dem kleinen Fermatschen Satz n^p-1 ≡ 1 mod p und insbesondere seiner Verallgemeinerung durch Leonhard Euler: n^φ(m) ≡ 1 mod m, falls n und m teilerfremd sind, also ggT(n,m)=1 ist.

Als m wird gewöhnlich das Produkt zweier Primzahlen gewählt, die so groß sein müssen, daß die Faktorisierung von m nahezu unmöglich ist, wodurch φ(m) quasi nicht berechnet werden kann.

Verschlüsselt wird die „Botschaft“ in Form einer Zahl n mit n^e mod m = c, wobei e beliebig, aber teilerfremd zu m gewählt wird. Die so verschlüsselte Botschaft kann mit dem zu e innerhalb des Restklassenringes Z_m Inversen d wieder decodiert werden: c^d mod m = n.

Wenn n^e ≡ c mod m für c in den letzten Ausdruck in der Form c^d ≡ n mod m eingesetzt wird, ergibt sich n^e·d ≡ n mod m, woraus mit Fermat/Euler folgt, daß e·d ≡ 1 mod φ(m) sein muß.

Man setzt also mit den obigen Bezeichnungen a=e und b=φ(m) und erhält mit s das zu e Inverse.

 
Beispiel

Wir wählen m=4091969407709 (=534571·7654679) und berechnen mit dem Wissen um die beiden Primfaktoren φ(m) = 534570·7654678 = 4091961218460. (In der Wirklichkeit muß m wesentlich größer sein. Diese Zahl wird selbst von meinem kleinen Javascriptrechner in wenigen Augenblicken faktorisiert.) Zu diesem φ(m) ist z.B. e=4321 teilerfremd, das wir als Schlüssel festlegen. Der erweiterte Euklidsche Algorithmus ergibt –501906837719·4321 + 530·4091961218460 = 1, woraus sich t=–501906837719 ablesen läßt. Das ist modulo 4091961218460 kongruent zu 3590054380741, welches unser Inverses d ist.

Nun werden m=4091969407709 und e=4321 als „öffentliches Schlüsselpaar“ (public key) veröffentlicht. Mit diesem kann nun jeder Nachrichten so verschlüsseln, daß sie nur mithilfe des privaten Schlüssels d (private key) wieder entschlüsselt werden können, der aus diesem Grunde natürlich geheimgehalten wird. (In der Regel werden mit diesem Verfahren nicht lange Botschaften, sondern nur kürzere Schlüssel für schnellere, aber nicht so sichere, sogenannte symmetrische Verschlüsselungsverfahren ausgetauscht, mit denen dann die eigentlichen Botschaften kodiert werden.)

Ich will nochmal darauf hinweisen, daß es möglich ist, den privaten Schlüssel d aus den öffentlichen Schlüsseln m und e zu berechnen, wenn nur die Faktorisierung von m gelingt, die ihrerseits für die Berechnung von φ(m) nötig ist. Daher müßte m eigentlich so groß gewählt werden, daß diese Faktorisierung mit den heute zu Gebote stehenden Mitteln mit an Sicherheit grenzender Wahrscheinlichkeit nicht gelingen wird. D.h.: unser m ist für die Realität unbrauchbar. Probieren Sie unten aus, wie schnell φ(4091969407709) selbst durch ein Javascript berechnet wird! Ich habe es allerdings so groß gewählt, daß Sie eine Vorstellung vom Verfahren bekommen und daß wir damit eine hinreichend lange Botschaft auf einmal verschlüsseln können.

Nun soll nämlich mit dem RSA-Verfahren und unseren Schlüsseln die Botschaft „Euler“ übermittelt werden. Die ASCII-Codes der fünf Buchstaben sind 69, 117, 108, 101 und 114, hexadezimal: 0x45, 0x75, 0x6C, 0x65, 0x72. Zusammengesetzt ergibt das: 0x45756C6572 = (dezimal) 298322781554. Es wird kodiert: 298322781554⁴³²¹ mod 4091969407709 = 3211318268883. (Für solche scheinbar jeden Rechner überfordernde Terme gibt es einen verblüffend schnellen Algorithmus, siehe →hier). Die Nachricht „3211318268883“ kann per Ansichtskarte oder E-Mail (etwa gleiche Sicherheitsstufe) verschickt werden. Beim Empfänger wird sie mithilfe des geheimen Zauberschlüssels 3590054380741 dekodiert: 3211318268883^{3590054380741} mod 4091969407709 = 298322781554 = 0x45756C6572 →→ „Euler“.

Ausprobieren
(Inversenberechnung, Eulersche φ-Funktion, Modulo-Potenzieren, automatisch mit inverser Operation)

m=    φ()     

e =              modulo = φ(m) =

                      (Bei Eingabe: Berechnung des Inversen zu e)

Verschlüsselung:
			mod	=
	(Nachricht)	(e)	(m)		(Code)

 

 

m immer als Produkt zweier Primzahlen

© Arndt Brünner, 16. 8. 2007
Version: 30. 10. 2011