Kryptologie/Eulersche φ-Funktion

Um den Entschlüsselungsexponenten ${\displaystyle d}$ zum Verschlüsselungsexponenten ${\displaystyle e}$ zu berechnen, betrachten wir beim RSA-Verschlüsselungsverfahren die Kongruenz ${\displaystyle e\cdot d\equiv 1{\bmod {\varphi (N)}}}$. Diese können wir mit dem erweiterten euklidischen Algorithmus lösen und ${\displaystyle d}$ als das multiplikative Inverse zu ${\displaystyle e}$ berechnen^[1]. Bevor wir dies jedoch können, müssen wir die eulersche ${\displaystyle \varphi }$-Funktion definieren.

Teilerfremdheit
Teilerfremdheit
Zwei ganze Zahlen ${\displaystyle a}$ und ${\displaystyle b}$, wobei mindestens einer der beiden Zahlen ungleich Null ist, heißen teilerfremd, wenn ${\displaystyle ggT(a,b)=1}$[2]. Betrachten wir mehr als zwei Zahlen, dann nennen wir diese paarweise teilerfremd, wenn je zwei beliebige von diesen Zahlen zueinander teilerfremd sind[3][2].

Die eulersche ${\displaystyle \varphi }$-Funktion (ausgesprochen "eulersche Phi-Funktion") gibt für jede positive natürliche Zahl ${\displaystyle n}$ an, wie viele zu ${\displaystyle n}$ teilerfremde natürliche Zahlen es gibt, die nicht größer als ${\displaystyle n}$ sind^[4][5]. Formal bedeutet dies:

${\displaystyle \varphi (n)\;:=\mid G_{n}\mid }$^[6][5] mit ${\displaystyle G_{n}:=\;\{a\in \mathbb {N} \,|\,1\leq a\leq n\land \operatorname {ggT} (a,n)=1\}}$^[4][5].

Beispiel ${\displaystyle n=1}$

Die Zahl ${\displaystyle n=1}$ hat genau ${\displaystyle 1}$ teilerfremde natürliche Zahlen, die nicht größer als ${\displaystyle 1}$ ist, da ${\displaystyle ggT(1,1)=1}$.

Es gilt also ${\displaystyle \varphi (1)=\mid G_{1}\mid =1}$.

Beispiel ${\displaystyle n=4}$

Die Zahl ${\displaystyle n=4}$ hat genau ${\displaystyle 2}$ teilerfremde natürliche Zahlen, die nicht größer als ${\displaystyle 4}$ sind, da ${\displaystyle ggT(1,4)=1}$, ${\displaystyle ggT(2,4)=2}$, ${\displaystyle ggT(3,4)=1}$ und ${\displaystyle ggT(4,4)=4}$.

Es gilt also ${\displaystyle \varphi (4)=\mid G_{4}\mid =2}$.

Beispiel ${\displaystyle n=7}$

Die Zahl ${\displaystyle n=7}$ hat genau ${\displaystyle 6}$ teilerfremde natürliche Zahlen, die nicht größer als ${\displaystyle 7}$ sind, da ${\displaystyle ggT(1,7)=1}$, ${\displaystyle ggT(2,7)=1}$, ${\displaystyle ggT(3,7)=1}$, ${\displaystyle ggT(4,7)=1}$, ${\displaystyle ggT(5,7)=1}$, ${\displaystyle ggT(6,7)=1}$ und ${\displaystyle ggT(7,7)=7}$.

Es gilt also ${\displaystyle \varphi (7)=\mid G_{7}\mid =6}$.

Für das RSA-Kryptosystem benötigen wir drei Eigenschaften der eulerschen ${\displaystyle \varphi }$-Funktion.

Sei ${\displaystyle p}$ prim, dann gilt: ${\displaystyle \varphi (p)=p-1}$^[4][7].

