Kryptografische Verfahren – Asymmetrische Verschlüsselungsverfahren

RSA-Verfahren

Verfahren

RSA-Verfahren: Das RSA-Verfahren wurde 1977 von Rivest, Shamir und Adleman als das erste Public-Key-Verfahren entwickelt und basiert auf dem Problem der Faktorisierung von großen Zahlen. RSA ist weit verbreitet, zum einen liegt das daran, dass es sich bei der Faktorisierung um ein viel untersuchtes Verfahren handelt, zum anderen kann gezeigt werden, dass Faktorisierung auf die Berechnung des geheimen Schlüssels reduzierbar ist.

Schlüsselgenerierung:

Wähle zwei große Primzahlen $p \not = q$ (zufällig und stochastisch unabhängig).
Berechne $n := pq$ (RSA-Modul) und $\varphi (n) = (p - 1)(q - 1)$.
Wähle $1 < e < \varphi (n)$ mit $\ggT (e, \varphi (n)) = 1$.
Berechne $s \in \integer /\varphi (n)\integer $ mit $es \equiv 1 \pmod {\varphi (n)}$.
Veröffentliche $k_e := (n, e)$ und halte $k_s := (n, s)$ geheim.

$p$, $q$ und $\varphi (n)$ werden nicht mehr benötigt und können gelöscht werden. Allerdings lässt sich beim Entschlüsseln Zeit sparen, wenn man $p$ und $q$ im Speicher behält (indem man zunächst modulo $p$ und $q$ rechnet und den chinesischen Restsatz anwendet). $e$ wird aus Effizienzgründen oft klein gewählt, z. B. als die Primzahl $2^{16} + 1 = 65537$.

Verschlüsselung: Eine Nachricht $x \in \ZnZ $ wird durch $y := x^e \bmod n$ verschlüsselt.

Entschlüsselung: Eine Nachricht $y \in \ZnZ $ wird durch $z := y^s \bmod n$ entschlüsselt.

Aufgrund der Korrektheit eines kryptografischen Verfahrens gilt $d_{k_s}(c_{k_e}(x)) = x$ immer. Bei RSA gilt allerdings auch $c_{k_e}(d_{k_s}(y)) = y$, d. h. $k_e$ und $k_s$ sind theoretisch austauschbar (in der Praxis allerdings nicht zu empfehlen, weil $e$ oft klein ist).
Bei RSA gilt außerdem $d_{k_s}(c_{k’_e}(c_{k_e}(x))) = c_{k’_e}(x)$, d. h. eine Verschlüsselung kann wieder „aufgehoben“ werden, obwohl die Nachricht ein zweites Mal verschlüsselt wurde.

Korrektheit

Satz (Korrektheit des RSA-Verfahrens): Es gilt $z = x$.

Beweis der Korrektheit: Es gilt $z \equiv _n y^s \equiv _n (x^e)^s$ und nach dem chinesischen Restsatz daher $z \equiv _p x^{es} = x^{1+k(p-1)(q-1)}$ für ein $k \in \integer $. Für $x \equiv _p 0$ (also $p \teilt x$) gilt $x^{1+k(p-1)(q-1)} \equiv _p 0$. Für $x \not \equiv _p 0$ gilt $x^{1+k(p-1)(q-1)} = x \cdot (x^{p-1})^{k(q-1)} \equiv _p x \cdot 1 = x$ wegen $x^{p-1} \equiv _p 1$ (kleiner Satz von Fermat). In jedem Fall gilt $x^{1+k(p-1)(q-1)} \equiv _p x$, also $z \equiv _p x$. Analog zeigt man $z \equiv _q x$.
Nach dem chinesischen Restsatz gilt $z \equiv _n x$. Wegen $x, z \in \ZnZ $ folgt $x = z$.

Sicherheit

Der folgende Satz zeigt, dass es genauso schwierig ist, den geheimen Schlüssel $(n, s)$ aus dem öffentlichen Schlüssel $(n, e)$ zu berechnen, wie $n$ zu faktorisieren. Dabei ist eine Richtung klar: Ist $n$ in $p \cdot q$ faktorisiert, so kann man wie bei der Schlüsselgenerierung $s$ berechnen. Die andere Richtung besagt, dass man aus der Kenntnis von $s$ den RSA-Modul $n$ effizient faktorisieren kann. Wenn man nun davon ausgeht, dass Faktorisierung schwierig ist, dann ist auch die Berechnung von $s$ aus $(n, e)$ schwierig (sonst könnte man ja Faktorisierung effizient durchführen). Allerdings heißt das nicht, dass das RSA-Verfahren an sich sicher ist: Es könnte z. B. sein, dass $(n, s)$ zwar nicht aus $(n, e)$ effizient berechnet werden kann, es aber eine Entschlüsselungsmethode gibt, die $(n, s)$ gar nicht benötigt (oder nur Teilinformationen).

