Dies ist eine alte Version des Dokuments!
IV. Das RSA-Verfahren
Die drei Mathematiker Ron Rivest, Adi Shamir und Leonard Adleman fanden eine Möglichkeit, wie ein asymmetrisches Kryptosystem mathematisch realisiert werden kann und daraus entstand das auch heute noch am häufigsten angewandte und nach ihnen benannte RSA-Verfahren.
1. Das RSA-Verfahren anhand eines Beispiels
Das RSA-Verfahren verwendet für die Ver- und Entschlüsselung sehr einfache Prinzipien. Ähnlich wie bei Diffie-Hellman muss man hochrechnen modulo n.
Öffentlicher Schlüssel von Bob: $e = 24'019$ und $n=213'693'769$
Privater Schlüssel von Bob: d = 142'312'027
Alice möchte die Meldung $m=24356$ verschlüsseln:
Verschlüsselung: Alice nimmt den öffentl. Schlüssel von Bob und rechnet: $c = m^e \mod n = 24356^{24019} \mod 213693769 = 198'232'690$
Entschlüsselung: Bob erhält den verschlüsselten Text $c$ und rechnet: $ c^d \mod n = 198232690^{142312027} \mod 213693769 = 24356 = m$
Bob konnte also mit seinem Privaten Schlüssel $d$ die verschlüsselte Nachricht entschlüsseln.
2. Wie kann der öffentliche und der private Schlüssel generiert werden?
2.1 Eulersche Phi-Funktion
Die Eulersche $\varphi$-Funktion ordnet jeder Zahl $n$ die Anzahl ganzer Zahlen zu, die kleiner als $n$ und teilerfremd zu $n$ sind.
Aufgabe
- Bestimme $\varphi(n)$ für alle Zahlen $n<20$.
- Wie gross ist $\varphi(p)$ für eine Primzahl $p$?
- Wie gross ist $\varphi(p \cdot q)$, wenn $p$ und $q$ Primzahlen sind?
2.2 Euklidischer Algorithmus, um den GGT zu bestimmen
Der Euklidische Algorithmus ist ein sehr effizientes Verfahren, um den grössten gemeinsamen Teiler (GGT) von zwei Zahlen $a$ und $b$ herauszufinden. Es gilt nämlich: GGT(a,b) = GGT(b, a mod b). Wollen wir z.B. den GGT von 2210 und 910 bestimmen, so können wir sukzessive reduzieren:
| a | b | a mod b |
|---|---|---|
| 2210 | 910 | 390 |
| 910 | 390 | 130 |
| 390 | 130 | 0 |
Der GGT von 2210 und 910 ist also derselbe wir derjenige von 390 und 130, welcher natürlich 130 ist.
2.3 Erweiterter Euklidischer Algorithmus
Wenn man eine zusätzliche Spalte einführt, und den Rest jeweils als Linearkombination von a und b schreibt, erhält man am Schluss auch den GGT als Linearkombination von a und b. Dies ist der Erweiterte Euklidische Algorithmus.
| a | b | a mod b | Rechnung |
|---|---|---|---|
| 2210 | 910 | $390=2210-2\cdot 910 $ | |
| 910 | 390 | $130=910-2\cdot 390 $ | $130 = 910-2\cdot(2210-2\cdot 910)= 5\cdot 910 - 2 \cdot 2210$ |
| 390 | 130 | 0 |
Wir haben also den GGT von 2210 und 910 als Linearkombination dieser beiden Zahlen geschrieben: $130 = 5\cdot 910 - 2\cdot 2210$.
2.3 Privater und öffentlicher Schlüssel erstellen
Um die Schlüssel zu erstellen, geht man folgendermassen vor:
- Wähle zwei Primzahlen $p$ und $q$ (in der Praxis oft 512-1024 Bit gross) und multipliziere diese zur Zahl $n = p \cdot q$.
- Berechne $\varphi(n) = (p-1) (q-1)$
- Wähle einen öffentlichen Schlüssel $e$, wobei GGT($e$,$\varphi(n)$)=1 sein muss.
- Berechne den privaten Schlüssel $d$, so dass $e \cdot d = 1$ mod $\varphi(n)$ ist.
Dies ist durch den erweiterten Euklidischen Algorithmus möglich (siehe Bemerkung unten).
Bemerkung zu Punkt 4:
- Da $e \cdot d = 1$ mod $\varphi(n)$ gilt, ist $d$ das Inverse von $e$ modulo $\varphi(n)$.
- Da der GGT von $\varphi(n)$ und $e$ Eins ist können wir mit dem erweiterten Euklidischen Algorithmus diese Eins schreiben als: $1 = a \cdot \varphi(n) + d\cdot e$.
Nehmen wir diese Gleichung modulo $\varphi(n)$ erhalten wir $1 = d\cdot e$ mod $\varphi(n)$ (da $a\cdot \varphi(n)$ ein Vielfaches von $\varphi(n)$ ist, fällt es weg).
Aufgabe 2
- Verschlüssle den Text m=6 mit dem öffentilchen Schlüssel $e=19, n=65$
- Knacke den öffentlichen Schlüssel von oben, d.h. finden $\varphi(n)$ und den privaten Schlüssel $d$.
- Worauf basiert die Sicherheit des RSA-Verfahrens? Weshalb ist es schwierig, einen öffentlichen Schlüssel zu knacken?
- Jemand fängt die Nachricht $c=15$ ab und er weiss, dass der Absender den öffentlichen Schlüssel $e=7$ und $n=27$ hat.
Wie lautet der Klartext? - Versuche mit Hilfe von Python/Mathematica den Schlüssel aus dem Einführungsbeispiel zu knacken ($e = 24'019$ und $n=213'693'769$).
2.4 Beweis der Korrektheit des RSA-Verfahrens
Wenn man verstehen will, warum das RSA-Verfahren funktioniert, d.h. warum der private Schlüssel die Verschlüsselung rückgängig macht, muss man einen Satz von Euler anwenden.
Der Satz von Euler
Für zwei teilerfremde Zahlen $a$ und $n$ gilt: $a^{\varphi(n)}=1$ mod n.
Beim RSA-Verfahren wird die Meldung $m$ zu einem Geheimtext $c$ verschlüsselt durch $c=m^e$ mod $n$. Danach wird der Geheimtext wieder hoch den privaten Schlüssel $d$ gerechnet, man hat also insgesamt: $( (m^e)$ mod n $)^d$ mod n. Und dies sollte wieder m geben.
Das Obige kann man auch mit einem einzigen mod n schreiben: $m^{e\cdot d}$ mod n sollte also wieder m geben.
Da $d$ so gewählt ist, dass $e\cdot d = 1$ mod $\varphi(n)$, ist $e\cdot d = 1 + k \cdot \varphi(n)$, woraus folgt:
$m^{e\cdot d}$ mod n = $m^{1 + k \cdot \varphi(n)} = m^1 \cdot m^{k\cdot \varphi(n)} = m^1 \cdot (m^{\varphi(n)})^k$
Und da $m^{\varphi(n)=1}$ mod n (zumindest für m teilerfremd zu n), gilt:
m^{e\cdot d}$ mod n $=m$. Zurück zur Übersicht