Cryptography Reference
In-Depth Information
10.1.2 Enumeration
Die naive Herangehensweise, nämlich das sukzessive Berechnen von
g
,
g
2
,
g
3
,
g
4
, ...
g
x
=
(
|
|
)
und Vergleich mit
a
, ist also nicht
sehr effizient. Diese Methode nennt man auch
Enumeration
. Wir besprechen im
Folgenden bessere Methoden zur Berechnung diskreter Logarithmen.
in jedem Schritt, hat Laufzeit
O
G
10.2 Der Baby-Step-Giant-Step-Algorithmus von Shanks
Der Baby-Step-Giant-Step-Algorithmus von Shanks ist eine Methode zur
schnel-
len
Berechnung diskreter Logarithmen. Die Aufgabenstellung lautet:
∈
=
=
Log
g
(
)
Gegeben ist a
G
g
, gesucht ist x
a
.
10.2.1 Das Verfahren
Benötigt wird eine obere Schranke für die Gruppenordnung, wir setzen:
min
k
,
;
k
2
n
:
=
|
G
|
=
∈
N
≥|
G
|
es ist dann
n
2
größer oder gleich
n
2
.
|
G
|
. Für jedes
a
∈
G
gilt somit
x
=
Log
g
(
a
)
≤
Wir dividieren die (gesuchte) Zahl
x
durch die Zahl
n
=
|
G
|
mit Rest:
x
=
qn
+
r
, wobei
r
∈{
0, . . . ,
n
−
1
}
und
q
∈{
0, . . . ,
n
}
.
Der Clou ist hierbei, dass das Element
q
wegen der Wahl von
n
in der Menge
{
0,...,
n
}
liegt. Wir erhalten
g
x
g
qn
+
r
, also
ag
−
r
g
qn
.
a
=
=
=
Wir ermitteln aus dieser letzten Formel nun
r
und
q
und damit den gesuchten
diskreten Logaritmus
x
=
+
qn
r
. Für
r
gibt es
n
Möglichkeiten, für
q
sind es
n
+
1 Möglichkeiten. Wir erhalten zwei Listen von Gruppenelementen.
ag
−
r
g
qn
=
ag
−
r
,
r
g
qn
,
q
=
=
0, . . . ,
n
−
1
0, . . . ,
n
ag
0
,
ag
−
1
,
ag
−
2
,...,
ag
−
n
+
1
Die
Baby-Step-Liste:
und
g
0
,
g
n
,
g
2
n
,...,
g
nn
.
die
Giant-Step-Liste:
