RSA

Das Symmetrische-Schlüssel-Problem

Wird der Schlüssel beim Austausch abgefangen, so ist die gesamte Verschlüsselung wertlos. Lange Zeit galt diese Sicherheitslücke als unvermeidbar. Es gibt aber auch Verschlüsselungen, die ganz ohne unsicheren Schlüsselaustausch auskommen:

Wir denken uns für eine erste Idee, dass eine Kiste geschickt wird, die man mit einem Vorhängeschloss abschliessen kann. Dabei wird zwar die Nachricht mehrfach hin und her geschickt, es wird aber kein Schlüssel ausgetauscht.

Das geht so, wenn Alice Bob eine verschlüsselte Nachricht schicken möchte:

Alice verschliesst die Kiste mit ihrem Schloss und schickt sie Bob.
Bob verschliesst die Kiste ein zweites Mal mit seinem Schloss und schickt sie Alice zurück.
Alice entfernt ihr Schloss mit ihrem Schlüssel und schickt die Kiste wieder an Bob.
Bob kann die Kiste mit seinem Schlüssel öffnen.

Exercise 1: Kisten verschicken

Das Verfahren geht natürlich einfacher, ohne die Kiste hin und her schicken zu müssen. Nämlich ...

Solution

Bob könnte Alice beispielsweise ein offenes Vorhängeschloss, dessen Schlüssel er besitzt, schicken.

Das Diffie-Hellman-Merkle-Verfahren

Im Jahr 1976 hatte Hellman die Idee für ein Konzept zum Schlüsselaustausch, das auf dem oben genannten Prinzip aufbaut. Es erlaubt Alice und Bob, einen Schlüsselaustausch vorzunehmen, ohne sich dazu treffen zu müssen.

Example 1

Alice und Bob wählen gemeinsam eine Primzahl $p$ und eine Primitivwurzel $g\in\mathbb{Z}^\ast_p$ .
Alice wählt eine geheime Zahl $a \in \mathbb{Z}_p^*$
Bob wählt eine geheime Zahl $b \in \mathbb{Z}_p^*$

Sie berechnen jeweils ihren "öffentlichen Schlüssel":

Alice: $A = g^a \mod p$
Bob: $B = g^b \mod p$

Diese Werte $A$ und $B$ werden öffentlich übermittelt; es ist praktisch unmöglich, daraus $a$ oder $b$ zu berechnen.

Nun berechnen beide den gemeinsamen Schlüssel $K$ :

Alice: $K_A = B^a \mod p$
Bob: $K_B = A^b \mod p$

Es ist $K_A = K_B$ ; dieser Schlüssel $K$ kann nun für die symmetrische Verschlüsselung verwendet werden.

Proof

K_A = B^a \mod p = (g^b)^a \mod p = g^{ba} \mod p = g^{ab} \mod p = (g^a)^b \mod p = A^b = K_B;

daher: $K = K_A = K_B$

Example 2

Gegeben:

$p = 31$
$g = 2$
$a = 3$
$b = 6$

Berechnung:

$A = 2^3 \mod 31 = 8$
$B = 2^6 \mod 31 = 64 \mod 31 = 2$

Schlüsselberechnung:

$K_A = B^a \mod 31 = 2^3 = 8$
$K_B = A^b \mod 31 = 8^6 \mod 31 = 262144 \mod 31 = 8$

Beide erhalten denselben Schlüssel: $K = 8$

Betrachte noch folgende Überlegungen: Falls Eve den Wert $B = 2$ (oder $A = 8$ ) abfängt, muss sie versuchen, den Exponenten $b$ (bzw. $a$ ) durch Ausprobieren zu finden.

Angenommen

2^x \mod 31 = 2

Schon der erste Versuch mit $x = 1$ liefert das korrekte Resultat: $2^1 \mod 31 = 2$ . Das bedeutet: Eve findet irgendein gültiges $x$ , aber nicht notwendigerweise das ursprünglich gewählte $b = 6$ .

Oder, falls man keine Primitivwurzel wählt, hat man die Schwachstelle, dass die Werte $2^x \mod 31$ nicht alle möglichen Reste aus $\mathbb{Z}_{31}^*$ besuchen:

$x$	$2^x \mod 31$	$3^x \mod 31$
1	2	3
2	4	9
3	8	27
4	16	19
5	1	26
6	2	16
7	4	17
8	8	20
9	16	29
10	1	25
11	2	13
12	4	8
13	8	24
14	16	10
15	1	30

Note 1

Die Zahl $2$ ist keine Primitivwurzel modulo $31$ - es gibt nur 5 verschiedene Resultate: $1$ , $2$ , $4$ , $8$ , $16$ . Dadurch ist es für Eve einfacher, auf den Schlüssel zu schliessen. Wähle also $g$ so, dass $g^x \mod p$ alle Zahlen von $1$ bis $p-1$ abdeckt. Dann ist $g$ eine Primitivwurzel modulo $p$ , und der diskrete Logarithmus wird schwerer zu berechnen.

Einwegfunktionen

Eine Einwegfunktion ist eine Funktion, die in einer Richtung einfach zu berechnen aber sehr schwer umkehrbar ist.

Definition 1: One-Way-Function

Eine One-Way-Function ist eine injektive Funktion

f:X\to Y

so dass gilt:

Es gibt ein effizientes Verfahren zur Bestimmung von $y=f(x)\quad\forall x\in X$ .
Die Umkehrung ist praktisch unmöglich, d.h. es gibt kein effizientes Verfahren zur Bestimmung von $x=f^{-1}(y)\quad\forall y\in f(X)$ .

Note 2

Das heisst nicht, dass eine Einwegfunktion nicht umkehrbar ist, die Umkehrung ist nur so schwierig, dass sie sehr schwer umzusetzen ist. Man braucht also etwas anderes: eine Einwegfunktion mit Falltür; das heisst die Umkehrbarkeit ist effizient möglich, falls man "ein Geheimnis" kennt.

