Kryptologie/Sicherheit des RSA-Kryptosystems

Einleitung

RSA-Problem und multiplikative Inverse
RSA-Problem
Gegeben sind der öffentliche Schlüssel $(e,N)$ sowie der Geheimtext $c$ . Gesucht wird der Klartext $m$ wobei gilt: $m^{e}\equiv c{\bmod {N}}$ . Das Problem liegt hier in der Schwierigkeit, $e$ -te Wurzeln modulo $N$ zu ziehen oder das multiplikative Inverse von $e$ zu bestimmen^[1]^[2].
Multiplikative Inverse
Die Restklasse $[a]_{m}$ ist genau dann invertierbar in $\mathbb {Z} /m\mathbb {Z}$ , wenn gilt $ggT(a,m)=1$ und die Lösung $[s]_{m}$ der Kongruenz $as\equiv 1{\bmod {m}}$ ist eindeutig bestimmt und wir nennen diese multiplikative Inverse von $[a]_{m}$ ^[3].

Im Gegensatz zur Korrektheit des RSA-Kryptosystems, können wir die Sicherheit des RSA-Kryptosystems nicht beweisen^[4]. Wie bereits auf der Übersichtsseite zum RSA-Kryptosystem besprochen, beruht die Sicherheit des RSA-Kryptosystems zunächst auf dem RSA-Problem^[2].

Wir wollen nun zeigen, dass das Bestimmen des multiplikativen Inversen $d$ von $e$ ebenso schwer ist, wie das Faktorisierungsproblem.

Faktorisierungsproblem

Das Faktorisierungsproblem besteht seit Jahrhunderten^[5]. Bei diesem sollen für eine zusammengesetzte Zahl $n$ Teiler gefunden werden, die weder $1$ noch $n$ sind^[2]. Es gibt bisher jedoch keinen effizienten Faktorisierungsalgorithmus zum Lösen des Faktorisierungsproblems für beliebige $n$ ^[6].

Die Sicherheit des RSA-Algorithmus beruht heute vor allem auf dem RSA- bzw. Faktorisierungsproblem^[2]. Könnte ein Angreifer die Primfaktoren des RSA-Modul $N=p\cdot q$ berechnen, so könnte dieser den kompletten Schlüsselerzeugungsalgorithmus des Empfängers nachvollziehen^[4]. Der Angreifer benötigt hierfür zwar den Verschlüsselungsexponenten $e$ , aber diesen hat der Empfänger beim RSA-Verschlüsselungsverfahren öffentlich zur Verfügung gestellt^[7].

Bemerkung: Es gibt unterschiedliche Faktorisierungsalgorithmen, die effizient versuchen Teiler von $n$ zu finden und dabei entweder von den Größe von $n$ oder dessen Teilern abhängen^[8]. Beispiele für solche Algorithmen sind Pollard- $p-1$ -Methode^[9]^[10], das Quadratisches Sieb^[11]^[12] und die Methode der elliptischen Kurven^[13].

Sicherheit des privaten Schlüssels $(d,N)$

Um die Sicherheit des privaten Schlüssels zu untersuchen, wollen wir zeigen, dass das RSA-Kryptosystem die Public-Key-Eigenschaft erfüllt, d.h. dass es praktisch unmöglich ist von dem öffentlichen auf den privaten Schlüssel zu schließen^[14]. Wir orientieren uns dabei an den Bezeichnungen des RSA-Verschlüsselungsverfahrens.

Wie im Abschnitt Faktorisierungsproblem thematisiert, beruht die Sicherheit des RSA-Verschlüsselungsverfahrens vor allem auf der Schwierigkeit große Zahlen, wie $N$ , zu faktorisieren und der Schwierigkeit vom öffentlichen Verschlüsselungsexponenten $e$ auf den privaten Entschlüsselungsexponenten $d$ zu schließen^[15]. Es stellt sich nun die Frage, welche der beiden Herausforderungen im Allgemeinen schwerer zu bewerkstelligen ist. Wir beantworten diese Frage, indem wir zeigen, dass beide Probleme äquivalent zueinander sind. Die Berechnung des Entschlüsselungsexponenten $d$ ist also nicht leichter als die Faktorisierung von $N$ .

