IMP 10 · Kryptologie und Rechner

RSA im Kleinen

Bei RSA gibt es zwei Schlüssel: Mit dem öffentlichen kann jeder verschlüsseln, nur der private entschlüsselt wieder. Die Sicherheit beruht darauf, dass man zwei große Primzahlen leicht multiplizieren, ihr Produkt aber kaum wieder zerlegen kann. Die kleinen Zahlen hier zeigen nur die Rechnung. Sicher sind sie nicht, ein Rechner zerlegt sie sofort.

So gehst du vor

1Wähle zwei Primzahlen und einen passenden Exponenten e.
2Rechne d selbst mit dem euklidischen Algorithmus aus und vergleiche.
3Verschlüssele eine Zahl und entschlüssele sie wieder. Verfolge die Tabelle.
4Spiele zum Schluss Angreifer: Zerlege n und finde d.

1. Schlüssel erzeugen

passt zum Beispiel:

n = p · q = 11 · 17 = 187

φ(n) = (p − 1)(q − 1) = 10 · 16 = 160

ggT(e, φ(n)) = ggT(3, 160) = 1 ✓

Öffentlicher Schlüssel

(n = 187; e = 3)

für alle sichtbar

Privater Schlüssel

(n = 187; d = 107)

bleibt geheim, wie p und q

2. d mit dem erweiterten euklidischen Algorithmus

Gesucht ist das Inverse von e modulo φ(n): eine Zahl d mit e · d ≡ 1 (mod 160).

Teilen mit Rest

160 = 53 · 3 + 1

3 = 3 · 1 + 0

Rückwärts einsetzen

1 = 1 · 160 + (−53) · 3

Also (−53) · 3 ≡ 1 (mod 160), und −53 + 160 = 107. Damit ist d = 107. Probe: 3 · 107 = 321 = 2 · 160 + 1.

3. Eine Zahl verschlüsseln und entschlüsseln

Nachricht mEs muss 0 ≤ m < n gelten, also höchstens 186.

Verschlüsseln: c = m^e mod n

Exponent 3 als Binärzahl: 11

Ziffer	quadrieren	mal 42	erreicht
1	1² ≡ 1	1 · 42 ≡ 42	42¹ ≡ 42
1	42² ≡ 81	81 · 42 ≡ 36	42³ ≡ 36

c = 42³ mod 187 = 36

Entschlüsseln: m = c^d mod n

Exponent 107 als Binärzahl: 1101011

Ziffer	quadrieren	mal 36	erreicht
1	1² ≡ 1	1 · 36 ≡ 36	36¹ ≡ 36
1	36² ≡ 174	174 · 36 ≡ 93	36³ ≡ 93
0	93² ≡ 47	–	36⁶ ≡ 47
1	47² ≡ 152	152 · 36 ≡ 49	36¹³ ≡ 49
0	49² ≡ 157	–	36²⁶ ≡ 157
1	157² ≡ 152	152 · 36 ≡ 49	36⁵³ ≡ 49
1	49² ≡ 157	157 · 36 ≡ 42	36¹⁰⁷ ≡ 42

m = 36¹⁰⁷ mod 187 = 42

Alle Rechnungen modulo 187. Jedes Zwischenergebnis wird sofort reduziert, deshalb bleiben die Zahlen klein. Zum Ausprobieren von Hand reicht ein Taschenrechner.

4. Ein Wort Buchstabe für Buchstabe

Wort (A = 1, B = 2, …, Z = 26)

Buchstabe	I	M	M	E	R
m	9	13	13	5	18
c	168	140	140	125	35
zurück	I	M	M	E	R

Gleiche Buchstaben ergeben gleiche Geheimzahlen. Das ist wieder nur eine Ersetzung der Buchstaben, und die Häufigkeitsanalyse knackt sie. Darum verschlüsselt man in der Praxis nie einzelne Buchstaben, sondern lange Blöcke mit Zufallsanteil.

5. Der Angriff: n zerlegen

Ein Angreifer kennt n = 187, e = 3 und die Geheimzahl c = 36. Kann er n in p und q zerlegen, rechnet er φ(n) und d genauso aus wie du.

Stellen von n	Versuche bis zur Wurzel aus n	Dauer bei einer Milliarde Versuchen je Sekunde
10	10⁵	0,1 Millisekunden
20	10¹⁰	10 Sekunden
40	10²⁰	etwa 3200 Jahre
617 (RSA mit 2048 Bit)	etwa 10³⁰⁸	unvorstellbar: Das Weltall ist erst etwa 4 · 10¹⁷ Sekunden alt

Es gibt schnellere Verfahren als Probieren. Deshalb nimmt man heute mindestens 2048 Bit. Mit den Zahlen dieser Seite darf man nie etwas wirklich verschlüsseln.

Aufträge

Bestimme von Hand für p = 5, q = 11 und e = 3 die Zahlen n, φ(n) und d. Prüfe mit der Seite.
Verschlüssele mit diesem Schlüssel m = 2 von Hand und entschlüssele auf der Seite.
Stelle p = 5, q = 11 ein und versuche e = 5. Was geschieht und warum?
Stelle das Beispiel 61 und 53 mit e = 17 ein. Zähle in der Tafel, wie viele Quadrierungen und Multiplikationen man für m¹⁷ braucht. Vergleiche mit dem Malnehmen Schritt für Schritt.
Du fängst die Geheimzahl c = 2790 ab, der öffentliche Schlüssel ist (3233; 17). Bestimme die Nachricht.
Das Wort IMMER ergibt in Teil 4 zwei gleiche Geheimzahlen hintereinander. Erkläre, warum ein Angreifer damit etwas anfangen kann, obwohl er d nicht kennt. Er kennt sogar den öffentlichen Schlüssel: Was kann er noch tun?

Warum klappt das? Aus e · d ≡ 1 (mod φ(n)) folgt nach dem Satz von Euler m^{e · d} ≡ m (mod n). Verschlüsseln und Entschlüsseln heben sich also auf.