Kryptologie/Angriff auf das RSA-Verschlüsselungsverfahren

Einleitung

In einigen Spezialfällen kann man das RSA-Kryptosystem brechen, ohne das Faktorisierungsproblem gelöst zu haben^[1]^[2]. Ein solches Beispiel von vielen ist der Low-Exponent-Angriff^[3]. Es handelt sich dabei um keinen direkten Angriff auf das RSA-Kryptosystem. Stattdessen nutzt man die falsche Verwendung des RSA-Kryptosystems in bestimmten Kontexten^[4]. Wir wollen dies am Beispiel des Low-Exponent-Angriffs veranschaulichen^[5].

Low-Exponent-Angriff

Formal beruht der Low Exponent-Angriff auf dem folgenden Satz^[5]:

Satz Low-Exponent-Angriff

Seien $e,c\in \mathbb {N}$ und $N_{1},N_{2},\dots N_{e}\in \mathbb {N}$ paarweise teilerfremd, sowie $m\in \mathbb {N}$ mit $0\leq m\leq N_{j}$ , wobei $0\leq j\leq e$ .

Es gelte außerdem $c=m^{e}{\bmod {N}}_{j}$ nach dem Verschlüsselungsalgorithmus des RSA-Verschlüsselungsverfahrens mit $0\leq c<N_{1}N_{2}\cdots N_{e}$ .

Dann gilt:

$c=m^{e}$ ^[5].

Beweis Low-Exponent-Angriff

Teilerfremdheit und chinesischer Restsatz
Teilerfremdheit
Zwei ganze Zahlen $a$ und $b$ , wobei mindestens einer der beiden Zahlen ungleich Null ist, heißen teilerfremd, wenn $ggT(a,b)=1$ ^[6]. Betrachten wir mehr als zwei Zahlen, dann nennen wir diese paarweise teilerfremd, wenn je zwei beliebige von diesen Zahlen zueinander teilerfremd sind^[7]^[6].
Chinesische Restsatz
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. Darüber hinaus ist jedes $g\in \mathbb {Z}$ genau dann eine Lösung der Kongruenz $b\equiv a_{i}{\bmod {c}}_{i}$ , wenn gilt $g\equiv b{\bmod {c}}$ mit $c=c_{1}\cdot c_{2}\cdot \dots \cdot c_{v}$ ^[8].

Betrachten wir eine Zahl $c'=m^{e}$ .

Es gilt nach Voraussetzung $0\leq m\leq N_{j}$ und $0\leq j\leq e$ .

Es ist also $c'\equiv m^{e}{\bmod {N}}_{j}$ und $0\leq c_{1}<N_{1}N_{2}\cdots N_{e}$ .

$c_{1}\equiv m^{e}{\bmod {N}}_{1}$

$c_{2}\equiv m^{e}{\bmod {N}}_{2}$

$\dots$

$c_{e}\equiv m^{e}{\bmod {N}}_{e}$

Dieses System hat nach dem chinesischen Restsatz die eindeutige Lösung

$c'=c$ ^[5].

Low-Exponent-Angriff auf das RSA-Verschlüsselungsverfahren

Angenommen ein Sender schickt einen Klartext $m$ an mehrere Empfänger und unter diesen Empfängern $1$ , $2$ und $3$ gibt es mindestens $e=3$ Empfänger, die - beispielsweise aus Effizienzgründen - den Verschlüsselungsexponenten $e=3$ verwenden. Es ist einem Angreifer, der die zugehörten Geheimtexten $c_{1}$ , $c_{2}$ und $c_{3}$ abfängt, möglich den Klartext $m$ mit Hilfe des chinesischen Restsatzes zu bestimmen, denn der Angreifer weiß, dass folgendes System existiert:

$c_{1}=m^{3}{\bmod {N}}_{1}$ ,

$c_{2}=m^{3}{\bmod {N}}_{2}$ ,

$c_{3}=m^{3}{\bmod {N}}_{3}$ .

Wir nehmen an, dass $N_{1}$ , $N_{2}$ und $N_{3}$ teilerfremd sind, da die Primfaktoren von $N_{1}$ , $N_{2}$ und $N_{3}$ zufällig gewählt wurden. Außerdem soll gelten $m<min\{N_{1}N_{2}N_{3}\}$ , da wir sonst die Bedingungen des RSA-Verschlüsselungsverfahren verletzen.

