Kryptologie/RSA-Kryptosystem
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: |
- 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].
- Verschlüsselungsalgorithmus
- Entschlüsselungsalgorithmus
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: |
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
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
Ü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
- ↑ Menezes, A. J., van Oorschot, P. C., & Vanstone, S. A. (1997). Handbook of Applied Cryptography. 5. S. 15.
- ↑ 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.
- ↑ Diffie, W., & Hellman, M. (1976). New directions in cryptography. IEEE Transactions on Information Theory, 22(6) (S. 644–654). S. 645.
- ↑ 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.
- ↑ 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.
- ↑ 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.
- ↑ 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.
- ↑ a b Boneh, D. (1999). Twenty Years of Attacks on the RSA Cryptosystem. 46(2), 11. S. 203.
- ↑ Kunjadić, G., & Jović, Z. (2016). Bitcoin—Banking and Technological Challenges. Proceedings of the International Scientific Conference FINIZ 2016 (S. 185–189). S. 188.
- ↑ Raji, M. A., Amiri, F., & Ahmadian, M. (2016). A New secure email scheme Using Digital Signature with S/MIME. 8. S. 56.
- ↑ 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.
- ↑ Buchmann, J. (2016). Einführung in die Kryptographie (6. Aufl.). Berlin, Heidelberg: Springer. S. 157.
- ↑ 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)
- ↑ a b Stroth, G., & Waldecker, R. (2019). Elementare Algebra und Zahlentheorie (2. Aufl.). Birkhäuser Basel. S. 77.
- ↑ 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)
- ↑ a b Lehman, E., Leighton, T., & Meyer, A. R. (2010). Mathematics for computer science. Technical report, 2006. Lecture notes. S. 249.
- ↑ a b Kurzweil, H. (2008). Endliche Körper: Verstehen, rechnen, anwenden (2., überarb. Aufl). Springer. S. 57.
- ↑ 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)
- ↑ 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.
- ↑ 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.
- ↑ 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.
- ↑ Buchmann, J. (2016). Einführung in die Kryptographie (6. Aufl.). Berlin, Heidelberg: Springer. S. 43.
- ↑ Buchmann, J. (2016). Einführung in die Kryptographie (6. Aufl.). Berlin, Heidelberg: Springer. S. 37.
- ↑ 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.
- ↑ a b c d e f Hinek, M. J. (2009). Cryptanalysis of RSA and Its Variants. CRC Press. S. 8.
- ↑ Buchmann, J. (2016). Einführung in die Kryptographie (6. Aufl.). Springer. S. 172.
- ↑ 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.
- ↑ Moore, J. H. (1988). Protocol failures in cryptosystems. Proceedings of the IEEE, 76(5) (S. 594–602). S. 594.