Definition 2: Trap-Door One-Way-Function

Eine Trap-Door One-Way-Function ist eine injektive Funktion $f:X\to Y$ , für die gilt:

Es gibt effiziente Verfahren zur Berechnung von $y=f(x)\quad\forall x\in X$ und $x=f^{-1}(y)\quad\forall y\in f(X)$ .
Das Verfahren zur Berechnung von $f^{-1}$ kann nicht aus dem Verfahren zur Berechnung von $f$ hergeleitet werden - man benötigt eine (geheime) Zusatzinformation.

Dass Funktionen in der modularen Arithmetik zu Einwegfunktionen werden können, wird klar, wenn wir uns folgendes Beispiel anschauen:

Example 3

Nehmen wir die Funktion $f(x) = 3^x$ : Wenn $x = 4$ ist, ist $f(4)=81$ . Auch die Umkehrung ist nicht so schwierig: Ist $f(x) = 81$ , nehmen wir einfach den $\log_3(81)$ und erhalten $4$ als Resultat für $x$ .

Schauen wir uns nun die Funktion in $\mod 17$ an; da wird die Sache kniffliger:

f(x) = 3^x \mod 17

Für $x = 4$ ist das Resultat $13$ . Haben wir nur die Basis $3$ und das Resultat $13 \mod 17$ , wird es schon schwieriger, $x$ zu finden - wir müssen raten.

Definition 3: Diskrete Exponentialfunktion

Eine Funktion der Form $b^x \mod m$ heisst diskrete Exponentialfunktion. Die Umkehrung davon heisst diskreter Logarithmus. Erstere lässt sich selbst für grosse Zahlen effizient ausrechnen.

Example 4

Wir wollen $17^{553} \mod 31$ ausrechnen: Für eine effiziente Berechnung suchen wir eine Zahl der Form $17^x$ , die modulo $31$ einen kleinen Wert ergibt. Wir finden:

17^{30} \mod 31 \equiv 1.

Jetzt wird damit gerechnet:

17^{553} \mod 31 \equiv 17^{30 \cdot 18 + 13} \mod 31 \equiv (17^{30} \mod 31)^{18} \cdot 17^{13} \mod 31.

Da $17^{30} \mod 31 \equiv 1$ , ergibt sich:

1^{18} \cdot 17^{13} \mod 31 \equiv 17^{13} \mod 31 \equiv 3 \mod 31 \equiv 3.

Exercise 2: Mod mit grossen Exponenten

Berechne:

a) $2^{55} \mod 9$

b) $7^{1223} \mod 18$

c) $3^{1023} \mod 10$

Solution

\begin{align*} 2^{55} \mod 9 &\equiv 2^{3 \cdot 18 + 1} \mod 9 \equiv (2^3)^{18} \cdot 2^1 \mod 9\\ &\equiv (-1)^{18} \cdot 2 \mod 9\equiv 2 \mod 9 \end{align*}

\begin{align*} 7^{1223} \mod 18 &\equiv 7^{3 \cdot 407 + 2} \mod 18 \equiv (7^3)^{407} \cdot 7^2\mod 18\\ &\equiv 1^{407} \cdot 49\mod 18 \equiv 13 \mod 18 \end{align*}

\begin{align*} 3^{1023} \mod 10 &\equiv 3^{2 \cdot 511 + 1} \mod 10 \equiv (3^2)^{511} \cdot 3^1 \mod 10\\ &\equiv (-1)^{511} \cdot 3 \mod 10 \equiv -3 \mod 10 \equiv 7 \mod 10 \end{align*}

Der Weg, um den diskreten Logarithmus auszurechnen, ist im Allgemeinen sehr viel langwieriger, da wir nur ausprobieren können. Bei einem sehr hohen Modulus kann das äusserst lange dauern.

Eine andere One-Way-Function ist die Multiplikation grosser Primzahlen. Wir wissen, dass das Produkt zweier Primzahlen einfach zu berechnen ist - wie sieht es mit der Umkehrung aus?

Exercise 3: Primfaktorzerlegung

Bestimme die Primfaktorzerlegung von

a) 21

b) 65

c) 14'803

d) 12'863'273

Solution

$3\cdot7$ , $5\cdot13$ , $113\cdot131$ und $3259\cdot3947$

Je grösser die Zahl, desto aufwändiger kann es werden, ihre Primfaktorzerlegung zu bestimmen.

Exercise 4: Primfaktorzerlegung II

Bestimme die Primfaktorzerlegung von $2,\,469,\,135$ und $782$ .

Solution

$2$ , $7\cdot 67$ , $5\cdot 3^3$ und $2\cdot17\cdot23$

Obige Übung ist einfach, weil einer der beiden Primfaktoren sehr klein ist. Im Allgemeinen gilt aber, dass das Multiplizieren zweier grosser Primzahlen eine One-Way-Trap-Door-Function ist.

Auf der Multiplikation zweier grosser Primzahlen beruht das bekannteste asymmetrische Verschlüsselungsverfahren RSA. Wählt nämlich Bob zwei grosse Primzahlen $p$ und $q$ und hält diese geheim, so kann er das Produkt $N = p\cdot q$ veröffentlichen, ohne in Gefahr zu laufen, dass jemand die Primfaktoren $p$ und $q$ bestimmen kann.

RSA: Das Verfahren

RSA ist ein asymmetrisches Verfahren; es gibt einen Public Key und einen Private Key. Beide Keys werden mit Hilfe von Primzahlen gebildet und in das Verfahren spielt die Modulo-Rechnung hinein. Den Namen hat das Verfahren von Ronald Rivest, Adi Shamir und Leonard Adleman; sie haben es 1977 kreiert.