Satz (Sicherheit des geheimen RSA-Schlüssels):
$p$ und $q$ können effizient berechnet werden, wenn man $(n, e)$ und $(n, s)$ kennt.

Algorithmus: Der Beweis ist konstruktiv und verwendet folgenden Algorithmus:

Schreibe $es - 1 = 2^\ell u$ mit $\ell \in \natural _0$ und $u$ ungerade.
Wähle $a \in \{2, \dotsc , n - 1\}$ zufällig und teste, ob $\ggT (a, n) = 1$. Falls ja, dann wurde ein Teiler gefunden. Falls nicht, so fahre fort.
Berechne $\ggT (a^{2^k u} - 1, n)$ für alle $k = 0, \dotsc , \ell - 1$ und brich ab, wenn ein nicht-trivialer Teiler gefunden wurde.
Falls kein nicht-trivialer Teiler gefunden wurde, dann gehe wieder zu Schritt (2).

Lemma: Für $a$ mit $\ggT (a, n) = 1$ gilt $\ord _n(a^u) \in \{2^0, \dotsc , 2^\ell \}$.

Beweis: Wegen $\ggT (a, n) = 1$ ist auch $\ggT (a^u, n) = 1$, d. h. $a^u \in (\ZnZ )^\ast $ und $\ord _n(a^u)$ ist wohldefiniert. Wegen dem Satz von Euler gilt $a^{\varphi (n)} \equiv _n 1$, d. h. auch $(a^u)^{2^\ell } = a^{es-1} \equiv _n 1$ (wegen $\varphi (n) \teilt (es - 1)$). Somit gilt $\ord _n(a^u) \teilt 2^\ell $.

Lemma: Für $a$ mit $\ggT (a, n) = 1$ und $\ord _p(a^u) \not = \ord _q(a^u)$ gibt es ein $k \in \{0, \dotsc , \ell - 1\}$, sodass $1 < \ggT (a^{2^k u} - 1, n) < n$.

Beweis: Nach dem Lemma von eben ist $\ord _n(a^u) = 2^m$, d. h. $(a^u)^{2^m} \equiv _n 1$. Wegen dem chinesischen Restsatz gilt $(a^u)^{2^m} \equiv _p 1$ und $(a^u)^{2^m} \equiv _q 1$, d. h. $\ord _p(a^u) \teilt 2^m$ und $\ord _q(a^u) \teilt 2^m$. Es gilt also $\ord _p(a^u) = 2^k$ und $\ord _q(a^u) = 2^w$ mit $k, w \in \{0, \dotsc , \ell \}$ und $k \not = w$ nach Voraussetzung, oBdA sei $k < w$. Dann gilt $(a^u)^{2^k} \equiv _p 1 \iff p \teilt (a^{2^k u} - 1)$ und $(a^u)^{2^k} \not \equiv _q 1 \iff q \notteilt (a^{2^k u} - 1)$, weil $2^w$ der kleinste Exponent ist, sodass $a^u$ hoch diesem $\equiv _q 1$ ist (aber $2^k < 2^w$). Daraus folgt $\ggT (a^{2^k u} - 1, n) = p$, wobei $1 < p < n$.

Lemma: Die Anzahl der Elemente $a \in (\ZnZ )^\ast $, für die $\ord _p(a^u) \not = \ord _q(a^u)$, ist mindestens $\frac {1}{2} (p-1)(q-1)$.

Beweis: Seien $g_1 \in (\ZpZ )^\ast $ und $g_2 \in (\ZqZ )^\ast $ Primitivwurzeln modulo $p$ bzw. $q$. Dann gibt es nach dem chin. Restsatz ein $g \in (\ZnZ )^\ast $, das Primitivwurzel modulo $p$ und modulo $q$ ist.

Fall 1: $\ord _p(g^u) \not = \ord _q(g^u)$
OBdA sei $\ord _p(g^u) < \ord _q(g^u)$. Seien $x \in \{0, \dotsc , p - 2\}$, $y \in \{1, \dotsc , q - 1\}$ mit $y$ ungerade und $a \in (\ZnZ )^\ast $ mit $a \equiv _p g^x$ und $a \equiv _q g^y$.

Dann gilt $\ord _q(a^u) = \ord _q((g^u)^y) = \ord _q(g^u)$. Die letzte Gleichung gilt, weil $\ord _q(g^u)$ nach dem ersten Lemma und dem chin. Restsatz eine Zweierpotenz ist – es gilt immer
$\ord _q((g^u)^y) \teilt \ord _q(g^u)$, umgekehrt gilt immer $\ord _q(g^u) \teilt y \ord _q((g^u)^y)$ und wegen $\ord _q(g^u)$ einer Zweierpotenz, aber $y$ ungerade folgt $\ord _q(g^u) \teilt \ord _q((g^u)^y)$.

