Wikiversity

Kryptologie/RSA-Kryptosystem

< Kryptologie


Einleitung

(Asymmetrische) Kryptosystem, Sicherheitsziele,

Verschlüsselungsverfahren und digitale Signatur

Kryptosystem
Verfahren zur Umsetzung von Sicherheitszielen in der Kryptografie[1].
Asymmetrische Kryptosysteme
Kryptosystem, bei dem Sender und Empfänger über kein gemeinsamen

geheimen Schlüssel verfügen[2].

Authentizität
Der Empfänger einer Nachricht kann sich davon überzeugen, dass

die erhaltene Nachricht von einem eindeutigen Sender stammt[3].

Verbindlichkeit
Der Empfänger der Nachricht kann Dritten gegenüber nachweisen,

dass die Nachricht von einem bestimmten Sender stammt[4].

Vertraulichkeit
Höchstens Sender und Empfänger können den Inhalt des

Klartextes einer übermittelten Nachricht verstehen[2].

Verschlüsselungsverfahren
Kryptosystem zur Umsetzung von Vertraulichkeit[2].
Digitale Signatur
Kryptosystem zur Umsetzung von Authentizität und Verbindlichkeit[2].

Das RSA-Kryptosystem ist ein asymmetrisches Kryptosystem aus den 70er Jahren des letzten Jahrhunderts[5]. Es beruht auf der Annahme, dass die Potenzierung modulo   unter bestimmten Voraussetzungen eine Falltür-Funktion ist[6]. Das Kryptosystem kann zur Realisierung all unserer bekannten Sicherheitsziele genutzt werden: Vertraulichkeit oder Authentizität und Verbindlichkeit. Das RSA-Kryptosystem, kann also als Verschlüsselungsverfahren oder als digitale Signatur verwendet werden[5]. Es gilt als eines der aktuell besten Kryptosysteme[7] und kommt als Verschlüsselungsverfahren oder digitale Signatur in unterschiedlichen Einsatzgebiete vor[8]. Zwei von vielen Beispielen hierfür sind Bankkarten zum Geld abheben und bargeldlosem Bezahlen[9] und S/MIME, einem Standard für Verschlüsselung und Signatur von Emails, der den RSA-Algorithmus als Verfahren zur digitalen Signatur verwendet[10].

RSA-Algorithmus

Wir beschreiben den RSA-Algorithmus anhand des RSA-Verschlüsselungsverfahrens. Die Berechnungen finden dabei alle im Restklassenring   statt[11].

Primzahltest, Eulersche  -Funktion und Erweiterter Euklidischer Algorithmus
Primzahltest
Test mit Ziel zu überprüfen, ob eine Zahl (mit hoher Wahrscheinlichkeit) prim ist[12].
Eulersche  -Funktion
Für die eulersche  -Funktion gilt:  [13][14] mit  [15][14].
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[16]),
  2. Berechnung zweier ganzer Zahlen   und  , welche die Gleichung   erfüllen[17].
  1. Schlüsselerzeugungsalgorithmus
    • Berechnung des RSA-Modul   aus zwei Primzahlen   definierter Größenordnung
    • Wahl eines zu   teilerfremden Verschlüsselungsexponenten  
    • Berechnung des Entschlüsselungsexponenten   aus der Gleichung   mittels erweitertem euklidischen Algorithmus
    • Privaten Schlüssel   und öffentlichen Schlüssel   bilden[18][19]
    • Bemerkung: Die Wahl der Primzahlen geschieht aus Sicherheitsgründen zufällig, wobei eine gewisse Größenordnung vorausgesetzt wird. In der Praxis wählt man eine zufällige Zahl dieser Größenordnung und testet dann mit einem Primzahltest, ob die Zahl prim ist[20].
  2. Verschlüsselungsalgorithmus
    •   mit Klartext  , Geheimtext   und dem öffentlichen Schlüssel  [18][21]
  3. Entschlüsselungsalgorithmus
    •   mit  ,   und dem privaten Schlüssel  [18][21]

Bemerkung: Die Algorithmen der RSA-Signatur sind zu denen des RSA-Verschlüsselungsverfahrens fast identisch. Sie unterscheiden sich in der Notation und in der Reihenfolge des zweiten und dritten Schritts[21].

Beispiel

Wir wollen den Klartext   mit dem Verschlüsselungsalgorithmus verschlüsseln und anschließend mit dem Entschlüsselungsalgorithmus entschlüsseln.

Schritt 1: Schlüsselerzeugung

