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.

  1. m ← [√n]+1
  2. Pour tout j tel que 0 ≤ j < m: //Baby-Step
    1. Calculer αj et sauvegarder la paire (j, αj) dans une table de hashage.
  3. Calculer αm.
  4. γ ← β. (Faire γ = β)
  5. Pour i = 0 à (m − 1): //Giant-Step
    1. Verifier si γ est le second composant (αj) d'une paire quelconque dans la table.
    2. Si oui, retourner im + j.
    3. Si non , γ ← γ • αm.


Algorithme en C avec la bibliothèque GNU MP[modifier | modifier le code]

void baby_step_giant_step (mpz_t g, mpz_t h, mpz_t p, mpz_t n, mpz_t x ){
   unsigned long int i;
   long int j = 0;
   mpz_t N;
   mpz_t* gr ; /* liste g^r */
   unsigned long int* indices; /* indice[ i ] = k <=> gr[ i ] = g^k */
   mpz_t hgNq ; /* hg^(Nq) */
   mpz_t inv ; /* inverse de g^(N) */
   mpz_init (N) ;
   mpz_sqrt (N, n ) ;
   mpz_add ui (N, N, 1 ) ;
 
   gr = malloc (mpz_get_ui (N) * sizeof (mpz t) ) ;
   indices = malloc ( mpz_get_ui (N) * sizeof (long int ) ) ;
   mpz_init_set_ui (gr[ 0 ], 1);
 
   /* on calcule la suite {g^r} r = 1 ,.. ,N (Baby step ) */
   for ( i = 1 ; i <= mpz get ui (N) ; i++) {
      indices[i - 1] = i - 1 ;
      mpz_init (gr[ i ]) ;
      mpz_mul (gr[ i ], gr[ i - 1 ], g ); /* multiplier gr[i - 1] pour g */
      mpz_mod (gr[ i ], gr[ i ], p );
   }
   /* on trie les valeurs (k , g^k) par rapport à g^k */
   quicksort ( gr, indices, 0, mpz_get_ui (N) ) ;
   /* on calcule g^(-Nq)   (Giant step) */
   mpz_init_set (inv, g) ;
   mpz_powm (inv, inv, N, p);  /* inv <- inv ^ N (mod p)  */
   inverse (inv, p, inv) ;
 
   mpz_init_set (hgNq, h);
 
   /* on cherche les éléments égales dans les deux suites */
   for ( i = 0 ; i <= mpz get ui (N) ; i++){
      /* busque binaire (chercher hgNq dans le tableau gr ) */
      j = busque_binaire (gr, hgNq, 0, mpz_get_ui (N) ) ;
      if ( j >= 0 ){
         mpz_mul_ui (N, N, i);
         mpz_add_ui (N, N, indices [j]);
         mpz_set (x, N) ;
         return;
      }
      /* sinon , on calcule le prochain valeur de g^(Nq) */
      mpz_mul (hgNq, hgNq, inv);
      mpz_mod (hgNq, hgNq, p);
   }
}

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,‎ 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