Cryptography Reference
In-Depth Information
Wichtige Beispiele für generische Algorithmen sind die sogenannte
Babystep-Giantstep-
Methode
sowie der
Pohlig-Hellman-Algorithmus
. Die erstgenannte Methode wird meist
auf Gruppen angewendet, deren Ordnung eine Primzahl
q
ist; allerdings muss die Ord-
nung der Gruppe nicht bekannt sein. Diese Methode erlaubt es, das DL-Problem in Zeit
O
(
√
q
log
o
(1)
q
)
zu lösen. Der Pohlig-Hellman-Algorithmus wird dagegen bevorzugt, wenn
die Ordnung der Gruppe eine zusammengesetzte Zahl ist und die Faktoren dieser Zahl be-
kannt sind, da dieser Algorithmus das DL-Problem dann auf Gruppen kleinerer Ordnung
herunterbricht. Unter anderem deshalb bevorzugt man in der Kryptographie Gruppen
mit Primzahlordnung, wie etwa die Gruppen
QR(
p
)
der quadratischen Reste für star-
ke Primzahlen
p
, da dadurch das Herunterbrechen des Problems auf kleinere Instanzen
verhindert wird.
Beispiele für spezielle Algorithmen zur Lösung des DL-Problems, die in den Einhei-
tengruppen
·
Z
p
für Primzahlen
p
arbeiten, sind die
Index-Calculus-Methode
sowie das
all-
gemeine Zahlkörpersieb
. Das letztgenannte Verfahren ist, wie der Name vermuten lässt,
eng verwandt mit dem entsprechenden Verfahren für das Faktorisieren großer Zahlen.
Es stellt zudem das zur Zeit beste bekannte Verfahren zur Lösung des DL-Problems
dar, mit einer erwarteten heuristischen Laufzeit von
O
(2
o
(1)
·
(log
p
)
1
/
3
·
(log log
p
)
2
/
3
)
.Derar-
tige Algorithmen sind für die oben erwähnten elliptischen Kurven nicht bekannt. Aus
diesem Grund kann man die Ordnung dieser Gruppen deutlich kleiner wählen als für
die Einheitengruppen
Z
p
und ihre Untergruppen, um das gleiche Maß an Sicherheit zu
erhalten. Elliptische Kurven werden deshalb häufig eingesetzt, wenn besonders e
ziente
Implementationen nötig sind, zum Beispiel Implementationen in Hardware mit geringen
Ressourcen.
6.5.3
Beweisbare Sicherheit des ElGamal-Kryptoschemas
Wir zeigen nun, dass jedes GroupGen-ElGamal-Kryptoschema
(
t,
2
ε
)
-sicher ist, falls
die DDH-Annahme bzgl. GroupGen,
t
,mit
t
≈ t
, und
ε
gilt. Wie gesagt wird vermutet,
dass die DDH-Annahme für eine große Laufzeit
t
und ein kleines
ε
gilt, falls die Klasse
der Gruppen
QR(
p
)
für starke und ausreichend große Primzahlen
p
betrachtet wird; in
der Praxis übliche Werte für die Größe der Primzahlen liegen zur Zeit bei 1024 bis 2048
Bits. Liefert GroupGen eine derartige Klasse von Gruppen, dann ist also das GroupGen-
ElGamal-Kryptoschema ein sicheres asymmetrisches Kryptoschema.
Um dies zu zeigen, reduzieren wir die Sicherheit des GroupGen-ElGamal-Kryptosche-
mas auf die DDH-Annahme. Genauer werden wir nun zeigen, dass es für jeden Angreifer
A
auf das GroupGen-ElGamal-Kryptoschema
S
einen Unterscheider
U
für
(Un[
GroupGen
]
,
DH[
GroupGen
])
gibt, so dass der Vorteil von
A
durch denjenigen von
U
beschränkt wer-
denkannund
U
und
A
ähnliche Laufzeiten haben. Wir führen also, in bekannter Manier,
einen Reduktionsbeweis.
Es sei dazu ein Angreifer
A
=(
S
AF
,
AG
)
auf das GroupGen-ElGamal-Kryptoschema
gegeben. Zu diesem Angreifer konstruieren wir einen Unterscheider
U
für das Paar
(Un[
GroupGen
]
,
DH[
GroupGen
])
wie folgt. Die Grundidee dabei ist dieselbe wie im Be-
weis von Satz 5.4.1. Der Unterscheider erhält nach Definition ein Tripel
(
u, v, w
)
als
Eingabe; genauer ein Tupel der Form
(
S
G
,n,g,u,v,w
)
. Mit Hilfe dieses Tripels simuliert
