Kryptologie/RSA-Kryptosystem: Unterschied zwischen den Versionen

Aus testwiki
Zur Navigation springen Zur Suche springen
imported>Philip Holtappel
K Fehler korrigiert
 
(kein Unterschied)

Aktuelle Version vom 24. April 2020, 08:48 Uhr


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 N 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 (ℤ/Nℤ,⊕,⊙) 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: φ(n):=∣Gn∣[13][14] mit Gn:={a∈ℕ|1≤a≤n∧ggT⁡(a,n)=1}[15][14].
Erweiterte euklidische Algorithmus
Der erweiterte euklidische Algorithmus wird auf zwei Zahlen a,b∈ℕ angewandt und besteht aus zwei Teilen:
  1. Berechnung des ggT⁡(a,b)=s⋅a+t⋅b (auch als euklidischer Algorithmus bekannt[16]),
  2. Berechnung zweier ganzer Zahlen s und t, welche die Gleichung ggT⁡(a,b)=s⋅a+t⋅b erfüllen[17].
  1. Schlüsselerzeugungsalgorithmus
    • Berechnung des RSA-Modul N=p⋅q aus zwei Primzahlen p,q definierter Größenordnung
    • Wahl eines zu φ(N)=(p−1)⋅(q−1) teilerfremden Verschlüsselungsexponenten e
    • Berechnung des Entschlüsselungsexponenten d aus der Gleichung e⋅d≡1modφ(N) mittels erweitertem euklidischen Algorithmus
    • Privaten Schlüssel (d,N) und öffentlichen Schlüssel (e,N) 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
    • c≡memodN mit Klartext m∈ℤ/Nℤ, Geheimtext c∈ℤ/Nℤ und dem öffentlichen Schlüssel (e,N)[18][21]
  3. Entschlüsselungsalgorithmus
    • m≡cdmodN mit m∈ℤ/Nℤ, c∈ℤ/Nℤ und dem privaten Schlüssel (d,N)[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 m=7 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 [a]m ist genau dann invertierbar in ℤ/mℤ, wenn gilt ggT(a,m)=1 und die Lösung

[s]m der Kongruenz as≡1modm ist eindeutig bestimmt und wir nennen diese multiplikative Inverse

von [a]m[22].

Erweiterte euklidische Algorithmus
Der erweiterte euklidische Algorithmus wird auf zwei Zahlen a,b∈ℕ angewandt und besteht aus zwei Teilen:
  1. Berechnung des ggT⁡(a,b)=s⋅a+t⋅b (auch als euklidischer Algorithmus bekannt[16]),
  2. Berechnung zweier ganzer Zahlen s und t, welche die Gleichung ggT⁡(a,b)=s⋅a+t⋅b erfüllen[17].
Kongruenz
Seien a,b∈ℤ und m∈ℕ, dann gilt a≡bmodm⇔m∣(a−b)[23].

Seien p=11 und q=13

Wir bestimmen zunächst den RSA-Modul N=p⋅q=11⋅13=143.

Dann ist

φ(N)=(p−1)⋅(q−1)=10⋅12=120.

Wähle e mit ggT(e,φ(N))=1, dann sei e=23.

Nun berechnen wir das multiplikative Inverse d mit e⋅d≡1modφ(N):

23⋅d≡1mod120

Wir wenden den erweiterten euklidischen Algorithmus an:

  • Teil 1: Berechnung des ggT

Gleichung 1: 120=5⋅23+5

Gleichung 2: 23=4⋅5+3

Gleichung 3: 5=1⋅3+2

Gleichung 4: 3=1⋅2+1

Gleichung 5: 2=2⋅1+0

⇒ggT(23,120)=1, da der hintere Summand in der vorletzten Gleichung 1 ist

  • Teil 2: Berechnung zweier ganzer Zahlen s und t, welche die Gleichung ggT⁡(23,120)=s⋅23+t⋅120 erfüllen

1=3−1⋅2

⇔1=(23−4⋅5)−1⋅(5−3), wegen Gleichung 2 und 3

⇔1=23−5⋅5+3

⇔1=23−5⋅5+(23−4⋅5), wegen Gleichung 1 und 2

⇔1=23−5⋅(120−5⋅23)+(23−4⋅(120−5⋅23)), wegen Gleichung 1

⇔1=23−5⋅120+25⋅23+23−4⋅120+20⋅23

⇔1=47⋅23−9⋅120

⇒s=47 und t=−9

Es folgt wegen der Kongruenz 23⋅d≡1mod120, dass d=s=47.

Nun bilden wir den privaten und öffentlichen Schlüssel

  • Private Schlüssel (d,N)=(47,143)
  • Öffentliche Schlüssel (e,N)=(23,143)

Schritt 2: Verschlüsseln des Klartextes m=7 mit c≡memodN

c≡723≡721⋅72≡(77)3⋅72≡63⋅72≡73⋅49≡2mod143, da 77=5759⋅143+6

⇒c=2

Schritt 3: Entschlüsseln des Geheimtextes c=2 mit m≡cdmodN

m≡247≡26⋅27⋅25≡64⋅128⋅32≡7mod143

⇒m=7[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 (e,N) sowie der Geheimtext c. Gesucht wird der Klartext m wobei gilt: me≡cmodN. Das Problem liegt hier in der Schwierigkeit die e-te Wurzel modulo N zu ziehen oder das multiplikative Inverse von e 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 N) 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 n einen anderen Teiler als 1 und n 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 N=p⋅q 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. ↑ 2,0 2,1 2,2 2,3 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. ↑ 5,0 5,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. 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. ↑ 8,0 8,1 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. ↑ 14,0 14,1 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. ↑ 16,0 16,1 Lehman, E., Leighton, T., & Meyer, A. R. (2010). Mathematics for computer science. Technical report, 2006. Lecture notes. S. 249.
  17. ↑ 17,0 17,1 Kurzweil, H. (2008). Endliche Körper: Verstehen, rechnen, anwenden (2., überarb. Aufl). Springer. S. 57.
  18. ↑ 18,0 18,1 18,2 18,3 18,4 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. ↑ 21,0 21,1 21,2 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. ↑ 25,0 25,1 25,2 25,3 25,4 25,5 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.beta.math.wmflabs.org/w/index.php?title=Kryptologie/RSA-Kryptosystem&oldid=947“