Kryptologie/Chinesischer Restsatz

Einleitung

Bevor wir die Korrektheit der RSA-Verschlüsselungsverfahrens zeigen können, benötigen wir neben dem Satz von Euler noch den chinesischen Restsatz. Mit diesem werden wir dort für die zwei die Kongruenzen $(m^{e})^{d} \equiv m mod p$ und $(m^{e})^{d} \equiv m mod q$ zeigen, dass diese gelten, wenn $g g T (m, N) \neq 1$ und der Satz von Euler somit nicht anwendbar ist^[1]^[2]. Wir werden Satz von Euler jedoch nutzen können, um den chinesischen Restsatz zu beweisen^[3]. Den Abschnitt Finden einer Lösung werden wir benötigen, sobald wir uns mit Angriffsszenarien auf das RSA-Verschlüsselungsverfahren beschäftigen^[4].

Chinesischer Restsatz

Teilerfremdheit und Kongruenz
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$ ^[5]. Betrachten wir mehr als zwei Zahlen, dann nennen wir diese paarweise teilerfremd, wenn je zwei beliebige von diesen Zahlen zueinander teilerfremd sind^[6]^[5].
Kongruenz
Seien $a, b \in ℤ$ und $m \in ℕ$ , dann gilt $a \equiv b mod m \Leftrightarrow m ∣ (a - b)$ ^[7].

Seien $c_{1}, c_{2}, \dots, c_{v} \in ℕ$ paarweise teilerfremd in $ℤ$ , $v \in ℕ$ und $a_{1}, a_{2}, \dots, a_{v} \in ℤ$ .

Dann existiert eine Lösung $b \in ℤ$ , sodass für jedes $i \in {1, 2, \dots, v}$ die Kongruenz $b \equiv a_{i} {mod c}_{i}$ gilt.

Die Lösung ist eindeutig $mod c$ mit $c = c_{1} \cdot c_{2} \cdot \dots \cdot c_{v}$ ^[3].

Bemerkung: Bevor wir den chinesischen Restsatz beweisen können, benötigen wir den nun folgenden Hilfssatz.

Hilfssatz zum chinesischen Restsatz

Seien $a, b, c \in ℤ$ .

Es gilt $g g T (a, b c) = 1$ genau dann, wenn $g g t (a, b) = 1$ und $g g T (a, c) = 1$ ^[8].

Beweis Hilfssatz zum chinesischen Restsatz

Hinrichtung

Größte gemeinsame Teiler
Größte gemeinsame Teiler
Seien $a, b \in ℤ$ , wobei mindestens eine der beiden Zahlen ungleich Null. Wir bezeichnen $d : = g g T (a, b)$ mit $d \in ℕ$ als den größten gemeinsamen Teiler der Zahlen $a$ und $b$ , falls gilt: $(1)$ : $d ∣ a$ und $d ∣ b$ und $(2)$ : Für alle $c \in ℤ$ mit $c ∣ a$ und $c ∣ b \Rightarrow c \leq d$ ^[9].

Voraussetzung

Seien $a, b, c \in ℤ$ und $g g T (a, b c) = 1$

Zu zeigen

$g g T (a, b) = 1$ und $g g T (a, c) = 1$

Beweis

Sei $g g T (a, b c) = 1$ .

Wir definieren $d = g g T (a, b)$ und somit gilt nach Definition $g g T$ $d ∣ a$ und $d ∣ b$ .

Da $d ∣ b$ , gilt auch $d ∣ b c$ und somit ist $g g T (a, b c) \geq d$ .

Da nach Voraussetzung jedoch $g g T (a, b c) = 1$ , muss wegen $g g T (a, b c) \geq d$ auch $g g T (a, b) = d = 1$ sein.

Man kann nun ein $e = g g T (a, c)$ definieren und auf analoge Weise begründen, dass $g g T (a, c) = e = 1$ .

Rückrichtung