Für die Erzeugung der beiden Schlüssel wählt man zunächst zwei grosse Primzahlen $p$ und $q$ . Diese werden multipliziert und man erhält $n = p\cdot q$ . Diese Zahl $n$ sowie eine weitere, (fast) beliebig wählbare Zahl $e$ (encipher: verschlüsseln) bilden den Public Key $(e\mid n)$ . Eine dritte Zahl $d$ (decipher: entschlüsseln), zu deren Berechnung wir später kommen, ist Grundlage des Private Keys. Verschlüsselt wird durch

C\equiv m^e\mod n;

$m$ ist der Klartext (Message), $C$ der verschlüsselte Text (Cipher).

Exercise 5: Modulo is it

Nehmen wir an, du willst an Alice die Nachricht $m$ schicken. Alices Public Key sei $(7\mid 187)$ , also $n=187$ und $e=7$ . Das $m$ sei $76$ ; die Nachricht lautet also ... .

Solution

$76^7\mod187\equiv32=100000_{(2)}$

Zum Entschlüsseln benötigt man den geheimen Schlüssel $d$ . Entschlüsselt wird damit analog durch

m\equiv C^d\mod n.

Exercise 6: Wieder Modulo

Und umgekehrt? Angenommen, dein öffentlicher Schlüssel ist $(7\mid 187)$ . Du erhältst die damit verschlüsselte Nachricht $C=142$ . Um diese zu entschlüsseln, benötigst du deinen Private Key - der ist in diesem Fall $d=23$ .

Solution

$142^{23}\mod187\equiv65$

Note 3

Das funktioniert allerdings nur, wenn die Nachricht $m$ (als Zahl) kleiner ist als $n$ . Dies ist allerdings keine Einschränkung. Will man eine Nachricht verschlüsseln, deren Zahlenwert "zu gross" ist, so teilt man sie in kleinere Blöcke und verschlüsselt jeden Block einzeln.

Example 5

Um es einfach zu halten, codieren wir: Leerzeichen = 00, A = 01, B = 02, \dots, Z = 26. Mit dem Schlüssel $(e\mid n) = (17\mid 2773)$ wird die Nachricht:

\begin{align*} & 05\quad 18\quad 18\quad 01\quad 18\quad 05\quad 00\quad 08\quad 21\\ & 13\quad 01\quad 14\quad 21\quad 13\quad 00\quad 05\quad 19\quad 20 \end{align*}

in 3er-Blöcke geteilt (die sind sicher kleiner als $n$ ):

\begin{align*} & 051\quad 818\quad 011\quad 805\quad 000\quad 821\\ & 130\quad 114\quad 211\quad 300\quad 051\quad 920 \end{align*}

und verschlüsselt zu (mit führenden Nullen auf vier Stellen aufgefüllt):

\begin{align*} & 2236\quad 2000\quad 1725\quad 0542\quad 0000\quad 0436\\ & 1988\quad 1684\quad 1064\quad 0567\quad 2236\quad 0948 \end{align*}

Nun zur Frage, wie man den Private Key $d$ berechnet:

Note 4

Der Private Key $d$ errechnet sich aus der Gleichung

e\cdot d\mod(p-1)(q-1) = 1

Grundlage zur Berechnung von $d$ ist folgender Satz, der garantiert, dass es eine solche Zahl überhaupt gibt - vorausgesetzt die Zahl $e$ hat eine bestimmte Eigenschaft ...

Theorem 1

Sind $a,b\in\mathbb{Z}$ teilerfremd, so gibt es eine ganze Zahl $c$ , so dass

b\cdot c\mod a\equiv1

Proof

Da $a$ und $b$ teilerfremd sind, gilt $\gcd(a,b) = 1$ . Nach dem Satz von Bézout gibt es ganze Zahlen $x,y \in \mathbb{Z}$ mit

a \cdot x + b \cdot y = 1.

Betrachten wir diese Gleichung modulo $a$ , so erhalten wir

a \cdot x + b \cdot y \equiv 1 \pmod{a}.

Da $a \cdot x \equiv 0 \pmod{a}$ , folgt

b \cdot y \equiv 1 \pmod{a}.

Setze $c := y$ . Dann gilt

b \cdot c \equiv 1 \pmod{a},

womit die Existenz von $c$ gezeigt ist.

Definition 4: Modulo Inverses

Mit den Bezeichnungen aus obigem Satz sagt man, $b$ ist Modulo $a$ invertierbar und nennt $c$ das modular Inverse von $b$ .

Exercise 7: Finde mod Inverse

Finde das modular Inverse Element $c$ zu $3$ modulo $5$ .

Solution

Mit Ausprobieren findet man $3^{-1}\equiv2\mod5$ .

In unserem Fall sind wir daran interessiert $e$ modulo $(p-1)(q-1)$ zu invertieren. Das heisst insbesondere, dass $e$ und $(p-1)(q-1)$ teilerfremd sein müssen.

Und wie berechnet man das modular Inverse nun? Ein Verfahren für diese Berechnung ist in dem Beweis zu obigem Satz versteckt. Deswegen folgt er hier ausführlich. Er erfolgt in drei Schritten:

Mit dem euklidschen Algorithmus zur Bestimmung des ggT
Summendarstellung des ggT von entsprechenden Vielfachen der beiden Zahlen (erweiterter Euklidscher Algorithmus)
Betrachtung des Falls, dass $a$ und $b$ teilerfremd sind, d.h. dass ihr ggT $1$ ist.

Wir wissen bereits, wie man den ggT von zwei Zahlen mit dem Euklidschen Algorithmus bestimmt - der ggT ist ja dann der letzte, nichttriviale Rest.

Exercise 8: Recap Euklid'scher Algorithmus

Schreibe allgemein das Verfahren des Euklidschen Algorithmus für zwei Zahlen $a$ und $b$ auf.

Solution

OEdA $a\geq b$ und für unsere Zwecke $\gcd(a,b)=1$ .

