Kryptografische Verfahren – Diskreter Logarithmus

diskreter Logarithmus: Gegeben ist eine endliche Gruppe \(G\), \(g \in G\) und \(y \in \erzeugnis {g}\).
Gesucht ist ein diskreter Logarithmus \(x\) von \(y\) zur Basis \(g\), d. h. \(x \in \natural _0\) mit \(y = g^x\).

Im Folgenden sei \(n := |G|\). \(n\) ist aber nicht zwangsläufig bekannt (bei großen Elementordnungen kann man sich auch vorstellen, dass \(n \approx \ord (g)\)).

naiver Ansatz:
Man berechnet alle Potenzen \(g^0, g^1, \dotsc , g^{n-1}\) und überprüft, welches Element gleich \(y\) ist.

Zeitbedarf: \(\O (n)\)

Speicherbedarf: \(\O (1)\)

Der naive Ansatz ist für große Gruppenordnungen (\(n > 2^{160}\)) praktisch nicht durchführbar.

Shanks Babystep-Giantstep-Methode

Idee: Mit \(m \in \natural \) mit \(m \ge \sqrt {n}\) (z. B. \(m := \left \lceil \sqrt {n}\right \rceil \)) gilt \(\exists _{0 \le s, r < m}\; x = sm + r\). Man kann nun \(s, r\) mehr oder weniger separat berechnen.

Shanks Babystep-Giantstep-Methode: Die Babystep-Giantstep-Methode (BSGS-Methode) von Shank berechnet einen diskreten Logarithmus wie folgt.

Berechne \(m := \left \lceil \sqrt {n}\right \rceil \) oder, soweit \(n\) nicht bekannt ist, eine obere Schranke \(m \ge \sqrt {n}\).
Berechne \((r, yg^{-r}) \in \natural \times G\) für alle \(r = 0, \dotsc , m - 1\) und speichere die Paare in einer Hashtabelle (Nachschlagen in Zeit \(\O (1)\)).
Berechne \(h^s \in G\) mit \(h := g^m\) für alle \(s = 0, \dotsc , m - 1\) und breche ab, sobald \((r, h^s)\) mit einem \(r \in \{0, \dotsc , m - 1\}\) in der Hashtabelle vorkommt.
\(x = sm + r\) ist dann der diskrete Logarithmus, weil \(g^x = g^{sm + r} = h^s g^r = y g^{-r} g^r = y\).

Bei Schritt (2) werden die Babysteps und bei Schritt (3) die Giantsteps berechnet.

Zeitbedarf: \(\O (m)\) Gruppenoperationen (für \(m = \left \lceil \sqrt {n}\right \rceil \): \(\O (\sqrt {n})\))

Speicherbedarf: \(\O (m)\) Gruppenelemente (für \(m = \left \lceil \sqrt {n}\right \rceil \): \(\O (\sqrt {n})\))

Die BSGS-Methode ist daher in der Praxis ebenfalls nicht anwendbar (Speicherverbrauch zu groß).

Pollards ϱ-Methode für den diskreten Logarithmus

Idee: Partitioniere \(G\) in drei Mengen \(P_1, P_2, P_3\). Die Zugehörigkeit eines Elements aus \(G\) zu einer drei Klassen sollte sich leicht berechnen lassen und die Aufteilung sollte sich in etwa zufällig verhalten. Meistens rechnet man modulo \(3\) und sammelt jedes dritte Element in einer Klasse. Definiere nun die Abbildung \(f\colon \ZnZ \times \ZnZ \rightarrow \ZnZ \times \ZnZ \) mit

\(f(r, s) := (r + 1, s)\), falls \(g^r y^s \in P_1\),
\(f(r, s) := (2r, 2s)\), falls \(g^r y^s \in P_2\), und
\(f(r, s) := (r, s + 1)\), falls \(g^r y^s \in P_3\).

Sei \(r, s \in \ZnZ \). Ist \((r’, s’) := f(r, s)\), \(h := g^r y^s\) und \(h’ := g^{r’} y^{s’}\), so gilt

\(h’ = gh\), falls \(h \in P_1\),
\(h’ = h^2\), falls \(h \in P_2\), und
\(h’ = hy\), falls \(h \in P_3\)

(weil \(y \in \erzeugnis {g}\)). Man startet daher mit einem zufälligen Paar \((r_1, s_1) \in \ZnZ \times \ZnZ \). Die Folge \((h_k)_{k \in \natural }\) mit \(h_k := g^{r_k} y^{s_k}\) und \((r_{k+1}, s_{k+1}) := f(r_k, s_k)\) für \(k \in \natural \) ist dann eine Pseudozufallsfolge. Nach dem Geburtstagsparadoxon gilt \(\exists _{i, j \in \natural ,\; i < j}\; h_i = h_j\), wobei \(j = \O (\sqrt {n})\) (erwartet). Es gilt also \(g^{r_i+xs_i} = g^{r_i} y^{s_i} = g^{r_j} y^{s_j} = g^{r_j+xs_j}\) und damit \(x(s_i - s_j) \equiv _n r_j - r_i\). Man braucht also nur noch für Lösungen \(x\) dieser Kongruenz zu testen, ob \(y = g^x\) gilt. Je kleiner \(\ggT (s_i - s_j, n)\) ist, desto weniger Lösungen \(x\) müssen überprüft werden.