Größte gemeinsame Teiler, Satz Primteiler und Satz 2 Eigenschaften von Primzahlen
Größte gemeinsame Teiler
Seien $a, b \in ℤ$ , wobei mindestens eine der beiden Zahlen ungleich Null. Wir bezeichnen $d : = g g T (a, b)$ mit $d \in ℕ$ als den größten gemeinsamen Teiler der Zahlen $a$ und $b$ , falls gilt: $(1)$ : $d ∣ a$ und $d ∣ b$ und $(2)$ : Für alle $c \in ℤ$ mit $c ∣ a$ und $c ∣ b \Rightarrow c \leq d$ ^[9].
Satz Primteiler
Sei $n \in ℕ$ mit $n > 1$ , dann hat $n$ einen Primteiler, d.h. einen Teiler, der gleichzeitig eine Primzahl ist^[10].
Satz 2 Eigenschaften von Primzahlen
Seien $p \in ℕ$ prim und $a, b \in ℤ$ mit $p ∣ a b$ , dann gilt $p ∣ a$ oder $p ∣ b$ ^[11].

Voraussetzung

Seien $a, b, c \in ℤ$ , $g g T (a, b) = 1$ und $g g T (a, c) = 1$

Zu zeigen

$g g T (a, b c) = 1$

Beweis

Wir zeigen $g g T (a, b c) = 1$ durch Widerspruch.

Seien $g g T (a, b) = 1$ und $g g T (a, c) = 1$ und wir nehmen an, dass $g g T (a, b c) = f$ mit $f > 1$ .

Da $g g T (a, b) = 1$ und $g g T (a, c) = 1$ muss $f$ einen Primfaktor $p$ nach dem Satz Primteiler besitzen mit $p ∣ b c$ (wegen $f ∣ b c$ ).

Wie wir bereits in Satz 2 Eigenschaften von Primzahlen gezeigt haben, folgt $p ∣ b$ oder $p ∣ c$ .

Wenn $p ∣ b$ gelten würde, dann wäre $1 < p \leq g g T (a, b)$ , da $p ∣ a$ wegen $f ∣ a$ nach der Definition des $g g T$ gilt.

Dies ist ein Widerspruch zur Voraussetzung $g g T (a, b) = 1$ .

Analog gilt, unter der Annahme $p ∣ c$ , $1 < p \leq g g T (a, c)$ und erhalten einen Widerspruch zur Voraussetzung $g g T (a, c) = 1$ .

Wir haben also gezeigt, dass $f = 1$ gelten muss. Somit ist $g g T (a, b c) = f = 1$ ■^[8]

Beweis Chinesischer Restsatz

Voraussetzungen

Teilerfremdheit, Kongruenz, Hilfssatz zum chinesischen Restsatz und Satz von Euler
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$ ^[5]. Betrachten wir mehr als zwei Zahlen, dann nennen wir diese paarweise teilerfremd, wenn je zwei beliebige von diesen Zahlen zueinander teilerfremd sind^[6]^[5].
Kongruenz
Seien $a, b \in ℤ$ und $m \in ℕ$ , dann gilt $a \equiv b mod m \Leftrightarrow m ∣ (a - b)$ ^[7].
Hilfssatz zum chinesischen Restsatz
Seien für $a, b, c \in ℤ$ genau dann $g g T (a, b c) = 1$ , wenn $g g t (a, b) = 1$ und $g g T (a, c) = 1$ ^[8].
Satz von Euler
Seien $a, n \in ℕ$ und $ggT (a, n) = 1$ , dann gilt $a^{φ (n)} \equiv 1 mod n$ ^[12]^[13].

Seien $c_{1}, c_{2}, \dots, c_{v} \in ℕ$ paarweise teilerfremd und $a_{1}, a_{2}, \dots, a_{v} \in ℤ$ mit je $v \in ℕ$ .

Zu zeigen

Das System aus den Kongruenzen

$b \equiv a_{1} {mod c}_{1}$

$⋮$

$b \equiv a_{v} {mod c}_{v}$