Multiplikative Inverse, erweiterte euklidische Algorithmus und Kongruenz
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  [22].

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[16]),
  2. Berechnung zweier ganzer Zahlen   und  , welche die Gleichung   erfüllen[17].
Kongruenz
Seien   und  , dann gilt  [23].

Seien   und  

Wir bestimmen zunächst den RSA-Modul  .

Dann ist

 .

Wähle   mit  , dann sei  .

Nun berechnen wir das multiplikative Inverse   mit  :

 

Wir wenden den erweiterten euklidischen Algorithmus an:

  • Teil 1: Berechnung des  

Gleichung 1:  

Gleichung 2:  

Gleichung 3:  

Gleichung 4:  

Gleichung 5:  

 , da der hintere Summand in der vorletzten Gleichung   ist

  • Teil 2: Berechnung zweier ganzer Zahlen   und  , welche die Gleichung   erfüllen

 

 , wegen Gleichung 2 und 3

 

 , wegen Gleichung 1 und 2

 , wegen Gleichung 1

 

 

  und  

Es folgt wegen der Kongruenz  , dass  .

Nun bilden wir den privaten und öffentlichen Schlüssel

  • Private Schlüssel  
  • Öffentliche Schlüssel  

Schritt 2: Verschlüsseln des Klartextes   mit  

 , da  

 

Schritt 3: Entschlüsseln des Geheimtextes   mit  

 

 [24]

Sicherheit

Die Sicherheit des RSA-Algorithmus beruht heute vor allem auf dem RSA- bzw. Faktorisierungsproblem[25].

RSA-Problem

Gegeben sind der öffentliche Schlüssel   sowie der Geheimtext  . Gesucht wird der Klartext   wobei gilt:  . Das Problem liegt hier in der Schwierigkeit die  -te Wurzel modulo   zu ziehen oder das multiplikative Inverse von   zu bestimmen[18][25].

RSA-Annahme

Es ist bisher nicht klar wie schwer es tatsächlich ist das RSA-Problem zu lösen. Es wird jedoch angenommen, dass das Problem (bei ausreichend großem RSA-Modul  ) unverhältnismäßig schwer zu lösen ist. Diese Annahme heißt RSA-Annahme[25].

Faktorisierungsproblem

Dass das RSA-Problem schwer zu lösen ist, wird auch durch das Faktorisierungsproblem bekräftigt. Das Faktorisierungsproblem besteht schon seit Jahrhunderten[26]. Die Problemstellung besteht darin, für eine zusammengesetzte Zahl   einen anderen Teiler als   und   zu finden[25]. Wir werden in einer späteren Lerneinheit zur Sicherheit des RSA-Kryptosystems sogar zeigen, dass das RSA-Problem höchstens so schwer zu lösen ist, wie das Faktorisierungsproblem[25].

Zukunft der Sicherheit des RSA-Algorithmus

Ob der RSA-Algorithmus auch noch in einigen Jahrzehnten als sicher gilt, ist fraglich. Möglicherweise gelingt es bis dahin einen Faktorisierungsalgorithmus zu finden, der das Faktorisierungsproblem löst oder es gibt eine andere Möglichkeit, um den RSA-Algorithmus unabhängig von der Faktorisierung von   zu brechen und somit das RSA-Problem zu lösen[25]. Ein solcher effizienter Faktorisierungsalgorithmus ist bereits beschrieben worden, jedoch setzt dieser den Einsatz von Quantencomputern voraus[27].

Angriffe auf das RSA-Kryptosystem

In einigen Spezialfällen kann ein Angreifer einen Geheimtext entschlüsseln[18][8]. Diese Angriffsszenarien basieren jedoch auf einer falschen Verwendung des RSA-Kryptosystems[28]. Ein solches Beispiel behandeln wir in der Lerneinheit Angriff auf das RSA-Verschlüsselungsverfahren.

Lernempfehlung

Kursübersicht
Übergeordnete Lerneinheit
5: Asymmetrische Kryptosysteme
Vorherige Lerneinheit Aktuelle Lerneinheit Empfohlene Lerneinheit
5: Asymmetrische Kryptosysteme 6: RSA-Kryptosystem 7.1: Schlüsselerzeugung des RSA-Verschlüsselungsverfahrens
Grundlagen der empfohlenen Lerneinheit
7.1.1: Primzahl(-eigenschaften) 7.1.2: Probedivision (Primzahltest 1) 7.1.3: Fermat-Test (Primzahltest 2)
7.1.4: Miller-Rabin-Test (Primzahltest 3) 7.1.5: Erweiterter euklidischer Algorithmus 7.1.6: Eulersche φ-Funktion

