ef:kryptographie:rsa [DokuWiki CSC]

Diese Seite ist nicht editierbar. Sie können den Quelltext sehen, jedoch nicht verändern. Kontaktieren Sie den Administrator, wenn Sie glauben, dass hier ein Fehler vorliegt.
~~NOTOC~~
<WRAP center 1200px>
====== 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.

<WRAP nicebox green>
**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?
</WRAP>

==== 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  |  <color #ed1c24>130</color>  |  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  |  <color #ed1c24>130</color>  |  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: 
<WRAP nicebox blue>
  - 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). 
</WRAP>
** 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).

<WRAP nicebox green>
**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$).
</WRAP>

==== 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]]
</WRAP>