Ein Zyklus in der Folge könnte mit dem Verfahren bei Pollards \(\varrho \)-Methode für die Faktorisierung gefunden werden. Es geht aber auch anders (diese Methode kann auch bei der Faktorisierung verwendet werden).

Pollards \(\varrho \)-Methode für den DL: Pollards \(\varrho \)-Methode für den diskreten Logarithmus berechnet einen diskreten Logarithmus wie folgt.

Sei \(\ell := 1\) und \(h_1 := g^{r_1} y^{s_1}\) mit einem zufälligen Paar \((r_1, s_1) \in \ZnZ \times \ZnZ \).
Berechne sukzessive \(h_k\) für \(k = \ell + 1, \dotsc , 2\ell \), wobei sich \(h_k\) aus \(h_{k-1}\) wie oben ergibt und \((r_k, s_k) := f(r_{k-1}, s_{k-1})\) wie oben (damit gilt \(h_k = g^{r_k} y^{s_k}\)). Stimmt eines der Elemente \(h_k\) mit \(h_\ell \) überein, so breche ab. Ansonsten verdopple \(\ell \) und wiederhole.
Definiere \((r, s) := (r_\ell , s_\ell )\) und \((r’, s’) := (r_k, s_k)\). Dann teste für jede Lösung \(x\) der Kongruenz \(x(s - s’) \equiv _n r’ - r\), ob \(y = g^x\) gilt. Falls ja, ist \(x\) der gesuchte diskrete Logarithmus.

Gilt \(\exists _{i, j \in \natural ,\; i < j}\; h_i = h_j\) mit \(j = \O (\sqrt {n})\) (erwartet) wie oben, so terminiert der Algorithmus spätestens für \(\ell \ge j\) (weil dann \(h_\ell = h_{\ell +j-i}\)).

Zeitbedarf: erwartet \(\O (\sqrt {n})\) Gruppenoperationen

Speicherbedarf: \(\O (1)\) Gruppenelemente

Vorteile gegenüber BSGS: konstanter Speicherverbrauch, leichter zu implementieren

Nachteile gegenüber BSGS: probabilistisches Verfahren (Laufzeit kann schlecht sein), Vielfaches von \(\ord (g)\) (z. B. \(n = |G|\)) muss bekannt sein

Pohlig-Hellman-Algorithmus

Für den Pohlig-Hellman-Algorithmus seien \(G\) zyklisch, d. h. \(G = \erzeugnis {g}\), und die Primfaktorzerlegung \(\prod _{p \in \PP ,\; p \teilt n} p^{e(p)}\) von \(n = |G|\) bekannt.

Für jedes \(p \in \PP \) mit \(p \teilt n\) seien im Folgenden \(n_p := \frac {n}{p^{e(p)}}\), \(g_p := g^{n_p}\), \(y_p := y^{n_p}\) und \(x_p \in \natural _0\) mit \(y_p = g_p^{x_p}\). \(g_p\) und \(y_p\) sind Elemente der Untergruppe \(G_p := \{h^{n_p} \;|\; h \in G\}\) von \(G\). Diese ist zyklisch mit Ordnung \(|G_p| = p^{e(p)}\).

Lemma: Sei \(x \in \natural _0\) mit \(\forall _{p \in \PP ,\; p \teilt n}\; x \equiv x_p \pmod {p^{e(p)}}\). Dann ist \(y = g^x\).

Beweis: Für jedes \(p \in \PP \) mit \(p \teilt n\) gilt \((g^{-x} y)^{n_p} = g_p^{-x} y_p = g_p^{-x_p} y_p = 1\), da \(g_p^x = g_p^{x_p}\) (es gilt \(g_p \in G_p\) und \(x, x_p\) unterscheiden sich nur um ein Vielfaches der Gruppenordnung \(p^{e(p)}\) von \(G_p\)). Daraus folgt, dass \(\ord _G(g^{-x} y) \teilt n_p\) für jeden Primteiler \(p\) von \(n\). Insbesondere gilt
\(\ord _G(g^{-x} y) \teilt \ggT (\{n_p \;|\; p \in \PP ,\; p \teilt n\}) = 1\) (bei jeder Zahl \(n_p\) wurde eine Primzahl \(p\) herausgeteilt). Damit ist \(\ord _G(g^{-x} y) = 1\) und \(g^x = y\).

OBdA kann man also von \(G\) zyklisch mit \(n = p^e\) (\(p \in \PP \), \(e \in \natural \)) ausgehen. Sonst bestimmt man für jeden Primteiler \(p \teilt n\) die \(x_p\) mit \(y_p = g_p^{x_p}\) und löst das System \(\forall _{p \in \PP ,\; p \teilt n}\; x \equiv x_p \pmod {p^{e(p)}}\) von Kongruenzen mit dem chinesischen Restsatz.