Primzahl, Menge ${\displaystyle G_{n}}$ und Primfaktorzerlegung
Primzahl
Sei ${\displaystyle p\in \mathbb {N} }$ mit ${\displaystyle p>1}$, dann heißt ${\displaystyle p}$ Primzahl oder prime Zahl, wenn gilt: ${\displaystyle p}$ besitzt nur zwei Teiler in ${\displaystyle \mathbb {N} }$, nämlich ${\displaystyle 1}$ und ${\displaystyle p}$. Andernfalls heißt ${\displaystyle p}$ zusammengesetzte Zahl[8].
Menge ${\displaystyle G_{n}}$
Sei ${\displaystyle n\in \mathbb {N} }$, dann gilt ${\displaystyle G_{n}:=\;\{a\in \mathbb {N} \,|\,1\leq a\leq n\land \operatorname {ggT} (a,n)=1\}}$[4][5].
Primfaktorzerlegung
Sei ${\displaystyle n\in \mathbb {N} }$ mit ${\displaystyle n>1}$, dann ist ${\displaystyle n}$ als Produkt von Primzahlen darstellbar und wir nennen diese Primfaktorzerlegung. Es gilt ${\displaystyle n=p_{1}\cdot p_{2}\cdot \dots \cdot p_{i}}$mit ${\displaystyle i\in \mathbb {N} }$. Die Darstellung ist, abgesehen von der Reihenfolge der Faktoren, eindeutig[9].

Voraussetzung

${\displaystyle p}$ ist prim

Zu zeigen

${\displaystyle \varphi {(p)}=p-1}$

Beweis

Wir betrachten die Menge ${\displaystyle G_{p}}$.

Wir wissen, dass nach Definition der Menge ${\displaystyle G_{p}}$

${\displaystyle G_{p}:=\;\{a\in \mathbb {N} \,|\,1\leq a\leq p\land \operatorname {ggT} (a,p)=1\}}$.

Demnach ist ${\displaystyle 1\leq a\leq p}$ und somit die Anzahl der Elementen in ${\displaystyle G_{p}}$ höchstens ${\displaystyle p}$.

Um die Anzahl der Elemente genau zu bestimmen, untersuchen wir die möglichen Elemente der Menge in Hinblick auf die zweite Voraussetzung der Menge. Diese lautet ${\displaystyle ggT(a,p)=1}$.

Für ${\displaystyle a=1}$ gilt ${\displaystyle ggT(1,p)=1}$, da ${\displaystyle 1\mid 1}$ und ${\displaystyle 1\mid p}$ und es keine weitere Zahl ${\displaystyle d\in \mathbb {N} }$ gibt, für die gilt ${\displaystyle d\mid 1}$.

Für ${\displaystyle a=p}$ gilt ${\displaystyle ggT(p,p)=p\neq 1}$ und da ${\displaystyle 1}$ nicht prim. Es folgt ${\displaystyle p\not \in G_{n}}$.

Für ${\displaystyle 1<a<p}$ gilt ${\displaystyle ggT(a,p)=1}$, denn sonst wäre ${\displaystyle p}$ keine Primzahl und hätte den Teiler ${\displaystyle a}$ mit ${\displaystyle a\mid p}$ und ${\displaystyle 1<a<p}$.

Insgesamt gilt also ${\displaystyle G_{p}=\{1,2,...,p-1\}}$ und ${\displaystyle \mid G_{p}\mid =\varphi (p)=p-1}$■^[6][10]

Seien ${\displaystyle p}$ und ${\displaystyle q}$ prim und ${\displaystyle p\neq q}$, dann gilt ${\displaystyle \varphi (p\cdot q)=\varphi (p)\cdot \varphi (q)}$^[6][7].

Beweis Multiplikativität von ${\displaystyle \varphi }$ für Primzahlen

