~~NOTOC~~ ====== IV. Das RSA-Verfahren ====== Die drei Mathematiker Ron **R**ivest, Adi **S**hamir und Leonard **A**dleman 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 1** \\ - 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: |< 450px 150px 150px 150px >| ^ 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**. |< 1000px 100px 100px 250px 550px >| ^ 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 öffentlichen Schlüssel $e=19, n=65$ - Knacke den öffentlichen Schlüssel von oben, d.h. finde $\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=77$ 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)} mod n =1$. 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$. [[ef:start|Zurück zur Übersicht]]