Baby-step giant-step

Un article de Wikipédia, l'encyclopédie libre.

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 opérations de comparaison, une autre solution est 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: une valeur x vérifiant .
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 (l'inverse de 𝛼m ou encore 𝛼n - m).
𝛾 ← 𝛽. (Faire 𝛾 = 𝛽)
Pour i tel que 0 ≤ i < m:   //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 en temps (une opération par itération des boucles)[3].

D'autres méthodes comme l'algorithme ρ de Pollard (avec l'algorithme de Floyd pour la détection de cycle) 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.

Un exemple d'utilisation : calcul d'ordre[modifier | modifier le code]

Le calcul de l'ordre d'un point dans un groupe de cardinal inconnu peut être nécessaire dans de nombreuses situations, comme notamment en cryptographie. L'algorithme Baby-Steps, Giant-Steps peut apporter une solution à ce problème.

Considérons un groupe qui sera noté multiplicativement. Supposons que l'on connaisse une approximation du cardinal de , que l'on notera . Soit un élément de fixé. On recherche son ordre dans . Il s'agit alors de trouver le plus petit entier non nul vérifiant . Il s'agit donc d'un cas particulier de la résolution du logarithme discret.

On peut donc utiliser l'algorithme Baby-Steps, Giant-Steps, mais il est nécessaire de le modifier légèrement afin d'obtenir une solution qui soit d'une part non nulle et d'autre part minimale. Pour cela, il suffit de calculer les baby-steps de (inclus) ) (exclus), dans l'ordre décroissant. On obtient l'algorithme suivant :

Entrée: un groupe cyclique G d'ordre environ N, et un élément α
Sortie: une valeur x vérifiant .
m ← [√n]+1
Pour j allant de m à 1:    //Baby-Step
   Calculer αj et sauvegarder la paire (j, αj), par exemple dans une table de hachage. 
Calculer αm.
γ ← 1
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.

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é « Baby-step giant-step » (voir la liste des auteurs).
  1. (en) D. Shanks, « Class number, a theory of factorization and genera », Proc. Symp. Pure Math., vol. 20,‎ , p. 415-440.
  2. (en) Alfred J. Menezes, Paul C. van Oorschot et Scott A. Vanstone, Handbook of Applied Cryptography, Boca Raton, CRC Press, , 780 p. (ISBN 0-8493-8523-7, lire en ligne [PDF]), chap. 3.6 (« The discrete logarithm problem ») pour l'ensemble du paragraphe.
  3. Menezes, van Oorschot et Vanstone 1996.

Annexes[modifier | modifier le code]

Sur les autres projets Wikimedia :

Bibliographie[modifier | modifier le code]

  • (en) Henri Cohen, A Course in Computational Algebraic Number Theory [détail de l’édition]
  • (en) A. Stein et E. Teske, « Optimized baby step-giant step methods », J. Ramanujan Math. Soc., vol. 1, no 20,‎ , p. 1-32
  • (en) A. V. Sutherland, Order computations in generic groups : PhD thesis, MIT, (lire en ligne [PDF])
  • (en) D. C. Terr, « A modification of Shanks’ baby-step giant-step algorithm », Math. Comput., vol. 69,‎ , p. 767-773

Article connexe[modifier | modifier le code]

Algorithme de Pohlig-Hellman

Lien externe[modifier | modifier le code]

Guénaël Renault, « La Naissance de la Cryptographie Asymétrique » (version du 17 janvier 2015 sur l'Internet Archive) [PDF].