Blum Blum Shub

Un article de Wikipédia, l'encyclopédie libre.

Pour les articles homonymes, voir BBS.

Cet article est une ébauche concernant la cryptologie.

Vous pouvez partager vos connaissances en l’améliorant. (Comment ?).

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

On calcule la sortie de BBS en itérant la suite :

$x_{n+1} = (x_n)^2 \,\operatorname{mod}\, M$

Avec $M = pq~$ , le produit de deux grands nombres premiers $p~$ et $q~$ , et la sortie de l'algorithme est le bit le moins significatif (least signifiant bit ou LSB) de $x_n~$ . Alternativement, la sortie peut être plusieurs des derniers bits de $x_n~$

Les deux nombres premiers, $p~$ et $q~$ , devraient tous deux être congruents à 3 modulo 4 (cela garantit que chaque résidu quadratique possède une racine carrée qui possède également un résidu quadratique) et $\operatorname{pgcd}(\phi(p-1),\phi(q-1))$ doit être petit (ce qui fait que le cycle est long).

[modifier] Sécurité de l'algorithme

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 $log(log(M~))$ bits de poids faible de chaque $x_n~$ 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.

[modifier] Références

Lenore Blum, Manuel Blum, et Michael Shub. "A Simple Unpredictable Pseudo-Random Number Generator", SIAM Journal on Computing, volume 15, pages 364–383, mai 1986.
Pascal Junod, "Cryptographic Secure Pseudo-Random Bits Generation: The Blum-Blum-Shub Generator", août 1999. PDF de 21 pages
Martin Geisler, Mikkel Krøigård, et Andreas Danielsen. "About Random Bits", décembre 2004. Disponible en PDF et Gzipped Postscript.
Umesh V. Vazirani, Vijay V. Vazirani. "Efficient and Secure Pseudo-Random Number Generation", Crypto'84, Lecture Notes in Computer Science Volume 196, p. 193--202, Springer-Verlag (1985)