Discrete Logarithm
Logarithme discret : étant donnés g et h, trouver l'entier x tel que g^x=h (mod p) ; c'est le fondement de sécurité de Diffie-Hellman et DSA.
Objectif
Comprendre l'hypothèse de sécurité sous-jacente à la cryptographie à clé publique et analyser la difficulté du logarithme discret.
Mécanisme
Résoudre x dans un groupe d'ordre n. Les algorithmes génériques (BSGS, rho de Pollard) coûtent O(√n). Les groupes particuliers (ordre friable) permettent la décomposition de Pohlig-Hellman. La méthode du calcul d'indice est sous-exponentielle pour certains groupes.
Cas d’usage
- Analyse de sécurité cryptographique
- Choix des paramètres DH
- Théorie des nombres