\begin{align*} a &= q_1b+r_1\\ b &= q_2r_1+r_2\\ r_1 &= q_3r_2+r_3\\ \vdots &= \vdots\\ r_{k-2} &= q_{k}r_{k-1}+r_{k}\\ r_{k-1} &= q_{k+1}r_{k}+0 \end{align*}

Rechnet man nun rückwärts und ersetzt die Reste durch entsprechende Ausdrücke, so erhält man eine Vielfachendarstellung von $a$ und $b$ für ihren ggT $1$ .

Exercise 9: Recap Beweis Euklid'scher Algorithmus

Zeige dies.

Solution

Aus der letzten Zeile folgt $0=r_{k-1} - q_{k+1}r_k\Leftrightarrow r_{k-1}=q_{k+1}r_k$ und weiter

\begin{align*} r_{k-2} &= q_{k}r_{k-1}+r_{k}\\ &= q_{k}q_{k+1}r_k+r_{k}\\ &= (q_{k}q_{k+1}+1)r_{k}\\ &= l_{k-2}\cdot r_k\tag{$l_{k-2}\in\mathbb{Z}$}\\ &\sim r_k \end{align*}

Rückwärts eingesetzt folgt $b=l_br_k$ und $a=l_ar_k$ , also $r_k|a$ und $r_k|b$ . Also gibt es $x,y\in\mathbb{Z}$ so, dass $r_k=xa+yb$

Exercise 10: Berechne gcd

Berechne mit Hilfe des euklidischen Algorithmus:

a) $\gcd(234,\ 566)$

b) $\gcd(357,\ 131)$

c) $\gcd(728,\ 1339)$

Solution

a) $\gcd(234,\ 566)$
Wende den Algorithmus an:

$566 = 2 \cdot 234 + 98$
$234 = 2 \cdot 98 + 38$
$98 = 2 \cdot 38 + 22$
$38 = 1 \cdot 22 + 16$
$22 = 1 \cdot 16 + 6$
$16 = 2 \cdot 6 + 4$
$6 = 1 \cdot 4 + 2$
$4 = 2 \cdot 2 + 0$

$\Rightarrow \gcd(234,566) = \boxed{2}$

b) $\gcd(357,\ 131)$

$357 = 2 \cdot 131 + 95$
$131 = 1 \cdot 95 + 36$
$95 = 2 \cdot 36 + 23$
$36 = 1 \cdot 23 + 13$
$23 = 1 \cdot 13 + 10$
$13 = 1 \cdot 10 + 3$
$10 = 3 \cdot 3 + 1$
$3 = 3 \cdot 1 + 0$

$\Rightarrow \gcd(357,131) = \boxed{1}$

c) $\gcd(728,\ 1339)$

$1339 = 1 \cdot 728 + 611$
$728 = 1 \cdot 611 + 117$
$611 = 5 \cdot 117 + 26$
$117 = 4 \cdot 26 + 13$
$26 = 2 \cdot 13 + 0$

$\Rightarrow \gcd(728,1339) = \boxed{13}$

Theorem 2: Lemma von Bézout

Zu zwei Zahlen $a,b\in\mathbb{Z}$ gibt es immer Zahlen $x,y\in\mathbb{Z}$ , so dass

\gcd(a,b)=x\cdot a+y\cdot b.

Proof

Idee: Wir betrachten alle ganzzahligen Linearkombinationen von $a$ und $b$ :

S = \{\, x \cdot a + y \cdot b \mid x, y \in \mathbb{Z},\ x \cdot a + y \cdot b > 0 \,\}.

Diese Menge $S$ ist eine Teilmenge der positiven ganzen Zahlen $\mathbb{N}$ und damit nichtleer (z. B. $|a|$ oder $|b|$ liegt in $S$ für geeignetes $x,y$ ). Nach dem Prinzip des wohlgeordneten $\mathbb{N}$ hat $S$ ein kleinstes Element – nennen wir es $d$ . Dann ist $d = x_0 \cdot a + y_0 \cdot b$ für gewisse $x_0, y_0 \in \mathbb{Z}$ .

Nun zeigen wir, dass $d$ der grösste gemeinsame Teiler von $a$ und $b$ ist:

$d$ teilt sowohl $a$ als auch $b$ :
Division mit Rest: Teile $a$ durch $d$ :
$a = q \cdot d + r,\quad \text{mit } 0 \le r < d.$
Dann ist
$r = a - q \cdot d = a - q(x_0 a + y_0 b) = a(1 - qx_0) + b(-q y_0).$
Also ist $r$ eine weitere Linearkombination von $a$ und $b$ , also $r \in S$ . Aber $r < d$ – Widerspruch zur Minimalität von $d$ , ausser für $r = 0$ . Also gilt: $d \mid a$ .

Analog zeigt man: $d \mid b$ .
Wenn $c$ ein Teiler von $a$ und $b$ ist, dann gilt $c \mid d$ :

Denn jede Linearkombination $x \cdot a + y \cdot b$ ist durch $c$ teilbar, also insbesondere $d$ .

$\Rightarrow$ $d$ ist der grösste gemeinsame Teiler von $a$ und $b$ .

Da $d = x_0 \cdot a + y_0 \cdot b$ , folgt die Behauptung.

Damit ist Schritt drei nur noch Formsache. Für teilerfremde $a,b$ gilt jetzt

1=x\cdot a+ y\cdot b

Dies gilt natürlich auch noch modulo $a$ bzw. $b$ , da $x\cdot a\mod a=0$ ist.

x\cdot a+y\cdot b\mod a=y\cdot b\mod a=1.

Also ist $c=y$ modulo $a$ invers zu $b$ .

Hat man also die Vielfachensummendarstellung

1=\gcd((p-1)(q-1),e)=x\cdot(p-1)(q-1)+y\cdot e

bestimmt, so ist die kleinste positive Zahl der Form

y+k\cdot(p-1)(q-1)

gleich dem Private Key $d$ .

