Satz von Euler

Version vom 15. November 2026, 07:51 Uhr von Flbkwikiadmin (Diskussion | Beiträge) (Die Seite wurde neu angelegt: „Warum liefert das Entschlüsseln beim RSA-Verfahren wieder den Klartext? Die Antwort gibt ein Satz, den Leonhard Euler im 18. Jahrhundert bewiesen hat. ==Definition== Der '''Satz von Euler''' lautet: Für alle natürlichen Zahlen <math>a</math> und <math>n</math>, die teilerfremd sind, gilt :<math>a^{\varphi(n)} \equiv 1 \pmod{n}</math> Dabei ist <math>\varphi(n)</math> der Wert der eulerschen φ-Funktio…“)
(Unterschied) ← Nächstältere Version | Aktuelle Version (Unterschied) | Nächstjüngere Version → (Unterschied)

Warum liefert das Entschlüsseln beim RSA-Verfahren wieder den Klartext? Die Antwort gibt ein Satz, den Leonhard Euler im 18. Jahrhundert bewiesen hat.

Definition

Der Satz von Euler lautet: Für alle natürlichen Zahlen [math]\displaystyle{ a }[/math] und [math]\displaystyle{ n }[/math], die teilerfremd sind, gilt

[math]\displaystyle{ a^{\varphi(n)} \equiv 1 \pmod{n} }[/math]

Dabei ist [math]\displaystyle{ \varphi(n) }[/math] der Wert der eulerschen φ-Funktion. In Worten: Potenziert man [math]\displaystyle{ a }[/math] mit [math]\displaystyle{ \varphi(n) }[/math], bleibt bei der Division durch [math]\displaystyle{ n }[/math] der Rest 1. Die Schreibweise mit [math]\displaystyle{ \equiv }[/math] erklärt der Artikel Modulo.

Eulersche φ-Funktion

Die eulersche φ-Funktion (gesprochen: Phi-Funktion) gibt zu einer natürlichen Zahl [math]\displaystyle{ n }[/math] an, wie viele der Zahlen von 1 bis [math]\displaystyle{ n }[/math] zu [math]\displaystyle{ n }[/math] teilerfremd sind.

  • Für eine Primzahl [math]\displaystyle{ p }[/math] gilt [math]\displaystyle{ \varphi(p) = p - 1 }[/math], denn alle Zahlen von 1 bis [math]\displaystyle{ p - 1 }[/math] sind zu [math]\displaystyle{ p }[/math] teilerfremd.
  • Für das Produkt zweier verschiedener Primzahlen [math]\displaystyle{ p }[/math] und [math]\displaystyle{ q }[/math] gilt
[math]\displaystyle{ \varphi(p \cdot q) = (p - 1) \cdot (q - 1) }[/math]

Begründung: Von den [math]\displaystyle{ p \cdot q }[/math] Zahlen von 1 bis [math]\displaystyle{ p \cdot q }[/math] sind genau die Vielfachen von [math]\displaystyle{ p }[/math] und die Vielfachen von [math]\displaystyle{ q }[/math] nicht teilerfremd zu [math]\displaystyle{ p \cdot q }[/math]. Es gibt [math]\displaystyle{ q }[/math] Vielfache von [math]\displaystyle{ p }[/math] und [math]\displaystyle{ p }[/math] Vielfache von [math]\displaystyle{ q }[/math]. Die Zahl [math]\displaystyle{ p \cdot q }[/math] selbst gehört zu beiden Gruppen und wurde doppelt gezählt. Übrig bleiben

[math]\displaystyle{ p \cdot q - q - p + 1 = (p - 1) \cdot (q - 1) }[/math]

Zahlen.

Wer [math]\displaystyle{ p }[/math] und [math]\displaystyle{ q }[/math] kennt, berechnet [math]\displaystyle{ \varphi(p \cdot q) }[/math] also mit einer einzigen Multiplikation. Wer nur das Produkt kennt, muss es erst in seine Primfaktoren zerlegen (siehe Primfaktorzerlegung).

Bedeutung für RSA

Beim RSA-Verfahren ist [math]\displaystyle{ N = p \cdot q }[/math], und die Zahlen [math]\displaystyle{ e }[/math] und [math]\displaystyle{ d }[/math] der beiden Schlüssel erfüllen [math]\displaystyle{ e \cdot d \equiv 1 \pmod{\varphi(N)} }[/math]. Es gibt also eine ganze Zahl [math]\displaystyle{ k }[/math] mit

[math]\displaystyle{ e \cdot d = 1 + k \cdot \varphi(N) }[/math]

Verschlüsselt man eine Nachricht [math]\displaystyle{ m }[/math] und entschlüsselt das Ergebnis, wird [math]\displaystyle{ m }[/math] insgesamt mit [math]\displaystyle{ e \cdot d }[/math] potenziert. Mit dem Satz von Euler folgt:

[math]\displaystyle{ m^{e \cdot d} = m^{1 + k \cdot \varphi(N)} = m \cdot \left(m^{\varphi(N)}\right)^k \equiv m \cdot 1^k = m \pmod{N} }[/math]

Das Entschlüsseln liefert also wieder die Nachricht [math]\displaystyle{ m }[/math]. Der Satz von Euler setzt voraus, dass [math]\displaystyle{ m }[/math] und [math]\displaystyle{ N }[/math] teilerfremd sind. Für einen RSA-Modul lässt sich zeigen, dass die Gleichung auch für die übrigen Nachrichten gilt.

Allgemein folgt aus dem Satz: Beim Rechnen modulo [math]\displaystyle{ n }[/math] darf man im Exponenten Vielfache von [math]\displaystyle{ \varphi(n) }[/math] weglassen, solange die Basis zu [math]\displaystyle{ n }[/math] teilerfremd ist.

Beispiele

φ durch Abzählen und mit der Formel bestimmen

  • [math]\displaystyle{ n = 9 }[/math]: Von den Zahlen 1 bis 9 sind 1, 2, 4, 5, 7, 8 zu 9 teilerfremd. Das sind 6 Zahlen, also [math]\displaystyle{ \varphi(9) = 6 }[/math].
  • [math]\displaystyle{ n = 14 = 2 \cdot 7 }[/math]: Hier hilft die Formel für das Produkt zweier Primzahlen: [math]\displaystyle{ \varphi(14) = (2 - 1) \cdot (7 - 1) = 6 }[/math]. Zur Kontrolle: Teilerfremd zu 14 sind 1, 3, 5, 9, 11, 13.

Satz von Euler nachrechnen

  • [math]\displaystyle{ a = 2 }[/math] und [math]\displaystyle{ n = 9 }[/math]: [math]\displaystyle{ 2^{6} = 64 = 7 \cdot 9 + 1 }[/math]
  • [math]\displaystyle{ a = 3 }[/math] und [math]\displaystyle{ n = 14 }[/math]: [math]\displaystyle{ 3^{6} = 729 = 52 \cdot 14 + 1 }[/math]

Großen Exponenten verkleinern

Gesucht ist [math]\displaystyle{ 3^{20} \bmod 14 }[/math]. Wegen [math]\displaystyle{ 3^{6} \equiv 1 \pmod{14} }[/math] darf man im Exponenten Vielfache von 6 weglassen:

[math]\displaystyle{ 3^{20} = 3^{3 \cdot 6 + 2} = (3^{6})^{3} \cdot 3^{2} \equiv 1 \cdot 9 = 9 \pmod{14} }[/math]

Also ist [math]\displaystyle{ 3^{20} \bmod 14 = 9 }[/math].