Kryptologie/Eulersche φ-Funktion

Einleitung

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

Eulersche φ-Funktion

Definition Eulersche φ-Funktion

Teilerfremdheit
Teilerfremdheit
Zwei ganze Zahlen $a$ und $b$ , wobei mindestens einer der beiden Zahlen ungleich Null ist, heißen teilerfremd, wenn $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 $\varphi$ -Funktion (ausgesprochen "eulersche Phi-Funktion") gibt für jede positive natürliche Zahl $n$ an, wie viele zu $n$ teilerfremde natürliche Zahlen es gibt, die nicht größer als $n$ sind^[4]^[5]. Formal bedeutet dies:

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

Beispiel Eulersche φ-Funktion

Beispiel $n=1$

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

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

Beispiel $n=4$

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

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

Beispiel $n=7$

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

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

Eigenschaften Eulersche φ-Funktion

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

Satz 1 Eigenschaft der $\varphi$ -Funktion bei Primzahlen

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

Beweis Eigenschaft der $\varphi (p)$ -Funktion bei Primzahlen

Primzahl, Menge $G_{n}$ und Primfaktorzerlegung
Primzahl
Sei $p\in \mathbb {N}$ mit $p>1$ , dann heißt $p$ Primzahl oder prime Zahl, wenn gilt: $p$ besitzt nur zwei Teiler in $\mathbb {N}$ , nämlich $1$ und $p$ . Andernfalls heißt $p$ zusammengesetzte Zahl^[8].
Menge $G_{n}$
Sei $n\in \mathbb {N}$ , dann gilt $G_{n}:=\;\{a\in \mathbb {N} \,\|\,1\leq a\leq n\land \operatorname {ggT} (a,n)=1\}$ ^[4]^[5].
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^[9].

Voraussetzung

$p$ ist prim

Zu zeigen

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

Beweis

Wir betrachten die Menge $G_{p}$ .

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

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

Demnach ist $1\leq a\leq p$ und somit die Anzahl der Elementen in $G_{p}$ höchstens $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 $ggT(a,p)=1$ .

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

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

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

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

Satz 2 Multiplikativität von $\varphi$ für Primzahlen

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

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

Primzahl, Menge $G_{n}$ , Primfaktorzerlegung und Teilerfremdheit
Primzahl
Sei $p\in \mathbb {N}$ mit $p>1$ , dann heißt $p$ Primzahl oder prime Zahl, wenn gilt: $p$ besitzt nur zwei Teiler in $\mathbb {N}$ , nämlich $1$ und $p$ . Andernfalls heißt $p$ zusammengesetzte Zahl^[8].
Menge $G_{n}$
Sei $n\in \mathbb {N}$ , dann gilt $G_{n}:=\;\{a\in \mathbb {N} \,\|\,1\leq a\leq n\land \operatorname {ggT} (a,n)=1\}$ ^[4]^[5].
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^[9].
Teilerfremdheit
Zwei ganze Zahlen $a$ und $b$ , wobei mindestens einer der beiden Zahlen ungleich Null ist, heißen teilerfremd, wenn $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 $p$ und $q$ prim und $p\neq q$

Zu zeigen

$\varphi (p\cdot q)=\varphi (p)\cdot \varphi (q)$

Beweis

Betrachten wir die Menge $G_{pq}$ .

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

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

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

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

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

Wir betrachten alle Zahlen, die nicht-teilerfremd zu $pq$ sind.

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

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

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

Damit folgt für die Anzahl der Elemente in

$\vert G_{pq}\vert$

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

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

$=pq-1-q+1-p+1$

$=pq-q-p+1$

$=q(p-1)-p+1$

$=q(p-1)-(p-1)$

$=(p-1)(q-1)$ ■^[6]^[7]

Beispiel

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

Somit ist $N=11\cdot 13=143$ .

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

Satz 3 Eigenschaft der $\varphi$ -Funktion bei Primzahlen

Primzahl, Menge $G_{n}$ und Teilerfremdheit
Primzahl
Sei $p\in \mathbb {N}$ mit $p>1$ , dann heißt $p$ Primzahl oder prime Zahl, wenn gilt: $p$ besitzt nur zwei Teiler in $\mathbb {N}$ , nämlich $1$ und $p$ . Andernfalls heißt $p$ zusammengesetzte Zahl^[8].
Menge $G_{n}$
Sei $n\in \mathbb {N}$ , dann gilt $G_{n}:=\;\{a\in \mathbb {N} \,\|\,1\leq a\leq n\land \operatorname {ggT} (a,n)=1\}$ ^[4]^[5].
Teilerfremdheit
Zwei ganze Zahlen $a$ und $b$ , wobei mindestens einer der beiden Zahlen ungleich Null ist, heißen teilerfremd, wenn $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 $p$ prim und $k\in \mathbb {N}$ mit $k>0$ , dann gilt:

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