Wir zeigen folgende Äquivalenz:

Seien $N$ und der öffentliche Verschlüsselungsexponent $e$ gegeben, dann sind für einen effizienten Angreifer folgenden Aussagen äquivalent

Der Angreifer kann die Primfaktoren $p$ und $q$ berechnen
Der Angreifer kann den privaten Entschlüsselungsexponenten $d$ mit $de\equiv 1{\bmod {\varphi }}(N)$ berechnen^[16]

Gelingt es uns diese Äquivalenz zu zeigen, dann wissen wir, dass nur ein Angreifer den privaten Entschlüsselungsexponenten $d$ berechnen kann, der auch $N$ faktorisieren kann. Nach dem Faktorisierungsproblem gehen wir jedoch davon aus, dass für ausreichend große und zufällige Primzahlen kein effizienter Algorithmus zur Faktorisierung von $N$ bekannt ist. Folglich ist auch kein Algorithmus zur Bestimmung des Entschlüsselungsexponenten $d$ bekannt, der ohne $\varphi (N)$ auskommt. Die Bestimmung des privaten Schlüssels $(d,N)$ aus $N$ und $e$ ist somit genauso schwierig, wie Faktorisierung von $N$ ^[17].

Achtung! Die Äquivalenz beweist nicht, dass das RSA-Kryptosystem sicher ist! Das Faktorisierungsproblem besteht seit mehreren Jahrhunderten, aber es ist denkbar, dass es gelöst wird. Außerdem könnte eine weitere Möglichkeit entdeckt werden, die unabhängig von dem Faktorisierungsproblem ist und das RSA-Kryptosystem knackt^[5].

Beweis der Äquivalenz

$1.\Rightarrow 2.:$

Voraussetzung

Seien $N$ , $e$ , $p$ und $q$ bekannt.

Zu zeigen

Wir können den privaten Entschlüsselungsexponenten $d$ mit $d\cdot e\equiv 1{\bmod {\varphi }}(N)$ berechnen.

Beweis

Nach Schritt 5 des Schlüsselerzeugungsalgorithmus wissen wir, dass der private Schlüssel $(d,N)$ durch Lösen der Kongruenz $de\equiv 1{\bmod {\varphi }}(N)$ berechnet werden kann, wenn die Primfaktoren $p$ und $q$ und der öffentliche Verschlüsselungsexponent $e$ bekannt sind.

$2.\Rightarrow 1.:$

Voraussetzung

Seien $N$ , $e$ , und $d$ bekannt.

Zu zeigen

Wir können die Primfaktoren $p$ und $q$ berechnen.

Beweis

Wir beschreiben einen Algorithmus, der mit den Informationen $N$ , $e$ und $d$ in der Lage ist, $p$ bzw. $q$ zu bestimmen.

Wir setzen zunächst

$j=max\{v\in \mathbb {N} :2^{v}\mid (ed-1)\}$

und

$k={\frac {ed-1}{2^{j}}}$ ^[16]

und zeigen folgenden Hilfssatz, den wir später im Satz Bestimmung eines Primfaktors aus $N$ , $e$ und $d$ nutzen.

Hilfssatz

Für alle Zahlen $a\in \mathbb {Z}$ mit $ggT(a,N)=1$ gilt $ord([a^{k}]_{N})\in \{2^{i}{\text{ mit }}0\leq i\leq j\}$ ^[16].

Korrektheit des RSA-Kryptosystems, (Satz zur) Ordnung von Elementen in Gruppen
Korrektheit des RSA-Kryptosysems
Seien $p,q$ prim, $N=p\cdot q$ , $m\in \mathbb {Z} /N\mathbb {Z}$ , $e\in (\mathbb {Z} /\varphi (N)\mathbb {Z} ,\odot )$ und $e\cdot d\equiv 1{\bmod {\varphi (N)}}$ , dann gilt für alle $m\in \mathbb {Z} /N\mathbb {Z}$ : $c^{d}\equiv (m^{e})^{d}\equiv m^{e\cdot d}\equiv (m^{d})^{e}\equiv m{\bmod {N}}$ ^[18]
Ordnung von Elementen in Gruppen
Seien $a\in G$ und $e\in \mathbb {N}$ . Wenn es ein ${\ce {e}}$ gibt, sodass $a^{e}=1$ gilt, dann heißt die kleinste derartige Zahl Ordnung von $a$ in $G$ und wird als $ord_{G}(a)$ geschrieben^[19].
Satz zur Ordnung von Elementen in Gruppen
Seien $a\in G$ und $e\in \mathbb {Z}$ . Es gilt $a^{e}=1$ genau dann, wenn $ord_{G}(a)\mid e$ ^[19].