Primzahl, Menge ${\displaystyle G_{n}}$, Primfaktorzerlegung und Teilerfremdheit
Primzahl
Sei ${\displaystyle p\in \mathbb {N} }$ mit ${\displaystyle p>1}$, dann heißt ${\displaystyle p}$ Primzahl oder prime Zahl, wenn gilt: ${\displaystyle p}$ besitzt nur zwei Teiler in ${\displaystyle \mathbb {N} }$, nämlich ${\displaystyle 1}$ und ${\displaystyle p}$. Andernfalls heißt ${\displaystyle p}$ zusammengesetzte Zahl[8].
Menge ${\displaystyle G_{n}}$
Sei ${\displaystyle n\in \mathbb {N} }$, dann gilt ${\displaystyle G_{n}:=\;\{a\in \mathbb {N} \,|\,1\leq a\leq n\land \operatorname {ggT} (a,n)=1\}}$[4][5].
Primfaktorzerlegung
Sei ${\displaystyle n\in \mathbb {N} }$ mit ${\displaystyle n>1}$, dann ist ${\displaystyle n}$ als Produkt von Primzahlen darstellbar und wir nennen diese Primfaktorzerlegung. Es gilt ${\displaystyle n=p_{1}\cdot p_{2}\cdot \dots \cdot p_{i}}$mit ${\displaystyle i\in \mathbb {N} }$. Die Darstellung ist, abgesehen von der Reihenfolge der Faktoren, eindeutig[9].
Teilerfremdheit
Zwei ganze Zahlen ${\displaystyle a}$ und ${\displaystyle b}$, wobei mindestens einer der beiden Zahlen ungleich Null ist, heißen teilerfremd, wenn ${\displaystyle ggT(a,b)=1}$[2]. Betrachten wir mehr als zwei Zahlen, dann nennen wir diese paarweise teilerfremd, wenn je zwei beliebige von diesen Zahlen zueinander teilerfremd sind[3][2].

Voraussetzung

Seien ${\displaystyle p}$ und ${\displaystyle q}$ prim und ${\displaystyle p\neq q}$

Zu zeigen

${\displaystyle \varphi (p\cdot q)=\varphi (p)\cdot \varphi (q)}$

Beweis

Betrachten wir die Menge ${\displaystyle G_{pq}}$.

Wir wissen, dass nach der Definition der Menge ${\displaystyle G_{pq}}$ gilt${\displaystyle G_{pq}:=\;\{a\in \mathbb {N} \,|\,1\leq a\leq pq\land \operatorname {ggT} (a,pq)=1\}}$.

In ${\displaystyle G_{pq}}$ können nur die Elemente ${\displaystyle {1,...,pq-1,pq}}$ also ${\displaystyle pq}$ Elemente enthalten sein. Es gilt ${\displaystyle \vert G_{pq}\vert \leq pq}$.

Nun schließen wir aus dieser Menge Elemente aus, die nicht in ${\displaystyle G_{pq}}$ enthalten sein können.

Es gilt ${\displaystyle pq\notin G_{pq}}$, da ${\displaystyle ggT(pq,pq)=pg\neq 1}$.

Wir definieren eine neue Menge ${\displaystyle M_{pq}}$ mit den übrigen Elementen, also ${\displaystyle M_{pq}=\{1,2,\dots ,pq-1\}}$ und ${\displaystyle \vert M_{pq}\vert =pq-1}$.

Wir betrachten alle Zahlen, die nicht-teilerfremd zu ${\displaystyle pq}$ sind.

${\displaystyle 1\cdot p,2\cdot p,...,(q-1)p}$, also sind ${\displaystyle q-1}$ Zahlen nicht-teilerfremde Zahlen zu ${\displaystyle p}$ aus ${\displaystyle M_{pq}}$.

${\displaystyle 1\cdot q,2\cdot q,...,(p-1)q}$, also sind ${\displaystyle p-1}$ Zahlen nicht teilerfremde Zahlen zu ${\displaystyle q}$ aus ${\displaystyle M_{pq}}$.

