Logarithme discret

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

Dans un groupe cyclique G fini engendré par α, le logarithme discret est une application réciproque de l'exponentiation k ↦ αk (la loi de groupe étant notée multiplicativement) définie sur les entiers : elle associe à un élément β du groupe G le plus petit entier naturel k tel que αk = β. C'est l'analogue du logarithme réel qui est la réciproque de l'exponentielle.

Le logarithme discret est utilisé pour la cryptographie à clé publique, ainsi 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 linéaire en la taille de l'argument (voir exponentiation rapide),

Définition[modifier | modifier le code]

On considère un groupe cyclique G 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].

Il est aussi possible de définir le logarithme discret 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.

Propriétés[modifier | modifier le code]

La formule de changement de bases pour les logarithmes ordinaires reste valide : si c est un autre générateur de G, alors

\log_c (x) = \log_c(b) \cdot \log_b(x)

On peut par exemple calculer ainsi le logarithme discret de 4 dans le groupe cyclique ℤ7*, pour la base 3 (3 est un générateur du groupe). 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 β est le plus petit entier k tel que 3k ≡ β (mod 7).

Pour certains groupes, le calcul des logarithmes discrets s'avère difficile, tandis que le problème inverse de 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[modifier | modifier le code]

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 :

Le 9 mai 2014, 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 est qu'il devient inenvisageable de reposer sur la difficulté de ce problème, dans les applications cryptographiques.

Notes et références[modifier | modifier le code]

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Discrete logarithm » (voir la liste des auteurs).

  1. Stinson2006, p. 234.
  2. Un nouvel algorithme secoue la cryptographie.

Bibliographie[modifier | modifier le code]

Sur les autres projets Wikimedia :