Cryptography Reference
In-Depth Information
10 Diskrete Logarithmen
Die Sicherheit vieler kryptografischer Verfahren basiert auf der Schwierigkeit,
diskrete Logarithmen zu bestimmen. Beispiele sind der Diffie-Hellman-Schlüs-
selaustausch und das ElGamal-Verfahren, auch in der Variante als Signatur-
Verfahren, das wir in Kapitel 12 besprechen werden. Das diskrete Logarithmen-
problem ist daher von großer Bedeutung für die Kryptologie.
Wir behandeln in diesem Kapitel die zwei wichtigsten, nicht spezialisierten Al-
gorithmen, die zu einem Gruppenelement
a
einer zyklischen Gruppe
g
kleiner
g
x
bestimmen -
Ordnung den diskreten Logarithmus
x
, d. h. die Potenz
x
mit
a
=
den
Baby-Step-Giant-Step-Algorithmus
von Shanks und
Pollards
-Methode
. Damit
erhalten wir ein grobes Maß für die Sicherheit solcher kryptografischer Verfahren.
In einem letzten Abschnitt zeigen wir, dass die Wahl einer großen Gruppenord-
nung
alleine nicht vor den Algorithmen von Shanks und Pollard schützt.
Entscheidend ist letztlich der größte Primteiler der Gruppenordnung
|
G
|
|
|
. Dieser
muss genügend
groß
gewählt werden. Andernfalls greifen die Algorithmen von
Shanks und Pollard zusammen mit der
Reduktion
der Gruppe
G
auf Gruppen von
der Ordnung der Primteiler von
G
|
|
G
.
10.1 Das diskrete Logarithmenproblem
Sowohl das Diffie-Hellman- als auch das ElGamal-Verfahren lassen sich in einer
beliebigen endlichen zyklischen Gruppe
G
realisieren. Beide Verfahren
sind unsicher, wenn diskrete Logarithmen berechnet werden können, d. h.:
=
g
g
x
und g kann x berechnet werden
.
Aus a
=
In diesem Abschnitt bezeichne
G
eine zyklische Gruppe und
g
∈
G
ein erzeugen-
=
des Element von
G
, also
G
g
.
10.1.1 Der diskrete Logarithmus
Das
diskrete Logarithmenproblem
, kurz
DLP
, lautet:
Gegeben ist a
g
x
.
Das kleinste nichtnegative solche
x
heißt
diskreter Logarithmus
von
a
zur
Basis
g
; wir schreiben hierfür
x
∈
G
=
g
, gesucht ist x
∈
Z
mit a
=
=
Log
g
a
.
Beispi
e
l
Es ist 2 eine Primitivwurzel modulo 13, d. h.
. Wegen 2
6
Z
13
=
2
=
12 und
2
8
=
9 gilt:
Log
2
(
12
)=
6 und Log
2
(
9
)=
8.