hat eine Lösung $b \equiv a_{i} {mod c}_{i}$ und alle $g \in ℤ$ mit $g \equiv b mod c$ sind ebenfalls Lösungen der Kongruenz

Beweis

Wir zeigen zunächst, dass wenn man $c = c_{1} c_{2} \dots c_{v}$ und $C_{i} = c / c_{i}$ mit $i \in {1, 2, \dots, v}$ definiert,

dann gilt für $b = a_{1} C_{1}^{φ (c_{1})} + a_{2} C_{2}^{φ (c_{2})} + \dots + a_{v} C_{v}^{φ (c_{v})}$ genau

$b \equiv a_{i} {mod c}_{i}$ mit $i \in {1, 2, \dots, v}$ .

Betrachten wir hierfür $C_{j}$ mit $i \neq j$ .

Da $C_{j} = c / c_{j} = \frac{c_{1} c_{2} \dots c_{v}}{c_{j}}$ und $i \neq j$ , kann $c_{i}$ nicht aus dem Produkt gekürzt werden und somit gilt

$C_{j} \equiv 0 {mod c}_{i}$ .

Es gilt also auch $a_{j} C_{j}^{φ (c_{j})} \equiv 0 {mod c}_{i}$ im Restklassenring $(ℤ / c_{i} ℤ, \oplus, ⊙)$

Es sind daher alle Summanden von

$b \equiv a_{1} C_{1}^{φ (c_{1})} + a_{2} C_{2}^{φ (c_{2})} + \dots + a_{v} C_{v}^{φ (c_{v})} {mod c}_{i}$

Es sind alle Summanden Null, bis auf den Summanden $a_{i} C_{i}^{φ (c_{i})}$ und man kann schreiben

$b \equiv a_{i} C_{i}^{φ (c_{i})} {mod c}_{i} (*)$ mit $i \in {1, 2, \dots, v}$ .

Da nach Voraussetzung $c_{1}, c_{2}, \dots, c_{v} \in ℕ$ paarweise teilerfremd sind, gilt $g g T (c_{i}, c_{j}) = 1$ mit $i \neq j$ .

Nach Hilfssatz zum chinesischen Restsatz ist auch $g g T (c_{i}, C_{i}) = 1$ .

Somit sind die Voraussetzungen für den Satz von Euler erfüllt und wir können diesen anwenden:

$C_{i}^{φ (c_{i})} \equiv 1 {mod c}_{i} (* *)$ mit $i \in {1, 2, \dots, v}$ .

Wir können die Kongruenz $(* *)$ nutzen, um die Kongruenz $(*)$ zu vereinfachen und erhalten:

$b \equiv a_{i} {mod c}_{i}$ mit $i \in {1, 2, \dots, v}$ .

Somit ist $b = a_{1} C_{1}^{φ (c_{1})} + a_{2} C_{2}^{φ (c_{2})} + \dots + a_{v} C_{v}^{φ (c_{v})}$ eine Lösung des Systems der Kongruenzen^[14].

Nun müssen wir noch die Eindeutigkeit $mod c$ zeigen:

Angenommen es gibt eine weitere Lösung $g$ des Systems der Kongruenzen, dann gilt

Transitivität, Kongruenz und Teilerfremdheit
Transitivität
Seien $a, b \in ℤ$ und $m \in ℕ$ . Wenn $a \equiv b mod m$ und $b \equiv c mod m$ , dann gilt $a \equiv c mod m$ ^[15].
Kongruenz
Seien $a, b \in ℤ$ und $m \in ℕ$ , dann gilt $a \equiv b mod m \Leftrightarrow m ∣ (a - b)$ ^[7].
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$ ^[5]. Betrachten wir mehr als zwei Zahlen, dann nennen wir diese paarweise teilerfremd, wenn je zwei beliebige von diesen Zahlen zueinander teilerfremd sind^[6]^[16].

$g \equiv a_{i} {mod c}_{i}$ .