Note 5

Dieses $y$ lässt sich also mit dem Euklid'schen Algorithmus berechnen. Erweiterter Euklid kommentiert.

Der erweiterte Euklid'sche Algorithmus

Berechnung des inversen Elements $d$ zu $e \mod \varphi(n)$

Um das inverse Element $d$ zu $e \mod \varphi(n)$ zu berechnen, wird der erweiterte euklidische Algorithmus verwendet. Dabei soll gelten:

d \cdot e \equiv 1 \mod \varphi(n).

Example 6

Gegeben:

$p = 31$
$q = 71$
$n = p \cdot q = 2201$
$e = 37$

Berechne:

\varphi(n) = (p - 1)(q - 1) = 30 \cdot 70 = 2100

Gesucht ist $d$ mit:

d \cdot 37 \equiv 1 \mod 2100

Berechne $\gcd(2100, 37)$ :

$2100 = 56 \cdot 37 + 28$
⇒ $28 = 2100 - 56 \cdot 37$
$37 = 1 \cdot 28 + 9$
⇒ $9 = 37 - 1 \cdot 28$
$28 = 3 \cdot 9 + 1$
⇒ $1 = 28 - 3 \cdot 9$

Rücksubstitution: Substituiere von unten nach oben:

$1 = 28 - 3 \cdot 9$
$= 28 - 3 \cdot (37 - 1 \cdot 28)$
$= 28 - 3 \cdot 37 + 3 \cdot 28$
$= 4 \cdot 28 - 3 \cdot 37$

Jetzt $28$ durch Ausdruck aus 1. Gleichung ersetzen:

$= 4 \cdot (2100 - 56 \cdot 37) - 3 \cdot 37$
$= 4 \cdot 2100 - 224 \cdot 37 - 3 \cdot 37$
$= 4 \cdot 2100 - 227 \cdot 37$

Damit:

1 = 4 \cdot 2100 - 227 \cdot 37

Schlussfolgerung: Das ist eine Darstellung von $1$ als Linearkombination:

1 = x \cdot \varphi(n) + d \cdot e

In unserem Fall:

d = -227 \Rightarrow \text{modulo } 2100 \Rightarrow d \equiv -227 \mod 2100 = \boxed{1873}

Ergebnis: Das modulare Inverse von $e = 37$ modulo $\varphi(n) = 2100$ ist:

\boxed{d = 1873}

Kontrolle:

1873 \cdot 37 = 69301 \mod 2100 = 1 \quad \checkmark

Exercise 11: Inverse Elemente

Gegeben: $e = 59$ , $n = 222$ . Finde das inverse Element $d$ zu $e$ modulo $\varphi(n)$ .

Solution

Gegeben: $e = 59$ , $n = 222$

Zuerst die Primfaktorzerlegung $n = 2 \cdot 3 \cdot 37$ .

Da $\varphi$ multiplikativ ist, gilt:

\begin{align*} \varphi(n) &= \varphi(2 \cdot 3 \cdot 37) = \varphi(2) \cdot \varphi(3) \cdot \varphi(37)\\ &= (2 - 1) \cdot (3 - 1) \cdot (37 - 1) = 1 \cdot 2 \cdot 36 = 72 \end{align*}

Gesucht: $d$ mit $d \cdot 59 \equiv 1 \mod 72$

$72 = 1 \cdot 59 + 13 \Rightarrow 13 = 72 - 1 \cdot 59$
$59 = 4 \cdot 13 + 7 \Rightarrow 7 = 59 - 4 \cdot 13$
$13 = 1 \cdot 7 + 6 \Rightarrow 6 = 13 - 1 \cdot 7$
$7 = 1 \cdot 6 + 1 \Rightarrow 1 = 7 - 1 \cdot 6$

und nun mit dem erweiterten Euklid:

$1 = 7 - 1 \cdot 6$
$= 7 - 1 \cdot (13 - 1 \cdot 7) = -1 \cdot 13 + 2 \cdot 7$
$= -1 \cdot 13 + 2 \cdot (59 - 4 \cdot 13) = -1 \cdot 13 + 2 \cdot 59 - 8 \cdot 13$
$= 2 \cdot 59 - 9 \cdot 13$
$= 2 \cdot 59 - 9 \cdot (72 - 1 \cdot 59) = 2 \cdot 59 - 9 \cdot 72 + 9 \cdot 59$
$= 11 \cdot 59 - 9 \cdot 72$

Ergebnis: $1 = 11 \cdot 59 - 9 \cdot 72$ .

Damit ist $d = \boxed{11}$ .

Kontrolle: $11 \cdot 59 = 649,\quad 649 \mod 72 = 1 \quad \checkmark$

Das modulare Inverse von $59 \mod 72$ ist also: $\boxed{d = 11}$

Note 6

Mit Hilfe des euklidischen Algorithmus kann man also den Private Key $d$ bestimmen. Kennt man die beiden Primzahlen $p$ und $q$ , so ist es also einfach, $d$ zu berechnen und damit dann die mit $n$ und $e$ verschlüsselten Nachrichten zu entschlüsseln. Allerdings ist es nahezu unmöglich, $d$ zu berechnen, ohne $p$ und $q$ zu kennen.

Beweis des RSA-Verfahrens

Aber warum funktioniert das Verfahren denn nun überhaupt? Warum kommt wirklich wieder der Klartext heraus, mit anderen Worten: warum gilt

C^d\mod n=m?

Wir erinnern uns, wie der Cipher-Text entstanden ist,

C^d\mod n = (m^e)^d\mod n= m^{e\cdot d}\mod n,

und können daher die Frage umformulieren: gilt tatsächlich

m^{e\cdot d}\mod n=m?

Die Antwort auf diese Frage lautet natürlich ja. Für den Beweis brauchen wir den kleinen Satz von Fermat, der ein Spezialfall des Satzes von Euler ist. Zur einfachen Formulierung des Satzes brauchen wir die sogenannte Euler'sche $\varphi$ -Funktion.

