Kryptologie/Korrektheit des RSA-Verschlüsselungsverfahrens

Aus Wikiversity


Einleitung

Wir haben nun die drei Algorithmen des RSA-Verschlüsselungsverfahren kennengelernt und beispielhaft durchgeführt. Nun bleibt zu zeigen, warum das Verfahren korrekt ist. Es muss für alle Klartexte also gelten, dass der Entschlüsselungsalgorithmus den verschlüsselten Klartext in den ursprünglichen Klartext umwandelt[1]. Die wichtigste Grundlage für den Ver- und Entschlüsselungsalgorithmus des RSA-Algorithmus ist der Satz von Euler[2].

Beweis Korrektheit des RSA-Verfahrens

Voraussetzung

Seien prim, , und

Zu zeigen

RSA-Algorithmus entschlüsselt korrekt, d.h. für alle gilt

Beweis

(Multiplikativität und Satz 1 der) Eulersche -Funktion, Kongruenz,

Größte gemeinsame Teiler, Teilbarkeit und Satz von Euler

Eulersche -Funktion
Für die eulersche -Funktion gilt: [3][4] mit

[5][4].

Multiplikativität der eulerschen -Funktion für Primzahlen
Seien und prim und , dann gilt [3][6].
Satz 1 Eigenschaft der -Funktion bei Primzahlen
Sei prim, dann gilt: [5][6].
Kongruenz
Seien und , dann gilt [7].
Größte gemeinsame Teiler
Seien , wobei mindestens eine der beiden Zahlen ungleich Null.

Wir bezeichnen mit als den größten gemeinsamen

Teiler der Zahlen und , falls gilt:

: und

und

: Für alle mit und [8].

Teilbarkeit
Eine ganze Zahl teilt eine ganze Zahl genau dann, wenn es eine

ganze Zahl gibt, für die ist.

Wir schreiben [9][10].

Satz von Euler
Seien und , dann gilt [11][12].

Laut Voraussetzung gilt:

, nach Voraussetzung

, wegen der Multiplikativität der -Funktion

, wegen Satz 1 Eigenschaft der -Funktion bei Primzahlen

mit und wegen der Definition der Kongruenz und Teilbarkeit.


Wir unterscheiden zunächst zwei Fälle:

und .


Fall 1: Sei :

, nach mit

, da nach dem Satz von Euler gilt

.

Wir müssen nun also nur noch den zweitem Fall betrachten.


Fall 2: Sei .

Kongruenz, Größte gemeinsame Teiler, Teilbarkeit,

Satz von Euler und chinesischer Restsatz

Kongruenz
Seien und , dann gilt [7].
Größte gemeinsame Teiler
Seien , wobei mindestens eine der beiden Zahlen ungleich Null.

Wir bezeichnen mit als den größten gemeinsamen

Teiler der Zahlen und , falls gilt:

: und

und

: Für alle mit und [8].

Teilbarkeit
Eine ganze Zahl teilt eine ganze Zahl genau dann, wenn es eine

ganze Zahl gibt, für die ist.

Wir schreiben [9][10].

Satz von Euler
Seien und , dann gilt [11][12].
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 [13].

Wegen gilt dann also entweder oder .

Hier ist der Satz von Euler nicht anwendbar, wegen .

Wenn wir jedoch trotzdem zeigen, dass

und , dann können wir (wegen ) den chinesischen Restsatz anwenden und erhalten:

, wegen .


Wir zeigen dies nun für den Fall , dass gilt:

und .

Sei .

Es gilt dann nach Definition der größten gemeinsamen Teilers bzw. nach Definition der Teilbarkeit mit .

Wir zeigen zunächst für

Dann gilt nach Definition der Kongruenz aber auch .

Nun betrachten wir .

, da ein Vielfaches von ist.

Also gilt und insgesamt

.

Nun bleibt noch zu zeigen, dass für .

Da , kann man den Satz von Euler anwenden.