Da jedoch auch $b \equiv a_{i} {mod c}_{i}$ , folgt aus der Transitivität der Kongruenz

$g \equiv b {mod c}_{i}$ .

Nun gilt nach Definition der Kongruenz für alle $i \in {1, 2, \dots, v}$

$c_{i} ∣ (g - b)$ .

Wegen $c_{1}, c_{2}, \dots, c_{v} \in ℕ$ paarweise teilerfremd in $ℤ$ , gilt sogar

$c ∣ (g - b)$ mit $c = c_{1} \cdot c_{2} \cdot \dots \cdot c_{v}$ .

Nach Definition der Kongruenz gilt also

$g \equiv b mod c$ .

Die Lösung ist eindeutig $mod c$ ■^[14]^[3]

Finden einer Lösung

Teilerfremdheit und Erweiterte euklidische Algorithmus
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$ ^[5]. Betrachten wir mehr als zwei Zahlen, dann nennen wir diese paarweise teilerfremd, wenn je zwei beliebige von diesen Zahlen zueinander teilerfremd sind^[6]^[16].
Erweiterte euklidische Algorithmus
Der erweiterte euklidische Algorithmus wird auf zwei Zahlen $a, b \in ℕ$ angewandt und besteht aus zwei Teilen: Berechnung des $ggT (a, b) = s \cdot a + t \cdot b$ (auch als euklidischer Algorithmus bekannt^[17]), Berechnung zweier ganzer Zahlen $s$ und $t$ , welche die Gleichung $ggT (a, b) = s \cdot a + t \cdot b$ erfüllen^[18].

Eine Lösung

b

kann wie folgt ermittelt werden: Für jedes

i

sind die Zahlen

c_{i}

und

C_{i} : = C / c_{i}

teilerfremd, also kann man z. B. mit dem erweiterten euklidischen Algorithmus zwei ganze Zahlen

r_{i}

und

s_{i}

finden, so dass

r_{i} \cdot c_{i} + s_{i} \cdot C_{i} = 1

.

Setze $e_{i} : = s_{i} \cdot C_{i}$ , dann gilt

e_{i} \equiv 1 mod c_{i}

, wegen

r_{i} \cdot c_{i} + s_{i} \cdot C_{i} = 1

,

e_{i} \equiv 0 mod c_{j}, j \neq i

und analog zur Argumentation im Beweis.

Die Zahl

b : = \sum_{i = 1}^{v} a_{i} e_{i}

ist dann eine Lösung der simultanen Kongruenz^[19]. Wir können dies nutzen, um in einer anderen Lerneinheit einen Angriff auf eine Anwendungssituation des RSA-Algorithmus durchzuführen.

Beispiel

Wir betrachten folgendes System:

$b \equiv 2 mod 3$

$b \equiv 3 mod 5$

$b \equiv 2 mod 7$

Da $g g T (2, 5) = g g T (2, 7) = g g T (7, 5) = 1$ und $2, 3 \in ℤ$ , können wir den chinesischen Restsatz anwenden:

Wir stellen die Gleichungen aus dem Abschnitt Finden einer Lösung auf:

$r_{1} \cdot 3 + s_{1} \cdot 35 = 1$ , da $C_{1} = 5 \cdot 7$

$r_{2} \cdot 5 + s_{2} \cdot 21 = 1$ , da $C_{2} = 3 \cdot 7$

$r_{3} \cdot 7 + s_{3} \cdot 15 = 1$ , da $C_{3} = 3 \cdot 5$

Erweiterte euklidische Algorithmus
Erweiterte euklidische Algorithmus
Der erweiterte euklidische Algorithmus wird auf zwei Zahlen $a, b \in ℕ$ angewandt und besteht aus zwei Teilen: Berechnung des $ggT (a, b) = s \cdot a + t \cdot b$ (auch als euklidischer Algorithmus bekannt^[17]), Berechnung zweier ganzer Zahlen $s$ und $t$ , welche die Gleichung $ggT (a, b) = s \cdot a + t \cdot b$ erfüllen^[18].

