<< . .

. 24
( : 33)



. . >>


Gegeben ist die zyklische Gruppe G = Z13 = 2 . Es ist also g = 2, und es sei
a = 9. Wir bestimmen x = Logg (a) mit Pollards -Methode.
1. Schritt: Wir w¤hlen

G1 := {1, 4, 7, 10} , G2 := {2, 5, 8, 11} , G3 := {3, 6, 9, 12} .

2. Schritt: Wir bestimmen nun die Folgenglieder x1 , . . . , xi , . . . , x j , sodass xi = x j :
0 1 2 3 4 5 6 7
i
1 9 5 12 11 4 10 12 Stop!
xi
±i 0 1 1 2 2 4 5 6
βi 0 0 1 2 3 6 6 6
Mit den Größen

i = 3 , j = 7 , ±i = 2 , ± j = 6 , β i = 2 , β j = 6

erhalten wir s = ’4 (bzw. s = 8) und t = 4.
3. Schritt: Als Lösungsmenge der Kongruenzgleichung

(’4) X ≡ 4 (mod 12)
184 10 Diskrete Logarithmen

erhalten wir wegen d = ggT(’4, 12) = 4 und da v = 2 eine Lösung der Kongru-
enzgleichung ist die Menge 2 + 12 Z = 2 + 3 Z. Folglich ist der diskrete Loga-
4
rithmus x = Logg (a) unter den Zahlen 2 , 5 , 8 , 11 zu suchen. Man testet:

2 5 8
2 = 4, 2 = 6, 2 = 9,

sodass x = Logg (a) = 8 gilt.


10.3.2 Modi¬kation des zweiten Schrittes

Bei der beschriebenen Version von Pollards -Methode sind im 2. Schritt für jedes
i die Tripel (xi , ±i , β i ) zu speichern. Wir geben nun eine Modi¬kation dieses 2.
Schrittes an, sodass fast kein Speicher benötigt wird. Dazu begründen wir vorab:

Lemma 10.2
Es seien X eine endliche Menge und f : X ’ X eine Abbildung. Für jede Folge (xi ) in
X mit xi+1 = f (xi ) gibt es ein i ∈ N mit xi = x2i .

Beweis. Es seien x1 , x2 , . . . , xv , . . . , xv+p’1 verschieden, aber xv+p = xv . Dann gilt
für alle a ∈ N:
xv+ap = xv .
Es folgt x j+ap = x j für alle j ≥ v. W¤hle nun ein i ≥ v mit p | i, etwa i = d p.
Dann gilt
x2i = xi+i = xi+dp = xi .
Damit ist ein passendes i gefunden.

Bemerkung
Nach dem Beweis dieses Lemmas kreisen die Folgenglieder xi nach einer evtl.
Vorperiode x1 , . . . , xv mit der Periode p. Vergleiche diese Veranschaulichung mit
dem griechischen Buchstaben .

Wir nutzen Lemma 10.2 um Schritt 2 zu modi¬zieren.
2. Schritt “ modi¬ziert. Wir bestimmen ganze Zahlen s, t mit as = gt . Dazu er-
zeugen wir erneut die Folgenglieder x0 = 1, x1 , x2 , . . . ∈ a±i g βi ; ±i , β i ∈ N0 ,
die durch folgende Vorschrift gegeben sind:
§
⎨ a xi , falls xi ∈ G1
xi , falls xi ∈ G2 .
2
xi+1 :=
©
g xi , falls xi ∈ G3

Nun speichern wir aber nicht alle Tripel (xi , ±i , β i ), sondern gehen wie folgt vor:
In jedem Schritt werden zwei Werte berechnet, n¤mlich xi+1 aus xi und x2 i+2 aus
x2 i , ausführlicher:
10.3 Pollards -Methode * 185

Berechne (x1 , ±1 , β 1 ) und (x2 , ±2 , β 2 ).

Falls x2 = x1 , Stop!, sonst:

Berechne (x2 , ±2 , β 2 ) und (x4 , ±4 , β 4 ).