Für $\ord _p(a^u)$ gilt Ähnliches, allerdings kann $x$ auch gerade sein, d. h. es gilt nur
$\ord _p((g^u)^x) \teilt \ord _p(g^u)$, woraus $\ord _p(a^u) = \ord _p((g^u)^x) \le \ord _p(g^u)$ folgt.

Insgesamt gilt damit $\ord _p(a^u) \le \ord _p(g^u) < \ord _q(g^u) = \ord _q(a^u)$ (die mittlere, strikte Ungleichung gilt nach Fallunterscheidung), d. h. $a$ erfüllt die gewünschte Eigenschaft. Für $x$ und $y$ gibt es insgesamt $(p-1) \cdot \frac {q-1}{2}$ Möglichkeiten. Weil $g$ eine Primitivwurzel modulo $p$ und modulo $q$ ist, sind die Lösungen $a \in (\ZnZ )^\ast $ mit $a \equiv _p g^x$ und $a \equiv _q g^y$ paarweise verschieden. Daher gibt es mindestens $(\frac {1}{2} (p-1)(q-1))$-viele solche $a$.

Fall 2: $\ord _p(g^u) = \ord _q(g^u)$
Hier wählt man $x$ und $y$ ähnlich wie in Fall 1, nur dass entweder $x$ gerade und $y$ ungerade ist oder $x$ ungerade und $y$ gerade ist. Mit obigen Argumenten folgt dann
$\ord _p(a^u) < \ord _p(g^u) = \ord _q(g^u) = \ord _q(a^u)$ oder $\ord _p(a^u) = \ord _p(g^u) = \ord _q(g^u) > \ord _q(a^u)$.
Somit gibt es $(\frac {p-1}{2} \cdot \frac {q-1}{2} + \frac {p-1}{2} \cdot \frac {q-1}{2} = \frac {1}{2} (p-1)(q-1))$-viele mögliche $a$.

Mit diesen Lemmata kann man nun den Satz beweisen.

Beweis des Satzes: Es gibt $\ge (\frac {1}{2} (p-1)(q-1))$-viele $a \in (\ZnZ )^\ast $ mit $\ord _p(a^u) \not = \ord _q(a^u)$. Nach Lemma 2 gilt für diese $a$, dass es ein $k \in \{0, \dotsc , \ell - 1\}$ gibt mit $1 < \ggT (a^{2^k u} - 1, n) < n$. Für ein $a \in (\ZnZ )^\ast $ ist wegen $|(\ZnZ )^\ast | = \varphi (n) = (p-1)(q-1)$ die Wahrscheinlichkeit, dass ein „gewünschtes“ $a$ zufällig getroffen wird, $\ge \frac {1}{2}$. Wegen $\ell \in \O (\log n)$ sind pro $a$ höchstens $\log n$-viele ggT-Berechnungen nötig, um ein $a$ zu untersuchen (ggT-Berechnungen können mit dem euklidischen Algorithmus effizient erledigt werden). Man kann davon ausgehen, dass der Algorithmus ein gewünschtes $a$ schnell findet, da nach $t$ Iterationen die Wahrscheinlichkeit dafür mindestens $1 - \frac {1}{2^t}$ beträgt.

Multi-Prime-RSA

Multi-Prime-RSA-Verfahren: Man kann das RSA-Verfahren auch mit $k$ Primzahlen verwenden (statt den zwei Primzahlen $p, q$). Auch in diesem Fall arbeitet das Verfahren korrekt und wird Multi-Prime-RSA-Verfahren genannt. Das Verfahren arbeitet schneller, wenn der Besitzer der geheimen Schlüssels die Primzahlen im Speicher behält (weil dann die einzelnen Primzahlen bei gleichem $n$ kleiner sind). Andererseits ist das Verfahren bei gleichem $n$ unsicherer als das normale RSA-Verfahren, weil die einzelnen Primzahlen dann deutlich kleiner sind, d. h. die Suche eines Faktors geht wesentlich schneller. Nach Teilen von $n$ durch diesen Faktor ist die Zahl kleiner und man findet noch schneller die anderen beiden Faktoren. Man darf also nicht zu viele Primzahlen wählen, sonst wird das Verfahren unsicher und die Zeitersparnis bringt nichts.

Rabin-Verfahren

Verfahren

Rabin-Verfahren: Das Rabin-Verfahren wurde 1979 von Michael Rabin entwickelt, findet aber kaum Anwendung, weil die Entschlüsselung im Gegensatz zu RSA nicht eindeutig ist.

Schlüsselgenerierung:

Wähle zwei große Primzahlen $p \not = q$ mit $p \equiv _4 q \equiv _4 3$
Berechne $n := pq$.
Veröffentliche $k_e := n$ und halte $k_s := (p, q)$ geheim.

Verschlüsselung: Eine Nachricht $x \in \ZnZ $ wird durch $y := x^2 \bmod n$ verschlüsselt.

