Kryptologie/Verschlüsselungsalgorithmus des RSA-Verschlüsselungsverfahrens

Einleitung

Nachdem wir den privaten und öffentlichen Schlüssel generiert und den öffentlichen Schlüssel veröffentlich haben, können nun Nachrichten an uns gesendet und diese von uns entschlüsselt werden. Zunächst muss eine solche Nachricht jedoch mit unserem öffentlichen Schlüssel verschlüsselt werden. In diesem Abschnitt beschäftigen wir uns daher mit dem Verschlüsselungsalgorithmus des RSA-Verschlüsselungsverfahrens und zeigen, wie man mit dem RSA-Verfahren Nachrichten, nur für uns lesbar, verschlüsseln kann.

Anforderungen an den Klartext

Bevor wir den Verschlüsselungsalgorithmus anwenden können, muss der Klartext $m$ in einem numerischen Alphabet vorliegen. Dies können wir, wenn nicht bereits der Fall, durch die Kodierung des Klartextes in ein numerisches Alphabet realisieren.

Darüber hinaus muss $m\in \mathbb{Z}/N\mathbb{Z}$ ein Standardrepräsentant von $\mathbb{Z}/N\mathbb{Z}$ sein. Andernfalls würden Informationen bei der Verschlüsselung und Entschlüsselung verloren gehen (siehe Lernaufgabe Verschlüsselung und Lernaufgabe Entschlüsselung). Wir können jedoch einen Klartext, der kein Standardrepräsentant von $\mathbb{Z}/N\mathbb{Z}$ ist, in kleiner Blöcke mit fester Reihenfolge aufteilen, sodass jeder dieser Blöcke Standardrepräsentant von $\mathbb{Z}/N\mathbb{Z}$ ist.

Man muss also manchen Fällen bis zu zwei Schritte ausführen, bevor man den Klartext verschlüsseln kann:

1. Übertragung des Klartextes in ein numerisches Alphabet
   • Transformiere den zu verschlüsselnden Klartext $m\in M$ (Menge der möglichen Klartexte) in das gewünschten numerisches Alphabet mittels Zeichenkodierung
2. Aufteilung des Klartextes in $l\in \mathbb{N}$ Blöcke
   • Die Blöcke werden in diesem Kurs mit $-$ voneinander getrennt dargestellt und es gilt $m=m_1-m_2-\dots -m_l$
     • Es handelt sich bei dem Zeichen $-$ in diesem Fall nicht um den mathematischen Operator des Minuszeichens der Subtraktion
   • Die Blöcke müssen kleiner $N$ sein, da der Block sonst kein Standardrepräsentant der Restklasse $\mathbb{Z}/N\mathbb{Z}$ ist und bei der Anwendung des Entschlüsselungsalgorithmus nur Standardrepräsentanten ausgegeben werden können. So würde also anstelle des ursprünglichen Klartextes ein vermeintlicher Klartext entschlüsselt werden
   • Aus dem selben Grund darf kein Block mit $0$ beginnen. Es würde nämlich zu einer Leserasterverschiebung kommen, sodass die Information "$0$" verloren gehen würde, da $0301=301$ für den Ver- und Entschlüsselungsalgorithmus

Verschlüsselungsalgorithmus

Nun beschreiben wir den eigentlichen Verschlüsselungsalgorithmus. Der Algorithmus besteht aus einem einzigen Schritt:

1. Berechnung des Geheimtextes $c\in \mathbb{Z}/N\mathbb{Z}$ aus $m\in \mathbb{Z}/N\mathbb{Z}$
   • $c\equiv m^{e}modN$
     • In der Praxis muss jeder Block eines Klartextes $m>N$ einzeln verschlüsselt werden und es gilt für alle $i\in \{1,2,\dots ,l\}$ $c_i\equiv m_i^{e}modN$.

Achtung: Die Blöcke des erzeugten Geheimtextes dürfen nicht aneinander gefügt werden, ohne diese wieder fehlerfrei trennen zu können. Andernfalls kommt es wahrscheinlich zu falschen Blöcken bei der Entschlüsselung.

Beispiel

