Der Satz von Euler erweitert den kleinen Satz von Fermat um Module, die nicht Primzahlen sind. Im Zusammenhang mit Verschlüsselung ist der Fall interessant, daß der Modul ein zusammengesetzte Zahl ist, die genau zwei Primfaktoren besitzt.
Wir nehmen zum Beispiel eine Zahl N, die aus den zwei Primzahlen p und q besteht, wobei N=p*q ist.
Nun gilt nach dem Satz von Euler:
a(p-1)(q-1)ºa (mod p*q)
für irgendeine Zahl, die mit p*q keine gemeinsamen Teiler besitzt.
Und genau hier setzt die Verschlüsselung nach RSA (Rivest, Shamir, Adleman) an:
- Man suche sich zwei große Primzahlen, nenne sie p und q.
- Man multipliziere p und q miteinander und nenne diese Zahl N.
- Man multipliziere p-1 und q-1 miteinander und nenne diese Zahl k.
- Man suche sich eine Zahlen E und berechne dann D,
so daß D*Eº1 (mod k) (, weil aD*E=akºa1 (mod N)),
wobei E und k teilerfremd sein müssen.
Das Paar (N,E) ist der private Schlüssel des einen Benutzers,
(N,D) ist der öffentliche Schlüssel,
a ist das Zeichen oder das Wort (in Zahlen übersetzt), das verschlüsselt werden soll.
Beispiel (mit kleinen Zahlen):
- p=3, q=7
- N=3*7=21
- k=(3-1)*(7-1)=12
- D*E soll nun º1 (12) sein, also z.B 1, 13, 25, 37, 49, 61, 73, 85, ...
Nun noch eine zusammengesetzte Zahl (Warum keine Primzahl?) für D*E wählen, z.B. 85=5*17. D wäre also 5 und E=17.
Die Botschaft soll 9 lauten.
Der Benutzer mit dem Schlüssel E (wie encrypt oder verschlüsseln) berechnet nun 9E=95=59049º 18 (mod 21).
Der Sender übergibt nun die verschlüsselte Botschaft, nämlich 18, an den Empfänger, der nun seinen Schlüssel D (decrypt oder entschlüsseln) einsetzt und rechnet:
18D=1817=2185911559738696531968º 9 (mod 21), also die ursprüngliche Botschaft.
zurück 