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 1

  1. Bestimme $\varphi(n)$ für alle Zahlen $n<20$.
  2. Wie gross ist $\varphi(p)$ für eine Primzahl $p$?
  3. 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:

  1. Wähle zwei Primzahlen $p$ und $q$ (in der Praxis oft 512-1024 Bit gross) und multipliziere diese zur Zahl $n = p \cdot q$.
  2. Berechne $\varphi(n) = (p-1) (q-1)$
  3. Wähle einen öffentlichen Schlüssel $e$, wobei GGT($e$,$\varphi(n)$)=1 sein muss.
  4. 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:

Aufgabe 2

  1. Verschlüssle den Text m=6 mit dem öffentlichen Schlüssel $e=19, n=65$
  2. Knacke den öffentlichen Schlüssel von oben, d.h. finde $\varphi(n)$ und den privaten Schlüssel $d$.
  3. Worauf basiert die Sicherheit des RSA-Verfahrens? Weshalb ist es schwierig, einen öffentlichen Schlüssel zu knacken?
  4. 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?
  5. 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$.

Zurück zur Übersicht