Tabelle 1: Zuordnung der Zeichenkodierung (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

Wir wollen den Klartext HALLO WELT. mit dem öffentlichen Schlüssel $(23,143)$ des Empfängers verschlüsseln. Da wir auch die Entschlüsselung in einer späteren Lerneinheit zeigen wollen, sind wir nicht nur Sender, sondern auch Empfänger in diesem Beispiel.

1. Mathematisierung des Klartextes $m\in \mathbb{Z}/143\mathbb{Z}$
   1. Übertragung des Klartextes in ein numerisches Alphabet
      • Wir definieren zu unserem Klartext HALLO WELT. das zugehörige Alphabet ${\mathrm{\Sigma }}_1=\{\text{NUL},.\}\cup \{A,B,\dots ,Z\}$
      • Als numerisches Alphabet wählen wir einen Ausschnitt aus ASCII-Zeichenkodierung und definieren das dazugehörige Alphabet ${\mathrm{\Sigma }}_2=\{0,46\}\cup \{65,66,\dots ,90\}$
      • Wir definieren unseren Zeichenkodierung $f:{\mathrm{\Sigma }}_1\to {\mathrm{\Sigma }}_2$ so, dass die Zeichen von ${\mathrm{\Sigma }}_1$ wie in Tabelle 1 beschrieben auf ${\mathrm{\Sigma }}_2$ abbilden (siehe Tabelle 1)
        • Wir erhalten den transformierten Klartext $m=726576767908769768446$, da $f(H)=72$, $f(A)=65$, etc.
   2. Aufteilung des Klartextes in $l$ Blöcke
      • Jeder Block muss kleiner $N=143$ sein und wir erhalten somit $11$ Blöcke
        • $m=m_1-m_2-\dots -m_{11}=72-65-76-76-7-90-87-69-76-84-46$
2. Verschlüsselungsalgorithmus
   1. Berechnung des Geheimtextes $c\in C$
      • Wir setzen den Verschlüsselungsexponenten $e=23$ und den RSA-Modul $N=143$ des öffentlichen Schlüssels aus der Aufgabe zum Schlüsselerzeugungsalgorithmus in den Verschlüsselungsalgorithmus $c\equiv m^{e}modN$ ein
      • Jeder Block wird einzeln mit dem Verschlüsselungsalgorithmus $E$ verschlüsselt
        • $c_1\equiv 72^{23}\equiv 106mod143$, $c_2\equiv 65^{23}\equiv 65mod143$, $c_3\equiv 76^{23}\equiv 32mod143$, $\dots$, $c_{11}\equiv 46^{23}\equiv 41mod143$
        • Man erhält die verschlüsselten Blöcke $106,65,32,32,2,129,120,49,32,24,41$ und den Geheimtext $c=106-65-32-32-2-129-120-49-32-24-41$.

Lernaufgabe

Aufgabe 1

Berechnen Sie die Verschlüsselung der Klartexte $m_1=0301$ und $m_2=301$ mit dem öffentlichen Schlüsse aus dem Beispiel und ignorieren Sie dabei die Bedingung $m\in \mathbb{Z}/143\mathbb{Z}$. Begründen Sie, warum ein Klartext nicht mit $0$ beginnen darf.

Lösung

Seien $e=23$ und $N=143$. Zu $m_1=0301$: Wir ignorieren die Bedingung $0301\in \mathbb{Z}/143\mathbb{Z}$ und verschlüsseln den Klartext: $c_1=20\equiv 0301^{23}mod143$. Zu $m_2=301$: Wir ignorieren die Bedingung $301\in \mathbb{Z}/143\mathbb{Z}$ und verschlüsseln den Klartext: $c_2=20\equiv 301^{23}mod143$. Die Verschlüsselung von $m_1$ bzw. $m_2$ liefert $c_1=20$ bzw. $c_2=20$. Es gilt $m_1\ne m_2$, aber $c_1=c_2$. Dies lässt darauf schließen, dass eine Information einer der beiden Klartexte verloren gegangen ist. Da bei Rechenoperationen in $\mathbb{Z}$ $0301=301$, kann man annehmen, dass $0301=301$ im Verschlüsselungsalgorithmus gilt.

Aufgabe 2

Berechnen Sie die Verschlüsselung des Klartextes "ASTERIX" aus dem Beispiel zum Caesar-Algorithmus oder einen eigenen Klartext mit dem RSA-Algorithmus und der Zeichenkodierung aus Tabelle 1. Sie können die Schlüsselpaare aus dem Beispiel verwenden oder die aus der Lernaufgabe zur Schlüsselerzeugung, falls Sie diese bearbeitet haben.

Lösung

Seien $e=23$ und $N=143$. Wir transformieren den Klartext $m=ASTERIX=65838469827388$. Wir erhalten folgende Blöcke kleiner $143$: $m=m_1-m_2-\dots -m_7=65-83-84-69-82-73-88$. Nun verschlüsseln wir die Blöcke einzeln mit dem Verschlüsselungsalgorithmus des RSA-Verschlüsselungsverfahren: $c_i=m_i^{23}mod143$ mit $i\in \{1,2,\dots ,7\}$ $c_1=65\equiv 65^{23}mod143$, $c_2=73\equiv 83^{23}mod143$, $c_3=24\equiv 84^{23}mod143$, $c_4=49\equiv 69^{23}mod143$, $c_5=114\equiv 82^{23}mod143$, $c_6=57\equiv 73^{23}mod143$, und $c_7=121\equiv 88^{23}mod143$. Der Geheimtext lautet also: $c=c_1-c_2-\dots -c_7=65-73-24-49-114-57-121$.

Lernempfehlung

Kursübersicht

Übergeordnete Lerneinheit
6: RSA-Kryptosystem
Vorherige Lerneinheit	Aktuelle Lerneinheit	Empfohlene Lerneinheit
7.1: Schlüsselerzeugung des RSA-Verschlüsselungsverfahrens	7.2: Verschlüsselungsalgorithmus des RSA-Verschlüsselungsverfahrens	7.3: Entschlüsselungsalgorithmus des RSA-Verschlüsselungsverfahrens