Nun wendet der Angreifer den chinesischen Restsatz an und erhält die Lösung $c=m^{e}$ des Systems $c\equiv c_{i}{\bmod {N}}_{i}$ mit $i\in \{1,2,3\}$ ^[3].

Es kann den Geheimtext $c$ nun, nach dem Satz zum Low-Exponent-Angriff, entschlüsseln, indem der Angreifer $c=m^{3}$ nach $m$ auflöst:

$m={\sqrt[{3}]{c}}$ .

Bemerkung: Es gibt noch viele weitere potenzielle Angriffe auf das RSA-Kryptosystem und bei Interesse kann man diverse Übersichtsarbeiten, wie beispieleweise Twenty Years of Attacks on the RSA Cryptosystem von D. Boneh^[9] studieren.

Lernaufgabe

Aufgabe 1

Nützliche Definitionen und Sätze
Chinesische Restsatz
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. Darüber hinaus ist jedes $g\in \mathbb {Z}$ genau dann eine Lösung der Kongruenz $b\equiv a_{i}{\bmod {c}}_{i}$ , wenn gilt $g\equiv b{\bmod {c}}$ mit $c=c_{1}\cdot c_{2}\cdot \dots \cdot c_{v}$ ^[8].
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^[10]), Berechnung zweier ganzer Zahlen $s$ und $t$ , welche die Gleichung $\operatorname {ggT} (a,b)=s\cdot a+t\cdot b$ erfüllen^[11].
Kongruenz
Seien $a,b\in \mathbb {Z}$ und $m\in \mathbb {N}$ , dann gilt $a\equiv b{\bmod {m}}\Leftrightarrow m\mid (a-b)$ ^[12].
Satz Low Exponent Angriff
Seien $e,c\in \mathbb {N}$ und $N_{1},N_{2},\dots N_{e}\in \mathbb {N}$ paarweise teilerfremd, sowie $m\in \mathbb {N}$ mit $0\leq m\leq N_{j}$ , wobei $0\leq j\leq e$ . Es gelte außerdem $c=m^{e}{\bmod {N}}_{j}$ nach dem Verschlüsselungsalgorithmus des RSA-Verschlüsselungsverfahrens mit $0\leq c<N_{1}N_{2}\cdots N_{e}$ . Dann gilt: $c=m^{e}$ ^[5].

Sie sind Kryptoanalyst in einem Kriminalfall und sollen herausfinden um wie viel Uhr die kriminellen Übergabe heute stattfinden wird.

Sie haben folgende Geheimtexte mit vermutlich identischem Klartext abgefangen und die zugehörige Kongruenz aufgestellt. Alle drei Geheimtexte wurden mit dem Verschlüsselungsexponenten $e=3$ verschlüsselt.

$m^{3}\equiv 25{\bmod {5}}1$

$m^{3}\equiv 34{\bmod {6}}5$

$m^{3}\equiv 6{\bmod {7}}7$

Berechnen Sie mittels des Low-Exponent-Angriff den Klartext.

Lösung

Wir nehmen an, dass die Voraussetzungen des Low-Exponent-Angriffs erfüllt sind.

Es gilt also $ggT(51,65)=ggT(51,77)=ggT(65,77)=1$ und $m<51$ .

Wir können nun den chinesischen Restsatz anwenden und wir stellen die zugehörigen Gleichungen auf:

$1=r_{1}\cdot 51+s_{1}\cdot 5005$ , da $C_{1}=65\cdot 77$ ,

$1=r_{2}\cdot 65+s_{2}\cdot 3927$ , da $C_{2}=51\cdot 77$ ,

$1=r_{3}\cdot 77+s_{3}\cdot 3315$ , da $C_{3}=51\cdot 65$ .

Die gesuchte Lösung mit $e_{i}=s_{i}\cdot C_{i}$ lautet:

$c:=\sum _{i=1}^{3}c_{i}e_{i}$ .

Um die Lösung zu bestimmen, wenden wir den erweiterten euklidischen Algorithmus an:

Wir beginnen mit $1=r_{1}\cdot 51+s_{1}\cdot 5005$

$\Rightarrow 5005=98\cdot 51+7$

$\Leftrightarrow 51=7\cdot 7+2$

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

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

$\Leftrightarrow 1=7-3\cdot (51-7\cdot 7)$ , wegen $5005=98\cdot 51+7$

$\Leftrightarrow 1=-3\cdot 51+22\cdot 7$

$\Leftrightarrow 1=-3\cdot 51+22\cdot (5005-98\cdot 51)$ , wegen $5005=98\cdot 51+7$

$\Leftrightarrow 1=-2159\cdot 51+22\cdot 5005$

$\Rightarrow r_{1}=-2159,s_{1}=22$

$\Rightarrow e_{1}=22\cdot 5005=110110$ .

Nun folgt die zweite Gleichung $1=r_{2}\cdot 65+s_{2}\cdot 3927$

$\Rightarrow 3927=60\cdot 65+27$

$\Leftrightarrow 65=2\cdot 27+11$

$\Leftrightarrow 27=2\cdot 11+5$

$\Leftrightarrow 11=2\cdot 5+1$

$\Leftrightarrow 1=11-2\cdot 5$

$\Leftrightarrow 1=11-2\cdot (27-2\cdot 11)$ , wegen $27=2\cdot 11+5$

$\Leftrightarrow 1=5\cdot 11-2\cdot 27$

$\Leftrightarrow 1=5\cdot (65-2\cdot 27)-2\cdot 27$ , wegen $65=2\cdot 27+11$

$\Leftrightarrow 1=5\cdot 65-12\cdot 27$

$\Leftrightarrow 1=5\cdot 65-12\cdot (3927-60\cdot 65)$ , wegen $3927=60\cdot 65+27$

$\Leftrightarrow 1=725\cdot 65-12\cdot 3927$

$\Rightarrow r_{2}=725,s_{2}=-12$

$\Rightarrow e_{2}=-12\cdot 3927=47124$

Zuletzt noch die dritte Gleichung $1=r_{3}\cdot 77+s_{3}\cdot 3315$

$\Rightarrow 3315=43\cdot 77+4$

$\Leftrightarrow 77=19\cdot 4+1$

$\Leftrightarrow 1=77-19\cdot 4$

$\Leftrightarrow 1=77-19\cdot (3315-43\cdot 77)$ , wegen $3315=43\cdot 77+4$

$\Leftrightarrow 1=818\cdot 77-19\cdot 3315$

$\Rightarrow r_{3}=818,s_{3}=-19$

$\Rightarrow e_{3}=-19\cdot 3315=-62985$

Wir erhalten die Lösung

$c:=\sum _{i=1}^{3}c_{i}e_{i}=25\cdot 110110+34\cdot 47124+6\cdot (-62985)=772624$ .

Man kann nun optional kontrollieren, dass die folgenden Kongruenzen tatsächlich stimmen.

$772624\equiv 25{\bmod {5}}1$

$772624\equiv 34{\bmod {6}}5$

$772624\equiv 6{\bmod {7}}7$

Da $772624>255255=51\cdot 65\cdot 77$ , müssen wir noch ein kleineres $c$ mit $c\in [772624]_{255255}$ finden.

$c=772624\equiv 6859{\bmod {2}}55255$

Da nach dem Satz zum Low-Exponent-Angriff gilt:

$m={\sqrt[{3}]{c}}$

$\Rightarrow m={\sqrt[{3}]{6859}}=6859^{\tfrac {1}{3}}=19$ .

Die Übergabe wird folglich vermutlich um 19 Uhr stattfinden.

Aufgabe 2

Erläutern Sie bis zu zwei Möglichkeiten, wie der Low-Exponent-Angriff in Aufgabe 1 hätte unterbunden werden können.

Lösung

1. Möglichkeit

Betrachtet man den Satz zum Low-Exponent-Angriff, so stellt man fest, dass für den Low-Exponent-Angriff die Anzahl der Kongruenzen mit identischem Verschlüsselungsexponenten $e$ mindestens ebenfalls dem Verschlüsselungsexponenten $e$ entsprechen muss. Man könnte also einen größeren Exponenten wählen, sodass die Anzahl der Kongruenzen des Systems kleiner $e$ ist.

