Blum Blum Shub

Un article de Wikipédia, l'encyclopédie libre.
Sauter à la navigation Sauter à la recherche
Page d’aide sur l’homonymie Pour les articles homonymes, voir BBS.

Blum Blum Shub (BBS) est un algorithme capable de produire des nombres pseudo-aléatoires. Il fut proposé en 1986 par Lenore Blum, Manuel Blum et Michael Shub[1], d'où son nom.

Définition[modifier | modifier le code]

On calcule la sortie de BBS en itérant la suite : où "mod" est l'opérateur reste lors de la division par , le produit de deux grands nombres premiers et . La sortie de l'algorithme est le bit le moins significatif ou les derniers bits de .

Les deux nombres premiers, et , devraient tous deux être congrus à 3 modulo 4 (cela garantit que chaque résidu quadratique possède une racine carrée qui soit également un résidu quadratique) et le PGCD de et doit être petit (ce qui fait que le cycle est long).

La graine aléatoire et doivent être premiers entre eux (c'est-à-dire que et ne doivent pas être des facteurs de ), et ne doit pas être 0 ou 1.

Sécurité de l'algorithme[modifier | modifier le code]

Le générateur n'est pas approprié aux simulations, mais plutôt à la cryptographie, car il est assez lent.

Cependant, il possède une sécurité inhabituelle, puisqu'il a été démontré, tout d'abord, qu'il était cryptographiquement sûr sous l'hypothèse qu'il soit difficile de déterminer si, modulo un entier composé, un nombre est un carré ou non (problème de la résiduosité quadratique). Par la suite, il a été prouvé qu'il était cryptographiquement sûr, sous l'hypothèse que le problème de la factorisation soit difficile, et qu'au plus bits de poids faible de chaque soient sortis à chaque itération. Dans ce cas, il n'est pas possible de différencier la suite produite d'une suite réellement aléatoire.

Générateur[modifier | modifier le code]

Lavarand (en) est un dispositif utilisant des lampes à lave afin d'obtenir la graine d'un algorithme BBS, et ainsi générer des nombres pseudo-aléatoires[2] très sûrs et même des nombres réellement aléatoires[3],[4].

Notes et références[modifier | modifier le code]

  1. Blum, Blum et Shub 1986.
  2. (en) Landon Curt Noll (en), Robert G. Mende, et Sanjeev Sisodiya pour Silicon Graphics, Inc., Brevet U.S. 5,732,138 : Method for seeding a pseudo-random number generator with a cryptographic hash of a digitization of a chaotic system, déposé le 29 janvier 1996, publié le 24 mars 1998, sur Google Patents.
  3. Audrey Oeillet, « Quand un mur de lampes à lave sert à sécuriser Internet à San Francisco », PLUGIN (01net), (consulté le 6 janvier 2018).
  4. (en) Joshua Liebow-Feeser, « LavaRand in Production: The Nitty-Gritty Technical Details », Cloudflare Blog, (consulté le 6 janvier 2018).

Annexes[modifier | modifier le code]

Bibliographie[modifier | modifier le code]

Liens externes[modifier | modifier le code]