Nun wenden wir den erweiterten euklidischen Algorithmus an (siehe Lernaufgabe) und erhalten

Zu $r_{1} \cdot 3 + s_{1} \cdot 35 = 1$ :

$r_{1} = 12$ , $s_{1} = - 1$ und $e_{1} = - 1 \cdot 35 = - 35$

Zu $r_{2} \cdot 5 + s_{2} \cdot 21 = 1$ :

$r_{2} = - 4$ , $s_{2} = 1$ und $e_{2} = 1 \cdot 21 = 21$

Zu $r_{3} \cdot 7 + s_{3} \cdot 15 = 1$ :

$r_{3} = - 2$ , $s_{2} = 1$ und $e_{3} = 1 \cdot 15 = 15$

Nun können wir $b : = \sum_{i = 1}^{v} a_{i} e_{i}$ berechnen:

$b : = \sum_{i = 1}^{3} a_{i} e_{i} = 2 \cdot (- 35) + 3 \cdot 21 + 2 \cdot 15 = 23$ .

Zur Veranschaulichung führen wir nun noch die Probe durch:

$23 \equiv 2 mod 3$ , wegen $23 = 7 \cdot 3 + 2$ ,

$23 \equiv 3 mod 5$ , wegen $23 = 4 \cdot 5 + 3$ ,

$23 \equiv 2 mod 7$ , wegen $23 = 3 \cdot 7 + 2$ .

Lernaufgabe

Aufgabe

Berechnen Sie mit dem erweiterten euklidischen Algorithmus $r_{i}$ und $s_{i}$ mit $i \in {1, 2, 3}$ für das Beispiel zum chinesischen Restsatz, also

$r_{1} \cdot 3 + s_{1} \cdot 35 = 1$ ,

$r_{2} \cdot 5 + s_{2} \cdot 21 = 1$

und

$r_{3} \cdot 7 + s_{3} \cdot 15 = 1$ .

Erweiterte euklidische Algorithmus
Erweiterte euklidische Algorithmus
Der erweiterte euklidische Algorithmus wird auf zwei Zahlen $a, b \in ℕ$ angewandt und besteht aus zwei Teilen: Berechnung des $ggT (a, b) = s \cdot a + t \cdot b$ (auch als euklidischer Algorithmus bekannt^[17]), Berechnung zweier ganzer Zahlen $s$ und $t$ , welche die Gleichung $ggT (a, b) = s \cdot a + t \cdot b$ erfüllen^[18].

Lösung

Zu

r_{1} \cdot 3 + s_{1} \cdot 35 = 1

:

$35 = 11 \cdot 3 + 2$

$\Leftrightarrow 3 = 1 \cdot 2 + 1$

$\Leftrightarrow 1 = 3 - 1 \cdot 2$

$\Leftrightarrow 1 = 3 - 1 \cdot (35 - 11 \cdot 3)$ , wegen $35 = 11 \cdot 3 + 2$

$\Leftrightarrow 1 = 3 - 35 + 11 \cdot 3$

$\Leftrightarrow 1 = 12 \cdot 3 + (- 1) \cdot 35$

$\Rightarrow r_{1} = 12, s_{1} = - 1$

Zu $r_{2} \cdot 5 + s_{2} \cdot 21 = 1$ :

$21 = 4 \cdot 5 + 1$

$\Leftrightarrow 1 = 21 - 4 \cdot 5$

$\Rightarrow r_{2} = - 4, s_{2} = 1$

Zu $r_{3} \cdot 7 + s_{3} \cdot 15 = 1$ :

$15 = 2 \cdot 7 + 1$

$\Leftrightarrow 1 = 15 - 2 \cdot 7$

$\Rightarrow r_{3} = - 2, s_{2} = 1$

Lernempfehlung

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

Literatur

