Einleitung

RSA-Problem und multiplikative Inverse
RSA-Problem
Gegeben sind der öffentliche Schlüssel   sowie der Geheimtext  .

Gesucht wird der Klartext   wobei gilt:  .

Das Problem liegt hier in der Schwierigkeit,  -te Wurzeln modulo   zu ziehen

oder das multiplikative Inverse von   zu bestimmen[1][2].

Multiplikative Inverse
Die Restklasse   ist genau dann invertierbar in  , wenn gilt

  und die Lösung   der Kongruenz   ist

eindeutig bestimmt und wir nennen diese multiplikative Inverse von  [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   von   ebenso schwer ist, wie das Faktorisierungsproblem.

Faktorisierungsproblem

Das Faktorisierungsproblem besteht seit Jahrhunderten[5]. Bei diesem sollen für eine zusammengesetzte Zahl   Teiler gefunden werden, die weder   noch   sind[2]. Es gibt bisher jedoch keinen effizienten Faktorisierungsalgorithmus zum Lösen des Faktorisierungsproblems für beliebige  [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   berechnen, so könnte dieser den kompletten Schlüsselerzeugungsalgorithmus des Empfängers nachvollziehen[4]. Der Angreifer benötigt hierfür zwar den Verschlüsselungsexponenten  , 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   zu finden und dabei entweder von den Größe von   oder dessen Teilern abhängen[8]. Beispiele für solche Algorithmen sind Pollard- -Methode[9][10], das Quadratisches Sieb[11][12] und die Methode der elliptischen Kurven[13].

Sicherheit des privaten Schlüssels

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  , zu faktorisieren und der Schwierigkeit vom öffentlichen Verschlüsselungsexponenten   auf den privaten Entschlüsselungsexponenten   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   ist also nicht leichter als die Faktorisierung von  .

Wir zeigen folgende Äquivalenz:

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

  1. Der Angreifer kann die Primfaktoren   und   berechnen
  2. Der Angreifer kann den privaten Entschlüsselungsexponenten   mit   berechnen[16]

Gelingt es uns diese Äquivalenz zu zeigen, dann wissen wir, dass nur ein Angreifer den privaten Entschlüsselungsexponenten   berechnen kann, der auch   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   bekannt ist. Folglich ist auch kein Algorithmus zur Bestimmung des Entschlüsselungsexponenten   bekannt, der ohne   auskommt. Die Bestimmung des privaten Schlüssels   aus   und   ist somit genauso schwierig, wie Faktorisierung von  [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

 

Voraussetzung

Seien  ,  ,   und   bekannt.

Zu zeigen

Wir können den privaten Entschlüsselungsexponenten   mit   berechnen.

Beweis

Nach Schritt 5 des Schlüsselerzeugungsalgorithmus wissen wir, dass der private Schlüssel   durch Lösen der Kongruenz   berechnet werden kann, wenn die Primfaktoren   und   und der öffentliche Verschlüsselungsexponent   bekannt sind.

 

Voraussetzung

Seien  ,  , und   bekannt.

Zu zeigen

Wir können die Primfaktoren   und   berechnen.

Beweis

Wir beschreiben einen Algorithmus, der mit den Informationen  ,   und   in der Lage ist,   bzw.   zu bestimmen.

Wir setzen zunächst

 

und

 [16]

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

Hilfssatz

Für alle Zahlen   mit   gilt  [16].

Korrektheit des RSA-Kryptosystems, (Satz zur) Ordnung

von Elementen in Gruppen

Korrektheit des RSA-Kryptosysems
Seien   prim,  ,  ,   und

 , dann gilt für alle  :

 [18]

Ordnung von Elementen in Gruppen
Seien   und  . Wenn es ein   gibt, sodass   gilt, dann

heißt die kleinste derartige Zahl Ordnung von   in   und wird als

  geschrieben[19].

Satz zur Ordnung von Elementen in Gruppen
Seien   und  . Es gilt   genau dann, wenn  [19].
Beweis Hilfssatz
Voraussetzung

Sei   mit  

Zu zeigen

 

Beweis

Sei   mit  . Aus der Korrektheit des RSA-Verfahrens wissen wir, dass   gilt.

Durch Multiplikation mit   ergibt sich nach den Potenzgesetzen:

 .

Da wir   mit   gesetzt haben, können wir dies nun nach   umformen, dann einsetzen und erhalten

 .

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

 

und somit  [16]

Wir betrachten nun einen Satz, welcher die Grundlage für einen Algorithmus bildet, mit dem man aus  ,   und   einen Primfaktor von   bestimmen kann.

Satz Bestimmung eines Primfaktors aus  ,   und  

Sei   mit  .

Wenn  , dann gilt   für ein  [16].

Beweis Bestimmung eines Primfaktors aus  ,   und  

Voraussetzung

Sei   mit   und  , wobei

  und  

Zu zeigen

  für ein  

Beweis

Betrachten wir zunächst   und  .

Da  , wissen wir, dass   und wir können den Hilfssatz anwenden:

 

und

 .

Hilfssatz Sicherheit des RSA-Kryptosystems, (Satz zur) Ordnung

von Elementen in Gruppen

Hilfssatz Sicherheit des RSA-Kryptosystems
Für alle Zahlen   mit   gilt  [16].
Ordnung von Elementen in Gruppen
Seien   und  . Wenn es ein   gibt, sodass   gilt, dann

heißt die kleinste derartige Zahl Ordnung von   in   und wird als

  geschrieben[19].

Satz zur Ordnung von Elementen in Gruppen
Seien   und  . Es gilt   genau dann, wenn  [19].

Sei nun nach Voraussetzung  , genauer

 

und

 .

Dann folgt   bzw.  .

Wir zeigen nun, dass   und  .

Nach Definition der Ordnung von Elementen in Gruppen gilt

 

und nach Potenzieren mit   folgt

 , da   und  .

Da  , folgt

 

Wir können   umstellen und erhalten

 .

Es folgt

 [16].

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

Der zugehörige Algorithmus geht wie folgt vor:

  1. Wir wählen ein zufälliges  
  2. Wir berechnen  
  3. Fallunterscheidung
    1. Ist  
      • Dann ist   ein Primfaktor von  
      • Der Algorithmus bricht ab und   wird ausgegeben
    2. Ist  
      • Dann fährt der Algorithmus mit Schritt 4 fort
  4. Wir berechnen   für alle  
  5. Fallunterscheidung
    1. Ist  ,
      • Dann ist   ein Primfaktor von  
      • Der Algorithmus bricht ab   wird ausgegeben
    2. Ist   für alle  
      • Dann hat der Algorithmus in diesem Durchlauf keinen Primfaktor von   gefunden
      • Der Algorithmus wird mit einem neuen   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   finden[20]. Da der Beweis der Erfolgswahrscheinlichkeit weitere neue Grundlagen benötigt[21], beschränken wir uns hier auf die Anwendung des Algorithmus'.

Da   können wir den unbekannten Primfakor durch Einsetzen von   und dem bekannten Primfakor leicht berechnen■[16]

Bemerkung: Nach dem RSA-Problem, könnte die Berechnung der  -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

  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. 2,0 2,1 2,2 2,3 Hinek, M. J. (2009). Cryptanalysis of RSA and Its Variants. CRC Press. S. 8.
  3. Buchmann, J. (2016). Einführung in die Kryptographie (6. Aufl.). Berlin, Heidelberg: Springer. S. 43.
  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.
  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.
  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.
  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.