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{\bmod {p}}$ und $(m^{e})^{d}\equiv m{\bmod {q}}$ zeigen, dass diese gelten, wenn $ggT(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 $ggT(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 \mathbb {Z}$ und $m\in \mathbb {N}$ , dann gilt $a\equiv b{\bmod {m}}\Leftrightarrow m\mid (a-b)$ ^[7].

Seien $c_{1},c_{2},\dots ,c_{v}\in \mathbb {N}$ paarweise teilerfremd in $\mathbb {Z}$ , $v\in \mathbb {N}$ und $a_{1},a_{2},\dots ,a_{v}\in \mathbb {Z}$ .

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

Die Lösung ist eindeutig ${\bmod {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 \mathbb {Z}$ .

Es gilt $ggT(a,bc)=1$ genau dann, wenn $ggt(a,b)=1$ und $ggT(a,c)=1$ ^[8].

Beweis Hilfssatz zum chinesischen Restsatz

Hinrichtung

Größte gemeinsame Teiler
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$ ^[9].

Voraussetzung

Seien $a,b,c\in \mathbb {Z}$ und $ggT(a,bc)=1$

Zu zeigen

$ggT(a,b)=1$ und $ggT(a,c)=1$

Beweis

Sei $ggT(a,bc)=1$ .

Wir definieren $d=ggT(a,b)$ und somit gilt nach Definition $ggT$ $d\mid a$ und $d\mid b$ .

Da $d\mid b$ , gilt auch $d\mid bc$ und somit ist $ggT(a,bc)\geq d$ .

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

Man kann nun ein $e=ggT(a,c)$ definieren und auf analoge Weise begründen, dass $ggT(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 \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$ ^[9].
Satz Primteiler
Sei $n\in \mathbb {N}$ 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 \mathbb {N}$ prim und $a,b\in \mathbb {Z}$ mit $p\mid ab$ , dann gilt $p\mid a$ oder $p\mid b$ ^[11].

Voraussetzung

Seien $a,b,c\in \mathbb {Z}$ , $ggT(a,b)=1$ und $ggT(a,c)=1$

Zu zeigen

$ggT(a,bc)=1$

Beweis

Wir zeigen $ggT(a,bc)=1$ durch Widerspruch.

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

Da $ggT(a,b)=1$ und $ggT(a,c)=1$ muss $f$ einen Primfaktor $p$ nach dem Satz Primteiler besitzen mit $p\mid bc$ (wegen $f\mid bc$ ).

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

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

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

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

Wir haben also gezeigt, dass $f=1$ gelten muss. Somit ist $ggT(a,bc)=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 $ggT(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 \mathbb {Z}$ und $m\in \mathbb {N}$ , dann gilt $a\equiv b{\bmod {m}}\Leftrightarrow m\mid (a-b)$ ^[7].
Hilfssatz zum chinesischen Restsatz
Seien für $a,b,c\in \mathbb {Z}$ genau dann $ggT(a,bc)=1$ , wenn $ggt(a,b)=1$ und $ggT(a,c)=1$ ^[8].
Satz von Euler
Seien $a,n\in \mathbb {N}$ und $\operatorname {ggT} (a,n)=1$ , dann gilt $a^{\varphi (n)}\equiv 1{\bmod {n}}$ ^[12]^[13].

Seien $c_{1},c_{2},\dots ,c_{v}\in \mathbb {N}$ paarweise teilerfremd und $a_{1},a_{2},\dots ,a_{v}\in \mathbb {Z}$ mit je $v\in \mathbb {N}$ .

Zu zeigen

Das System aus den Kongruenzen

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

$\vdots$

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

hat eine Lösung $b\equiv a_{i}{\bmod {c}}_{i}$ und alle $g\in \mathbb {Z}$ mit $g\equiv b{\bmod {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}^{\varphi {(c_{1})}}+a_{2}C_{2}^{\varphi {(c_{2})}}+\dots +a_{v}C_{v}^{\varphi {(c_{v})}}$ genau

$b\equiv a_{i}{\bmod {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{\bmod {c}}_{i}$ .

Es gilt also auch $a_{j}C_{j}^{\varphi (c_{j})}\equiv 0{\bmod {c}}_{i}$ im Restklassenring $(\mathbb {Z} /c_{i}\mathbb {Z} ,\oplus ,\odot )$

Es sind daher alle Summanden von

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

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

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

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

Nach Hilfssatz zum chinesischen Restsatz ist auch $ggT(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}^{\varphi (c_{i})}\equiv 1{\bmod {c}}_{i}\quad (**)$ mit $i\in \{1,2,\dots ,v\}$ .

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

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

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

Nun müssen wir noch die Eindeutigkeit ${\bmod {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 \mathbb {Z}$ und $m\in \mathbb {N}$ . Wenn $a\equiv b{\bmod {m}}$ und $b\equiv c{\bmod {m}}$ , dann gilt $a\equiv c{\bmod {m}}$ ^[15].
Kongruenz
Seien $a,b\in \mathbb {Z}$ und $m\in \mathbb {N}$ , dann gilt $a\equiv b{\bmod {m}}\Leftrightarrow m\mid (a-b)$ ^[7].
Teilerfremdheit
Zwei ganze Zahlen $a$ und $b$ , wobei mindestens einer der beiden Zahlen ungleich Null ist, heißen teilerfremd, wenn $ggT(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}{\bmod {c}}_{i}$ .

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

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

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

$c_{i}\mid (g-b)$ .

Wegen $c_{1},c_{2},\dots ,c_{v}\in \mathbb {N}$ paarweise teilerfremd in $\mathbb {Z}$ , gilt sogar

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

Nach Definition der Kongruenz gilt also

$g\equiv b{\bmod {c}}$ .

Die Lösung ist eindeutig ${\bmod {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 $ggT(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 \mathbb {N}$ angewandt und besteht aus zwei Teilen: Berechnung des $\operatorname {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 $\operatorname {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{\bmod {3}}$

$b\equiv 3{\bmod {5}}$

$b\equiv 2{\bmod {7}}$

Da $ggT(2,5)=ggT(2,7)=ggT(7,5)=1$ und $2,3\in \mathbb {Z}$ , 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 \mathbb {N}$ angewandt und besteht aus zwei Teilen: Berechnung des $\operatorname {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 $\operatorname {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{\bmod {3}}$ , wegen $23=7\cdot 3+2$ ,

$23\equiv 3{\bmod {5}}$ , wegen $23=4\cdot 5+3$ ,

$23\equiv 2{\bmod {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 \mathbb {N}$ angewandt und besteht aus zwei Teilen: Berechnung des $\operatorname {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 $\operatorname {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]