Beweis Hilfssatz

Voraussetzung

Sei $a\in \mathbb {Z}$ mit $ggT(a,N)=1$

Zu zeigen

$ord([a^{k}]_{N})\in \{2^{i}{\text{ mit }}0\leq i\leq j\}$

Beweis

Sei $a\in \mathbb {Z}$ mit $ggT(a,N)=1$ . Aus der Korrektheit des RSA-Verfahrens wissen wir, dass $a^{ed}\equiv a{\bmod {N}}$ gilt.

Durch Multiplikation mit $a^{-1}$ ergibt sich nach den Potenzgesetzen:

$a^{ed-1}\equiv 1{\bmod {N}}$ .

Da wir $k={\frac {ed-1}{2^{j}}}$ mit $j=max\{v\in \mathbb {N} :2^{v}\mid (ed-1)\}$ gesetzt haben, können wir dies nun nach $ed-1$ umformen, dann einsetzen und erhalten

$(a^{k})^{2^{j}}\equiv 1{\bmod {N}}$ .

Nach dem Satz zur Ordnung von Elementen in Gruppen folgt, dass

$ord([a^{k}]_{N})\mid 2^{j}$

und somit $ord([a^{k}]_{N})\in \{2^{i}{\text{ mit }}0\leq i\leq j\}$ ■^[16]

Wir betrachten nun einen Satz, welcher die Grundlage für einen Algorithmus bildet, mit dem man aus $N$ , $e$ und $d$ einen Primfaktor von $N=p\cdot q$ bestimmen kann.

Satz Bestimmung eines Primfaktors aus $N$ , $e$ und $d$

Sei $a\in \mathbb {Z}$ mit $ggT(a,N)=1$ .

Wenn $ord(a^{k}{\bmod {p}})\neq ord(a^{k}{\bmod {q}})$ , dann gilt $1<ggT(a^{2^{v}k}-1,N)<N$ für ein $v\in \{0,1,2,\dots ,j-1\}$ ^[16].

Beweis Bestimmung eines Primfaktors aus $N$ , $e$ und $d$

Voraussetzung

Sei $a\in \mathbb {Z}$ mit $ggT(a,N)=1$ und $ord(a^{k}{\bmod {p}})\neq ord(a^{k}{\bmod {q}})$ , wobei

$j=max\{v\in \mathbb {N} :2^{v}\mid (ed-1)\}$ und $k={\frac {ed-1}{2^{j}}}$

Zu zeigen

$1<ggT(a^{2^{v}k}-1,N)<N$ für ein $v\in \{0,1,2,\dots ,j-1\}$

Beweis

Betrachten wir zunächst $a^{k}{\bmod {p}}$ und $a^{k}{\bmod {q}}$ .

Da $ggt(a,N)=ggT(a,p\cdot q)=1$ , wissen wir, dass $ggT(a,p)=1=ggT(a,q)$ und wir können den Hilfssatz anwenden:

$ord(a^{k}{\bmod {p}})\in \{2^{i}{\text{ mit }}0\leq i\leq j\}$

und

$ord(a^{k}{\bmod {q}})\in \{2^{i}{\text{ mit }}0\leq i\leq j\}$ .