↑ Beweisarchiv: Kryptografie: Kryptosysteme: Korrektheit des RSA-Kryptosystems. (16. Juni 2013). Wikibooks, Die freie Bibliothek. Abgerufen am 10. Januar 2020, 12:20 von https://de.wikibooks.org/w/index.php?title=Beweisarchiv:_Kryptografie:_Kryptosysteme:_Korrektheit_des_RSA-Kryptosystems&oldid=674922. (Formulierung verändert)
↑ 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.
↑ ^3,0 ^3,1 ^3,2 Shoup, V. (2008). A Computational Introduction to Number Theory and Algebra (2. Aufl.). S. 23.
↑ Buchmann, J. (2016). Einführung in die Kryptographie (6. Aufl.). Springer. S. 175.
↑ ^5,0 ^5,1 ^5,2 ^5,3 ^5,4 ^5,5 Burton, D. M., & Dalkowski, H. (2005). Handbuch der elementaren Zahlentheorie mit über 1000 Übungsaufgaben und ihren Lösungen. Heldermann Verlag. S. 26.
↑ ^6,0 ^6,1 ^6,2 ^6,3 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)
↑ ^7,0 ^7,1 ^7,2 Buchmann, J. (2016). Einführung in die Kryptographie (6. Aufl.). Berlin, Heidelberg: Springer. S. 37.
↑ ^8,0 ^8,1 ^8,2 Burton, D. M., & Dalkowski, H. (2005). Handbuch der elementaren Zahlentheorie mit über 1000 Übungsaufgaben und ihren Lösungen. Heldermann Verlag. S. 146.
↑ ^9,0 ^9,1 Burton, D. M., & Dalkowski, H. (2005). Handbuch der elementaren Zahlentheorie mit über 1000 Übungsaufgaben und ihren Lösungen. Lemgo: Heldermann Verlag. S. 24.
↑ Buchmann, J. (2016). Einführung in die Kryptographie (6. Aufl.). Berlin, Heidelberg: Springer. S. 10.
↑ Burton, D. M., & Dalkowski, H. (2005). Handbuch der elementaren Zahlentheorie mit über 1000 Übungsaufgaben und ihren Lösungen. Lemgo: Heldermann Verlag. S. 48.
↑ „Satz von Euler“. In: Wikipedia, Die freie Enzyklopädie. Bearbeitungsstand: 27. März 2019, 10:16 UTC. URL: https://de.wikipedia.org/w/index.php?title=Satz_von_Euler&oldid=186980132 (Abgerufen: 25. November 2019, 10:25 UTC; Formulierung verändert)
↑ Euler, L. (1763). Theoremata arithmetica nova methodo demonstrata. 8 (S. 74–104). S. 102.
↑ ^14,0 ^14,1 Burton, D. M., & Dalkowski, H. (2005). Handbuch der elementaren Zahlentheorie mit über 1000 Übungsaufgaben und ihren Lösungen. Heldermann Verlag. S. 154f.
↑ Reiss, K., & Schmieder, G. (2014). Basiswissen Zahlentheorie: Eine Einführung in Zahlen und Zahlbereiche (3. Aufl.). Springer Spektrum. S. 157.
↑ ^16,0 ^16,1 Burton, D. M., & Dalkowski, H. (2005). Handbuch der elementaren Zahlentheorie mit über 1000 Übungsaufgaben und ihren Lösungen. Lemgo: Heldermann Verlag. S. 26.
↑ ^17,0 ^17,1 ^17,2 Lehman, E., Leighton, T., & Meyer, A. R. (2010). Mathematics for computer science. Technical report, 2006. Lecture notes. S. 249.
↑ ^18,0 ^18,1 ^18,2 Kurzweil, H. (2008). Endliche Körper: Verstehen, rechnen, anwenden (2., überarb. Aufl). Springer. S. 57.
↑ Seite „Chinesischer Restsatz“. In: Wikipedia, Die freie Enzyklopädie. Bearbeitungsstand: 11. November 2019, 11:56 UTC. URL: https://de.wikipedia.org/w/index.php?title=Chinesischer_Restsatz&oldid=193949389 (Abgerufen: 23. Januar 2020, 14:56 UTC)

