Die nach dem Schweizer Mathematiker Leonhard Euler benannte Formel löst folgende Gleichung auf:

(a × x) mod n = b

Ist b=1 handelt es sich um den Kehrwert modulo von x. Die Lösung lautet:

x = (b × a ^phi(n)-1) mod n

Voraussetzung ist, dass a und n über keinen gemeinsamen Teiler verfügen, das heisst relativ prim zueinander sind. phi(n) ist die Eulersche Funktion. Sie wird normalerweise mit dem griechischen Buchstaben phi "φ" geschrieben, aber ich bin nicht sicher, ob alle Browser ihn korrekt darstellen. phi(n) bezeichnet die Menge aller Zahlen zwischen 1 und n-1, die relativ prim zu n sind. Diese Menge heisst auch die reduzierte Residuenmenge. Die normale Residuenmenge umfasst alle Zahlen zwischen 1 und n-1.

Nehmen wir als Beispiel eine Gleichung aus dem RSA-Text:

(5 × x) mod 48 = 1

Um phi(48) zusammenzustellen, zerlegen wir 48 in Primzahlen:

48 = 2 × 2 × 2 × 2 × 3.

Die Residuenmenge von 48 enthält alle Zahlen zwischen 1 und 47. Bei der reduzierten Residuenmenge fallen alle Zahlen heraus, die Faktoren enthalten, die auch Faktoren von 48 sind. Im Beispiel also alle Zahlen, die 2 oder 3 als Faktor haben. Es bleibt als reduzierte Residuenmenge: 1, 5, 7, 11, 13, 17, 19, 23, 25, 29, 31, 35, 37, 41, 43, 47. Also sechzehn Zahlen. Damit ist

phi(48) = 16

Nun lösen wir die Eulersche Verallgemeinerung:

x = (b × a ^phi(n)-1) mod n = (1 × 5 ^phi(48)-1) mod 48 = 5 ¹⁵mod 48 = 29

Da das Distributivgesetz gilt, ist die Lösung dieses Ausdrucks nicht schwer. Die andere Gleichung des Textes funktioniert ebenso:

(5 × x) mod 16 = 1

Die Zerlegung von 16 lautet: 2 × 2 × 2 × 2. Die reduzierte Residuenmenge von 16 darf also keine Zahl enthalten, die 2 als Faktor besitzt. Es bleiben: 1, 3, 5, 7, 9, 11, 13, 15. Das sind acht Zahlen, phi(16) = 8. Wir lösen:

x = (b × a ^phi(n)-1) mod n = (1 × 5 ^phi(16)-1) mod 16 = 5 ⁷mod 16 = 13

Zurück zu RSA.

(c) Autor und Copyright Wolf Hosbach