Kryptologie/Satz von Euler

Einleitung

Der Satz von Euler ist eine Verallgemeinerung des kleinen Satzes von Fermat. Während der kleine Satz von Fermat nur für Primzahlen gilt, kann der Satz von Euler auf beliebige natürliche Zahlen $n$ angewendet werden, die teilerfremd zur Basis $a$ sind. Der Satz von Euler ist der zentrale Satz zum Beweis der Korrektheit des RSA-Kryptosystems. Außerdem werden wir ihn nutzen, um einen weiteren Satz für die Korrektheit des RSA-Kryptosystems zu zeigen, nämlich dem chinesischen Restsatz.

Satz von Euler

Größte gemeinsame Teiler, (Satz 1) Eulersche $\varphi$-Funktion und kleine Satz von Fermat
Größte gemeinsame Teiler
Seien $a,b\in \mathbb {Z}$, wobei mindestens eine der beiden Zahlen ungleich Null. Wir bezeichnen $d:=ggT(a,b)$ mit $d\in \mathbb {N}$ als den größten gemeinsamen Teiler der Zahlen $a$ und $b$, falls gilt: $(1)$: $d\mid a$ und $d\mid b$ und $(2)$: Für alle $c\in \mathbb {Z}$ mit $c\mid a$ und $c\mid b\Rightarrow c\leq d$.
Eulersche $\varphi$-Funktion
Für die eulersche $\varphi$-Funktion gilt: $\varphi (n)\;:=\mid G_{n}\mid$ mit $G_{n}:=\;\{a\in \mathbb {N} \,|\,1\leq a\leq n\land \operatorname {ggT} (a,n)=1\}$.
Satz 1 Eigenschaft der $\varphi$-Funktion bei Primzahlen
Sei $p$ prim, dann gilt: $\varphi (p)=p-1$.
Kleiner Satz von Fermat
Für jede Primzahl $p$ und jede dazu teilerfremde natürliche Zahl $a$ ist folgende Kongruenz erfüllt: $a^{p-1}\equiv 1{\bmod {p}}$.

Seien $a,n\in \mathbb {N}$ und $\operatorname {ggT} (a,n)=1$, dann gilt $a^{\varphi (n)}\equiv 1{\bmod {n}}$.

Bemerkung: Für prime Moduli $p$ gilt nach Satz 1 Eigenschaft der Eulerschen $\varphi$-Funktion bei Primzahlen $\varphi (p)=p-1$, also geht für diese der Satz von Euler in den kleinen Satz von Fermat über.

Beweis Satz von Euler

Teil 1

Wir zeigen zunächst die Aussage: wenn $p$ prim, dann gilt $p\nmid a$ mittels vollständiger Induktion nach $k$.

Bemerkung: Bei der vollständigen Induktion wird eine Aussage in der Regel für alle natürlichen Zahlen bewiesen. Dabei beginnt man bei einem Startwert (meist $0$ oder $1$) und zeigt, dass die Aussage für diesen Startwert gilt. Man nennt dies den Induktionsanfang. Anschließend wird während des Induktionsschritts gezeigt, dass wenn die Aussage für eine Zahl gilt, dann gilt sie auch für die nächstgrößere Zahl.

Seien $p$ prim und $p\nmid a$, dann soll gelten

$a^{\varphi (p^{k})}\equiv 1{\bmod {p}}^{k}$ für $k\in \mathbb {N} ^{+}$.

Eulersche $\varphi$-Funktion, Kongruenz, wichtige Sätze und der Binomialkoeffizient
Eulersche $\varphi$-Funktion
Für die eulersche $\varphi$-Funktion gilt: $\varphi (n)\;:=\mid G_{n}\mid$ mit $G_{n}:=\;\{a\in \mathbb {N} \,|\,1\leq a\leq n\land \operatorname {ggT} (a,n)=1\}$.
Kongruenz
Seien $a,b\in \mathbb {Z}$ und $m\in \mathbb {N}$, dann gilt $a\equiv b{\bmod {m}}\Leftrightarrow m\mid (a-b)$.
Satz 1 Eigenschaft der $\varphi$-Funktion bei Primzahlen
Sei $p$ prim, dann gilt: $\varphi (p)=p-1$.
Kleiner Satz von Fermat
Für jede Primzahl $p$ und jede dazu teilerfremde natürliche Zahl $a$ ist folgende Kongruenz erfüllt: $a^{p-1}\equiv 1{\bmod {p}}$.
Satz 3 Eigenschaft der $\varphi$-Funktion bei Primzahlen
Seien $p$ prim und $k\in \mathbb {N}$ mit $k>0$, dann gilt: $\varphi (p^{k})=p^{k}\left(1-{\frac {1}{p}}\right)$.
Binomischer Lehrsatz
Für alle Elemente $x$ und $y$ eines kommutativen monoiden Rings und für alle natürlichen Zahlen $n\in \mathbb {N}$ gilt die Gleichung $(x+y)^{n}=\sum _{k=0}^{n}{\binom {n}{k}}x^{n-k}y^{k}\quad (1)$.
Binomialkoeffizient
Seien $n,k\in \mathbb {N}$, dann gilt: ${\binom {n}{k}}={\frac {n\cdot (n-1)\dotsm (n-k+1)}{1\cdot 2\dotsm k}}={\frac {n!}{(n-k)!\cdot {k!}}}$