Definition 5: Euler'sche phi-Funktion

Für eine natürliche Zahl $n$ ist $\varphi(n)$ die Anzahl der natürlichen Zahlen $\leq n$ , deren grösster gemeinsamer Teiler mit $n$ gleich $1$ ist. Man nennt $\varphi$ die Euler'sche $\varphi$ -Funktion.

Theorem 3

Ist $p$ prim, dann gilt

\varphi(p) = p-1.

Proof

Da $p$ teilerfremd zu $1,2,3,\dots,p-1$ ist, folgt der Satz.

Theorem 4

Sind $p,q$ zwei verschiedene Primzahlen, so ist

\varphi(p\cdot q)=(p-1)(q-1).

Proof

Reminder: Die Eulersche $\varphi$ -Funktion zählt die positiven ganzen Zahlen kleiner oder gleich $n$ , die zu $n$ teilerfremd sind.

Seien $p$ und $q$ zwei verschiedene Primzahlen. Dann ist $pq$ zusammengesetzt, aber seine einzigen Primfaktoren sind $p$ und $q$ . Eine Zahl $1 \le k \le pq$ ist genau dann nicht teilerfremd zu $pq$ , wenn sie durch $p$ oder durch $q$ teilbar ist.

Die Anzahl der Zahlen zwischen $1$ und $pq$ , die durch $p$ teilbar sind, ist:

\left\lfloor \frac{pq}{p} \right\rfloor = q.

Analog gibt es $p$ Zahlen, die durch $q$ teilbar sind.

Aber Achtung: Eine Zahl, die sowohl durch $p$ als auch durch $q$ teilbar ist, ist durch $pq$ teilbar – und das ist nur die Zahl $pq$ selbst. Diese wurde also doppelt gezählt, also müssen wir 1 abziehen:

Die Anzahl der Zahlen $1 \le k \le pq$ , die nicht teilerfremd zu $pq$ sind, ist:

q + p - 1.

Somit ist die Anzahl der teilerfremden Zahlen gleich:

pq - (q + p - 1) = pq - p - q + 1 = (p - 1)(q - 1)

und daraus folgt die Behauptung

\varphi(pq) = (p - 1)(q - 1).

Nun folgt der kleine Satz von Fermat. Zuerst schicken wir aber einen Hilfssatz voraus.

Theorem 5

Beim Teilen der ersten $(p - 1)$ Vielfachen von $a \in \mathbb{N}$ , also der Zahlen

a,\, 2a,\, 3a,\, \dotsc,\,(p - 1)a,

durch eine Primzahl $p \in \mathbb{P}$ mit $\gcd(a, p) = 1$ tritt jeder Rest $r_i \in \{1, 2, \dotsc, p-1\}$ genau einmal auf. Formal:

i \cdot a \equiv r_i \mod p, \quad \text{mit } r_i \in \{1, \dotsc, p - 1\}.

Proof

Angenommen, es gäbe zwei gleiche Reste $r_i = r_j$ mit $i \neq j$ , $i, j \in \{1, \dotsc, p - 1\}$ . Dann gälte:

i \cdot a \equiv r_i \equiv r_j \equiv j \cdot a \mod p.

Daraus folgt:

i \cdot a \equiv j \cdot a \mod p \quad \Rightarrow \quad (i - j) \cdot a \equiv 0 \mod p.

Da $\gcd(a, p) = 1$ , kann man durch $a$ kürzen:

i - j \equiv 0 \mod p \quad \Rightarrow \quad i \equiv j \mod p.

Da aber $1 \leq i, j < p$ , folgt daraus $i = j$ , im Widerspruch zur Annahme $i \neq j$ : das heisst jeder Rest $r_i$ tritt genau einmal auf.

Theorem 6: Kleiner Fermatscher Satz

Sei $m$ eine natürliche Zahl und teilerfremd zur Primzahl $p$ . Dann gilt

m^{p-1}\mod p=1.

Proof

Multipliziert man alle möglichen Reste modulo $p$ :

a \cdot 2a \cdot 3a \cdots (p - 1)a \equiv r_1 \cdot r_2 \cdot \dotsc \cdot r_{p-1} \mod p.

Da laut Hilfssatz jeder Rest $r_i$ genau einmal vorkommt, ist:

a^{p - 1} \cdot (p - 1)! \equiv (p - 1)! \mod p.

Da $\gcd((p - 1)!, p) = 1$ , darf man kürzen:

a^{p - 1} \equiv 1 \mod p.

Der Beweis, dass die Entschlüsselung korrekt ist, geht damit so: Wir wissen, dass

e\cdot d\mod(p-1)(q-1)=1.

Das heisst, es gibt ein $k\in\mathbb{Z}$ mit

e\cdot d=k\cdot(p-1)(q-1)+1.

Wir betrachten eine Message $m$ , die ver- und entschlüsselt wird und ziehen vom Resultat $m$ ab:

\begin{align*} m^{e\cdot d}-m\mod p &= m^{k\cdot(p-1)(q-1)+1}-m\mod p\\ &= (m^{(p-1)})^{k(q-1)}\cdot m-m\mod p\\ &= 1^{k(q-1)}\cdot m-m\mod p=0. \end{align*}

Dies gilt insbesondere auch, wenn $p$ ein Teiler von $m$ ist, denn dann ist $m^{e\cdot d}-m\mod p$ sowieso gleich $0$ . Ferner sieht man analog, dass $m^{e\cdot d}-m\mod q = 0$ . Die Primzahlen $p$ und $q$ teilen also dieselbe Zahl $m^{e\cdot d}-m$ , also muss auch ihr Produkt diese Zahl teilen. Somit gilt:

m^{ed}\mod pq=m.

Der Beweis kommentiert.

Anleitung RSA

Schritte:

a) Wähle zwei Primzahlen $p$ und $q$

b) Berechne $n = p \cdot q$

c) Berechne die eulersche Phi-Funktion:

\varphi(n) = (p - 1) \cdot (q - 1)

d) Wähle eine natürliche Zahl $e$ mit $\gcd(e, \varphi(n)) = 1$

e) Berechne $d$ , das inverse Element zu $e \mod \varphi(n)$ mit dem erweiterten euklidischen Algorithmus.
Es gilt:

d \cdot e \equiv 1 \mod \varphi(n)

f) Öffentlicher Schlüssel: $(n,\ e)$

g) Privater Schlüssel: $(n,\ d)$

Der öffentliche Schlüssel wird veröffentlicht, sodass jeder, der eine verschlüsselte Nachricht senden möchte, darauf zugreifen kann. Der Klartext wird mit Hilfe der ASCII-Tabelle in eine binäre Zahl $m$ umgewandelt.

Verschlüsselung:

Gegeben: Nachricht $m$

c \equiv m^e \mod n

Entschlüsselung:

Gegeben: Chiffrat $c$

m \equiv c^d \mod n

Note 7

In der Praxis wird für $e$ oft $2^{16} + 1 = 65537$ gewählt. Ferner: Die Nachricht $m$ muss kleiner sein als $n$ , daher muss sie gegebenenfalls in kleinere Blöcke aufgeteilt werden.

Example 7

Wir erhalten von Alice eine verschlüsselte Nachricht $c$ . Gesucht sind:

der private Schlüssel $(d, n)$
der Klartext $m$

Gegeben:

$p = 43$
$q = 47$
$e = 19$
$c = 74$

Berechnungen:

$n = 43 \cdot 47 = 2021$
$\varphi(n) = (43 - 1)(47 - 1) = 42 \cdot 46 = 1932$

Berechne $d$ mit erweitertem euklidischen Algorithmus

$1932 = 101 \cdot 19 + 13 \Rightarrow 13 = 1932 - 101 \cdot 19$
$19 = 1 \cdot 13 + 6 \Rightarrow 6 = 19 - 1 \cdot 13$
$13 = 2 \cdot 6 + 1 \Rightarrow 1 = 13 - 2 \cdot 6$

Rückwärts eingesetzt:

$1 = 13 - 2 \cdot 6$
$= 13 - 2 \cdot (19 - 1 \cdot 13) = 3 \cdot 13 - 2 \cdot 19$
$= 3 \cdot (1932 - 101 \cdot 19) - 2 \cdot 19 = 3 \cdot 1932 - 305 \cdot 19$ also

1 = 3 \cdot 1932 - 305 \cdot 19

Modulo $\varphi(n) = 1932$ :

d \cdot 19 \equiv 1 \mod 1932 \Rightarrow d = -305 \mod 1932 = \boxed{1627}.

Entschlüsselung der Nachricht

m = c^d \mod n = 74^{1627} \mod 2021

Dies ergibt:

\boxed{m = 1371}

Exercise 12: mit RSA verschlüsseln

$p = 11$ , $q = 5$ und $e = 7$ . Finde $d$ und $n$ und verschlüssle die Zahl $15$ mit RSA.

Solution

$p = 11$ , $q = 5$ , $e = 7$ , $n = 55$

$\varphi(n) = (p−1)\cdot(q−1) = 40$

\begin{align*} 40 &= 5\cdot7 + 5 ⇒ 5 = 40 − 5\cdot7 7 &= 1\cdot5 + 2 ⇒ 2 = 7 − 1\cdot5 5 &= 2\cdot2 + 1 ⇒ 1 = 5 − 2\cdot2 \end{align*}

Rückwärts eingesetzt:

\begin{align*} 1 &= 5 − 2\cdot2 1 &= 5 − 2\cdot(7 − 1\cdot5) = 5 − 2\cdot7 + 2\cdot5 = 3\cdot5 − 2\cdot7 1 &= (−2)\cdot7 + 3\cdot(40 − 5\cdot7) = (−2)\cdot7 + 3\cdot40 − 15\cdot7 &= (−17)\cdot7 + 3\cdot40 \end{align*}

$d = (−17) (mod 40) ≡ 23 (mod 40) = 23$ , $c = m^e (mod n) ≡ 15^7 (mod 55) = 5$ .

Exercise 13: RSA entschlüsseln

$p = 83$ , $q = 113$ , $e = 29$ . Entschlüssle die Zahl $4029$ .

Solution

$p = 83$ , $q = 113$ , $e = 29$ , $n = 83 \cdot 113 = 9379$

$\varphi(n) = (p−1)\cdot(q−1) = 82 \cdot 112 = 9184$

\begin{align*} 9184 &= 316\cdot29 + 20 \Rightarrow 20 = 9184 − 316\cdot29 \\ 29 &= 1\cdot20 + 9 \Rightarrow 9 = 29 − 1\cdot20 \\ 20 &= 2\cdot9 + 2 \Rightarrow 2 = 20 − 2\cdot9 \\ 9 &= 4\cdot2 + 1 \Rightarrow 1 = 9 − 4\cdot2 \end{align*}

Rückwärts eingesetzt:

\begin{align*} 1 &= 9 − 4\cdot2 \\ &= 9 − 4\cdot(20 − 2\cdot9) = 9 − 4\cdot20 + 8\cdot9 = 9\cdot9 − 4\cdot20 \\ &= (−4)\cdot20 + 9\cdot(29 − 1\cdot20) = (−4)\cdot20 + 9\cdot29 − 9\cdot20 = (−13)\cdot20 + 9\cdot29 \\ &= 9\cdot29 − 13\cdot(9184 − 316\cdot29) = 9\cdot29 − 13\cdot9184 + 4108\cdot29 \\ &= 4117\cdot29 − 13\cdot9184 \end{align*}

$d = 4117$ . Entschlüsselung:

m = c^d\ \mathrm{mod}\ n \equiv 4029^{4117}\ \mathrm{mod}\ 9379 = 472

RSA knacken

Zum Schluss noch ein Beispiel, in dem es dem Codeknacker leicht gemacht wird. Also keine Angst, so schnell wie hier lässt sich RSA nicht knacken\dots

Example 8

Man fängt eine RSA-verschlüsselte Nachricht ab. Sie lautet

10473054210223505497035330523101828168 2305497093070549713322042531164705144

Ausserdem weiss man, für wen die Nachricht bestimmt ist. Der öffentliche Schlüssel des Empfängers ist $n=17947$ , $e=21$ . Um die Nachricht zu entschlüsseln, muss man wissen, aus welchen beiden Primzahlen $p$ und $q$ sich $n$ zusammensetzt. Eine erste Möglichkeit, $p$ und $q$ zu finden ist, bei 2 anzufangen und jede Zahl zu testen, ob sie ein Teiler von $n$ ist. Dabei kann man sich die Arbeit einfacher machen, wenn man bedenkt, dass

nicht $p$ und $q$ beide grösser als $\sqrt{n}$ sein können (Man braucht also "nur" die Zahlen bis $\sqrt{n}$ zu testen.)
die beiden gesuchten Teiler von $n$ Primzahlen sind (man braucht also z.B. die geraden Zahlen gar nicht testen).

Allerdings dauert diese Suche um so länger je grösser $p$ und $q$ sind. Es scheint also geschickter zu sein, die Suche bei möglichst grossen Zahlen anzufangen, d.h. bei $\sqrt{n}$ . Wenn die Zahlen $p$ und $q$ eruiert wurden, kann man den Private Key bestimmen.

Das RSA-Rätsel

Im August 1977 wurde mit der Veröffentlichung des RSA-Algorithmus im „Scientific American“ ein Rätsel gestellt: Gegeben ist:

\begin{align*} n = &114 381 625 757 888 867 669 235 779 976 146\\ &612 010 218 296 721 242 362 562 561 842 934\\ &706 935 245 733 897 830 597 123 563 958 705\\ &058 989 075 147 599 290 026 879 543 541 \end{align*}

\begin{align*} c = &96 869 613 754 622 061 477 140 922 254 355\\ &882 905 759 991 124 574 319 847 695 120 930\\ &816 298 225 145 708 356 931 476 622 883 989\\ &628 013 391 990 551 829 945 157 815 154 \end{align*}

e = 9 007

Man entschlüssle die Botschaft $c$ .

Damals ergab sich eine grobe Abschätzung, dass es etwa $4\cdot10^{16}$ ( $40'000'000'000'000'000$ ) Jahre dauern würde, um $n$ zu faktorisieren. Nach einem Zusammenschluss von 1600 Rechnern dauerte es aber nur ein halbes Jahr, bis klar war:

\begin{align*} p &= 3 490 529 510 847 650 949 147 849 619 903\\ &898 133 417 764 638 493 387 849 390 820 577 \end{align*}

\begin{align*} q &= 32 769 132 993 266 709 549 961 988 190 834\\ &461 413 177 642 967 992 942 539 798 288 533 \end{align*}

Die verschlüsselte Botschaft konnte nun leicht ermittelt werden. Sie lautete:

THE MAGIC WORDS ARE SQEAMISCH OSSIFRAGE

(Die magischen Worte sind zimperliche Lämmergeier)

Obwohl diese Nachricht ohne die Kenntnis des privaten Schlüssels dechiffriert wurde, muss man sich keine Sorgen über die Sicherheit von RSA machen. Diese basiert darauf, dass es sehr lange Zeit dauert, bis man von der Zahl n auf die Primfaktoren p und q kommt. Für wichtige Geschäfte wird heute die Zahl n mit mindestens 600 Dezimalstellen gewählt. Aus p und q kann ein Computer die Zahl $n = p\cdot q$ in kürzester Zeit ausrechnen. Um n jedoch zu faktorisieren, würden selbst die vereinten Kräfte von 100 Millionen aktueller Computer über tausend Jahre benötigen. Die einzige Chance, RSA unsicher zu machen, wäre die Entwicklung von besseren Algorithmen zur Primfaktorzerlegung. Allerdings sind Mathematiker schon seit dem Bekanntwerden, dass jede natürliche Zahl eine eindeutige Primfaktorzerlegung besitzt, an der Lösungssuche zur effizienten Primfaktorzerlegung.

$x$	$2^x \mod 31$	$3^x \mod 31$
1	2	3
2	4	9
3	8	27
4	16	19
5	1	26
6	2	16
7	4	17
8	8	20
9	16	29
10	1	25
11	2	13
12	4	8
13	8	24
14	16	10
15	1	30

$x$	$2^x \mod 31$	$3^x \mod 31$
1	2	3
2	4	9
3	8	27
4	16	19
5	1	26
6	2	16
7	4	17
8	8	20
9	16	29
10	1	25
11	2	13
12	4	8
13	8	24
14	16	10
15	1	30

RSA

Das Symmetrische-Schlüssel-Problem

Das Diffie-Hellman-Merkle-Verfahren

Einwegfunktionen

RSA: Das Verfahren

Der erweiterte Euklid'sche Algorithmus

Berechnung des inversen Elements dd zu emod φ(n)e \mod \varphi(n)

Beweis des RSA-Verfahrens

Anleitung RSA

Schritte:

Verschlüsselung:

Entschlüsselung:

RSA knacken

Das RSA-Rätsel

Berechnung des inversen Elements $d$ zu $e \mod \varphi(n)$

$x$	$2^x \mod 31$	$3^x \mod 31$
1	2	3
2	4	9
3	8	27
4	16	19
5	1	26
6	2	16
7	4	17
8	8	20
9	16	29
10	1	25
11	2	13
12	4	8
13	8	24
14	16	10
15	1	30