12.3.5 Asymmetrische Verschlüsselung


Bei einem asymmetrischen Verschlüsselungsverfahren gibt es zwei Schlüssel. Das Schlüsselpaar besteht aus:

  • einem privaten Schlüssel (private key) und
  • einem öffentlichen Schlüssel (public key).

Beispiel: Bob sendet an Alice eine verschlüsselte Botschaft

Schritt 1: Alice erzeugt ein Schlüsselpaar aus einem privaten und einem öffentlichen Schlüssel. 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 ...

Eine asymmetrische Verschlüsselung basiert auf der Anwendung von sogenannten Einweg-Funktionen.

Dabei gilt: je größer die Primzahlen sind, aus denen ein Produkt gebildet wird, desto schwieriger ist es, diese Zahl in zwei Primfaktoren zu zerlegen.


Beispiel

Auf folgender Seite findet man eine Liste der Primzahlen von 2 bis 100.000: Tabelle der Primzahlen

Nimmt man zwei dieser Primzahlen und multipliziert diese, dann entsteht eine große Zahl:

\[ 7.187 \cdot 6.361 = 45.716.507\]

Diese Rechnung kann jeder Taschenrechner leisten.

Kehrt man die Aufgabe um, dass also zu der Zahl 45.716.507 die beiden Primzahlen gefunden werden sollen, die Teiler dieser Zahl sind, dann müsste ein Computer im ungünstigsten Fall alle Kombinationen der Primzahlen zwischen 0 und 10.000 per Ausprobieren ermitteln. Das wird immer schwieriger, je größer die Zahl wird.

Eine besondere Variante von Einweg-Funktionen sind Falltür-Funktionen, welche sich effizient (in kurzer Zeit und mit wenig Rechenleistung) umkehren lassen, wenn man bestimmte Zusatzinformationen besitzt.

Die RSA-Verschlüsselung ist ein Beispiel für den Einsatz einer Falltür-Funktion. RSA leitet sich aus den Anfangsbuchstaben des Nachnamens seiner Erfinder (Rivest, Shamir, Adleman) ab und wurde im Jahr 1977 entwickelt.

Hinweis: 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.

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.

  • Setze \(m = 66\).

  • Berechne \(c\) aus \(m\) und dem öffentlichen Schlüssel \(S_\text{ö} = (109; 221)\) und folgender Formel:

\[ 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.

  • Setze \(c = 53\).

  • Berechne \(m\) aus \(c\) mit dem privaten Schlüssel \(S_\text{p} = (37; 221)\) und folgender Formel:

\[ 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