Cryptography Reference
In-Depth Information
Im Sinne der Komplexitätstheorie kann y aus x in
polynomialer
Zeit („einfach“) berechnet
werden (P). Dagegen ist die Ermittlung von x aus y nur in
nicht-polynomialer
Zeit möglich
(NP). Aus theoretischer Sicht konnte noch nicht bewiesen werden, ob es überhaupt Einweg-
funktionen gibt. Aus praktischer Sicht sind Einwegfunktionen solche, für welche die Aufgabe,
den Wert x für ein gegebenes y zu finden, praktisch nicht durchführbar ist, d.h. bei denen eine
Lösung mit polynomialem Aufwand nicht bekannt ist.
Diskreter Logarithmus
Ein Beispiel für eine Einwegfunktion ist der diskrete Logarithmus (DL). In Abb. 1-19 ist die
Zuordnung von x nach y für die diskrete Exponentiation y=(3
x
) mod 7 dargestellt. Bei der
Rechnung modulo 7 (mod 7) wird jeweils der Rest bezüglich des Moduls n=7 gebildet. Da-
durch entsteht ein endlicher Zahlenraum [0, 6]. Für die Werte x0 ist die Abbildung mit
y=(3
x
) mod 7 eineindeutig. Der diskrete Logarithmus ist die Umkehrfunktion, also in Abb. 1-
19 die Zuordnung von y nach x.
1
1
2
2
3
3
4
4
5
5
Abb. 1-19: Beispiel für
Einwegfunktion.
diskreter Logarithmus
y=(3
x
) mod 7
6
6
x
x
y = (3 ) mod 7
Angewendet wird der diskrete Logarithmus bei der „Diffie-Hellman-Schlüsselvereinbarung“
(Kap. 4.3) und bei dem ElGamal-Verfahren (Kap. 4.4). Bei letzterem wird für ein asymmetri-
sches Schlüsselpaar (e, d) der öffentliche Schlüssel e aus dem privaten Schlüssel d mittels
diskreter Exponentiation berechnet. Wenn ein Angreifer d aus e ermitteln wollte, müsste er den
diskreten Logarithmus in einem großen Zahlenraum lösen. Der diskrete Logarithmus spielt
auch eine Rolle bei der Kryptographie mittels elliptischer Kurven (ECC, elliptic curve cryptog-
raphy, Kap. 4.5). Dabei wird durch diskrete elliptische Kurven ein Zahlenraum definiert. Diese
Verfahren sind sehr effektiv und zukunftsträchtig.
Für die diskrete Exponentiation gibt es schnelle Algorithmen, nicht aber für den diskreten
Logarithmus. Natürlich besteht die Möglichkeit, alle x = 1, 2, 3, ... durchzuprobieren, bis sich
für y eingewünschtes Ergebnis einstellt. Wenn der Modul jedoch größer als 2
100
ist, dann kann
y mittels Durchprobieren praktisch nicht ermittelt werden. Weiteres zum DL findet sich in
Kap. 4.1.4.