Falls x4 = x2 , Stop!, sonst:

Berechne (x3 , ±3 , β 3 ) und (x6 , ±6 , β 6 ).

Falls x6 = x3 , Stop!, sonst:

Berechne (x4 , ±4 , β 4 ) und (x8 , ±8 , β 8 ) usw.

Da G endlich ist, gibt es nach Lemma 10.2 einen Index i mit x2 i = xi , der Algorith-
mus bricht somit ab. Wie im obigen Schritt 2 erhalten wir hieraus die gesuchten
Zahlen s und t:
s := ±i ’ ±2 i und t := β 2 i ’ β i .

Der Speicherbedarf wird durch die Modi¬kation sehr gering. Die gespeicherten
Tripel (xi , ±i , β i ) und (x2 i , ±2 i , β 2 i ) werden im Fall x2 i = xi durch die Tripel
(xi+1 , ±i+1 , β i+1 ) und (x2 i+2 , ±2 i+2 , β 2 i+2 ) überschrieben.

Beispiel

Wir betrachten erneut das Beispiel von Seite 183: Es sei G = Z13 = 2 . Wir
berechnen den diskreten Logarithmus x von a = 9 zur Basis 2 mit dem modi¬-
zierten 2. Schritt.
1. Schritt: Wir w¤hlen erneut

G1 := {1, 4, 7, 10} , G2 := {2, 5, 8, 11} , G3 := {3, 6, 9, 12} .

2. Schritt: Wir bestimmen nun die Folgenglieder x1 , . . . , xi wie oben beschrieben:

(xi , ±i , β i ) (x2 i , ±2 i , β 2 i )
i
(9, 1, 0) (5, 1, 1)
1
(5, 1, 1) (11, 2, 3)
2
(12, 2, 2) (10, 5, 6)
3
(11, 2, 3) (11, 6, 7)
4
Mit den Größen

i = 4 , j = 8 , ±i = 2 , ± j = 6 , β i = 3 , β j = 7

erhalten wir s = ’4 (bzw. s = 8) und t = 4. Nun erh¤lt man wie im Beispiel auf
Seite 183 den diskreten Logarithmus x = 8.
186 10 Diskrete Logarithmen

Bemerkung
Auch bei dieser modi¬zierten Version ist der Rechenaufwand bei Pollards -
Methode O( |G|) wegen des Geburtstagsparadoxons. Es gibt weitere Modi¬-
kationen, die in der Praxis etwas schneller laufen (siehe [7, § 8.5]). Der Vorteil
von Pollards -Methode gegenüber dem Baby-Step-Giant-Step-Algorithmus von
Shanks liegt im sehr geringen Speicherbedarf.


10.4 Die Reduktion nach Silver-Pohlig-Hellman
Auch wenn |G| beim ElGamal-Verfahren sehr groß ist, kann das DLP durch Pol-
lards -Methode oder den Baby-Step-Giant-Step-Algorithmus von Shanks sehr
einfach zu lösen sein. Das liegt daran, dass das DLP eventuell auf Gruppen klei-
ner Ordnung reduziert werden kann. Sind n¤mlich p1 , . . . , pn die Primteiler von
|G|, so l¤sst sich das DLP auf Gruppen von der Ordnung p1 , . . . , pn reduzieren.
Will man also etwa vor den Algorithmen von Shanks oder Pollard sicher sein, so
sollte der größte Primteiler von |G| sehr groß sein. Wir behandeln diese Reduktion
in diesem Abschnitt. Wir benötigen dazu ein Lemma aus der Gruppentheorie.
Lemma 10.3
Ist G = g eine endliche zyklische Gruppe der Ordnung n, so ist G zur additiven
Gruppe Z n isomorph.

Beweis. Wir betrachten den surjektiven Homomorphismus

Z G
¦: .
’ gk
k
Wegen o(g) = n ist n Z der Kern von ¦. Nach dem Homomorphiesatz auf Seite
150 gilt somit Z n = Z/n Z ∼ G.
=

