Baby-step giant-step

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

en théorie algorithmique des nombres et en théorie des groupes, l'algorithme baby-step giant-step permet de résoudre le problème du logarithme discret dans un groupe cyclique quelconque. Il est dû à Daniel Shanks en 1971[1]. C'est essentiellement un compromis temps-mémoire à partir de l'algorithme naïf par recherche exhaustive.

La difficulté du problème du logarithme discret est une hypothèse calculatoire sur laquelle reposent (plus ou moins directement) plusieurs schémas cryptographiques à clef publique, comme le chiffrement El Gamal, l'Échange de clés Diffie-Hellman ou le protocole de Schnorr. C'est pourquoi pouvoir évaluer la difficulté de ce problème est une question importante en cryptographie.

Théorie[modifier | modifier le code]

Soit G un groupe cyclique de générateur α d'ordre n, dont la loi est noté multiplicativement. Le problème du logarithme discret revient à chercher, pourβ dans G, un entier x tel que αx = β.

La méthode naïve serait d'essayer successivement les entiers à partir de 0 jusqu'à trouver l'entier x solution, ce qui peut demander n essais dans le pire des cas, un temps exponentiel en la taille de n.

Par division euclidienne par un entier m avec 0 ≤ j < m et 0 ≤ in/m. On a alors que αx = β si et seulement si αj = β(α-m)i

L'algorithme baby-step giant-step utilise ceci pour un m bien choisi, le plus souvent m=⌈n : pour trouver l'entier x on calcule la liste des (j, αj) (les baby-steps), puis les (i, β(α-m)i) (les giant-steps) jusqu'à trouver un second membre déjà présent dans la liste des baby-steps, le couple (i,j) correspondant donne x.

En prenant m=⌈n, l'algorithme demande au pire 2⌈n⌉ opérations de multiplications dans le groupe, contre n par recherche exhaustive, auquel il faut ajouter le temps nécessaire pour écrire la liste et chercher à un élément commun, sous une forme qui permet d'optimiser cette recherche, sachant qu'une opération de comparaison de deux éléments du groupe est de toute façon beaucoup moins coûteuse a priori qu'une multiplication. Une possibilité est d'utiliser un tableau trié sur le second membre pour la première liste, et de procéder par dichotomie pour la recherche dans celui-ci, on a alors 0(nlog n) opérations de comparaison, une autre d'utiliser une table de hachage.

L'algorithme demande par contre de stocker ⌈n⌉ éléments du groupe ce qui peut s'avérer à son tour rédhibitoire pour des groupes de taille importante (typiquement ceux utilisés en cryptographie)[2].

Algorithme[modifier | modifier le code]

Entrée: un groupe cyclique G d'ordre n, ayant un générateur α et un élément β.
Sortie: la valeur x satisfait .
m ← [√n]+1
Pour j tel que 0 ≤ j < m:    //Baby-Step
   Calculer αj et sauvegarder la paire (j, αj), par exemple dans une table de hachage. 
Calculer αm.
γ ← β. (Faire γ = β)
Pour i = 0 à (m − 1):   //Giant-Step
   Vérifier si γ est le second composant (αj) d'une paire quelconque dans la table.
   Si oui, retourner im + j.
   Si non , γ ← γ • αm.

Complexité[modifier | modifier le code]

L'algorithme requiert un espace en mémoire (pour le stockage des baby-steps), et opérations de multiplication[3].

D'autres méthodes comme l'algorithme ρ de Pollard avec l'algorithme de Floyd peuvent réduire la consommation mémoire à un , au prix d'une augmentation de la constante devant en temps. En notation L, le crible algébrique réduit ce temps à , où , ce qui est sous-exponentiel en , mais est limité aux sous-groupes multiplicatifs des corps finis. Ce qui rend l'algorithme inutilisable sur les groupes issus de courbes elliptiques, alors que l'algorithme baby-step giant-step reste applicable dans ce cas.

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

Notes[modifier | modifier le code]

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

Annexes[modifier | modifier le code]

Sur les autres projets Wikimedia :

Bibliographie[modifier | modifier le code]

  • [Cohen 1996] (en) H. Cohen, A Course In Computational Algebraic Number Theory, Springer, coll. « GTM » (no 138), (ISBN 0-387-55640-0)
  • [Menezes, van Oorschot et Vanstone 1996] (en) Alfred J. Menezes, Paul C. van Oorschot et Scott A. Vanstone, Handbook of Applied Cryptography, (ISBN 0-8493-8523-7, lire en ligne [PDF]), « Chapitre 3.6 The discrete logarithm problem »
  • [Shanks 1971] (en) D. Shanks, « Class number, a theory of factorization and genera », Proc. Symp. Pure Math., vol. 20,‎ , p. 415-440
  • [Stein et Teske 2005] (en) A. Stein et E. Teske, « Optimized baby step-giant step methods », J. Ramanujan Math. Soc., vol. 1, no 20,‎ , p. 1-32
  • [Sutherland 2007] (en) A. V. Sutherland, Order computations in generic groups : PhD thesis, MIT, (lire en ligne [PDF])
  • [Terr 2000] (en) D. C. Terr, « A modification of Shanks’ baby-step giant-step algorithm », Mathematics of Computation, vol. 69,‎ , p. 767-773

Articles connexes[modifier | modifier le code]

Liens externes[modifier | modifier le code]