Logarithme discret
Le logarithme discret est un objet mathématique utilisé en cryptologie. C'est l'analogue du logarithme réel qui est la réciproque de l'exponentielle, mais dans un groupe cyclique G fini.
Le logarithme discret est utilisé pour la cryptographie à clé publique, typiquement dans l'échange de clés Diffie-Hellman et le chiffrement El Gamal. La raison est que, pour un certain nombre de groupes, on ne connait pas d'algorithme efficace pour le calcul du logarithme discret, alors que celui de la réciproque, l'exponentiation, se réalise en un nombre de multiplications logarithmique en la taille de l'argument (voir exponentiation rapide),
Définition
On considère un groupe cyclique G fini d'ordre n (dont la loi est notée multiplicativement) et un générateur b de G. Alors chaque élément x de G peut être écrit sous la forme x = bk pour certains entiers k ; de plus, deux quelconques de ces entiers sont nécessairement congrus modulo n. Le logarithme discret peut être défini comme le plus petit entier naturel k vérifiant cette propriété (il en existe un seul tel que 0 ≤ k < n)[1]. C'est donc une application réciproque de l'exponentiation k ↦ bk.
Exemple
Considérons le groupe cyclique fini (ℤ7*, ×) et le générateur 3.
| 30 | 31 | 32 | 33 | 34 | 35 |
|---|---|---|---|---|---|
| 1 | 3 | 2 | 6 | 4 | 5 |
On a successivement 32 ≡ 2 mod 7, 33 ≡ 2×3 ≡ 6 mod 7, 34 ≡ 6×3 ≡ 4 mod 7. Dans ℤ7*, on a donc log3 4 = 4. De façon générale, dans ce groupe et pour le même générateur, le logarithme discret de x est le plus petit entier k tel que 3k ≡ x (mod 7).
| x | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|
| log3 x | 0 | 2 | 1 | 4 | 5 | 3 |
Logarithme discret comme isomorphisme de groupes
Le logarithme discret peut aussi se définir comme la fonction logb de G dans ℤn (où ℤn désigne l'anneau des entiers modulo n) en associant à tout élément x de G la classe de congruence de k modulo n. Cette fonction est un isomorphisme de groupes, appelé logarithme discret de base b.
Par exemple, le logarithme discret en base 3 est une application du groupe cyclique fini (ℤ7*, ×) dans (ℤ6, +).
Propriétés
La formule de changement de bases pour les logarithmes ordinaires reste valide : si c est un autre générateur de G, alors
Pour certains groupes, le calcul des logarithmes discrets s'avère difficile, tandis que le problème inverse, l'exponentiation discrète, ne l'est pas (grâce à l'algorithme d'exponentiation rapide) ; cette asymétrie est exploitée en cryptologie, pour la cryptographie à clé publique. On a d'abord utilisé les groupes cycliques ℤp* (constitués des nombres {1,...,p − 1} muni de la multiplication modulo le nombre premier p) pour p suffisamment grand (au moins 300 bits) et p - 1 avec au moins un « grand » facteur premier. On utilise également, déjà depuis quelque temps, les sous-groupes cycliques du groupe associé à une courbe elliptique sur un corps fini (Voir cryptologie sur les courbes elliptiques).
Algorithmes
Il existe plusieurs algorithmes pour le logarithme discret qui peuvent être plus efficaces que la recherche exhaustive, mais on n'en connaît aucun en temps polynomial en la taille des entrées.
Par exemple l'algorithme de Silver-Pohlig-Hellman peut être utilisé pour calculer le logarithme discret dans un groupe cyclique, si p – 1 est un produit de petits nombres premiers, ce qui oblige à l'éviter dans ce genre d'applications. L'algorithme de calcul d'indice (en) fonctionne dans les groupes ℤp*.
En voici quelques autres :
- Baby-step giant-step
- Algorithme rho de Pollard
- Algorithme de Pohlig-Hellman
- Crible spécial de corps de nombres (SNFS)
- Crible algébrique, également appelé Crible général de corps de nombres (GNFS)
Le , le CNRS a publié un communiqué de presse annonçant la résolution d'un pan du problème du logarithme discret[2]. La conclusion de l'article de recherche correspondant[3] est qu'il devient inenvisageable de faire reposer des applications cryptographiques sur la difficulté de ce problème dans le cas particulier pour lequel ces avancées ont eu lieu (lorsque l'on est dans un corps fini de petite caractéristique). Cependant, la grande majorité des techniques de chiffrement ne sont pas concernées par ce résultat[4] (le chiffrement RSA par exemple est utilisé sur l'anneau ℤ/nℤ de caractéristique n dont la longueur conseillée en 2016 est de 2048 bits[5]).
Notes et références
- Stinson2006, p. 234.
- Un nouvel algorithme secoue la cryptographie.
- A Heuristic Quasi-Polynomial Algorithm for Discrete Logarithm in Finite Fields of Small Characteristic.
- La principale conséquence de ce résultat a été de bannir l'utilisation des courbes elliptiques surpersingulières pour les couplages.
- Voir les recommandations du NIST : (en) « Taille de clefs »
Annexes
Bibliographie
- (en) Douglas Robert Stinson, Cryptography : Theory and Practice, Londres, CRC Press, , 3e éd., 616 p. (ISBN 978-1-58488-508-5, lire en ligne)
- Gilles Zémor, Cours de cryptographie, Paris, Cassini, , 227 p. (ISBN 2-84225-020-6, OCLC 45915497)