10.4.1 Reduktion auf Primzahlpotenzordnung
Wir reduzieren das DLP in einem ersten Schritt auf Gruppen von Primzahlpo-
tenzordnung. Dazu beachten wir, dass wir nach den Lemmata 7.3 und 10.3 jede
zyklische Gruppe G mit
|G| = n = p11 · · · pν
ν
(kanonische Primfaktorzerlegung)
als ein direktes Produkt
G = G1 — · · · — G
mit zyklischen Gruppen G1 , . . . , G mit paarweise teilerfremden Ordnungen
|G1 | = p11 , . . . , |G | = pν schreiben können. Wir führen die Reduktion für den
ν

Fall = 2 durch, der allgemeine Fall folgt hieraus induktiv.
Ist g1 bzw. g2 ein erzeugendes Element von G1 bzw. G2 , wobei die Gruppenord-
nungen |G1 | und |G2 | teilerfremd sind, so ist offenbar g = (g1 , g2 ) ein erzeugen-
des Element von G1 — G2 . Es gilt:
10.4 Die Reduktion nach Silver-Pohlig-Hellman 187

Lemma 10.4
Es seien G1 = g1 und G2 = g2 endliche zyklische Gruppen mit teilerfremden
Ordnungen. Weiter sei g = (g1 , g2 ) ein erzeugendes Element der zyklischen Gruppe
G1 — G2 , und es sei a := (a1 , a2 ) ∈ G. Für x = Logg (a) gilt:

x ≡ Loggi (ai ) (mod |Gi |) für i = 1, 2 .

Beweis. Da x der diskrete Logarithmus von a zur Basis g ist, gilt g x = a, d. h.
(g1 , g2 ) = (a1 , a2 ). Somit gilt nach (ii) in Lemma 6.1 (b):
xx


Logg (ai )
gix = ai = gi , d. h. x ≡ Loggi (ai ) (mod |Gi |) für i = 1, 2 .
i



Damit ist bereits alles gezeigt.
Kennt man die diskreten Logarithmen xi = Loggi (ai ) für i = 1, 2, so kann man
also den diskreten Logarithmus x = Logg (a) wegen der Teilerfremdheit von |G1 |
und |G2 | mithilfe des chinesischen Restsatzes 7.4 berechnen. Mit Lemma 10.4 ist
somit das DLP in einer endlichen zyklischen Gruppe G auf das DLP in zyklischen
Gruppen von Primzahlpotenzordnung zurückgeführt. Hierbei sind eigentlich die
Kosten für den chinesichen Restsatz zu berücksichtigen, aber die sind bekanntlich
nicht sehr hoch.

Beispiel

Es ist 5 eine Primitivwurzel modulo der Primzahl p = 73, d. h. Z73 = 5 . Wir
bestimmen den diskreten Logarithmus von a = 58, d. h. x = Log5 (58). Es gilt
Z — = G1 — G2 ∼ Z8 — Z9 , wobei
=
p

9 8
G1 = 5 = 10 mit |G1 | = 8 und G2 = 5 = 2 mit |G2 | = 9 .

Für das Element a = 58 erhalten wir in G1 — G2 die Darstellung
9 8
a = 58 = (58 , 58 ) = (51, 55) .

Wir bestimmen nun die einfach zu bestimmenden Logarithmen x1 = Log10 (51)
und x2 = Log2 (55) in den Gruppen G1 und G2 z. B. mit Pollards -Methode und
erhalten:
x1 = Log10 (51) = 3 und x2 = Log2 (55) = 7 .
Nun erhalten wir den gesuchten diskreten Logarithmus, indem wir mit dem chi-
nesischen Restsatz die kleinste positive Lösung des folgenden Kongruenzglei-
chungssystems bestimmen:

X ≡ 3 (mod 8) , X ≡ 7 (mod 9) .
43
Wir erhalten x = 46, und tats¤chlich gilt 5 = 58.
188 10 Diskrete Logarithmen

