Hinweise:
-
Beim RSA-Verfahren werden nur Zahlen ver- und entschlüsselt. Einem Buchstaben muss vor der Verschlüsselung eine Zahl zugeordnet werden (z.B. ASCII-Codierung).
-
Mit kleinen Primzahlen werden die folgenden Rechenoperationen nachvollziehbar. In einer ernsthaften RSA-Verschlüsselung werden deutlich größere Primzahlen für die Erzeugung des Schlüsselpaars gewählt.
-
In der RSA-Verschlüsselung wird die Restklassenfunktion \(\text{mod}\) verwendet. Beispiel: \(11 \, \text{mod} \, 3 = 2\), da 9 durch 3 ganzzahlig teilbar ist und der Rest \(11-9 = 2\) übrig bleibt.
-
Damit die RSA-Verschlüsselung gelingt, muss das Produkt der gewählten Primzahlen größer als die zu verschlüsselnde Zahl sein.
Schritt 1: Buchstabe in Zahl umwandeln
In diesem Beispiel wird der Buchstabe "B" verschlüsselt. Der ASCII-Code von "B" ist 66.
Zu verschlüsselnde Zahl: 66
Schritt 2: Schlüsselpaar erzeugen
-
Wähle zwei zufällige Primzahlen \(p\) und \(q\). Es seien \(p = 13\) und \(q = 17\).
-
Bilde das Produkt \(n = p \cdot q\) der beiden Primzahlen. Also \(n = 13 \cdot 17 = 221\).
-
Berechne das Produkt \(f = (p-1) \cdot (q-1)\) der Vorgänger der beiden Primzahlen. Also \(f = (13-1) \cdot (17-1) = 12 \cdot 16 = 192\).
-
Wähle eine Zahl \(e\), so dass \(e\) und \(f\) teilerfremd sind, was bedeutet, dass der ggT von \(e\) und \(f\) die Zahl 1 ist. Es sei \(e = 109\).
-
Stelle die Gleichung \(\, (e \cdot d) \, \text{mod} \, f = 1 \,\) auf und suche eine Zahl \(d\), welche diese Gleichung löst. Es sei \(d = 37\).
Probe mit \(e = 109\), \(d = 37\) und \(f = 192\):
- \(109 \cdot 37 = 4033\)
- \(4033 / 192 = 21 \, \text{Rest} \, 1\)
- \((e \cdot d) \, \text{mod} \, f = (109 \cdot 37) \, \text{mod} \, 192 = 1\)
Die Zahl \(37\) löst die Gleichung.
Das Schlüsselpaar aus privatem und öffentlichem Schlüssel kann gebildet werden:
-
Der private Schlüssel \(S_\text{p}\) besteht aus den Zahlen \(d\) und \(n\) mit \(d = 37\) und \(n = 221\), also \(S_\text{p} = (37; 221)\).
-
Der öffentliche Schlüssel \(S_\text{ö}\) besteht aus den Zahlen \(e\) und \(n\) mit \(e = 109\) und \(n = 221\), also \(S_\text{ö} = (109; 221)\).
Schritt 3: Botschaft mit öffentlichem Schlüssel verschlüsseln
Die zuverschlüsselnde Botschaft ist der ASCII-Code des Buchstabens "B", also die Zahl 66.
\[
c = m^e \, \text{mod} \, n\]
\(m\) = ASCII-Code des Buchstaben "B", also \(66\)
\(e\) = erster Teil des öffentlichen Schlüssels, also \(109\)
\(n\) = zweiter Teil des öffentlichen Schlüssels, also \(221\)
also
\[
c = 66^{109} \, \text{mod} \, 221\]
Solche großen Zahlen lassen sich mit dem Taschenrechner nicht berechnen. Wolfram-Alpha liefert:
\[
\begin{align}
66^{109} &= \\
& 21393851358629486016994635861174131831660915391570 \\
& 53356592523385641757907959637349280291639860500342 \\
& 28610595724619066641369366601201263310890858196934 \\
& 2714449679645647241643163676024429820827649703936
\end{align}\]
Wir suchen den Rest von
\[
\begin{align}
& 21393851358629486016994635861174131831660915391570 \\
& 53356592523385641757907959637349280291639860500342 \\
& 28610595724619066641369366601201263310890858196934 \\
& 2714449679645647241643163676024429820827649703936 \, / \,221
\end{align}\]
Wolfram-Alpha liefert:
\[
\begin{align}
& 21393851358629486016994635861174131831660915391570 \\
& 53356592523385641757907959637349280291639860500342 \\
& 28610595724619066641369366601201263310890858196934 \\
& 2714449679645647241643163676024429820827649703936 \, \text{mod} \, 221 = 53
\end{align}\]
Die RSA-Verschlüsselung des ASCII-Codes \(66\) zum Buchstaben "B" mit dem öffentlichen Schlüssel \(S_\text{ö} = (109; 221)\) liefert die Zahl \(53\).
Schritt 4: verschlüsselte Botschaft mit privatem Schlüssel entschlüsseln
Die verschlüsselte Botschaft wird als Zahl \(53\) empfangen.
\[
m = c^d \, \text{mod} \, n\]
\(c\) = Zahlenwert des verschlüsselten Buchstabens, also \(53\)
\(d\) = erster Teil des privaten Schlüssels, also \(37\)
\(n\) = zweiter Teil des privaten Schlüssels, also \(221\)
also
\[
m = 53^{37} \, \text{mod} \, 221\]
Wolfram-Alpha liefert:
\[
\begin{align}
53^{37} &= \\
& 6283580383636683322486356945483938304940 \\
& 731973668146791149026213
\end{align}\]
Wir suchen den Rest von
\[
\begin{align}
& 6283580383636683322486356945483938304940 \\
& 731973668146791149026213 \, / \, 221
\end{align}\]
Wolfram-Alpha liefert:
\[
\begin{align}
& 6283580383636683322486356945483938304940 \\
& 731973668146791149026213 \, \text{mod} \, 221 = 66
\end{align}\]
Die RSA-Entschlüsselung der verschlüsselten Botschaft \(53\) mit dem privaten Schlüssel \(S_\text{p} = (37; 221)\) liefert die Zahl \(66\), aus welcher mit Hilfe des ASCII-Codes der Buchstaben "B" entcodiert werden kann.
Damit ist die Botschaft "B" mit Hilfe der RSA-Verschlüsselung erfolgreich übertragen worden.
Simulation der RSA-Verschlüsselung
Schritt 2: Alice sendet ihren öffentlichen Schlüssel an Bob.
Schritt 3: Bob verschlüsselt seine Botschaft mit dem öffentlichen Schlüssel von Alice und sendet die verschlüsselte Botschaft an Alice.
Schritt 4: Alice entschlüsselt die verschlüsselte Botschaft mit ihrem privaten Schlüssel.
Schritt 5: Damit Alice eine Antwort an Bob senden kann, muss Bob ein Schlüsselpaar erzeugen und seinen öffentlichen Schlüssel an Alice senden ...
