Kryptologie/Entschlüsselungsalgorithmus des RSA-Verschlüsselungsverfahrens

Aus Wikiversity


Einleitung

Anforderungen an den Geheimtext
Anforderungen an den Geheimtext
  1. Der Geheimtext muss in einem numerischen Alphabet vorliegen
  2. Ist der Geheimtext kein Standardrepräsentant des RSA-Moduls, muss dieser in Standardrepräsentanten des RSA-Moduls mit fester Reihenfolge aufgeteilt werden
  3. Der Geheimtext darf nicht mit beginnen.[1]

Wir wollen nun zeigen, wie man eine mit dem eigenen öffentlichen Schlüssel verschlüsselte Nachricht mit dem privaten Schlüssel und dem Entschlüsselungsalgorithmus entschlüsseln kann[2]. Die Anforderungen an den Geheimtext entsprechen den Anforderungen an den Klartext[1].

Entschlüsselungsalgorithmus

Der eigentlichen Entschlüsselungsalgorithmus besteht aus einem einzigen Schritt:

  1. Berechnung des Klartextes aus ,
    • [3][4] mit und ,
      • In der Praxis muss jeder Block eines Geheimtextes einzeln verschlüsselt werden und es gilt für alle [1].

Beispiel

Tabelle 1: Ausschnitt aus der ASCII-Tabelle[5]
Zeichen

aus

Zugeordnetes

Zeichen aus

Zeichen

aus

Zugeordnetes

Zeichen aus

0 NUL (Leerzeichen[6]) 77 M
46 . 78 N
65 A 79 O
66 B 80 P
67 C 81 Q
68 D 82 R
69 E 83 S
70 F 84 T
71 G 85 U
72 H 86 V
73 I 87 W
74 J 88 X
75 K 89 Y
76 L 90 Z

Im Beispiel des RSA-Verschlüsselungsverfahrens wurde ein Geheimtext mit dem öffentlichen Schlüssel erzeugt. Dieser soll nun mit dem zugehörigen privaten Schlüssel entschlüsselt werden.

Sei also

  1. Entschlüsselungsalgorithmus
    • Wir wenden also auf jedes mit den Entschlüsselungsalgorithmus an:
      • ,
      • ,
    • Reiht man die Blöcke aneinander, so ergibt sich:
    • Bemerkung: Wie bereits auf der Seite zum Verschlüsselungsalgorithmus erklärt, ist es wichtig, dass die Blöcke getrennt bleiben und ihre Reihenfolge eindeutig ist, andernfalls geht der Klartext verloren[1]
  2. Umkehrung der Kodierung des Klartextes
    • Wir nutzen die Umkehrfunktion der Zeichenkodierung aus Tabelle 1
    • , , , , , , , , und
      • Aufgrund des sehr kleinen in unserem Beispiel, muss man bei der Zeichenkodierung darauf achten, an welcher Stelle kodiert wird. Eigentlich würde man wählen, aber in unserem Beispiel würde dann entweder ein Block entstehen, der mit beginnt oder den Wert annimmt. Dies widerspricht unserer Voraussetzung, dass Blöcke nicht mit beginnen dürfen und kleiner als sein müssen[1].

Lernaufgabe

Aufgabe 1

Berechnen Sie die Entschlüsselung des Geheimtextes mit dem privaten Schlüssel . Der Empfänger verschlüsselte und ignorierte die Voraussetzung . Begründen Sie anschließend anhand des Beispiels, warum bei der Verschlüsselung der Lernaufgabe 1 zur Verschlüsselung mit dem RSA-Verschlüsselungsverfahren die Notwendigkeit besteht den Klartext in Blöcke zu unterteilen.

Lösung
Seien und .

Wir entschlüsseln den Geheimtext mit dem Entschlüsselungsalgorithmus des RSA-Verschlüsselungsverfahrens:

.

entspricht nicht dem ursprünglichen Klartext . Dies liegt an der verletzen Voraussetzung .

Es gilt nämlich , d.h. , wobei der Standardrepräsentant der Restklasse ist und .

Da der Verschlüsselungsalgorithmus jedes Element der Restklasse in den Standardrepräsentanten umwandelt, gehen alle Information verloren bis auf, dass der ursprüngliche Klartext ist.

Aufgabe 2

Berechnen Sie die Entschlüsselung des Geheimtextes mit dem RSA-Algorithmus und wenden Sie die Zeichenkodierung aus Tabelle 1 an. Das zugehörige Zahlenpaar zur Entschlüsselung ist .

Lösung
Seien und .

Wir entschlüsseln den Geheimtext mit dem Entschlüsselungsalgorithmus mit des RSA-Algorithmus:

,

,

,

,

,

,

und

.

Der Klartext lautet also: .

Wir wenden die Zeichenkodierung aus Tabelle 1 an:

, , , , , und .


Der Klartext lautet also .

Lernempfehlung

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

Literatur

  1. 1,0 1,1 1,2 1,3 1,4 Coutinho, S. C. (1999). The mathematics of ciphers: Number theory and RSA cryptography. A K Peters, S. 163f.
  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. 120.
  3. 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: 10. Januar 2020, 10:40 UTC; Formulierung verändert)
  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. 122.
  5. Seite „American Standard Code for Information Interchange“. In: Wikipedia, Die freie Enzyklopädie. Bearbeitungsstand: 23. Dezember 2019, 09:20 UTC. URL: https://de.wikipedia.org/w/index.php?title=American_Standard_Code_for_Information_Interchange&oldid=195157263 (Abgerufen: 9. Januar 2020, 11:59 UTC)
  6. Seite „Leerzeichen“. In: Wikipedia, Die freie Enzyklopädie. Bearbeitungsstand: 25. November 2019, 20:03 UTC. URL: https://de.wikipedia.org/w/index.php?title=Leerzeichen&oldid=194374775 (Abgerufen: 16. Februar 2020, 22:20 UTC)