[1] Beweisarchiv: Kryptografie: Kryptosysteme: Korrektheit des RSA-Kryptosystems. (16. Juni 2013). Wikibooks, Die freie Bibliothek. Abgerufen am 10. Januar 2020, 12:20 von https://de.wikibooks.org/w/index.php?title=Beweisarchiv:_Kryptografie:_Kryptosysteme:_Korrektheit_des_RSA-Kryptosystems&oldid=674922. (Formulierung verändert)

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

[:4-3] 3,0 ^3,1 ^3,2 Shoup, V. (2008). A Computational Introduction to Number Theory and Algebra (2. Aufl.). S. 23.

[4] Buchmann, J. (2016). Einführung in die Kryptographie (6. Aufl.). Springer. S. 175.

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

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

[:322-7] 7,0 ^7,1 ^7,2 Buchmann, J. (2016). Einführung in die Kryptographie (6. Aufl.). Berlin, Heidelberg: Springer. S. 37.

[:1-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. Heldermann Verlag. S. 146.

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

[:26-10] Buchmann, J. (2016). Einführung in die Kryptographie (6. Aufl.). Berlin, Heidelberg: Springer. S. 10.

[:53-11] Burton, D. M., & Dalkowski, H. (2005). Handbuch der elementaren Zahlentheorie mit über 1000 Übungsaufgaben und ihren Lösungen. Lemgo: Heldermann Verlag. S. 48.

[:02-12] „Satz von Euler“. In: Wikipedia, Die freie Enzyklopädie. Bearbeitungsstand: 27. März 2019, 10:16 UTC. URL: https://de.wikipedia.org/w/index.php?title=Satz_von_Euler&oldid=186980132 (Abgerufen: 25. November 2019, 10:25 UTC; Formulierung verändert)

[13] Euler, L. (1763). Theoremata arithmetica nova methodo demonstrata. 8 (S. 74–104). S. 102.

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

[:09-15] Reiss, K., & Schmieder, G. (2014). Basiswissen Zahlentheorie: Eine Einführung in Zahlen und Zahlbereiche (3. Aufl.). Springer Spektrum. S. 157.

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

[:0-17] 17,0 ^17,1 ^17,2 Lehman, E., Leighton, T., & Meyer, A. R. (2010). Mathematics for computer science. Technical report, 2006. Lecture notes. S. 249.

[:2-18] 18,0 ^18,1 ^18,2 Kurzweil, H. (2008). Endliche Körper: Verstehen, rechnen, anwenden (2., überarb. Aufl). Springer. S. 57.

[19] Seite „Chinesischer Restsatz“. In: Wikipedia, Die freie Enzyklopädie. Bearbeitungsstand: 11. November 2019, 11:56 UTC. URL: https://de.wikipedia.org/w/index.php?title=Chinesischer_Restsatz&oldid=193949389 (Abgerufen: 23. Januar 2020, 14:56 UTC)

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

Kryptologie/Chinesischer Restsatz

Inhaltsverzeichnis

Einleitung

Chinesischer Restsatz

Chinesischer Restsatz

Hilfssatz zum chinesischen Restsatz

Beweis Hilfssatz zum chinesischen Restsatz

Beweis Chinesischer Restsatz

Finden einer Lösung

Beispiel

Lernaufgabe

Aufgabe

Lernempfehlung

Literatur

Navigationsmenü

Kryptologie/Chinesischer Restsatz

Einleitung

Chinesischer Restsatz

Chinesischer Restsatz

Hilfssatz zum chinesischen Restsatz

Beweis Hilfssatz zum chinesischen Restsatz

Beweis Chinesischer Restsatz

Finden einer Lösung

Beispiel

Lernaufgabe

Aufgabe

Lernempfehlung

Literatur

Navigationsmenü

Suche