Entschlüsselung: Eine Nachricht $y \in \ZnZ $ wird durch wie folgt entschlüsselt. Berechne zunächst $x_p := y^{(p+1)/4} \bmod p$ und $x_q := y^{(q+1)/4} \bmod q$. Dann sind $\pm x_p$ Wurzeln von $y$ modulo $p$ und $\pm x_q$ Wurzeln von $y$ modulo $q$. Mit dem chin. Restsatz erhält man nun vier mögliche Kandidaten für $x$.

Weil die Entschlüsselung nicht eindeutig ist, muss man die Menge der möglichen Klartexte einschränken. Zum Beispiel können die Kommunikationspartner vereinbaren, dass jede Nachricht mit einem bestimmten Codewort endet. Dann ist das Verfahren allerdings nicht mehr so sicher wie die Faktorisierung. Außerdem muss $p \equiv _4 q \equiv _4 3$ nicht gelten – dadurch geht aber die Entschlüsselung effizienter (sonst müsste man die Quadratwurzeln anderweitig berechnen).

Korrektheit

Quadratzahl/Quadratwurzel: $a \in \ZnZ $ heißt Quadratzahl modulo $n$, falls $\exists _{x \in \ZnZ }\; x^2 \equiv _n a$. In diesem Fall heißt $x$ Quadratwurzel von $a$ modulo $n$ ($x$ ist i. A. nicht eindeutig).

Lemma (Euler-Kriterium): Sei $p > 2$ prim.
Dann ist die Abbildung $(\ZpZ )^\ast \rightarrow \{1, -1\}$, $y \mapsto y^{(p-1)/2} \bmod p$ ein surjektiver (multiplikativer) Gruppenhomom. mit $y$ Quadratzahl modulo $p$ $\iff y^{(p-1)/2} \equiv _p 1$ für $y \in (\ZpZ )^\ast $.

Beweis: Zunächst wird die Äquivalenz gezeigt.

„$\implies $“: Sei $y \equiv _p x^2$ für ein $x \in \ZpZ $. Dann gilt $y^{(p-1)/2} \equiv _p (x^2)^{(p-1)/2} = x^{p-1} \equiv _p 1$ nach dem kleinen Satz von Fermat.

„$\impliedby $“: Sei $y \in (\ZpZ )^\ast $ keine Quadratzahl und $g$ eine Primitivwurzel modulo $p$. Dann gibt es ein $k \in \natural $ mit $y \equiv _p g^{2k+1}$ (wäre $y \equiv _p g^{2k}$ für ein $k$, dann wäre $g^k$ eine Quadratwurzel von $y$ modulo $p$). Es gilt $(g^{(p-1)/2})^2 - 1 = g^{p-1} - 1 \equiv _p 0$ nach dem kleinen Satz von Fermat, d. h. $g^{(p-1)/2}$ ist eine Nullstelle von $x^2 - 1 = (x+1)(x-1)$, somit gilt $g^{(p-1)/2} \bmod p \in \{1, -1\}$. Allerdings gilt $g^{(p-1)/2} \not \equiv _p 1$, weil $\ord ((\ZpZ )^\ast ) = \ord _p(g) = p - 1$ der kleinste Exponent ist, sodass $g$ hoch dieser Zahl $\equiv _p 1$ ist. Somit gilt $g^{(p-1)/2} \equiv _p -1$. Damit erhält man
$y^{(p-1)/2} \equiv _p (g^{2k+1})^{(p-1)/2} = g^{k(p-1)} g^{(p-1)/2} \equiv _p (g^{p-1})^k \cdot (-1) \equiv _p -1$ nach dem kleinen Satz von Fermat.

Damit wurde bereits die Wohldefiniertheit der Abbildung gezeigt (für $y$ Quadratzahl modulo $p$ ist $y^{(p-1)/2} \equiv _p 1$, sonst ist $y^{(p-1)/2} \equiv _p -1$). Die Homomorphie ist klar nach Definition. Die Surjektivität folgt aus $1^{(p-1)/2} \mod p = 1$ und $g^{(p-1)/2} \mod p = -1$ für einen Erzeuger
$g \in (\ZpZ )^\ast $ wie oben.

Korollar: Sei $p > 2$ prim. Dann sind Quadratzahlen modulo $p$ eine Untergruppe von $(\ZpZ )^\ast $ mit der Gruppenordnung $\frac {p-1}{2}$.

Beweis: Sei $g \in (\ZpZ )^\ast $ eine Primitivwurzel modulo $p$. Aus dem Beweis des Lemmas geht hervor, dass $g^{(p-1)/2} \equiv _p -1$. Damit gilt $(g^{(p-1)/2})^k \equiv _p 1$ für $k$ gerade und $(g^{(p-1)/2})^k \equiv _p -1$ für $k$ ungerade. Für $k$ gerade ist also $g^k$ eine Quadratzahl nach dem Lemma und sonst keine. Von den Gruppenelementen $g^1, \dotsc , g^{p-1}$ sind also genau die Quadratzahlen modulo $p$, die einen geraden Exponenten haben, d. h. genau $\frac {p-1}{2}$.

