Cryptography Reference
In-Depth Information
sonst
gib
0
aus
Wir bezeichnen im Folgenden
JacobiUnterscheiderDi
eHellman
kurz mit
U
und
S
(Un[GroupGen]
,
DH[GroupGen])
U
mit
S
. Aus Lemma 6.5.1 erhalten wir sofort
suc
(
U,
(Un[
GroupGen
]
,
DH[
GroupGen
])) = Prob
{
S
b
=1
=1
}
=1
.
Aus Lemma 6.5.1 erhält man auch leicht, dass
fail
(
U,
(Un[
GroupGen
]
,
DH[
GroupGen
])) = Prob
{
S
b
=0
=1
}
=
1
2
gilt, da in
das Gruppenelement
z
unabhängig von
x
und
y
gewählt wird und
wegen Lemma 6.5.1 die Wahrscheinlichkeit, dass
J
p
(
z
)=
j
gilt, genau
1
/
2
ist.
Insgesamt ergibt sich also
S
b
=0
adv
(
U,
(Un[
GroupGen
]
,
DH[
GroupGen
])) =
1
2
.
Den gerade beschriebenen Angriff kann man leicht dadurch umgehen, dass man sich
auf die Untergruppe
QR(
p
)
der quadratischen Reste von
Z
p
zurückzieht, da, wie wir
wissen, in dieser Gruppe alle Elemente das gleiche Jacobi-Symbol besitzen, nämlich
1
.
Man vermutet, dass die DDH-Annahme für diese Klasse von Gruppen gilt, falls die
Ordnung
(
p
1)
/
2
von
QR(
p
)
einen großen Primfaktor enthält. Häufig betrachtet man
deshalb Primzahlen
p
der Form
2
q
+1
, für eine große Primzahl
q
. Dann ist die Ordnung
von
QR(
p
)
nämlich
q
. Eine solche Primzahl
p
nennt man
starke
Primzahl. (Diese kann
man übrigens erzeugen, indem man eine große Zahl
p
erzeugt und dann testet, ob
p
und
(
p −
1)
/
2
Primzahlen sind.)
Man vermutet auch für andere Klassen von Gruppen, dass die DDH-Annahme gilt.
Ein wichtiges Beispiel sind bestimmte Gruppen, die aus Punkten auf elliptischen Kurven
bestehen (siehe auch Abschnitt 6.8).
−
Algorithmen für den diskreten Logarithmus
Da, wie wir bereits diskutiert haben, das Problem der Berechnung des diskreten Loga-
rithmus (kurz: DL-Problem) direkte Konsequenzen für die DDH-Annahme hat und das
DL-Problem ähnlich wie das Faktorisierungsproblem Gegenstand intensiver Forschung
ist und war, wollen wir an dieser Stelle kurz bekannte Algorithmen für das DL-Problem
diskutieren.
Man unterscheidet zwischen zwei Arten von Algorithmen: generische und spezifische
Algorithmen. Während spezifische Algorithmen auf spezielle Gruppen (z. B.
Z
p
)zuge-
schnitten sind und deren spezifische Eigenschaften ausnutzen, arbeiten generische Al-
gorithmen auf beliebigen endlichen zyklischen Gruppen, ohne spezielle Eigenschaften
auszunutzen.
