Cryptography Reference
In-Depth Information
Der diskrete Logarithmus ist die Umkehrung der diskreten Exponential-Funktion
y=(a
x
) mod p. Das Paar bildet eine Einwegfunktion: Die Berechnung auch großer Potenzen ist
durchführbar (vgl. Kap. 4.1.3). Die Umkehrung, der diskrete Logarithmus, ist für große Zah-
lenbereiche praktisch nicht durchführbar. Diskrete Logarithmen werden benutzt beim ElGa-
mal-Verfahren (Kap. 4.3), beim Schlüsselaustausch nach Diffie-Hellman (Kap. 4.3) und in der
Kryptographie mit elliptischen Kurven (Kap. 4.5).
Für den diskreten Logarithmus wird vorausgesetzt, dass der Modul n=p eine Primzahl und die
Basis a eine Primitivwurzel ist (auch Generator-Element, vgl. Kap. 4.1.1). Nur dann sind alle
Werte von y0 als Potenz a
x
darstellbar. Zur Veranschaulichung wird die Arithmetik modulo p
mit p=37 und die Basis a=2 gewählt. In Abb. 4-1 sind die Potenzen a
x
für alle Exponenten x
aufgetragen.
x x
y a)m dp(2)m d 7
(4.1-18)
Das Bild gleicht den ersten Regentropfen auf einem geteerten Weg, zumindest für den Bereich
x>5. Die Werte von y sind aus x leicht berechenbar. Der Aufwand für die Berechnung eines
Punktes steigt nur linear mit der Stellenlänge l
p
des Moduls p, (vgl. (4.1-17) in Kap. 4.1.3).
Will man dagegen den diskreten Logarithmus berechnen, d.h. für einen gegebenen Wert von y
das zugehörige x ausrechnen, dann ist der Aufwand viel größer. Als einfachster Algorithmus
wird die Folge a
1
, a
2
, a
3
,... berechnet, bis sich der erwünschte Wert von y einstellt. Beim
Durchlaufen der Folge erhält man keinen Hinweis, ob der gesuchte Wert x bald erreicht wird.
Wenn man in dem Beispiel von Abb. 4-1 die Aufgabe 14=(2
x
)mod37 lösen will, dann hat man
in der Folge trotz der „nahen“ y-Werte 13=(2
11
)mod37 und 15=(2
13
)mod37 keinen Hinweis,
dass sich die Lösung erst mit 14=(2
33
)mod37 einstellen wird.
Die Laufzeit für den einfachsten Algorithmus steigt mit der Ordnung O(p). Für schnellere
Algorithmen („Babystep-Giantstep“) steigt die Laufzeit mit der Ordnung O(p). Die Ordnung
sagt aus, dass die Laufzeit linear bzw. mit der Wurzel von p wächst. In beiden Fällen steigt die
Laufzeit exponentiell mit der Stellenlänge des Moduls p. Für manche Werte von p gibt es
jedoch spezielle Algorithmen, deren Laufzeit nur sub-exponentiell mit der Stellenlänge des
Moduls wächst. Diese sind für kryptographische Anwendungen ungeeignet. Weiterführendes
findet sich in [Bu04] und [BNS05].
Es wird bei erster Lesung empfohlen, mit Kapitel 4.2 „RSA, Rivest/Shamir/Adleman“ fortzu-
fahren. Von den nächsten Abschnitten sind 4.1.5 „Quadratwurzeln in der Rechnung modulo n“
und 4.1.6 „Chinesischer Restsatz“ erst bei praktischen Berechnungen für ElGamal und RSA
erforderlich.
4.1.5
Quadratwurzeln in der Rechnung modulo n
Dieses Kapitel kann bei erster Lesung überschlagen werden
. Quadratwurzeln werden für das
Authentifizierungsverfahren nach Fiat-Shamir in Kapitel 5 (Authentifikations-Protokolle)
benötigt. Quadratwurzeln werden bereits hier angesprochen, weil sie sich mit den Beispielen in
Kap. 4.1.2.4 gut veranschaulichen lassen.
