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 mod φ (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 $φ$ -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 $g g T (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 $φ$ -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:

$φ (n) : = ∣ G_{n} ∣$ ^[6]^[5] mit $G_{n} : = {a \in ℕ | 1 \leq a \leq n \land 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 $g g T (1, 1) = 1$ .

Es gilt also $φ (1) = ∣ G_{1} ∣ = 1$ .

Beispiel $n = 4$

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

Es gilt also $φ (4) = ∣ G_{4} ∣ = 2$ .

Beispiel $n = 7$

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

Es gilt also $φ (7) = ∣ G_{7} ∣ = 6$ .

Eigenschaften Eulersche φ-Funktion

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

Satz 1 Eigenschaft der $φ$ -Funktion bei Primzahlen

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

Beweis Eigenschaft der $φ (p)$ -Funktion bei Primzahlen

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

Voraussetzung

$p$ ist prim

Zu zeigen

$φ (p) = p - 1$

Beweis

Wir betrachten die Menge $G_{p}$ .

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

$G_{p} : = {a \in ℕ | 1 \leq a \leq p \land 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 $g g T (a, p) = 1$ .

Für $a = 1$ gilt $g g T (1, p) = 1$ , da $1 ∣ 1$ und $1 ∣ p$ und es keine weitere Zahl $d \in ℕ$ gibt, für die gilt $d ∣ 1$ .

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

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

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

Satz 2 Multiplikativität von $φ$ für Primzahlen

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

Beweis Multiplikativität von $φ$ für Primzahlen

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

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

Beweis

Betrachten wir die Menge $G_{p q}$ .

Wir wissen, dass nach der Definition der Menge $G_{p q}$ gilt $G_{p q} : = {a \in ℕ | 1 \leq a \leq p q \land ggT (a, p q) = 1}$ .

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

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

Es gilt $p q \notin G_{p q}$ , da $g g T (p q, p q) = p g \neq 1$ .

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

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

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

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

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

Damit folgt für die Anzahl der Elemente in

$| G_{p q} |$

$= | M_{p q} | - (q - 1) - (p - 1)$

$= p q - 1 - (q - 1) - (p - 1)$ , da $| M_{p q} | = p q - 1$

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

$= p q - 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$ .

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

Satz 3 Eigenschaft der $φ$ -Funktion bei Primzahlen

Primzahl, Menge $G_{n}$ und Teilerfremdheit
Primzahl
Sei $p \in ℕ$ mit $p > 1$ , dann heißt $p$ Primzahl oder prime Zahl, wenn gilt: $p$ besitzt nur zwei Teiler in $ℕ$ , nämlich $1$ und $p$ . Andernfalls heißt $p$ zusammengesetzte Zahl^[8].
Menge $G_{n}$
Sei $n \in ℕ$ , dann gilt $G_{n} : = {a \in ℕ \| 1 \leq a \leq n \land 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 $g g T (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 ℕ$ mit $k > 0$ , dann gilt:

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

Beweis Satz 3

Voraussetzung

Seien $p$ prim und $k \in ℕ$ mit $k > 0$

Zu zeigen

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

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 $g g T (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, 2 p, \dots, p \cdot p^{k - 1}$ .

Es gilt also
$φ (p^{k})$

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

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

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

Lernaufgabe

Aufgabe

Beweisen Sie die Folgerung aus Satz 1.

Folgerung

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

Lösung

Voraussetzungen

$N = p \cdot q$ .

Zu zeigen

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

Beweis

$φ (N)$

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

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

$= (p - 1) \cdot (q - 1)$ , Eigenschaft der $φ (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]

Kryptologie/Eulersche φ-Funktion

Inhaltsverzeichnis

Einleitung

Eulersche φ-Funktion

Definition Eulersche φ-Funktion

Beispiel Eulersche φ-Funktion

Eigenschaften Eulersche φ-Funktion

Satz 1 Eigenschaft der $φ$ -Funktion bei Primzahlen

Beweis Eigenschaft der $φ (p)$ -Funktion bei Primzahlen

Satz 2 Multiplikativität von $φ$ für Primzahlen

Beispiel

Satz 3 Eigenschaft der $φ$ -Funktion bei Primzahlen

Beweis Satz 3

Lernaufgabe

Aufgabe

Folgerung

Lernempfehlung

Literatur

Navigationsmenü

Kryptologie/Eulersche φ-Funktion

Einleitung

Eulersche φ-Funktion

Definition Eulersche φ-Funktion

Beispiel Eulersche φ-Funktion

Eigenschaften Eulersche φ-Funktion

Satz 1 Eigenschaft der φ-Funktion bei Primzahlen

Beweis Eigenschaft der φ(p)-Funktion bei Primzahlen

Satz 2 Multiplikativität von φ für Primzahlen

Beispiel

Satz 3 Eigenschaft der φ-Funktion bei Primzahlen

Beweis Satz 3

Lernaufgabe

Aufgabe

Folgerung

Lernempfehlung

Literatur

Navigationsmenü

Suche

Satz 1 Eigenschaft der $φ$ -Funktion bei Primzahlen

Beweis Eigenschaft der $φ (p)$ -Funktion bei Primzahlen

Satz 2 Multiplikativität von $φ$ für Primzahlen

Satz 3 Eigenschaft der $φ$ -Funktion bei Primzahlen