Kryptologie/Angriff auf das RSA-Verschlüsselungsverfahren

Aus Wikiversity
Zur Navigation springen Zur Suche springen


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 und paarweise teilerfremd, sowie mit , wobei .

Es gelte außerdem nach dem Verschlüsselungsalgorithmus des RSA-Verschlüsselungsverfahrens mit .

Dann gilt:

[5].

Beweis Low-Exponent-Angriff

Teilerfremdheit und chinesischer Restsatz
Teilerfremdheit
Zwei ganze Zahlen und , wobei mindestens einer der beiden Zahlen ungleich Null ist,

heißen teilerfremd, wenn [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 paarweise teilerfremd in , und .

Dann existiert eine Lösung , sodass für jedes die Kongruenz

gilt.

Darüber hinaus ist jedes genau dann eine Lösung der Kongruenz ,

wenn gilt mit [8].

Betrachten wir eine Zahl .

Es gilt nach Voraussetzung und .

Es ist also und .

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

[5].

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

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

,

,

.

Wir nehmen an, dass , und teilerfremd sind, da die Primfaktoren von , und zufällig gewählt wurden. Außerdem soll gelten , da wir sonst die Bedingungen des RSA-Verschlüsselungsverfahren verletzen.

Nun wendet der Angreifer den chinesischen Restsatz an und erhält die Lösung des Systems mit [3].

Es kann den Geheimtext nun, nach dem Satz zum Low-Exponent-Angriff, entschlüsseln, indem der Angreifer nach auflöst:

.

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 paarweise teilerfremd in , und .

Dann existiert eine Lösung , sodass für jedes die Kongruenz

gilt.

Darüber hinaus ist jedes genau dann eine Lösung der Kongruenz ,

wenn gilt mit [8].

Erweiterte euklidische Algorithmus
Der erweiterte euklidische Algorithmus wird auf zwei Zahlen angewandt und besteht aus zwei Teilen:
  1. Berechnung des (auch als euklidischer Algorithmus bekannt[10]),
  2. Berechnung zweier ganzer Zahlen und , welche die Gleichung erfüllen[11].
Kongruenz
Seien und , dann gilt [12].
Satz Low Exponent Angriff
Seien und paarweise teilerfremd, sowie mit , wobei .

Es gelte außerdem nach dem Verschlüsselungsalgorithmus des RSA-Verschlüsselungsverfahrens

mit . Dann gilt: [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 verschlüsselt.

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 und .

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

, da ,

, da ,

, da .

Die gesuchte Lösung mit lautet:

.

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

Wir beginnen mit

, wegen

, wegen

.

Nun folgt die zweite Gleichung

, wegen

, wegen

, wegen

Zuletzt noch die dritte Gleichung

, wegen

Wir erhalten die Lösung

.

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

Da , müssen wir noch ein kleineres mit finden.

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

.

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 mindestens ebenfalls dem Verschlüsselungsexponenten entsprechen muss. Man könnte also einen größeren Exponenten wählen, sodass die Anzahl der Kongruenzen des Systems kleiner ist.

Bemerkung: In der Praxis gilt 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 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 .

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

  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.
  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.
  5. 5,0 5,1 5,2 5,3 5,4 Buchmann, J. (2016). Einführung in die Kryptographie (6. Aufl.). Springer. S. 175.
  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.
  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)
  8. 8,0 8,1 Shoup, V. (2008). A Computational Introduction to Number Theory and Algebra (2. Aufl.). S. 23.
  9. https://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.
  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.