10.4.2 Reduktion auf Primzahlordnung
Wir reduzieren das DLP nun auf Gruppen von Primzahlordnung.
Lemma 10.5
Es sei G = g eine endliche zyklische Gruppe mit |G| = pν für eine Primzahl p und ein
ν ∈ N). Dann l¤sst sich das DLP in G auf ν -maliges Logarithmieren in Gruppen der
Ordnung p reduzieren.
Beweis. Wir begründen die Behauptung mit Induktion nach ν. Der Fall ν = 1
ist klar. Die Behauptung gelte für ν ’ 1. Es ist U := g p nach Lemma 6.2 eine
Untergruppe von G mit |U| = pν’1 . Folglich ist |G/U| = p, G/U = g U . Es sei
a ∈ G. Bestimme ein y ∈ N mit a U = (g U)y = gy U. Dann gilt a g’y ∈ U =
g p . Nach Induktionsvoraussetzung können wir x ∈ N durch (ν ’ 1) -maliges
Logarithmieren bestimmen mit a g’y = g p x , und es gilt a = gy+x p .
Mit Lemma 10.5 ist das DLP in Gruppen der Ordnung pν auf ν DLPs in Gruppen
der Ordnung p reduziert. In der Praxis führt man die Reduktion wie im Folgen-
den beschrieben durch.
Gegeben ist die zyklische Gruppe G = g mit |G| = pν , p prim, ν ∈ N. Zu einem
Element a ∈ G ist der diskrete Logarithmus x = Logg (a) gesucht. Man schreibe
den gesuchten diskreten Logarithmus x in der p -adischen Darstellung als

x = x0 + x1 p + · · · + xν’1 pν’1 , x0 , . . . , xν’1 ∈ {0, . . . , p ’ 1} .

Wir bestimmen nun der Reihe nach die Zahlen x0 , . . . , xν’1 aus der Gleichung
ν’1
g x0 +x1 p+···+xν’1 p
(—) gx = a , =a
d. h.

und erhalten so die gesuchte Zahl x. Im Folgenden beachte man den Satz 6.9 von
ν
Euler, wonach g p = 1 gilt.
Wir bestimmen x0 : Potenziere die Gleichung g x = a mit pν’1 und erhalte
x0
ν’1 ν’1 ν’1 ν’1
= gp = gp = ap
gp x x0
.

ν’1
Berechne den diskreten Logarithmus x0 = Logg pν’1 (a p ) “ man beachte, dass
ν’1
das Element g p die Ordnung p hat. Damit ist x0 bestimmt.
ν’1
Wir bestimmen x1 : Schreibe die Gleichung in (—) um zu g x1 p+···+xν’1 p =
a g’x0 und potenziere diese Gleichung mit pν’2 und erhalte
pν’2
x1
ν’1 ν’1
= a g’x0
= gp
gp x1
.

ν’2 ν’2
g’p
Berechne den diskreten Logarithmus x1 = Logg pν’1 (a p x0 ). Damit ist
x1 bestimmt.
usw.
10.4 Die Reduktion nach Silver-Pohlig-Hellman 189

Der Algorithmus bestimmt die ν diskreten Logarithmen x0 , . . . , xν’1 in der Grup-
ν’1
pe g p der Ordnung p und damit den gesuchten diskreten Logarithmus x in
der Gruppe g der Ordnung pν .
Beispiel

Wir betrachten in der Gruppe Z251 = 6 mit 250 Elementen die zyklische Unter-
2
gruppe G = 6 = 36 mit 125 = 53 Elementen und bestimmen den diskreten
Logarithmus x von a = 4, d. h. x = Log36 (4). Dazu schreiben wir x in der 5 -
adischen Darstellung als

x = x0 + x1 5 + x2 52 mit x0 , x1 , x2 ∈ {0, . . . , 4} .

Wir bestimmen nun die Zahlen x0 , x1 , x2 aus der Gleichung