Hilfssatz Sicherheit des RSA-Kryptosystems, (Satz zur) Ordnung von Elementen in Gruppen
Hilfssatz Sicherheit des RSA-Kryptosystems
Für alle Zahlen $a\in \mathbb {Z}$ mit $ggT(a,N)=1$ gilt $ord([a^{k}]_{N})\in \{2^{i}{\text{ mit }}0\leq i\leq j\}$ ^[16].
Ordnung von Elementen in Gruppen
Seien $a\in G$ und $e\in \mathbb {N}$ . Wenn es ein ${\ce {e}}$ gibt, sodass $a^{e}=1$ gilt, dann heißt die kleinste derartige Zahl Ordnung von $a$ in $G$ und wird als $ord_{G}(a)$ geschrieben^[19].
Satz zur Ordnung von Elementen in Gruppen
Seien $a\in G$ und $e\in \mathbb {Z}$ . Es gilt $a^{e}=1$ genau dann, wenn $ord_{G}(a)\mid e$ ^[19].

Sei nun nach Voraussetzung $ord(a^{k}{\bmod {p}})\neq ord(a^{k}{\bmod {q}})$ , genauer

$ord(a^{k}{\bmod {q}})<ord(a^{k}{\bmod {p}})$

und

$ord(a^{k}{\bmod {q}})=2^{v}$ .

Dann folgt $v<j$ bzw. $v\in \{0,1,2,\dots ,j-1\}$ .

Wir zeigen nun, dass $a^{2^{v}k}\equiv 1{\bmod {q}}$ und $a^{2^{v}k}\not \equiv 1{\bmod {p}}$ .

Nach Definition der Ordnung von Elementen in Gruppen gilt

$a^{2^{v}}\equiv 1{\bmod {q}}$

und nach Potenzieren mit $k$ folgt

$a^{2^{v}k}\equiv 1{\bmod {q}}$ , da $(a^{2^{v}})^{k}=a^{2^{v}k}$ und $1^{k}=1$ .

Da $ord(a^{k}{\bmod {q}})<ord(a^{k}{\bmod {p}})$ , folgt

$a^{2^{v}k}\not \equiv 1{\bmod {p}}$

Wir können $a^{2^{v}k}\equiv 1{\bmod {q}}$ umstellen und erhalten

$a^{2^{v}k}-1\equiv 0{\bmod {q}}$ .

Es folgt

$ggT(a^{2^{v}k}-1,N)=q$ ^[16].

Wir haben somit gezeigt, dass man mit den Informationen $N$ , $e$ und $d$ in der Lage ist, einen Primfaktor von $N$ zu bestimmen.

Der zugehörige Algorithmus geht wie folgt vor:

Wir wählen ein zufälliges $a\in \{1,2,\dots ,N-1\}$
Wir berechnen $ggT(a,N)$
Fallunterscheidung
1. Ist $ggT(a,N)\neq 1$ $ggT(a,N)\neq 1$
  - Dann ist $ggT(a,N)$ ein Primfaktor von $N$
  - Der Algorithmus bricht ab und $ggT(a,N)$ wird ausgegeben
2. Ist $ggT(a,N)=1$ $ggT(a,N)=1$
  - Dann fährt der Algorithmus mit Schritt 4 fort
Wir berechnen $ggT(a^{2^{v}k}-1,N)$ für alle $v\in \{j-1,j-2,\dots ,0\}$
Fallunterscheidung
1. Ist $ggT(a^{2^{v}k}-1,N)\neq 1$ $ggT(a^{2^{v}k}-1,N)\neq 1$ ,
  - Dann ist $ggT(a^{2^{v}k}-1,N)$ ein Primfaktor von $N$
  - Der Algorithmus bricht ab $ggT(a^{2^{v}k}-1,N)$ wird ausgegeben
2. Ist $ggT(a^{2^{v}k}-1,N)=1$ $ggT(a^{2^{v}k}-1,N)=1$ für alle $v\in \{j-1,j-2,\dots ,0\}$ $v\in \{j-1,j-2,\dots ,0\}$
  - Dann hat der Algorithmus in diesem Durchlauf keinen Primfaktor von $N$ gefunden
  - Der Algorithmus wird mit einem neuen $a\in \{1,2,\dots ,N-1\}$ wiederholt

Bemerkung: Die Erfolgswahrscheinlichkeit des Algorithmus ist pro Durchführung mindestens 50%, sodass wir durch mehrfaches Ausführen des Algorithmus einen Primfaktor von dem RSA-Modul $N$ finden^[20]. Da der Beweis der Erfolgswahrscheinlichkeit weitere neue Grundlagen benötigt^[21], beschränken wir uns hier auf die Anwendung des Algorithmus'.

