Baby-step giant-step

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

En théorie des groupes, une branche des mathématiques, l'algorithme baby-step giant-step est une série d'étapes bien définies pour calculer le logarithme discret. Le problème du logarithme discret, sur lequel se basent la plupart des cryptosystèmes modernes, est fondamental dans le domaine de la cryptographie à clé publique.

Théorie[modifier | modifier le code]

Soit G un groupe cyclique de générateur \alpha d'ordre n. Le problème de logarithme discret revient à chercher, pour \beta dans G, un entier x tel que : \alpha^x = \beta\,.

L'algorithme baby-step giant-step est basé sur la réécriture de x en le divisant sur m ainsi x = im + j, avec m = \lceil \sqrt{n} \rceil et 0 \leq i < m et 0 \leq j < m. Donc, on a:

\beta(\alpha^{-m})^i=\alpha^j\,.

L'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 \alpha^{x}=\beta.
m ← [√n]+1
Pour j tel que 0 ≤ j < m:    //Baby-Step
   Calculer αj et sauvegarder la paire (j, αj) dans une table de hashage. 
   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.

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é « Baby-step giant-step » (voir la liste des auteurs), dont les références étaient :
  • (en) H. Cohen, A Course In Computational Algebraic Number Theory, Springer, coll. « GTM » (no 138),‎ 1996 (ISBN 0-387-55640-0)
  • (en) D. Shanks, « Class number, a theory of factorization and genera », Proc. Symp. Pure Math., vol. 20,‎ 1971, p. 415-440
  • (en) A. Stein et E. Teske, « Optimized baby step-giant step methods », J. Ramanujan Math. Soc., vol. 1, no 20,‎ 2005, p. 1-32
  • (en) A. V. Sutherland, Order computations in generic groups : PhD thesis, MIT,‎ 2007 (lire en ligne)
  • (en) D. C. Terr, « A modification of Shanks’ baby-step giant-step algorithm », Mathematics of Computation, vol. 69,‎ 2000, p. 767-773

Lien externe[modifier | modifier le code]

Sur les autres projets Wikimedia :

La Naissance de la Cryptographie Asymétrique, cours de Guénaël Renault à l'UPMC