Dass die Quadratzahlen modulo $p$ eine Untergruppe von $(\ZpZ )^\ast $ bilden, folgt elementar oder nach dem Lemma (als Urbild der trivialen Untergruppe $\{1\} \subset \{1, -1\}$).

Satz (Korrektheit des Rabin-Verfahrens): Das Rabin-Verfahren arbeitet korrekt.

Beweis: Seien $p \not = q$ prim mit $p \equiv _4 q \equiv _4 3$, $n := pq$, $x \in \ZnZ $, $y := x^2 \bmod n$ und
$x_p := y^{(p+1)/4} \bmod p$. Zu zeigen ist, dass $x \equiv _p x_p$ oder $x \equiv _p -x_p$ (analog gilt dann $x \equiv _q x_q$ oder $x \equiv _q -x_q$).

Es gilt $x_p^2 \equiv _p y^{(p+1)/2} = y^{(p-1)/2} \cdot y \equiv _p y \equiv _p x^2$ nach dem Lemma, weil $y$ ein quadr. Rest modulo $n$ ist (d. h. nach dem chin. Restsatz auch modulo $p$ und modulo $q$). Damit gilt $x \equiv _p \pm x_p$.

Sicherheit

Beim RSA-Verfahren konnte nur gezeigt werden, dass das Faktorisierungsproblem äquivalent zum Berechnen des geheimen Schlüssels ist. Beim Rabin-Verfahren kann man sogar zeigen, dass mit einem Entschlüsselungs-Algorithmus $n$ faktorisiert werden kann.

Satz (Sicherheit des Rabin-Verfahrens):
Existiert ein effizienter Entschlüsselungs-Algorithmus, der nur mit Kenntnis von $n$ Geheimtexte entschlüsseln kann, so kann $n$ effizient faktorisiert werden.

Beweis: Sei $R$ ein effizienter Algorithmus mit $R(y) := \widehat {x}$, wobei $\widehat {x}^2 \equiv _n y$ (wenn $y$ eine Quadratzahl modulo $n$ ist). Dann kann $n$ wie folgt effizient faktorisiert werden: Wähle zunächst zufällig $x \in \{1, \dotsc , n - 1\}$. Berechne anschließend $y := x^2 \bmod n$ und $\widehat {x} := R(y)$. Dann gilt $x^2 \equiv _n \widehat {x}^2$, nach dem chin. Restsatz auch $x^2 \equiv _p \widehat {x}^2$ und $x^2 \equiv _q \widehat {x}^2$. Weil $\ZpZ $ und $\ZqZ $ Körper sind, gilt $x \equiv _p \pm \widehat {x}$ und $x \equiv _q \pm \widehat {x}$. Es gibt daher vier gleich wahrscheinliche Fälle (das liegt daran, dass $X^2 - y \in (\integer /n\integer )[X]$ vier Nullstellen hat, obwohl das Polynom nur quadratisch ist).

Für $x \equiv _p \widehat {x}, x \equiv _q -\widehat {x}$ gilt $p \teilt (x - \widehat {x})$ und $q \notteilt (x - \widehat {x})$ (wäre $q \teilt (x - \widehat {x})$, so wäre $-\widehat {x} \equiv _q x \equiv _q \widehat {x}$), daher gilt in diesem Fall $\ggT (x - \widehat {x}, n) = p$. Analog gilt im Fall $x \equiv _p -\widehat {x}, x \equiv _q \widehat {x}$, dass $\ggT (x - \widehat {x}, n) = q$. In diesen beiden Fällen hat man also einen Primteiler gefunden. Für $x \equiv _p \widehat {x}, x \equiv _q \widehat {x}$ oder $x \equiv _p -\widehat {x}, x \equiv _q -\widehat {x}$ lässt sich dagegen keine Aussage treffen.

Insgesamt kann man bei zufälliger Wahl von $x$ die Zahl $n$ mit 50-prozentiger Wahrscheinlichkeit faktorisieren. Durch Iteration des Verfahrens lässt sich daher $n$ effizient faktorisieren.

Eine Folgerung aus der Sicherheit des Rabin-Verfahrens ist, dass das RSA-Verfahren auch bei verhältnismäßig kleinen Exponenten $e$ nicht unsicher wird. Wenn man die Menge der Klartexte einschränkt (z. B. müssen die ersten $k$ Bit gleich den letzten $k$ Bit sein), dann sinkt die Sicherheit des Rabin-Verfahrens.

Diffie-Hellman-Schlüsselaustausch

