Cryptography Reference
In-Depth Information
Nun vergleicht man beide Listen. Ein gemeinsames Element
ag
−
r
g
qn
in bei-
den Listen liefert die Zahlen
r
und
q
und damit den diskreten Logarithmus
=
=
+
=
Log
g
(
)
x
qn
r
a
.
Wir führen den Algorithmus von Shanks an einem Beispiel durch.
Beispiel
Es sei
G
=
Z
97
=
=
=
=
Log
g
(
)
5
, also
g
5, und es s
ei
a
31. Wir bestimmen
x
a
.
< |
Z
97
|
=
Wegen 9
2
10
2
gilt
n
96
≤
=
|
G
|
=
10. Wir erhalten die Baby-Step-
Liste:
r
0
1
2
3
4
5
6
7
8
9
5
−
r
31
·
31
45
9
60
12
80
16
42
86
56
und die Giant-Step-Liste:
q
0
1
2
3
4
5
6
7
8
9
10
5
q
10
1
53
93
79
16
72
33
3
62
85
43
Für
r
=
6 und
q
=
4 erhalten wir dasselbe Ergebnis 16. Folglich ist
=
+
=
·
+
=
=
Log
5
(
)
x
qn
r
4
10
6
46
31
.
10.2.2 In der Praxis
Auf einem Rechner wird man die Giant-Step-Liste im Voraus berechnen, sie ist
unabhängig von der Größe
a
, dessen diskreter Logarithmus berechnet werden
soll. Die Giant-Step-Liste kann also mehrfach benutzt werden.
Anschließend berechnet man die Baby-Step-Liste schrittweise und vergleicht
nach Berechnen jedes einzelnen Wertes diesen mit den Werten aus der Giant-
Step-Liste - das Suchen wird vereinfacht, wenn die Giant-Step-Liste sortiert ist.
Man braucht
2
n
Gruppenoperationen und muss
n
Gruppenelemente spei-
chern. Wir halten fest:
≤
Lemma 10.1
Die Komplexität des Baby-Step-Giant-Step-Algorit
hmu
s zur Bestimmung des diskreten
Logarithmus in einer zyklischen Gruppe G ist O
(
|
|
)
G
.
Wegen des Zeit- und Speicherbedarfs ist der Baby-Step-Giant-Step-Algorithmus
bei der Größenordnung von
2
160
nicht mehr einsetzbar - bei einer zykli-
schen Gruppe der Größenordnung 2
80
ist bereits ein Speicher von einem Terabyte
nötig, falls man jedes Gruppenelement als ein Byte darstellen kann.
|
G
| >
10.3 Pollards
-Methode *
Deutlich weniger speicheraufwendig als der Baby-Step-Giant-Step-Algorithmus
ist
Pollards
-Methode
, die wir nun schildern. Die Aufgabenstellung lautet wie
oben:
Gegeben ist a
∈
G
=
g
, gesucht ist x
=
Log
g
(
a
)
.