Literatur

  1. ↑ Menezes, A. J., van Oorschot, P. C., & Vanstone, S. A. (1997). Handbook of Applied Cryptography. 5. S. 15.
  2. ↑ a b c d Diffie, W., & Hellman, M. (1976). New directions in cryptography. IEEE Transactions on Information Theory, 22(6) (S. 644–654). S. 644.
  3. ↑ Diffie, W., & Hellman, M. (1976). New directions in cryptography. IEEE Transactions on Information Theory, 22(6) (S. 644–654). S. 645.
  4. ↑ 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. 121.
  5. ↑ a b 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.
  6. ↑ 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.
  7. ↑ Singh, G., & Supriya, S. (2013). A Study of Encryption Algorithms (RSA, DES, 3DES and AES) for Information Security. International Journal of Computer Applications, 67(19) (S. 33–38). S. 35.
  8. ↑ a b Boneh, D. (1999). Twenty Years of Attacks on the RSA Cryptosystem. 46(2), 11. S. 203.
  9. ↑ Kunjadić, G., & Jović, Z. (2016). Bitcoin—Banking and Technological Challenges. Proceedings of the International Scientific Conference FINIZ 2016 (S. 185–189). S. 188.
  10. ↑ Raji, M. A., Amiri, F., & Ahmadian, M. (2016). A New secure email scheme Using Digital Signature with S/MIME. 8. S. 56.
  11. ↑ 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. 121.
  12. ↑ Buchmann, J. (2016). Einführung in die Kryptographie (6. Aufl.). Berlin, Heidelberg: Springer. S. 157.
  13. ↑ Kryptologie - Mathematische Vertiefung (PH Freiburg SS 2017). (5. Dezember 2019). Wikiversity, . Abgerufen am 8. Januar 2020, 12:14 von https://de.wikiversity.org/w/index.php?title=Kryptologie_-_Mathematische_Vertiefung_(PH_Freiburg_SS_2017)&oldid=605650. (Formulierung verändert)
  14. ↑ a b Stroth, G., & Waldecker, R. (2019). Elementare Algebra und Zahlentheorie (2. Aufl.). Birkhäuser Basel. S. 77.
  15. ↑ Seite „Eulersche Phi-Funktion“. In: Wikipedia, Die freie Enzyklopädie. Bearbeitungsstand: 24. August 2019, 16:52 UTC. URL: https://de.wikipedia.org/w/index.php?title=Eulersche_Phi-Funktion&oldid=191644019 (Abgerufen: 7. Januar 2020, 09:45 UTC; Formulierung verändert)
  16. ↑ a b Lehman, E., Leighton, T., & Meyer, A. R. (2010). Mathematics for computer science. Technical report, 2006. Lecture notes. S. 249.
  17. ↑ a b Kurzweil, H. (2008). Endliche Körper: Verstehen, rechnen, anwenden (2., überarb. Aufl). Springer. S. 57.
  18. ↑ a b c d e 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: 28. Dezember 2019, 16:29 UTC; Formulierung verändert)
  19. ↑ 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. 122f.
  20. ↑ 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. 118.
  21. ↑ a b c 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.
  22. ↑ Buchmann, J. (2016). Einführung in die Kryptographie (6. Aufl.). Berlin, Heidelberg: Springer. S. 43.
  23. ↑ Buchmann, J. (2016). Einführung in die Kryptographie (6. Aufl.). Berlin, Heidelberg: Springer. S. 37.
  24. ↑ Kryptologie - Mathematische Vertiefung (PH Freiburg SS 2017). (5. Dezember 2019). Wikiversity, . Abgerufen am 8. Januar 2020, 12:14 von https://de.wikiversity.org/w/index.php?title=Kryptologie_-_Mathematische_Vertiefung_(PH_Freiburg_SS_2017)&oldid=605650.
  25. ↑ a b c d e f Hinek, M. J. (2009). Cryptanalysis of RSA and Its Variants. CRC Press. S. 8.
  26. ↑ Buchmann, J. (2016). Einführung in die Kryptographie (6. Aufl.). Springer. S. 172.
  27. ↑ Shor, P. W. (1994). Algorithms for quantum computation: Discrete logarithms and factoring. Proceedings 35th Annual Symposium on Foundations of Computer Science (S. 124–134). S. 130.
  28. ↑ Moore, J. H. (1988). Protocol failures in cryptosystems. Proceedings of the IEEE, 76(5) (S. 594–602). S. 594.


Abgerufen von „https://de.wikiversity.org/w/index.php?title=Kryptologie/RSA-Kryptosystem&oldid=630899“