Da $N=p\cdot q$ können wir den unbekannten Primfakor durch Einsetzen von $N$ und dem bekannten Primfakor leicht berechnen■^[16]

Bemerkung: Nach dem RSA-Problem, könnte die Berechnung der $e$ -ten Wurzel das RSA-Kryptosystem ebenfalls knacken. Es wird aktuell angenommen, dass dies etwa so schwer ist, wie das Faktorisierungsproblem zu lösen. Ein Beweis steht jedoch noch aus^[22]^[23].

Lernempfehlung

Kursübersicht
Übergeordnete Lerneinheit
11: Kryptoanalyse
Vorherige Lerneinheit	Aktuelle Lerneinheit	Empfohlene Lerneinheit
11: Kryptoanalyse	12: Sicherheit des RSA-Kryptosystems	13: Angriff auf das RSA-Verschlüsselungsverfahren

Literatur

↑ Seite „RSA-Kryptosystem“. In: Wikipedia, Die freie Enzyklopädie. Bearbeitungsstand: 15. Dezember 2019, 19:39 UTC. URL: https://de.wikipedia.org/w/index.php?title=RSA-Kryptosystem&oldid=194933568 (Abgerufen: 27. Januar 2020, 14:29 UTC; Formulierung verändert)
↑ ^2,0 ^2,1 ^2,2 ^2,3 Hinek, M. J. (2009). Cryptanalysis of RSA and Its Variants. CRC Press. S. 8.
↑ Buchmann, J. (2016). Einführung in die Kryptographie (6. Aufl.). Berlin, Heidelberg: Springer. S. 43.
↑ ^4,0 ^4,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. 125.
↑ ^5,0 ^5,1 Buchmann, J. (2016). Einführung in die Kryptographie (6. Aufl.). Springer. S. 172.
↑ Rothe, J. (2008). Komplexitätstheorie und Kryptologie: Eine Einführung in Kryptokomplexität. Springer. S. 376.
↑ 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. 122.
↑ Yan, S., Y. (2009). Primality Testing and Integer Factorization in Public-Key Cryptography (2. Aufl.). Springer Science+Business Media, LLC. S. 208.
↑ Seite „Pollard-p − 1-Methode“. In: Wikipedia, Die freie Enzyklopädie. Bearbeitungsstand: 22. Januar 2020, 19:04 UTC. URL: https://de.wikipedia.org/w/index.php?title=Pollard-p_%E2%88%92_1-Methode&oldid=196076553 (Abgerufen: 27. Januar 2020, 13:21 UTC)
↑ PL1
↑ Seite „Quadratisches Sieb“. In: Wikipedia, Die freie Enzyklopädie. Bearbeitungsstand: 27. Dezember 2019, 16:04 UTC. URL: https://de.wikipedia.org/w/index.php?title=Quadratisches_Sieb&oldid=195259282 (Abgerufen: 27. Januar 2020, 13:22 UTC)
↑ PL2
↑ 2
↑ Diffie, W., & Hellman, M. (1976). New directions in cryptography. IEEE Transactions on Information Theory, 22(6) (S. 644–654). S. 644.
↑ 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. 120.
↑ ^16,0 ^16,1 ^16,2 ^16,3 ^16,4 ^16,5 ^16,6 ^16,7 Buchmann, J. (2016). Einführung in die Kryptographie (6. Aufl.). Springer. S. 173.
↑ Beutelspacher, A., Neumann, H. B., & Schwarzpaul, T. (2010). Kryptografie in Theorie und Praxis: Mathematische Grundlagen für Internetsicherheit, Mobilfunk und elektronisches Geld (2., überarb. Aufl). Vieweg + Teubner. S. 125.
↑ 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.
↑ ^19,0 ^19,1 ^19,2 ^19,3 Buchmann, J. (2016). Einführung in die Kryptographie (6. Aufl.). Springer. S. 47.
↑ Douglas R. Stinson. (1995). Cryptography. Theory and Practice. CRC Press LLC. S. 141.
↑ Buchmann, J. (2016). Einführung in die Kryptographie (6. Aufl.). Springer. S. 174.
↑ 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. 126.
↑ Boneh, D. (1999). Twenty Years of Attacks on the RSA Cryptosystem. 46(2). S. 204.