Diffie-Hellman-Schlüsselaustausch: Mit dem Diffie-Hellman-Schlüsselaustausch versucht man, das Grundproblem symmetrischer Verfahren zu lösen, nämlich der geheime Austausch eines gemeinsamen Schlüssels. Es ist selbst kein Verschlüsselungsverfahren, wird aber im ElGamal-Verfahren benutzt.

diskreter Logarithmus: Seien $G$ eine Gruppe, $g \in G$ und $A \in \erzeugnis {g}$.
Dann heißt $a \in \natural $ mit $A = g^a$ diskreter Logarithmus von $A$ bzgl. der Basis $g$.

Ist $\ord (g) = \infty $, dann ist der diskrete Logarithmus $a$ eindeutig.
Ist $n := \ord (g) < \infty $, dann ist der diskrete Logarithmus $a$ eindeutig in $\ZnZ $.

DL-Problem: Seien $G$ eine Gruppe und $g \in G$.
Das Problem, zu gegebenem $A \in \erzeugnis {g}$ den diskreten Log. $a$ zu bestimmen, heißt DL-Problem.

Das DL-Problem lässt sich leicht lösen, wenn $|G|$ nur kleine Primteiler besitzt oder wenn $\ord (g)$ klein ist.

Diffie-Hellman-Schlüsselaustausch: Der Diffie-Hellman-Schlüsselaustausch ist ein Verfahren zum Schlüsselaustausch und verläuft zwischen Alice und Bob wie folgt.

Wähle eine endliche Gruppe $G$ und $g \in G$ (öffentlich) und berechne $m := \ord (g)$.
Alice wählt zufällig ein $a \in \{1, \dotsc , m - 1\}$ und schickt $A := g^a$ an Bob.
Bob wählt zufällig ein $b \in \{1, \dotsc , m - 1\}$ und schickt $B := g^b$ an Alice.
Alice berechnet $k_1 := B^a$ und Bob berechnet $k_2 := A^b$.

Es gilt $k := k_1 = k_2 = g^{ab}$, d. h. $k$ ist nun der gemeinsame Schlüssel und Alice und Bob können mit diesem Schlüssel über ein symmetrisches Verschlüsselungsverfahren sicher kommunizieren.

Wahl von $G$ und $g$: Nach obiger Bemerkung sollte sowohl $|G|$ einen großen Primteiler besitzen als auch $\ord (g)$ groß sein. Die Wahl von $G = (\ZnZ , +)$ mit $g$ einem Erzeuger von $G$ (d. h. $\ggT (g, n) = 1$) ist schlecht, denn für $A = a \cdot g \in \ZnZ $ gilt $a = g^{-1} A$ mit $g^{-1}$ dem mult. Inversen von $g$ in $(\ZnZ )^\ast $, welches sich mit dem euklidischen Algorithmus leicht bestimmen lässt.

Eine bessere Möglichkeit ist $G = ((\ZpZ )^\ast , \cdot )$ mit $p$ prim. Dann gilt $|G| = p - 1$, d. h. um sicherzustellen, dass $|G|$ einen großen Primteiler besitzt, kann man $p := kq + 1$ mit $q$ einer großen Primzahl und $k$ klein und gerade wählen (sodass $p$ prim ist).
Bei der Wahl von $g$ wählt man zunächst $g \in (\ZpZ )^\ast $ zufällig und überprüft $g^q \equiv _p 1$ sowie $g \not \equiv _p 1$ (dann gilt $\ord _p(g) \teilt q$ und $\ord _p(g) \not = 1$, also $\ord _p(g) = q$). Gilt $g^q \not \equiv _p 1$, so könnte $\ord _p(g)$ ein Vielfaches von $q$ sein. In diesem Fall definiert man $g’ := g^k$ und überprüft $g’$ (damit gilt in jedem Fall bereits $(g’)^q = g^{kq} = g^{|G|} \equiv _p 1$).

Sicherheit: Wenn man das DL-Problem effizient lösen kann, dann kann man auch den Diffie-Hellman-Schlüsselaustausch effizient knacken (Diffie-Hellman-Problem: Berechnen von $k$ aus $G, g, A, B$), indem man aus $A$ den diskreten Logarithmus $a$ und $k := B^a$ berechnet. Allerdings ist die Gültigkeit der Umkehrung unbekannt, d. h. es kann sein, dass das DL-Problem „echt“ schwieriger als das Diffie-Hellman-Problem ist. Die Sicherheit kann auch durch eine Man-in-the-middle-Attacke sabortiert werden, siehe unten.

ElGamal-Verfahren

ElGamal-Verfahren: Das ElGamal-Verfahren ist im Prinzip das Diffie-Hellman-Verfahren zum Schlüsselaustausch mit anschließender Multiplikation des Klartexts mit dem gemeinsamen Schlüssel.

Schlüsselgenerierung:

Bestimme eine endliche Gruppe $G$ mit $n := |G|$, $g \in G$, $a \in \{0, \dotsc , n - 1\}$ und $A := g^a$.
Veröffentliche $k_e := (G, g, A)$ und halte $k_s := a$ geheim.