, nach : (in umgestellter Form)

, nach dem Satz von Euler

.

Also gilt für : .

Nun können wir den chinesischen Restsatz anwenden:

, wegen .

Wir haben also nun gezeigt, dass das RSA-Verschlüsselungsverfahren für korrekt ist. Dies können wir für analog zeigen, indem wir in der Notation und vertauschen. Sie können dies freiwillig eigenständig durchführen.

Damit haben wir die Korrektheit des RSA-Verschlüsselungsverfahrens für alle Fälle, nämlich und , gezeigt■[14][2]

Lernempfehlung

Kursübersicht
Übergeordnete Lerneinheit
6: RSA-Kryptosystem
Vorherige Lerneinheit Aktuelle Lerneinheit Empfohlene Lerneinheit
7.3: Entschlüsselungsalgorithmus des RSA-Verschlüsselungsverfahrens 8: Korrektheit des RSA-Verschlüsselungsverfahrens 9: RSA-Signatur
Grundlagen der aktuellen Lerneinheit
8.1: Satz von Euler 8.2: Chinesischer Restsatz

Literatur

  1. Diffie, W., & Hellman, M. (1976). New directions in cryptography. IEEE Transactions on Information Theory, 22(6) (S. 644–654). S. 648.
  2. 2,0 2,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. 123.
  3. 3,0 3,1 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)
  4. 4,0 4,1 Stroth, G., & Waldecker, R. (2019). Elementare Algebra und Zahlentheorie (2. Aufl.). Birkhäuser Basel. S. 77.
  5. 5,0 5,1 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; Formulierung verändert)
  6. 6,0 6,1 Wätjen, D. (2018). Kryptographie: Grundlagen, Algorithmen, Protokolle. Springer-Verlag. S. 42.
  7. 7,0 7,1 Buchmann, J. (2016). Einführung in die Kryptographie (6. Aufl.). Berlin, Heidelberg: Springer. S. 37.
  8. 8,0 8,1 Burton, D. M., & Dalkowski, H. (2005). Handbuch der elementaren Zahlentheorie mit über 1000 Übungsaufgaben und ihren Lösungen. Lemgo: Heldermann Verlag. S. 24.
  9. 9,0 9,1 Seite „Teilbarkeit“. In: Wikipedia, Die freie Enzyklopädie. Bearbeitungsstand: 25. November 2019, 15:44 UTC. URL: https://de.wikipedia.org/w/index.php?title=Teilbarkeit&oldid=194364839 (Abgerufen: 12. Dezember 2019, 14:43 UTC; Formulierung verändert)
  10. 10,0 10,1 Burton, D. M., & Dalkowski, H. (2005). Handbuch der elementaren Zahlentheorie mit über 1000 Übungsaufgaben und ihren Lösungen. Heldermann Verlag. 22f.
  11. 11,0 11,1 „Satz von Euler“. In: Wikipedia, Die freie Enzyklopädie. Bearbeitungsstand: 27. März 2019, 10:16 UTC. URL: https://de.wikipedia.org/w/index.php?title=Satz_von_Euler&oldid=186980132 (Abgerufen: 25. November 2019, 10:25 UTC; Formulierung verändert)
  12. 12,0 12,1 Euler, L. (1763). Theoremata arithmetica nova methodo demonstrata. 8 (S. 74–104). S. 102.
  13. Shoup, V. (2008). A Computational Introduction to Number Theory and Algebra (2. Aufl.). S. 23.
  14. Beweisarchiv: Kryptografie: Kryptosysteme: Korrektheit des RSA-Kryptosystems. (16. Juni 2013). Wikibooks, Die freie Bibliothek. Abgerufen am 10. Januar 2020, 12:20 von https://de.wikibooks.org/w/index.php?title=Beweisarchiv:_Kryptografie:_Kryptosysteme:_Korrektheit_des_RSA-Kryptosystems&oldid=674922. (Formulierung verändert)