Pohlig-Hellman-Algorithmus: Der Pohlig-Hellman-Algorithmus bestimmt den diskreten Logarithmus in einer zyklischen Gruppe (oBdA mit Primzahlpotenzordnung \(p^e\)) wie folgt.

Schreibe \(x = x_0 + x_1 p + \dotsb + x_{e-1} p^{e-1}\) mit \(x_0, \dotsc , x_{e-1} \in \{0, \dotsc , p-1\}\) (da \(x < |G| = p^e\)).
Zur Bestimmung der Koeffizienten \(x_0, \dotsc , x_{e-1}\) wiederhole für \(i = 0, \dotsc , e - 1\) Folgendes:
- Berechne \(z_i := yg^{-(x_0 p^0 + \dotsb + x_{i-1} p^{i-1})}\). Dann gilt \(g^{x_i p^i + \dotsb + x_{e-1} p^{e-1}} = z_i\). Potenzieren mit dem Exponenten \(p^{e-i-1}\) auf beiden Seiten führt zu \(g^{x_i p^{e-1}} = z_i^{p^{e-i-1}}\) wg. \(\forall _{e’ \ge e}\; g^{p^{e’}} = 1\).
- Berechne den diskreten Logarithmus \(x_i\) von \(z_i^{p^{e-i-1}}\) zur Basis \(g^{p^{e-1}}\) in der Untergruppe \(\{h^{p^{e-1}} \;|\; h \in G\}\) von \(G\) (zyklisch mit Ordnung \(p\)), also \(x_i \in \natural _0\) mit \((g^{p^{e-1}})^{x_i} = z_i^{p^{e-i-1}}\), z. B. mit der BSGS- oder Pollards \(\varrho \)-Methode.

Zeitbedarf: \(\O (\sum _{p \in \PP ,\; p \teilt n} e(p) \cdot (\log n + \sqrt {p}))\) Gruppenoperationen in \(G\)

Die Laufzeit des Pohlig-Hellman-Algorithmus ist daher gut, wenn \(n\) nur kleine Primteiler besitzt. Der Algorithmus kann nur durchgeführt werden, wenn nicht nur die Gruppenordnung \(n\), sondern sogar ihre Primfaktorzerlegung bekannt ist.

Index-Calculus-Algorithmus

Für den Index-Calculus-Algorithmus ist \(g \in G = (\ZpZ )^\ast \) mit \(p\) prim (oft kann man sich \(\erzeugnis {g} = (\ZpZ )^\ast \) vorstellen) und \(y \in \erzeugnis {g}\). Gesucht ist \(x \in \natural _0\) mit \(g^x \equiv _p y\).

Index-Calculus-Algorithmus: Mit dem Index-Calculus-Algorithmus kann man den diskreten Logarithmus in \((\ZpZ )^\ast \) für \(p\) prim wie folgt bestimmen.

Wähle eine Faktorbasis \(B = \{q \in \PP \;|\; q \le B_0\}\) für eine Schranke \(B_0 \in \natural \).
Für alle \(q \in B\) bestimme \(x_q \in \natural _0\) mit \(g^{x_q} \equiv _p q\) (diskreter Logarithmus von \(q\)).
Bestimme \(b \in \natural _0\), sodass \((yg^b \bmod p)\) \(B\)-glatt ist, d. h. \(yg^b \equiv _p \prod _{q \in B} q^{e_q}\).
Wähle \(x := (-b + \sum _{q \in B} x_q e_q) \bmod (p-1)\).

Lemma (Korrektheit): Der Index-Calculus-Algorithmus arbeitet korrekt, d. h. \(g^x \equiv _p y\).

Beweis: Es gilt \(g^x \equiv _p g^{-b} g^{\sum _{q \in B} x_q e_q} = g^{-b} \prod _{q \in B} g^{x_q e_q} \equiv _p g^{-b} \prod _{q \in B} q^{e_q} \equiv _p g^{-b} \cdot yg^b \equiv _p y\).

zu Schritt (2): Wähle zufällige Zahlen \(z \in \natural _0\) mit \((g^z \bmod p)\) \(B\)-glatt, d. h. \(g^z \equiv _p \prod _{q \in B} q^{f(q,z)}\) für bestimmte \(f(q,z) \in \natural _0\). Wenn man nun \((f(q,z))_{q \in B}\) als Vektor abspeichert und \(q \equiv _p g^{x_q}\) mit den Variablen \((x_q)_{q \in B}\) setzt, dann gilt \(z \equiv \sum _{q \in B} x_q f(q, z) \pmod {p - 1}\). Gibt es genügend solche viele Zahlen \(z\), dann hat das entstehende LGS modulo den höchsten Primteilerpotenzen von \((p-1)\) genügend viele Gleichungen und dann gibt es eine Lösung \((x_q)_{q \in B}\).

zu Schritt (3): Bestimme \(y\) zufällig mit \((yg^b \bmod p)\) \(B\)-glatt.

Zeitbedarf: erwartet \(2^{\weakO (\sqrt {\log p})}\)

Der Index-Calculus-Algorithmus ist nicht auf andere Gruppen übertragbar, weil „\(B\)-glatt“ dann keinen Sinn mehr ergibt.