Voir la source de Blum Blum Shub

{{voir homonymes|BBS}}
'''Blum Blum Shub''' (BBS) est un [[algorithme]] capable de produire des nombres [[pseudo-aléatoire]]s. Il fut proposé en 1986 par [[Lenore Blum]], [[Manuel Blum]] et [[Michael Shub]]<ref>{{harvsp|Blum|Blum|Shub|1986}}.</ref>, d'où son nom.

== Définition ==
On calcule la sortie de BBS en itérant la suite :
{{retrait|1= <math>x_{n+1} = (x_n)^2 \!\mod M </math> }}
où "mod" est l'opérateur [[reste]] (modulo) lors de la [[division euclidienne]] par <math>M = p\,q</math>, le produit de deux grands [[Nombre premier|nombres premiers]] <math>p</math> et <math>q</math>. La sortie de l'algorithme est le [[Bit de poids faible|bit le moins significatif]] ou les derniers bits de <math>x_{n+1}</math>.

Les deux nombres premiers, <math>p</math> et <math>q</math>, devraient tous deux être [[Congruence sur les entiers|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 [[Plus grand commun diviseur|PGCD]] de [[Indicatrice d'Euler|<math>\varphi</math>]]<math>(p-1)</math> et [[Indicatrice d'Euler|<math>\varphi</math>]]<math>(q-1)</math> doit être petit (ce qui fait que le cycle est long).

La [[graine aléatoire]] <math>x_{0}</math> et <math>M</math> doivent être [[Nombres premiers entre eux|premiers entre eux]] (c'est-à-dire que <math>p</math> et <math>q</math> ne doivent pas être des facteurs de <math>x_{0}</math>), et <math>x_{0}</math> ne doit pas être 0 ou 1.

== 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 <math>\log(\log(M))</math> bits de poids faible de chaque <math>x_n</math> 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 ==

[[Lavarand]] est un dispositif utilisant des [[Lampe à lave#Nombres aléatoires|lampes à lave]] afin d'obtenir la graine d'un algorithme BBS, et ainsi générer des nombres pseudo-aléatoires<ref>{{US patent|5,732,138|title=Method for seeding a pseudo-random number generator with a cryptographic hash of a digitization of a chaotic system|inventor={{lien|Landon Curt Noll}}, Robert G. Mende, et Sanjeev Sisodiya|assignee=[[Silicon Graphics|Silicon Graphics, Inc.]]|filed=29 janvier 1996|date=24 mars 1998}}</ref> très sûrs et même des nombres réellement aléatoires<ref>{{lien web|langue=fr-FR|auteur1=Audrey Oeillet|titre=Quand un mur de lampes à lave sert à sécuriser Internet à San Francisco|périodique=PLUGIN ([[01net (site web)|01net]])|date=08/11/2017|lire en ligne=http://plugin.01net.com/tech/quand-un-mur-de-lampes-a-lave-sert-a-securiser-internet-a-san-francisco-1298138.html|consulté le=2018-01-06}}.</ref>{{,}}<ref>{{lien web|langue=en|auteur1=Joshua Liebow-Feeser|titre=LavaRand in Production: The Nitty-Gritty Technical Details|périodique=Cloudflare Blog|date=2017-11-06|lire en ligne=https://blog.cloudflare.com/lavarand-in-production-the-nitty-gritty-technical-details/|consulté le=2018-01-06}}.</ref>.
 
== Notes et références ==
{{Références}}

== Annexes ==
=== Bibliographie ===
{{sources à lier|date = 8 janvier 2016}}
* {{article|langue=en|auteur1=[[Lenore Blum]]|auteur2=[[Manuel Blum]]|auteur3=[[Michael Shub]]|titre=A Simple Unpredictable Pseudo-Random Number Generator|périodique=[[SIAM Journal on Computing]]|volume=15|numéro=2|pages=364–383|date=mai 1986|doi=10.1137/0215025}}.
* Pascal Junod, "Cryptographic Secure Pseudo-Random Bits Generation: The Blum-Blum-Shub Generator", août 1999. [http://crypto.junod.info/bbs.pdf PDF de 21 pages]
* Martin Geisler, Mikkel Krøigård, et Andreas Danielsen. "About Random Bits", décembre 2004. Disponible en [http://daimi.au.dk/~mg/mamian/random-bits.pdf PDF] et [http://daimi.au.dk/~mg/mamian/random-bits.ps.gz Gzipped Postscript].
* [[Umesh 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)
* [[Alfred Menezes]], Paul C. van Oorschot et [[Scott Vanstone]], "Handbook of Applied Cryptography", 5<sup>ième</sup> édition (août 2001), chapitre 5.5.2. [https://cacr.uwaterloo.ca/hac/about/chap5.pdf PDF du chapitre 5]

=== Liens externes ===
* {{lien archive|url=http://moanlisa.org/gmpbbs/|titre=GMPBBS|horodatage archive=20150217133034}} - une implémentation [[GNU]] de l'algorithme Blum Blum Shub.

{{Palette|Générateur de nombres pseudo-aléatoires}}{{Portail|cryptologie}}

[[Catégorie:Nombre aléatoire]]