Im Bereich der reellen Zahlen
gilt die Identität
(xa)1/a = x. Ist a bekannt und 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. |
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. Beweis: Erinnern wir uns, dass Alice n und m aus zwei verschiedenen Primzahlen p und q berechnet: 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 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. |