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) D. Shanks, « Class number, a theory of factorization and genera », Proc. Symp. Pure Math., vol. 20,â , p. 415-440.
- (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.
- 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
Lien externe
Guénaël Renault, « La Naissance de la Cryptographie Asymétrique » (version du 17 janvier 2015 sur Internet Archive) [PDF].