Wir zeigen nun durch vollständige Induktion, dass die Kongruenz $a^{\varphi (p^{k})}\equiv 1{\bmod {p}}^{k}$ korrekt ist.

Induktionsanfang

Wir beginnen mit $k=1$.

$a^{\varphi (p^{k})}\equiv 1{\bmod {p}}^{k}$

$\Leftrightarrow a^{\varphi (p)}\equiv 1{\bmod {p}}$, für $k=1$

$\Leftrightarrow a^{p-1}\equiv 1{\bmod {p}}$, nach Satz 1 der Eigenschaft für $\varphi$-Funktionen $p-1=\varphi (p)$

Dies ist genau der kleine Satz von Fermat, welchen wir bereits bewiesen haben.

Induktionsvoraussetzung

Wir nehmen an, dass $a^{\varphi (p^{k})}\equiv 1{\bmod {p}}^{k}$ für ein festes $k\in \mathbb {N}$ mit $k>0$ gilt.

Induktionsbehauptung

Wir wollen zeigen, dass $a^{\varphi (p^{k+1})}\equiv 1{\bmod {p}}^{k+1}$ gilt.

Induktionsschritt

Nach der Kongruenz gilt folgende Äquivalenz der Induktionsvoraussetzung:

$a^{\varphi (p^{k})}\equiv 1{\bmod {p}}^{k}\Leftrightarrow a^{\varphi (p^{k})}=x\cdot p^{k}+1$ mit $x\in \mathbb {Z}$ und Satz 3 der eulerschen $\varphi$-Funktion gilt $\varphi (p^{k})=p^{k}\left(1-{\frac {1}{p}}\right)$.

Für $p^{k+1}$ folgt unter erneuter Verwendung von Satz 3 der eulerschen $\varphi$-Funktion

$\varphi (p^{k+1})=p^{k+1}\left(1-{\frac {1}{p}}\right)=p\cdot \varphi (p^{k})$.

Wir können $a^{\varphi (p^{k+1})}$ nun umschreiben:

$a^{\varphi (p^{k+1})}$

$=a^{p\varphi (p^{k})}\quad$, da $\varphi (p^{k+1})=p\cdot \varphi (p^{k})$

$=a^{\varphi (p^{k})^{p}}\quad$

$=(1+x\cdot p^{k})^{p}\quad$, nach $a^{\varphi (p^{k+1})}=x\cdot p^{k}+1$

Nun kann man den binomischen Lehrsatz anwenden, da es sich bei dem Restklassenring $(\mathbb {Z} /m\mathbb {Z} ,\oplus ,\odot )$ um einen kommutativen Ring handelt, wobei $(\mathbb {Z} /m\mathbb {Z} ,\odot )$ ein Monoid ist (siehe Lernaufgabe).

Also

$(1+x\cdot p^{k})^{p}=1+{\binom {p}{1}}(xp^{k})+{\binom {p}{2}}(xp^{k})^{2}+\dots +{\binom {p}{p-1}}(xp^{k})^{p-1}+(qp^{k})^{p}$

Betrachten wir nun die Summen

${\binom {p}{2}}(xp^{k})^{2}+\dots +{\binom {p}{p-1}}(xp^{k})^{p-1}+(qp^{k})^{p}$, ${\binom {p}{1}}(xp^{k})$ und $1$ getrennt voneinander.

Es gilt

${\binom {p}{2}}(xp^{k})^{2}+\dots +{\binom {p}{p-1}}(xp^{k})^{p-1}+(qp^{k})^{p}\equiv 0{\bmod {p}}^{k+1}$, da jeder der Summanden aus einem Faktoren $(xp^{k})^{i}$ mit $i\in \{2,3,...p\}$ und einem Binomialkoeffizienten besteht und der Faktor $(xp^{k})^{i}$ immer von $p^{k+1}$ teilbar ist und lediglich mit einer natürlichen Zahl (dem zugehörigen Binomialkoeffizienten) multipliziert wird.

Wir müssen nun also nur noch die beiden Summanden ${\binom {p}{1}}(xp^{k})$ und $1$ betrachten.

Da ${\binom {p}{1}}=\left({\frac {p!}{(p-1)!\cdot 1!}}\right)=p$, ist ${\binom {p}{1}}(xp^{k})=xp^{k+1}$ .

Es gilt: $p^{k+1}\mid qp^{k+1}$.

Wir wissen nun also, dass

${\binom {p}{1}}(xp^{k})+{\binom {p}{2}}(xp^{k})^{2}+\dots +{\binom {p}{p-1}}(xp^{k})^{p-1}+(qp^{k})^{p}\equiv 0{\bmod {p}}^{k+1}$

