AccueilđŸ‡«đŸ‡·Chercher

Baby-step giant-step

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

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 ≀ i ≀ n/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

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é

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

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

(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

Bibliographie

  • (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

Algorithme de Pohlig-Hellman

Lien externe

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

Cet article est issu de wikipedia. Text licence: CC BY-SA 4.0, Des conditions supplĂ©mentaires peuvent s’appliquer aux fichiers multimĂ©dias.