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[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$ , $x=im+j$ avec $0 \leq j < m$ et $0 \leq i \leq 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 =⌈ \sqrt 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 = ⌈ \sqrt n ⌉$ , l'algorithme demande au pire 2⌈ $\sqrt 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 ${\ce {{\mathcal {O}}({\sqrt {n}}\log(n))}}$ opérations de comparaison, une autre solution est d'utiliser une table de hachage.

L'algorithme demande par contre de stocker ⌈ $\sqrt 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  $\alpha ^{x}=\beta$ .
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 ${\mathcal {O}}({\sqrt {n}})$ en mémoire (pour le stockage des baby-steps), et ${\mathcal {O}}({\sqrt {n}})$ 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 ${\mathcal {O}}(1)$ , au prix d'une augmentation de la constante devant ${\sqrt {n}}$ en temps. En notation L, le crible algébrique réduit ce temps à $L\left({\tfrac {1}{3}},c\right)=\exp((c+o(1))\cdot (\log n)^{1/3}\cdot (\log \log n)^{1-1/3})$ , où $c={\sqrt[{3}]{\tfrac {64}{9}}}\approx 1{,}923\ldots$ , ce qui est sous-exponentiel en $\log n$ , 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 $G$ qui sera noté multiplicativement. Supposons que l'on connaisse une approximation du cardinal de $G$ , que l'on notera $N$ . Soit $a$ un élément de $G$ fixé. On recherche son ordre dans $G$ . Il s'agit alors de trouver le plus petit entier $x$ non nul vérifiant $a^{x}=1$ . 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 $m$ (inclus) à $0$ (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  $\alpha ^{x}=\beta$ .
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).

↑ (en) D. Shanks, « Class number, a theory of factorization and genera », Proc. Symp. Pure Math., vol. 20,‎ 1971, p. 415-440.
↑ (en) Alfred J. Menezes, Paul C. van Oorschot et Scott A. Vanstone, Handbook of Applied Cryptography, Boca Raton, CRC Press, 1996, 780 p. (ISBN 0-8493-8523-7, lire en ligne [PDF]), chap. 3.6 (« The discrete logarithm problem ») pour l'ensemble du paragraphe.
↑ Menezes, van Oorschot et Vanstone 1996.

Annexes[modifier | modifier le code]

Sur les autres projets Wikimedia :

Algorithmes de cryptographie et le problème du logarithme discret, sur Wikimedia Commons

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, n^o 20,‎ 2005, p. 1-32
(en) A. V. Sutherland, Order computations in generic groups : PhD thesis, MIT, 2007 (lire en ligne [PDF])
(en) D. C. Terr, « A modification of Shanks’ baby-step giant-step algorithm », Math. Comput., vol. 69,‎ 2000, 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 Internet Archive) [PDF].

[1] (en) D. Shanks, « Class number, a theory of factorization and genera », Proc. Symp. Pure Math., vol. 20,‎ 1971, p. 415-440.

[2] (en) Alfred J. Menezes, Paul C. van Oorschot et Scott A. Vanstone, Handbook of Applied Cryptography, Boca Raton, CRC Press, 1996, 780 p. (ISBN 0-8493-8523-7, lire en ligne [PDF]), chap. 3.6 (« The discrete logarithm problem ») pour l'ensemble du paragraphe.

[Menezesvan_OorschotVanstone1996-3] Menezes, van Oorschot et Vanstone 1996.

[1]

[2]

[3]