Discrete Logarithm
Diskreter Logarithmus: zu gegebenen g und h das ganze x mit g^x=h (mod p) finden; er ist die Sicherheitsgrundlage von Diffie-Hellman und DSA.
Zweck
Die Sicherheitsannahme hinter der Public-Key-Kryptografie verstehen und die Schwierigkeit des diskreten Logarithmus analysieren.
Mechanismus
x in einer Gruppe der Ordnung n lösen. Generische Algorithmen (BSGS, Pollard-Rho) kosten O(√n). Spezielle Gruppen (glatte Ordnung) erlauben die Pohlig-Hellman-Zerlegung. Die Index-Calculus-Methode ist für bestimmte Gruppen subexponentiell.
Anwendungsfälle
- Kryptografische Sicherheitsanalyse
- DH-Parameterwahl
- Zahlentheorie