Verschlüsselung: Eine Nachricht $x \in G$ wird wie folgt verschlüsselt:
Wähle $b \in \{1, \dotsc , n - 1\}$ zufällig. Berechne $B := g^b$, $k := A^b$ und $y := kx$ und sende $(y, B)$.

Entschlüsselung: Eine Nachricht $(y, B) \in G^2$ wird wie folgt entschlüsselt:
Berechne $k := B^a$ und $x := k^{-1} y$.

Sicherheit: Das Brechen des geheimen Schlüssels $a$ ist genau das DL-Problem.
Das Entschlüsseln einer Nachricht $(y, B)$ ist genauso schwierig wie das Diffie-Hellman-Problem (ist der Klartext $x$ berechenbar, so ist $k := yx^{-1}$ der Schlüssel, ist der Schlüssel $k$ berechenbar, so ist $x := k^{-1} y$ der Klartext).
Für jede Nachricht muss ein anderes $b$ gewählt werden. Ist nämlich ein einziges Klartext-Geheimtext-Paar $(\widetilde {x}, \widetilde {y})$ bekannt (Known-Plaintext-Attacke), so können alle Nachrichten, die mit demselben $b$ verschlüsselt wurden, auch entschlüsselt werden (indem zunächst $k := \widetilde {y} \widetilde {x}^{-1}$ berechnet wird und alle folgenden Geheimtexte $y \in G$ mit $x := k^{-1} y$ entschlüsselt werden).

Geheimtexte $(y, B)$ sind zwar doppelt so lang wie bei anderen Verfahren, da allerdings $b$ sowieso zufällig gewählt werden sollte, ist eine Zufallskomponente (hier $B$), die bei anderen Verfahren explizit an jeden Klartext angefügt werden müsste, hier bereits eingebaut.

Man-in-the-middle-Angriff: Das Verfahren ist allerdings, wie bereits der Diffie-Hellman-
Schlüsselaustausch, anfällig gegenüber dem sog. Man-in-the-middle-Angriff. Dazu schaltet sich eine dritte Person (hier Oscar) zwischen die beiden Kommunikationspartner (Alice und Bob), fängt die Nachrichten ab, entschlüsselt sie und verschlüsselt sie wieder.

$(3.1–3.0) \{begin}{align*} \xymatrix @R=2mm@C=25mm{ *+++[F]{\txt {\textbf {Alice}\\($a_1, k_1$)}}\ar [r]^{G_1, g_1, A_1, B_1}& *+++[F]{\txt {\textbf {Oscar}\\($b_1, k_1$)}}\ar [l]\ar [r]& *+++[F]{\txt {\textbf {Bob}\\($b_2, k_2$)}}\ar [l]_{G_2, g_2, A_2, B_2}\\ x = d_1(y’)& \txt {$x = d_2(y)$\\$y’ = c_1(x)$}\ar @/^5mm/[l]^{y’}& y = c_2(x)\ar @/^5mm/[l]^y } \{end}{align*}$

Oscar kann also nicht nur die gesamte Kommunikation mithören, sondern könnte auch Nachrichten fälschen, indem er eine selbst gewählte Nachricht $x’$ statt $x$ mit Alices Schlüssel verschlüsseln würde.

Merkle-Hellman-Kryptosystem

Merkle-Hellman-Kryptosystem: Das Merkle-Hellman-Kryptosystem basiert auf
dem Subsetsum-Problem, einem NP-vollständigen Spezialfall des Rucksack-Problems.

Subsetsum-Problem: Beim Subsetsum-Problem sind Zahlen $s_1, \dotsc , s_n, y \in \natural $ gegeben.
Gefragt ist, ob $I \subset \{1, \dotsc , n\}$ existiert mit $y = \sum _{i \in I} s_i$.

Definiert man die Verschlüsselung von $x = x_1 \dotsc x_n \in \BB ^n$ durch $y = \sum _{i=1}^n x_i s_i$, so bekommt man das Problem, dass Alice ein NP-Problem lösen müsste und die Entschlüsselung eventuell nicht eindeutig wäre. Daher setzt man voraus, dass $(s_1, \dotsc , s_n)$ eine stark wachsende Folge ist.

stark wachsend: Die Folge $s_1, \dotsc , s_n \in \real ^+$ heißt stark wachsend, falls $\forall _{i=1,\dotsc ,n}\; s_i > \sum _{k=1}^{i-1} s_k$.

Das Subsetsum-Problem für stark wachsende Folgen ist eindeutig in Linearzeit lösbar, indem man $s_n, \dotsc , s_1$ durchgeht (was wiederum heißt, dass jeder entschlüsseln könnte).

Schlüsselgenerierung:

Wähle z. B. $n = 100$, $s_1, \dotsc , s_n \in \natural $ mit $s_i$ jeweils $n + i - 1$ Bit und $p$ prim mit $2n$ Bit.
Wähle $u, w \in (\ZmZ )^\ast $ mit $uw \equiv _p 1$ und eine Perm. $\pi \in \Sigma _n$ und $a_{\pi (i)} := (s_i u \bmod p)$.
Veröffentliche $a_1, \dotsc , a_n$ (jeweils etwa $2n$ Bit) und halte $u, w, \pi , s_1, \dotsc , s_n$ geheim.

Verschlüsselung:
Eine Nachricht $x_1 \dotsb x_n \in \BB ^n$ wird verschlüsselt durch $y := \sum _{i=1}^n x_i a_i < n 2^{2n}$.

Entschlüsselung: Eine Nachricht $y$ wird wie folgt entschlüsselt.
Man berechnet $y \cdot w = \sum _{i=1}^n x_i a_i w = \sum _{i=1}^n x_{\pi (i)} a_{\pi (i)} w \equiv _p \sum _{i=1}^n x_{\pi (i)} s_i uw \equiv _p \sum _{i=1}^n x_{\pi (i)} s_i$.
Nach Wahl von $p$ ist $\sum _{i=1}^n x_{\pi (i)} s_i < p$, d. h. es gilt $(yw \bmod p) = \sum _{i=1}^n x_{\pi (i)} s_i$. Mit dieser Beziehung kann $x = x_1 \dotsb x_n$ berechnet werden.

Sicherheit: Shamir hat 1982 das Merkle-Hellman-Kryptosystem gebrochen, sodass dieses als unsicher angesehen werden muss.

McEliece-Kryptosystem

McEliece-Kryptosystem:
Für das McEliece-Kryptosystem benötigt man etwas Codierungstheorie. Sei $F := \integer /2\integer $.

Code: Ein (linearer) Code ist ein Unterraum $C \le F^n$.

Hamming-Distanz: Die Hamming-Distanz von $x, y \in F^n$ ist $|\{i \in \{1, \dotsc , n\} \;|\; x_i \not = y_i\}|$.
Die Hamm.-Dist. eines Codes $C$ ist die minimale Hamm.-Dist. zweier versch. Vektoren.

Haben $x, y \in F^n$ die Hamming-Distanz $2d + 1$, dann können bis zu $2d$ Fehler erkannt werden und man kann $d$ Fehler korrigieren (erkennen, ob von $x$ oder $y$ gestartet wurde).

Generatormatrix:
Eine Generatormatrix ist eine Matrix $G \in F^{m \times n}$ mit $m \le n$ und $\Rang (G) = m$.
Der durch $G$ definierte Code ist $C := \{xG \;|\; x \in F^m\}$. $xG$ heißt Codierung von $x$.

Kontrollmatrix:
Zu einer Gen.matrix $G$ existiert eine Kontrollmatrix $H \in F^{n \times m}$ mit $C = \{y \in F^n \;|\; yH = 0\}$.
$H$ entsteht dabei aus einer Basis des Orthogonalraums. Die maximale Anzahl von linear unabhängigen Vektoren in $H$ liefert die Hamming-Distanz von $C$.

Ist $yH = 0$ (d. h. ist $y \in C$), dann ist $x \in F^m$ mit $xG = y$ leicht zu finden. Gilt aber $y \notin C$, dann ist es i. A. schwierig, die Fehler zu korrigieren und somit zu decodieren. Das zugehörige Entscheidungsproblem ist außerdem NP-vollständig.

Schlüsselgenerierung:

Wähle eine Generatormatrix $G \in F^{m \times n}$, für welche man $t$ Fehler effizient korrigieren kann (d. h. die Hamming-Distanz des Codes sollte $\ge 2t + 1$ sein).
Wähle eine zufällige Permutationsmatrix $M \in F^{m \times m}$ und eine zufällige invertierbare Matrix $N \in F^{n \times n}$.
Setze $G’ := MGN$, veröffentliche $G’, t$ und halte $G, M, N$ geheim.

Die Idee ist nun, dass $G’$ immer noch $t$ Fehler korrigieren kann.

Verschlüsselung: Eine Nachricht $x \in F^m$ wird durch $y := y’ \xor z$ verschlüsselt, wobei $y’ := xG’$ und $z \in F^n$ zufällig mit $t$ Einsen.

Entschlüsselung: Eine Nachricht $y \in F^n$ wird durch $y’’ := yN^{-1}$, $x’$ der Decodierung von $y’’$ für $G$ mit Fehlerkorrektur und $x := x’ M^{-1}$ entschlüsselt.

Sicherheit: Das Verfahren gilt als sicher, außerdem sind keine Algorithmen für Quantencomputer bekannt. Allerdings sind die Schlüssellängen um ein Wesentliches größer als z. B. bei RSA (Faktor $1000$). NTRU verfolgt einen ähnlichen Ansatz wie McEliece.