und nach hinzufügen des Summanden $1$:

$1+{\binom {p}{1}}(xp^{k})+{\binom {p}{2}}(xp^{k})^{2}+\dots +{\binom {p}{p-1}}(xp^{k})^{p-1}+(qp^{k})^{p}\equiv 1{\bmod {p}}^{k+1}$.

Wir haben also gezeigt, dass gilt:

$a^{\varphi (p^{k+1})}\equiv 1{\bmod {p}}^{k+1}$

und die vollständige Induktion ist abgeschlossen.

Primfaktorzerlegung, Teilerfremdheit, (Multiplikativität für Primzahlen der) Eulersche $\varphi$-Funktion und Folgerung aus Lemma 4 des $ggT$
Primfaktorzerlegung
Sei $n\in \mathbb {N}$ mit $n>1$, dann ist $n$ als Produkt von Primzahlen darstellbar und wir nennen diese Primfaktorzerlegung. Es gilt $n=p_{1}\cdot p_{2}\cdot \dots \cdot p_{i}$mit $i\in \mathbb {N}$. Die Darstellung ist, abgesehen von der Reihenfolge der Faktoren, eindeutig.
Teilerfremdheit
Zwei ganze Zahlen $a$ und $b$, wobei mindestens einer der beiden Zahlen ungleich Null ist, heißen teilerfremd, wenn $ggT(a,b)=1$. Betrachten wir mehr als zwei Zahlen, dann nennen wir diese paarweise teilerfremd, wenn je zwei beliebige von diesen Zahlen zueinander teilerfremd sind.
Eulersche $\varphi$-Funktion
Für die eulersche $\varphi$-Funktion gilt: $\varphi (n)\;:=\mid G_{n}\mid$ mit $G_{n}:=\;\{a\in \mathbb {N} \,|\,1\leq a\leq n\land \operatorname {ggT} (a,n)=1\}$.
Multiplikativität der eulerschen $\varphi$-Funktion für Primzahlen
Seien $p$ und $q$ prim und $p\neq q$, dann gilt $\varphi (p\cdot q)=\varphi (p)\cdot \varphi (q)$.
Folgerung aus Lemma 4 des $ggT$
Gilt $a\mid c$ und $b\mid c$ mit $ggT(a,b)=1$, dann folgt $ab\mid c$.

Teil 2

Nun wählen wir eine Zahl $n\in N$ mit $ggT(a,n)=1$ und folgender Primfaktorzerlegung:

$n=p_{1}^{k_{1}}\cdot p_{2}^{k_{2}}\cdot ...\cdot p_{s}^{k_{s}}$.

Da $a$ und $n$ teilerfremd sind, kann auch keiner der Primfaktoren $p_{j}$ mit $j\in \{1,2,\dots ,s\}$ ein Teiler von $a$ sein.

Wir erhalten die Kongruenz:

$a^{\varphi (p_{j}^{k_{j}})}\equiv 1{\bmod {p}}_{j}^{k_{j}}$ mit $j\in \{1,2,\dots ,s\}$.

Nun nutzen wir die Multiplikativität der eulerschen $\varphi$-Funktion:

$\varphi (n)=\varphi (p_{1}^{k_{1}})\cdot \varphi (p_{2}^{k_{2}})\cdot ...\cdot \varphi (p_{s}^{k_{s}})$, also ist jeder Faktor $\varphi (p_{j}^{k_{j}})$ ein Teiler von $\varphi (n)$.

Daher gilt nicht nur $a^{\varphi (p_{j}^{k_{j}})}\equiv 1{\bmod {p}}_{j}^{k_{j}}$, sondern auch

$a^{\varphi (n)}\equiv 1{\bmod {p}}_{j}^{k_{j}}$ mit $j\in \{1,2,\dots ,s\}$.

Da die Primfaktorpotenzen $p_{j}^{k_{j}}$ paarweise teilerfremd sind, gilt nach der Folgerung aus Lemma 4 des ggT :

$a^{\varphi (n)}\equiv 1{\bmod {p}}_{1}^{k_{1}}p_{2}^{k_{2}}\cdots p_{s}^{k_{s}}$,

und da

$n=p_{1}^{k_{1}}\cdot p_{2}^{k_{2}}\cdot ...\cdot p_{s}^{k_{s}}$

die Primfaktorzerlegung von $n$ ist, gilt

$a^{\varphi (n)}\equiv 1{\bmod {n}}$.

Wir haben somit den Satz von Euler bewiesen■

Lernempfehlung

Kursübersicht

Übergeordnete Lerneinheit
8: Korrektheit des RSA-Verschlüsselungsverfahrens
Vorherige Lerneinheit	Aktuelle Lerneinheit	Empfohlene Lerneinheit
8: Korrektheit des RSA-Verschlüsselungsverfahrens	8.1: Satz von Euler	8.2: Chinesischer Restsatz