RSA-Verschlüsselung mit kleinen Zahlen
Beim Online-Banking, in Messengern und bei jeder Webseite mit Schloss-Symbol steckt Mathematik mit Resten dahinter. Das bekannteste Verfahren ist RSA (nach Rivest, Shamir und Adleman, 1977). Hier lernst Du es mit kleinen Zahlen kennen, die Du von Hand nachrechnen kannst – dazu den chinesischen Restsatz, der RSA schneller macht.
Nur zum Lernen: Mit kleinen Primzahlen ist RSA sofort zu knacken – man zerlegt einfach $n$ in seine Faktoren. Echte Schlüssel haben über 600 Dezimalstellen und brauchen zusätzlich ein Auffüllen der Nachricht („Padding“). Für echte Geheimnisse nutzt man geprüfte Software, nie selbst geschriebene Rechnungen.
Die Idee: ein Schloss, das jeder zudrücken kann
Bei RSA gibt es zwei Schlüssel. Den öffentlichen Schlüssel $(n, e)$ darf jeder kennen – damit kann jeder eine Nachricht verschlüsseln. Entschlüsseln kann sie nur, wer den privaten Schlüssel $d$ besitzt. Das funktioniert, weil sich $d$ zwar leicht aus den beiden Primfaktoren von $n$ berechnen lässt, aber nicht aus $n$ allein: Große Zahlen in Primfaktoren zu zerlegen ist extrem aufwendig.
Schlüssel erzeugen
- Wähle zwei verschiedene Primzahlen $p$ und $q$ und berechne den Modul $n = p \cdot q$.
- Berechne $\varphi(n) = (p - 1)(q - 1)$. Das ist die Anzahl der Zahlen von 1 bis $n$, die mit $n$ keinen gemeinsamen Teiler haben (Eulersche φ-Funktion).
- Wähle den öffentlichen Exponenten $e$ mit $1 < e < \varphi(n)$ und $\operatorname{ggT}(e, \varphi(n)) = 1$.
- Berechne den privaten Exponenten $d$ als Inverses von $e$ modulo $\varphi(n)$: $e \cdot d \equiv 1 \pmod{\varphi(n)}$ – mit dem erweiterten euklidischen Algorithmus.
Beispiel: $p = 11$, $q = 13$, $e = 7$
$n = 11 \cdot 13 = 143$ und $\varphi(n) = 10 \cdot 12 = 120$. Es ist $\operatorname{ggT}(7, 120) = 1$, also passt $e = 7$.
Gesucht ist $d$ mit $7 \cdot d \equiv 1 \pmod{120}$. Der erweiterte euklidische Algorithmus (oder geduldiges Probieren) liefert $d = 103$, denn $7 \cdot 103 = 721 = 6 \cdot 120 + 1$.
Öffentlicher Schlüssel: $(n, e) = (143, 7)$. Privater Schlüssel: $d = 103$. Die Primzahlen 11 und 13 werden danach nicht mehr gebraucht – und dürfen niemandem verraten werden.
Ver- und Entschlüsseln
Eine Nachricht wird zuerst in Zahlen $m$ mit $0 \le m < n$ übersetzt, z. B. A = 1, B = 2, …, Z = 26. Dann gilt:
Beispiel: $m = 9$ verschlüsseln
Mit schnellem Potenzieren: $9^2 = 81$, $9^4 = 81^2 = 6561 \equiv 126 \pmod{143}$. Wegen $7 = 4 + 2 + 1$ ist
$c = 9^7 = 9^4 \cdot 9^2 \cdot 9 \equiv 126 \cdot 81 \cdot 9 \equiv 48 \pmod{143}$.
Wer den privaten Schlüssel kennt, rechnet $48^{103} \bmod 143 = 9$ und erhält die Zahl 9 zurück.
Das Wort MATHE wird Buchstabe für Buchstabe verschlüsselt:
| Buchstabe | $m$ | $c = m^7 \bmod 143$ | $c^{103} \bmod 143$ |
|---|---|---|---|
| M | 13 | 117 | 13 |
| A | 1 | 1 | 1 |
| T | 20 | 136 | 20 |
| H | 8 | 57 | 8 |
| E | 5 | 47 | 5 |
Gleiche Buchstaben ergeben dabei immer dieselbe Zahl – über die Häufigkeit der Buchstaben ließe sich so ein langer Text knacken. Echtes RSA verschlüsselt deshalb große Blöcke mit zufälligem Auffüllen.
Warum kommt die Nachricht zurück?
Wegen $e \cdot d \equiv 1 \pmod{\varphi(n)}$ ist $e \cdot d = 1 + k \cdot \varphi(n)$ für eine ganze Zahl $k$. Der Satz von Euler (eine Verallgemeinerung des kleinen Satzes von Fermat) sagt: Ist $\operatorname{ggT}(m, n) = 1$, dann gilt $m^{\varphi(n)} \equiv 1 \pmod n$. Also
Mit dem chinesischen Restsatz (unten) zeigt man, dass es sogar für alle $m$ mit $0 \le m < n$ klappt.
Der chinesische Restsatz
Schon vor über 1500 Jahren stand in einem chinesischen Rechenbuch sinngemäß die Frage: Welche Zahl lässt beim Teilen durch 3 den Rest 2, durch 5 den Rest 3 und durch 7 den Rest 2? Der chinesische Restsatz sagt:
Chinesischer Restsatz
Sind die Moduln $m_1, m_2, \ldots, m_k$ paarweise teilerfremd, dann hat das System
$x \equiv a_1 \pmod{m_1}, \quad x \equiv a_2 \pmod{m_2}, \quad \ldots, \quad x \equiv a_k \pmod{m_k}$
genau eine Lösung $x$ mit $0 \le x < M = m_1 \cdot m_2 \cdots m_k$. Alle Lösungen sind $x + t \cdot M$ mit ganzem $t$.
Beispiel: $x \equiv 2 \pmod 3$, $x \equiv 3 \pmod 5$, $x \equiv 2 \pmod 7$
Schrittweise: Aus der ersten Kongruenz ist $x = 2 + 3t$, also $x \in \{2, 5, 8, 11, 14, \ldots\}$. Davon lässt 8 bei Division durch 5 den Rest 3, also $x \equiv 8 \pmod{15}$: $x \in \{8, 23, 38, \ldots\}$. Schon 23 lässt bei Division durch 7 den Rest 2. Also $x = 23$, alle Lösungen sind $23 + 105t$.
Mit der Formel: $M = 105$, $M_1 = 105 : 3 = 35$, $M_2 = 21$, $M_3 = 15$. Die Inversen sind $35^{-1} \equiv 2 \pmod 3$, $21^{-1} \equiv 1 \pmod 5$ und $15^{-1} \equiv 1 \pmod 7$. Dann
$x \equiv 2 \cdot 35 \cdot 2 + 3 \cdot 21 \cdot 1 + 2 \cdot 15 \cdot 1 = 140 + 63 + 30 = 233 \equiv 23 \pmod{105}$.
Sind die Moduln nicht teilerfremd, gibt es entweder keine Lösung oder Lösungen modulo des kgV. So ist $x \equiv 1 \pmod 4$, $x \equiv 3 \pmod 6$ lösbar ($x \equiv 9 \pmod{12}$), $x \equiv 1 \pmod 4$, $x \equiv 2 \pmod 6$ dagegen nicht – die erste Gleichung verlangt ein ungerades, die zweite ein gerades $x$. Solche Systeme löst der Modulo-Rechner im Modus „Chinesischer Restsatz“.
Anwendung: RSA schneller entschlüsseln
Wer $p$ und $q$ kennt, rechnet statt einer großen Potenz modulo $n$ zwei kleine: modulo $p$ und modulo $q$, mit verkleinerten Exponenten $d \bmod (p - 1)$ und $d \bmod (q - 1)$. Im Beispiel: $d \bmod 10 = 3$ und $d \bmod 12 = 7$, also
$m \equiv 4^{3} \equiv 9 \pmod{11}$ und $m \equiv 9^{7} \equiv 9 \pmod{13}$.
Der chinesische Restsatz setzt beides zu $m = 9$ zusammen. Bei echten Schlüsseln spart das etwa drei Viertel der Rechenzeit.
Typische Fehler
- $e$ nicht teilerfremd zu $\varphi(n)$: Dann gibt es kein $d$. Bei $\varphi(n) = 120$ scheiden z. B. 2, 3, 4, 5 und 6 aus.
- $d$ modulo $n$ statt modulo $\varphi(n)$: Das Inverse wird modulo $\varphi(n)$ berechnet – potenziert wird aber modulo $n$.
- Nachricht zu groß: Es muss $m < n$ gelten, sonst kommt nur $m \bmod n$ zurück.
- Erst ganz potenzieren: $9^7$ ist noch klein, $48^{103}$ hat aber 174 Stellen. Nach jedem Schritt modulo $n$ reduzieren!
Eigene Schlüssel erzeugen und Nachrichten Schritt für Schritt ver- und entschlüsseln kannst Du mit dem RSA-Rechner. Die Grundlagen – Reste, Inverses, schnelles Potenzieren – stehen unter Modulo und euklidischer Algorithmus.
Online üben
Bei mehreren gesuchten Werten trennst Du sie mit Semikolon, z. B. 143; 120; 103. Beim chinesischen Restsatz ist die kleinste Lösung $x \ge 0$ gesucht.
Stufe 1: Schlüssel erzeugen
-
Aufgabe 1
\(p = 7,\) \(q = 11,\) \(e = 7:\) \(n,\) \(\varphi(n),\) \(d = ?\)\(n; φ(n); d\)\(n = 77;\) \(\varphi(n) = 6 \cdot 10\) \(= 60;\) \(d = 43\ \ (7 \cdot 43 = 301 = 5 \cdot 60 + 1)\)
-
Aufgabe 2
\(p = 19,\) \(q = 29,\) \(e = 5:\) \(n,\) \(\varphi(n),\) \(d = ?\)\(n; φ(n); d\)\(n = 551;\) \(\varphi(n) = 18 \cdot 28\) \(= 504;\) \(d = 101\ \ (5 \cdot 101 = 505 = 1 \cdot 504 + 1)\)
-
Aufgabe 3
\(p = 5,\) \(q = 29,\) \(e = 17:\) \(n,\) \(\varphi(n),\) \(d = ?\)\(n; φ(n); d\)\(n = 145;\) \(\varphi(n) = 4 \cdot 28\) \(= 112;\) \(d = 33\ \ (17 \cdot 33 = 561 = 5 \cdot 112 + 1)\)
-
Aufgabe 4
\(p = 17,\) \(q = 19,\) \(e = 7:\) \(n,\) \(\varphi(n),\) \(d = ?\)\(n; φ(n); d\)\(n = 323;\) \(\varphi(n) = 16 \cdot 18\) \(= 288;\) \(d = 247\ \ (7 \cdot 247 = 1729 = 6 \cdot 288 + 1)\)
-
Aufgabe 5
\(p = 11,\) \(q = 23,\) \(e = 17:\) \(n,\) \(\varphi(n),\) \(d = ?\)\(n; φ(n); d\)\(n = 253;\) \(\varphi(n) = 10 \cdot 22\) \(= 220;\) \(d = 13\ \ (17 \cdot 13 = 221 = 1 \cdot 220 + 1)\)
-
Aufgabe 6
\(p = 5,\) \(q = 23,\) \(e = 5:\) \(n,\) \(\varphi(n),\) \(d = ?\)\(n; φ(n); d\)\(n = 115;\) \(\varphi(n) = 4 \cdot 22\) \(= 88;\) \(d = 53\ \ (5 \cdot 53 = 265 = 3 \cdot 88 + 1)\)
Tippe Deine Lösung ein und klicke auf „Prüfen“ (oder drücke Enter). Brüche als 3/4, Dezimalzahlen mit Komma, mehrere Lösungen mit ; trennen, Potenzen als x^2, Wurzeln als sqrt(5). Punkte: 10 für richtig beim ersten Versuch, 6 nach einem Fehlversuch, 5 mit Tipp, 0 wenn Du Dir vorher die Lösung anschaust. Deine Punkte und Abzeichen siehst Du unter Mein Training.
Arbeitsblatt: RSA mit kleinen Zahlen und chinesischer Restsatz
Eine volle DIN-A4-Seite Aufgaben mit Lösungsblatt zum Ausdrucken – bei jedem Klick neue Aufgaben. Klasse 11–13.
Weiterlesen: RSA-Kryptosystem, Chinesischer Restsatz bei Wikipedia