x0 +x1 5+x2 52
x
36 = 36 = 4.
x
Wir bestimmen x0 : Potenziere die Gleichung 36 = 4 mit 52 = 25 und erhalte

25
x0 25
= (36 ) x0 = 4 = 1.
219

Berechne den diskreten Logarithmus x0 = Log (1) = 0.
25
36

’0
x 5+x2 52
= 4 · 36 = 4 mit
Wir bestimmen x1 : Potenziere die Gleichung 36 1
51 = 5 und erhalte
25 x1 5
= 4 = 20 .
36

Berechne den diskreten Logarithmus x1 = Log 25 20 = 2. Damit ist x1 be-
36
stimmt.
’0’2·5
x2 52
= 4 · 36 = 149 mit
Wir bestimmen x2 : Potenziere die Gleichung 36
50 = 1 und erhalte
25 x2
= 149 .
36

Berechne den diskreten Logarithmus x2 = Log 25 149 = 4. Damit ist x2
36
bestimmt.

Wir erhalten somit für x = Log36 (4) = 0 + 2 · 5 + 4 · 52 = 110. Und tats¤chlich
110
= 4.
gilt 36



10.4.3 Volle Reduktion
Wir fassen nun die beiden Reduktionen zusammen und erhalten die volle Reduk-
tion des diskreten Logarithmenproblems auf Gruppen von Primzahlordnung.
190 10 Diskrete Logarithmen

Korollar 10.6
ν ν
Es sei G eine endliche zyklische Gruppe mit |G| = p11 · · · pr r (kanonische Primfaktor-
zerlegung). Dann l¤sst sich das DLP auf das DLP in Gruppen der Ordnung p1 , . . . , pr
zurückführen.

Hat |G| nur kleine Primteiler, so ist das DLP in G relativ leicht lösbar. Ist etwa p
eine Primzahl, sodass p ’ 1 nur kleine Primteiler hat, so ist Z — für die Verfahren
p
von Dif¬e-Hellman und ElGamal nicht brauchbar. Man w¤hle besser eine sichere
(große) Primzahl p, d. h. p = 2 q + 1 mit einer Primzahl q.

Beispiel
Die Zahl p = 2104 · 344 · 549 · 747 + 1 ist eine Primzahl mit 420 Bit. Das DLP in Z —
p
— | stecken.
ist aber sehr einfach, da nur die Primteiler 2, 3, 5, 7 in p ’ 1 = |Z p


Bemerkung
Kombiniert man die Reduktion mit einem der beiden allgemeinen Algorithmen,
√ √
so betr¤gt die Komplexit¤t O(ν1 p1 + · · · + ν p ) Gruppenoperationen. Falls

|G| einen dominanten Primteiler p enth¤lt, betr¤gt die Komplexit¤t O( p).
Falls es Gruppen gibt, für die es zur Lösung des DLP keine wesentlich besseren
Algorithmen als die in diesem Kapitel beschriebenen gibt, so ist für diese Grup-
pen die Potenzfunktion f : x ’ g x eine Einwegfunktion.


Aufgaben

Bestimmen Sie den diskreten Logarithmus von 3 in Z53 zur Basis 2 mit
10.1

(a) dem Baby-Step-Giant-Step-Algorithmus von Shanks bzw.
(b) Pollards -Methode für Gi := {a ∈ {1, . . . , 52} ; a ≡ i mod 3} für i =
1, 2, 3.

10.2 Implementieren Sie die Algorithmen von Silver-Pohlig-Hellman, Shanks
und Pollard und testen Sie diese an Beispielen.

10.3 Wenn g keine Primitivwurzel modulo p ist, muss Pollards -Methode zur
Berechnung diskreter Logarithmen nicht funktionieren. Geben Sie ein Beispiel
dafür an.

10.4 Bestimmen Sie mit dem Silver-Pohlig-Hellman-Algorithmus den diskreten

Logarithmus von 500 zur Basis 7 in Z601 .
11 Faktorisierung

<< . .

. 24
( : 33)



. . >>