Da die Primfaktorzerlegung eindeutig ist, kommt keine Zahl doppelt vor.

Damit folgt für die Anzahl der Elemente in

${\displaystyle \vert G_{pq}\vert }$

${\displaystyle =\vert M_{pq}\vert -(q-1)-(p-1)}$

${\displaystyle =pq-1-(q-1)-(p-1)}$, da ${\displaystyle \vert M_{pq}\vert =pq-1}$

${\displaystyle =pq-1-q+1-p+1}$

${\displaystyle =pq-q-p+1}$

${\displaystyle =q(p-1)-p+1}$

${\displaystyle =q(p-1)-(p-1)}$

${\displaystyle =(p-1)(q-1)}$■^[6][7]

Wir wählen die Primzahlen ${\displaystyle p=11}$ und ${\displaystyle q=13}$ aus dem Beispiel der Schlüsselerzeugung.

Somit ist ${\displaystyle N=11\cdot 13=143}$.

${\displaystyle \varphi (143)=\varphi (11\cdot 13)=(11-1)\cdot (13-1)=10\cdot 12=120}$.

Primzahl, Menge ${\displaystyle G_{n}}$ und Teilerfremdheit
Primzahl
Sei ${\displaystyle p\in \mathbb {N} }$ mit ${\displaystyle p>1}$, dann heißt ${\displaystyle p}$ Primzahl oder prime Zahl, wenn gilt: ${\displaystyle p}$ besitzt nur zwei Teiler in ${\displaystyle \mathbb {N} }$, nämlich ${\displaystyle 1}$ und ${\displaystyle p}$. Andernfalls heißt ${\displaystyle p}$ zusammengesetzte Zahl[8].
Menge ${\displaystyle G_{n}}$
Sei ${\displaystyle n\in \mathbb {N} }$, dann gilt ${\displaystyle G_{n}:=\;\{a\in \mathbb {N} \,|\,1\leq a\leq n\land \operatorname {ggT} (a,n)=1\}}$[4][5].
Teilerfremdheit
Zwei ganze Zahlen ${\displaystyle a}$ und ${\displaystyle b}$, wobei mindestens einer der beiden Zahlen ungleich Null ist, heißen teilerfremd, wenn ${\displaystyle ggT(a,b)=1}$[2]. Betrachten wir mehr als zwei Zahlen, dann nennen wir diese paarweise teilerfremd, wenn je zwei beliebige von diesen Zahlen zueinander teilerfremd sind[3][2].

Seien ${\displaystyle p}$ prim und ${\displaystyle k\in \mathbb {N} }$ mit ${\displaystyle k>0}$, dann gilt:

${\displaystyle \varphi (p^{k})=p^{k}\left(1-{\frac {1}{p}}\right)}$^[4][7].

Voraussetzung

Seien ${\displaystyle p}$ prim und ${\displaystyle k\in \mathbb {N} }$ mit ${\displaystyle k>0}$

Zu zeigen

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

Beweis

Betrachten wir die Zahlen ${\displaystyle 1,2,\dots ,p^{k}}$.

Nach Definition der Menge ${\displaystyle G_{p^{k}}}$ sind genau die Zahlen ${\displaystyle 1\leq x\leq p^{k}}$, für die gilt ${\displaystyle ggT(x,p^{k})=1}$ Elemente der Menge ${\displaystyle G_{p^{k}}}$.

Wir können nun also alle Zahlen ${\displaystyle 1\leq x\leq p^{k}}$ bestimmen, für die dies nicht zutrifft und deren Anzahl von der Mächtigkeit von ${\displaystyle \{1,2,\dots ,p^{k}\}}$ abziehen.

