Index Calculus
La méthode du calcul d'indice résout les logarithmes discrets dans Z_p^* à l'aide d'une base de factorisation et d'algèbre linéaire, avec une complexité sous-exponentielle L_p[1/2,√2].
Objectif
Battre les algorithmes génériques pour les logarithmes discrets en corps premier, éclairant le choix de paramètres DSA/DH.
Mécanisme
On choisit une base de factorisation S={petits nombres premiers}. On tire des k aléatoires et calcule g^k mod p ; si le résultat est S-friable, cela donne une relation linéaire ∑e_i·log(s_i)≡k (mod p−1). On collecte assez de relations, on résout les log(s_i) par algèbre linéaire, puis on calcule le log(h) visé.
Cas d’usage
- Attaques par logarithme discret
- Cryptanalyse
- Algorithmes arithmétiques