Beweis Satz 3

Voraussetzung

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

Zu zeigen

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

Beweis

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

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

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

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

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

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

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

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

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

Lernaufgabe

Aufgabe

Beweisen Sie die Folgerung aus Satz 1.

Folgerung

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

Lösung

Voraussetzungen

$N=p\cdot q$ .

Zu zeigen

$\varphi (N)=(p-1)\cdot (q-1)$

Beweis

$\varphi (N)$

$=\varphi (p\cdot q)$ , nach Voraussetzung,

$=\varphi (p)\cdot \varphi (q)$ , aufgrund der Multiplikativität von $\varphi$

$=(p-1)\cdot (q-1)$ , Eigenschaft der $\varphi (p)$ -Funktion bei Primzahlen■^[7]

Lernempfehlung

Kursübersicht
Übergeordnete Lerneinheit
7.1: Schlüsselerzeugung des RSA-Verschlüsselungsverfahrens
Vorherige Lerneinheit	Aktuelle Lerneinheit	Empfohlene Lerneinheit
7.1.5: Erweiterter euklidischer Algorithmus	7.1.6: Eulersche φ-Funktion	7.1: Schlüsselerzeugung des RSA-Verschlüsselungsverfahrens

Literatur

↑ 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,0 ^2,1 ^2,2 ^2,3 ^2,4 ^2,5 Burton, D. M., & Dalkowski, H. (2005). Handbuch der elementaren Zahlentheorie mit über 1000 Übungsaufgaben und ihren Lösungen. Heldermann Verlag. S. 26.
↑ ^3,0 ^3,1 ^3,2 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,0 ^4,1 ^4,2 ^4,3 ^4,4 ^4,5 ^4,6 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,0 ^5,1 ^5,2 ^5,3 ^5,4 ^5,5 Stroth, G., & Waldecker, R. (2019). Elementare Algebra und Zahlentheorie (2. Aufl.). Birkhäuser Basel. S. 77.
↑ ^6,0 ^6,1 ^6,2 ^6,3 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,0 ^7,1 ^7,2 ^7,3 ^7,4 ^7,5 Wätjen, D. (2018). Kryptographie: Grundlagen, Algorithmen, Protokolle. Springer-Verlag. S. 42.
↑ ^8,0 ^8,1 ^8,2 Burton, D. M., & Dalkowski, H. (2005). Handbuch der elementaren Zahlentheorie mit über 1000 Übungsaufgaben und ihren Lösungen. Lemgo: Heldermann Verlag. S. 47.
↑ ^9,0 ^9,1 Ziegenbalg, J. (2015). Elementare Zahlentheorie: Beispiele, Geschichte, Algorithmen (2., überarb. Aufl). Springer Spektrum. S. 66.
↑ Burton, D. M., & Dalkowski, H. (2005). Handbuch der elementaren Zahlentheorie mit über 1000 Übungsaufgaben und ihren Lösungen. Lemgo: Heldermann Verlag. S. 145.
↑ 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.

[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.

[:92-2] 2,0 ^2,1 ^2,2 ^2,3 ^2,4 ^2,5 Burton, D. M., & Dalkowski, H. (2005). Handbuch der elementaren Zahlentheorie mit über 1000 Übungsaufgaben und ihren Lösungen. Heldermann Verlag. S. 26.

[:55-3] 3,0 ^3,1 ^3,2 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)

[:0-4] 4,0 ^4,1 ^4,2 ^4,3 ^4,4 ^4,5 ^4,6 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)

[:4-5] 5,0 ^5,1 ^5,2 ^5,3 ^5,4 ^5,5 Stroth, G., & Waldecker, R. (2019). Elementare Algebra und Zahlentheorie (2. Aufl.). Birkhäuser Basel. S. 77.

[:3-6] 6,0 ^6,1 ^6,2 ^6,3 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)

[:2-7] 7,0 ^7,1 ^7,2 ^7,3 ^7,4 ^7,5 Wätjen, D. (2018). Kryptographie: Grundlagen, Algorithmen, Protokolle. Springer-Verlag. S. 42.

[:1222-8] 8,0 ^8,1 ^8,2 Burton, D. M., & Dalkowski, H. (2005). Handbuch der elementaren Zahlentheorie mit über 1000 Übungsaufgaben und ihren Lösungen. Lemgo: Heldermann Verlag. S. 47.

[:0222-9] 9,0 ^9,1 Ziegenbalg, J. (2015). Elementare Zahlentheorie: Beispiele, Geschichte, Algorithmen (2., überarb. Aufl). Springer Spektrum. S. 66.

[:10-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.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]