Bemerkung: In der Praxis gilt $e=2^{16}+1=65537$ als besonders gut geeignet, da die Zahl einen guten Kompromiss aus maximaler Sicherheit und effizientem Rechnen darstellt^[13].

2. Möglichkeit

Alternativ kann man eine andere Voraussetzung des Satzes zum Low-Exponent-Angriff verletzten, nämlich die Bedingung, dass der Klartext $m$ für alle Kongruenzen des System identisch sein muss. Man könnte also den Inhalt eines jeden Klartextes personalisieren, beispielsweise durch eine personalisierte Anrede, damit $m_{1}\neq m_{2}$ .

Bemerkung: Die Verletzung der Voraussetzung kann jedoch sogar erreicht werden, ohne den tatsächlichen Inhalt des Klartextes zu verändern. Hierfür wird in der Praxis ein variables Element (z.B. Zeitstempel, Zufallszahl, etc.) mit dem Klartext verrechnet und erst danach mit dem Verschlüsselungsexponenten verschlüsselt^[3].

Lernempfehlung

Kursübersicht
Übergeordnete Lerneinheit
11: Kryptoanalyse
Vorherige Lerneinheit	Aktuelle Lerneinheit
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)
↑ Boneh, D. (1999). Twenty Years of Attacks on the RSA Cryptosystem. 46(2), 11. S. 203.
↑ ^3,0 ^3,1 ^3,2 Moore, J. H. (1988). Protocol failures in cryptosystems. Proceedings of the IEEE, 76(5) (S. 594–602). S. 597.
↑ Moore, J. H. (1988). Protocol failures in cryptosystems. Proceedings of the IEEE, 76(5) (S. 594–602). S. 594.
↑ ^5,0 ^5,1 ^5,2 ^5,3 ^5,4 Buchmann, J. (2016). Einführung in die Kryptographie (6. Aufl.). Springer. S. 175.
↑ ^6,0 ^6,1 Burton, D. M., & Dalkowski, H. (2005). Handbuch der elementaren Zahlentheorie mit über 1000 Übungsaufgaben und ihren Lösungen. Heldermann Verlag. S. 26.
↑ 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)
↑ ^8,0 ^8,1 Shoup, V. (2008). A Computational Introduction to Number Theory and Algebra (2. Aufl.). S. 23.
↑ https://www.ams.org/notices/199902/boneh.pdf 21.01.2020 15:05
↑ Lehman, E., Leighton, T., & Meyer, A. R. (2010). Mathematics for computer science. Technical report, 2006. Lecture notes. S. 249.
↑ Kurzweil, H. (2008). Endliche Körper: Verstehen, rechnen, anwenden (2., überarb. Aufl). Springer. S. 57.
↑ Buchmann, J. (2016). Einführung in die Kryptographie (6. Aufl.). Berlin, Heidelberg: Springer. S. 37.
↑ Blakley, B., & Blakley, G. R. (1979). SECURITY OF NUMBER THEORETIC PUBLIC KEY CRYPTOSYSTEMS AGAINST RANDOM ATTACK, II. Cryptologia, 3(1) (S. 29–42). S. 38.

[: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)

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

[:0-3] 3,0 ^3,1 ^3,2 Moore, J. H. (1988). Protocol failures in cryptosystems. Proceedings of the IEEE, 76(5) (S. 594–602). S. 597.

[4] Moore, J. H. (1988). Protocol failures in cryptosystems. Proceedings of the IEEE, 76(5) (S. 594–602). S. 594.

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

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

[:55-7] 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)

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

[9] ttps://www.ams.org/notices/199902/boneh.pdf 21.01.2020 15:05

[10] Lehman, E., Leighton, T., & Meyer, A. R. (2010). Mathematics for computer science. Technical report, 2006. Lecture notes. S. 249.

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

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

[13] Blakley, B., & Blakley, G. R. (1979). SECURITY OF NUMBER THEORETIC PUBLIC KEY CRYPTOSYSTEMS AGAINST RANDOM ATTACK, II. Cryptologia, 3(1) (S. 29–42). S. 38.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]