Kryptologie/Entschlüsselungsalgorithmus des RSA-Verschlüsselungsverfahrens

Einleitung

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

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. Die Anforderungen an den Geheimtext entsprechen den Anforderungen an den Klartext.

Entschlüsselungsalgorithmus

Der eigentlichen Entschlüsselungsalgorithmus besteht aus einem einzigen Schritt:

1. Berechnung des Klartextes $m\in \mathbb{Z}/N\mathbb{Z}$ aus $c\in \mathbb{Z}/N\mathbb{Z}$ ,
   • $m\equiv c^{d}modN$ mit $m=m_1-m_2-\dots -m_l$ und $c=c_1-c_2-\dots -c_l$,
     • In der Praxis muss jeder Block eines Geheimtextes $c\mathbb{Z}/N\mathbb{Z}$ einzeln verschlüsselt werden und es gilt für alle $i\in \{1,2,\dots ,l\}$ $m_i\equiv c_i^{d}modN$.

Beispiel

Tabelle 1: Ausschnitt aus der ASCII-Tabelle

Zeichen aus ${\mathrm{\Sigma }}_2$	Zugeordnetes Zeichen aus ${\mathrm{\Sigma }}_1$	Zeichen aus ${\mathrm{\Sigma }}_2$	Zugeordnetes Zeichen aus ${\mathrm{\Sigma }}_1$
0	NUL (Leerzeichen)	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 $(23,143)$ erzeugt. Dieser soll nun mit dem zugehörigen privaten Schlüssel $(47,143)$ entschlüsselt werden.

Sei also $c=106-65-32-32-2-129-120-49-32-24-41$

1. Entschlüsselungsalgorithmus
   • Wir wenden also auf jedes $c_i$ mit $i\in \{1,2,\dots ,l\}$ den Entschlüsselungsalgorithmus $m_i\equiv c_i^{47}mod143$ an:
     • $106^{47}\equiv 72mod143\Rightarrow m_1=72$,
     • $65^{47}\equiv 65mod143\Rightarrow m_2=65$,
     • $76^{47}\equiv 32mod143\Rightarrow m_3=32$
     • $\dots$
     • $41^{47}\equiv 46mod143\Rightarrow m_{11}=46$
   • Reiht man die Blöcke aneinander, so ergibt sich: $m=726576767908769768446$
   • 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
2. Umkehrung der Kodierung des Klartextes
   • Wir nutzen die Umkehrfunktion der Zeichenkodierung aus Tabelle 1 $f^{-1}:{\mathrm{\Sigma }}_2\to {\mathrm{\Sigma }}_1$
   • $f^{-1}(72)=H$, $f^{-1}(65)=A$, $f^{-1}(76)=L$, $f^{-1}(76)=L$, $f^{-1}(79)=O$, $f^{-1}(0)=NUL$, $f^{-1}(87)=W$, $f^{-1}(69)=E$, $f^{-1}(76)=L$ und $f^{-1}(84)=T$
     • Aufgrund des sehr kleinen $N$ in unserem Beispiel, muss man bei der Zeichenkodierung darauf achten, an welcher Stelle $NUL$ kodiert wird. Eigentlich würde man $\text{NUL}\to 00$ wählen, aber in unserem Beispiel würde dann entweder ein Block entstehen, der mit $0$ beginnt oder den Wert $900$ annimmt. Dies widerspricht unserer Voraussetzung, dass Blöcke nicht mit $0$ beginnen dürfen und kleiner als $N$ sein müssen.

Lernaufgabe

Aufgabe 1

Berechnen Sie die Entschlüsselung des Geheimtextes $c=20$ mit dem privaten Schlüssel $(47,143)$. Der Empfänger verschlüsselte $c=20\equiv 301^{23}mod143$ und ignorierte die Voraussetzung $m\in \mathbb{Z}/143\mathbb{Z}$. 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 $d=47$ und $N=143$. Wir entschlüsseln den Geheimtext $c=20$ mit dem Entschlüsselungsalgorithmus des RSA-Verschlüsselungsverfahrens: $m=15\equiv 20^{47}mod143$ . $m=15$ entspricht nicht dem ursprünglichen Klartext $m=301$. Dies liegt an der verletzen Voraussetzung $m\in \mathbb{Z}/143\mathbb{Z}$. Es gilt nämlich $301=2\cdot 143+15$, d.h. $m=15\equiv 301mod143$, wobei $15$ der Standardrepräsentant der Restklasse $[15{]}_{143}$ ist und $301\in [15{]}_{143}$. Da der Verschlüsselungsalgorithmus jedes Element der Restklasse in den Standardrepräsentanten umwandelt, gehen alle Information verloren bis auf, dass der ursprüngliche Klartext $m\in [15{]}_{143}$ ist.

Aufgabe 2

Berechnen Sie die Entschlüsselung des Geheimtextes $c=c_1-c_2-\dots -c_7=65-73-24-49-114-57-121$ mit dem RSA-Algorithmus und wenden Sie die Zeichenkodierung aus Tabelle 1 an. Das zugehörige Zahlenpaar zur Entschlüsselung $(d,N)$ ist $(47,143)$.

Lösung

Seien $d=47$ und $N=143$. Wir entschlüsseln den Geheimtext $c=c_1-c_2-\dots -c_7=65-73-24-49-114-57-121$ mit dem Entschlüsselungsalgorithmus $m_i\equiv c_i^{47}mod143$ mit $i\in \{1,2,\dots ,7\}$ des RSA-Algorithmus: $m_1=65\equiv 65^{47}mod143$, $m_2=83\equiv 73^{47}mod143$, $m_3=84\equiv 24^{47}mod143$, $m_4=69\equiv 49^{47}mod143$, $m_5=82\equiv 114^{47}mod143$, $m_6=73\equiv 57^{47}mod143$, und $m_7=88\equiv 121^{47}mod143$. Der Klartext lautet also: $m=m_1-m_2-\dots -m_7=65-83-84-69-82-73-88=65838469827388$. Wir wenden die Zeichenkodierung aus Tabelle 1 an: $f^{-1}(65)=A$, $f^{-1}(83)=S$, $f^{-1}(84)=T$, $f^{-1}(69)=E$, $f^{-1}(82)=R$, $f^{-1}(73)=I$ und $f^{-1}(88)=X$. Der Klartext lautet also $m=65838469827388=ASTERIX$.

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