[:12-1] Seite „RSA-Kryptosystem“. In: Wikipedia, Die freie Enzyklopädie. Bearbeitungsstand: 15. Dezember 2019, 19:39 UTC. URL: https://de.wikipedia.org/w/index.php?title=RSA-Kryptosystem&oldid=194933568 (Abgerufen: 27. Januar 2020, 14:29 UTC; Formulierung verändert)

[:05-2] 2,0 ^2,1 ^2,2 ^2,3 Hinek, M. J. (2009). Cryptanalysis of RSA and Its Variants. CRC Press. S. 8.

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

[:2-4] 4,0 ^4,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. 125.

[:1-5] 5,0 ^5,1 Buchmann, J. (2016). Einführung in die Kryptographie (6. Aufl.). Springer. S. 172.

[6] Rothe, J. (2008). Komplexitätstheorie und Kryptologie: Eine Einführung in Kryptokomplexität. Springer. S. 376.

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

[8] Yan, S., Y. (2009). Primality Testing and Integer Factorization in Public-Key Cryptography (2. Aufl.). Springer Science+Business Media, LLC. S. 208.

[9] Seite „Pollard-p − 1-Methode“. In: Wikipedia, Die freie Enzyklopädie. Bearbeitungsstand: 22. Januar 2020, 19:04 UTC. URL: https://de.wikipedia.org/w/index.php?title=Pollard-p_%E2%88%92_1-Methode&oldid=196076553 (Abgerufen: 27. Januar 2020, 13:21 UTC)

[10] PL1

[11] Seite „Quadratisches Sieb“. In: Wikipedia, Die freie Enzyklopädie. Bearbeitungsstand: 27. Dezember 2019, 16:04 UTC. URL: https://de.wikipedia.org/w/index.php?title=Quadratisches_Sieb&oldid=195259282 (Abgerufen: 27. Januar 2020, 13:22 UTC)

[12] PL2

[13] 2

[14] Diffie, W., & Hellman, M. (1976). New directions in cryptography. IEEE Transactions on Information Theory, 22(6) (S. 644–654). S. 644.

[15] 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. 120.

[:0-16] 16,0 ^16,1 ^16,2 ^16,3 ^16,4 ^16,5 ^16,6 ^16,7 Buchmann, J. (2016). Einführung in die Kryptographie (6. Aufl.). Springer. S. 173.

[17] Beutelspacher, A., Neumann, H. B., & Schwarzpaul, T. (2010). Kryptografie in Theorie und Praxis: Mathematische Grundlagen für Internetsicherheit, Mobilfunk und elektronisches Geld (2., überarb. Aufl). Vieweg + Teubner. S. 125.

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

[:04-19] 19,0 ^19,1 ^19,2 ^19,3 Buchmann, J. (2016). Einführung in die Kryptographie (6. Aufl.). Springer. S. 47.

[20] Douglas R. Stinson. (1995). Cryptography. Theory and Practice. CRC Press LLC. S. 141.

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

[22] 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. 126.

[23] Boneh, D. (1999). Twenty Years of Attacks on the RSA Cryptosystem. 46(2). S. 204.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]

Einleitung

Faktorisierungsproblem

Sicherheit des privaten Schlüssels ( d , N ) {\displaystyle (d,N)}

Beweis der Äquivalenz

Hilfssatz

Satz Bestimmung eines Primfaktors aus N {\displaystyle N} , e {\displaystyle e} und d {\displaystyle d}

Beweis Bestimmung eines Primfaktors aus N {\displaystyle N} , e {\displaystyle e} und d {\displaystyle d}

Lernempfehlung

Literatur

Sicherheit des privaten Schlüssels $(d,N)$

Satz Bestimmung eines Primfaktors aus $N$ , $e$ und $d$

Beweis Bestimmung eines Primfaktors aus $N$ , $e$ und $d$