Da ${\displaystyle p^{k}}$ ein um ${\displaystyle k}$ Vielfaches der Primzahl ${\displaystyle p}$ ist, hat ${\displaystyle p^{k}}$ genau ${\displaystyle p^{k-1}}$ nicht zu ${\displaystyle p^{k}}$ teilerfremde Zahlen ${\displaystyle x}$ mit ${\displaystyle 1\leq x\leq p^{k}}$.

Diese sind nämlich: ${\displaystyle p,2p,\dots ,p\cdot p^{k-1}}$.

Es gilt also
${\displaystyle \varphi (p^{k})}$

${\displaystyle =p^{k}-p^{k-1}}$

${\displaystyle =p^{k-1}(p-1)}$

${\displaystyle =p^{k}\left(1-{\frac {1}{p}}\right)}$■^[7]

Beweisen Sie die Folgerung aus Satz 1.

Für ${\displaystyle N=p\cdot q}$ mit ${\displaystyle p,q}$ prim folgt ${\displaystyle \varphi (N)=(p-1)\cdot (q-1)}$^[11].

1. ↑ Rivest, R. L., Shamir, A., & Adleman, L. (1978). A method for obtaining digital signatures and public-key cryptosystems. Communications of the ACM, 21(2) (S. 120–126). S. 122f.
2. ↑ ^{a b c d e f} Burton, D. M., & Dalkowski, H. (2005). Handbuch der elementaren Zahlentheorie mit über 1000 Übungsaufgaben und ihren Lösungen. Heldermann Verlag. S. 26.
3. ↑ ^{a b c} Seite „Teilerfremdheit“. In: Wikipedia, Die freie Enzyklopädie. Bearbeitungsstand: 26. September 2019, 13:33 UTC. URL: https://de.wikipedia.org/w/index.php?title=Teilerfremdheit&oldid=192615323 (Abgerufen: 10. Januar 2020, 13:56 UTC; Formulierung verändert)
4. ↑ ^{a b c d e f g} Seite „Eulersche Phi-Funktion“. In: Wikipedia, Die freie Enzyklopädie. Bearbeitungsstand: 24. August 2019, 16:52 UTC. URL: https://de.wikipedia.org/w/index.php?title=Eulersche_Phi-Funktion&oldid=191644019 (Abgerufen: 7. Januar 2020, 09:45 UTC; Formulierung verändert)
5. ↑ ^{a b c d e f} Stroth, G., & Waldecker, R. (2019). Elementare Algebra und Zahlentheorie (2. Aufl.). Birkhäuser Basel. S. 77.
6. ↑ ^{a b c d} Kryptologie - Mathematische Vertiefung (PH Freiburg SS 2017). (5. Dezember 2019). Wikiversity, . Abgerufen am 8. Januar 2020, 12:14 von https://de.wikiversity.org/w/index.php?title=Kryptologie_-_Mathematische_Vertiefung_(PH_Freiburg_SS_2017)&oldid=605650. (Formulierung verändert)
7. ↑ ^{a b c d e f} Wätjen, D. (2018). Kryptographie: Grundlagen, Algorithmen, Protokolle. Springer-Verlag. S. 42.
8. ↑ ^{a b c} Burton, D. M., & Dalkowski, H. (2005). Handbuch der elementaren Zahlentheorie mit über 1000 Übungsaufgaben und ihren Lösungen. Lemgo: Heldermann Verlag. S. 47.
9. ↑ ^{a b} Ziegenbalg, J. (2015). Elementare Zahlentheorie: Beispiele, Geschichte, Algorithmen (2., überarb. Aufl). Springer Spektrum. S. 66.
10. ↑ Burton, D. M., & Dalkowski, H. (2005). Handbuch der elementaren Zahlentheorie mit über 1000 Übungsaufgaben und ihren Lösungen. Lemgo: Heldermann Verlag. S. 145.
11. ↑ Rivest, R. L., Shamir, A., & Adleman, L. (1978). A method for obtaining digital signatures and public-key cryptosystems. Communications of the ACM, 21(2) (S. 120–126). S. 123.