Cryptography Reference
In-Depth Information
Korollar 10.6
Es sei G eine endliche zyklische Gruppe mit
p
ν
r
r
(kanonische Primfaktor-
zerlegung). Dann lässt sich das DLP auf das DLP in Gruppen der Ordnung p
1
,...,
p
r
zurückführen.
p
ν
1
|
|
=
···
G
Hat
nur kleine Primteiler, so ist das DLP in
G relativ leicht
lösbar. Ist etwa
p
eine Primzahl, sodass
p
|
G
|
Z
p
für die Verfahren
von Diffie-Hellman und ElGamal
nicht
brauchbar. Man wähle besser eine sichere
(große) Primzahl
p
,d.h.
p
−
1 nur kleine Primteiler hat, so ist
=
2
q
+
1 mit einer Primzahl
q
.
Beispiel
Die Zahl
p
Z
p
2
104
3
44
5
49
7
47
=
·
·
·
+
1 ist eine Primzahl mit 420 Bit. Das DLP in
=
|
Z
p
|
ist aber sehr einfach, da nur die Primteiler 2, 3, 5, 7 in
p
−
1
stecken.
Bemerkung
Kombiniert man die Reduktion mi
t e
inem der bei
de
n allgemeinen Algorithmen,
so beträgt die Komplexität
O
(
ν
1
√
p
1
+
···
+
ν
√
p
)
Gruppenoperatio
n
en. Falls
(
√
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
|
einen
dominanten
Primteiler
p
enthält, beträgt die Komplexität
O
)
g
x
eine Einwegfunktion.
→
Aufgaben
Z
53
zur Basis 2 mit
(a) dem Baby-Step-Giant-Step-Algorithmus von Shanks bzw.
(b) Pollards
10.1
Bestimmen Sie den diskreten Logarithmus von 3in
=
{
∈{
}
≡
}
=
-Methode für
G
i
:
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.
-Methode zur
Berechnung diskreter Logarithmen nicht funktionieren. Geben Sie ein Beispiel
dafür an.
10.3
Wenn
g
keine Primitivwurzel modulo
p
ist, muss Pollards
10.4
Bestimmen
Sie
mit dem S
il
ver-Pohlig-Hellman-Algorithmus den diskreten
Logarithmus von 500 zur Basis 7in
Z
601
.
