Blum Blum Shub

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

Vous avez de nouveaux messages (diff^?).

Cet article est une ébauche à compléter concernant la cryptologie, vous pouvez partager vos connaissances en le modifiant.

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 à été démontré qu'il était cryptographiquement sûr sous l'hypothèse qu'il soit difficile de factoriser un produit de grand nombres premiers, et que au plus $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] Voir aussi

[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.