Der Satz von Euler

Hintergründe zur interaktiven Flash-Animation
RSA-Verschlüsselung


Satz von Euler: Es seien Dann gilt

xkm + 1 mod n  =  x.



Wir wollen diesen Satz hier nicht beweisen, sondern besprechen, wie sich mit seiner Hilfe das Protokoll des RSA-Verfahrens verstehen lässt. Bevor wir es exakt formulieren, beschreiben wir seine Grundidee:

Im Bereich der reellen Zahlen gilt die Identität

(xa)1/a  =  x.

Ist a bekannt und
y  =  xa

gegeben, so kann mit ihrer Hilfe x zurückgewonnen werden, und zwar gemäß der Formel

x  =  y1/a,

die wir auch in der Form

x  =  yb    mit    b  =  a-1

schreiben können.

Aus dem Satz von Euler folgt nun, dass die Grundstruktur dieses Verfahrens auf das Rechnen mit Restklassen übertragen werden kann:

Bob verschlüsselt seine Nachricht x gemäß der Formel

y  =  xa mod n.

Aus dem Satz von Euler folgt, dass Alice die Nachricht x gemäß der Formel

x  =  yb mod n

zurückgewinnen kann, wobei die "Inverse von a" nun modulo m berechnet werden muss, d.h.

b  =  a-1 mod m.

Beweis: Erinnern wir uns, dass Alice n und m aus zwei verschiedenen Primzahlen p und q berechnet: n = pq und m = (p - 1)(q - 1).
Zur Entschlüsselung von y berechnet sie die Zahl

yb mod n  =  (xa mod n)b mod n  =  xab mod n.

Nach der Definition von b gilt

ab mod m  =  1,

d.h. es gibt eine positive ganze Zahl k, so dass

ab  =  km + 1.

Die von Alice berechnete Zahl ist daher gleich

xab mod n  =  xkm + 1 mod n,

was nach dem Satz von Euler genau x ist. Damit hat Alice die ursprüngliche Nachricht zurückgewonnen.



Weitere Seiten zur RSA-Verschlüsselung: