Baby-step giant-step

Baby-step giant-step

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.

Sommaire

Théorie

Soit G un groupe cyclique de générateur α d'ordre n. Le problème de logarithme discret revient à chercher, pour β 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

Entrée: un groupe cyclique G d'ordre n, ayant un générateur α et un élément β.

Sortie: la valeur x satisfait αx = β.

  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.

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), dont les références étaient :
  • (en) H. Cohen, A Course In Computational Algebraic Number Theory, Springer-Verlag, 1996 (ISBN 0-387-55640-0) 
  • (en) D. Shanks, « Class number, a theory of factorization and genera », dans Proc. Symp. Pure Math. 20, 1971, p. 415-440.
  • (en) A. Stein et E. Teske, « Optimized baby step-giant step methods », dans Journal of the Ramanujan Mathematical Society 20 (2005), no. 1, 1–32.
  • (en) A. V. Sutherland, Order computations in generic groups, PhD thesis, M.I.T., 2007.
  • (en) D. C. Terr, « A modification of Shanks’ baby-step giant-step algorithm », dans Mathematics of Computation 69 (2000), 767–773.

Lien externe

La Naissance de la Cryptographie Asymétrique, cours de Guénaël Renault à l'UPMC


Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Baby-step giant-step de Wikipédia en français (auteurs)

Игры ⚽ Поможем сделать НИР

Regardez d'autres dictionnaires:

  • Baby-step giant-step — In group theory, a branch of mathematics, the baby step giant step algorithm is a series of well defined steps to compute the discrete logarithm. The discrete log problem is of fundamental importance to the area of public key cryptography. Many… …   Wikipedia

  • baby step — (in the game of giant steps) the shortest step permitted a player, executed by placing the heel of one foot against the toe of the other and drawing the back foot up to the front foot. Cf. umbrella step. * * * …   Universalium

  • baby step — (in the game of giant steps) the shortest step permitted a player, executed by placing the heel of one foot against the toe of the other and drawing the back foot up to the front foot. Cf. umbrella step …   Useful english dictionary

  • giant steps — 1. a children s game in which a leader calls upon individual players to advance toward him or her in a given number and variety of steps, the object being for one person to tag the leader and for all of them to run back to the starting line… …   Universalium

  • giant steps — 1. a children s game in which a leader calls upon individual players to advance toward him or her in a given number and variety of steps, the object being for one person to tag the leader and for all of them to run back to the starting line… …   Useful english dictionary

  • Giant's Causeway — For other uses, see Giant s Causeway (disambiguation). Coordinates: 55°14′27″N 6°30′42″W / 55.24083°N 6.51167°W / 55.2 …   Wikipedia

  • step — {{Roman}}I.{{/Roman}} noun 1 in walking, running, etc. ADJECTIVE ▪ large, small ▪ heavy, light ▪ quick, slow ▪ hesitant …   Collocations dictionary

  • umbrella step — (in the game of giant steps) a step executed by extending one foot forward and whirling on the heel. Cf. baby step. * * * …   Universalium

  • umbrella step — (in the game of giant steps) a step executed by extending one foot forward and whirling on the heel. Cf. baby step …   Useful english dictionary

  • Counting points on elliptic curves — An important aspect in the study of elliptic curves is devising effective ways of counting points on the curve. There have been several approaches to do so, and the algorithms devised have proved to be useful tools in the study of various fields… …   Wikipedia

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”