Blum Blum Shub
Source: Wikipédia sous licence CC-BY-SA 3.0.
La liste des auteurs de cet article est disponible ici.

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 ( En arithmétique modulaire, on parle de nombres congrus modulo n Le terme modulo peut aussi être associé à d'autres formes de congruence En informatique, le modulo...) 4 (cela garantit que chaque résidu quadratique possède une racine carrée (La racine carrée d’un nombre réel positif x est le nombre positif dont le carré vaut x. On le note ou x½; dans cette...) 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).

Sécurité de l'algorithme

Le générateur n'est pas approprié aux simulations, mais plutôt à la cryptographie (La cryptographie est une des disciplines de la cryptologie s'attachant à protéger des messages (assurant confidentialité, authenticité et intégrité) en s'aidant souvent de secrets ou clés.), 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(log(M~)) bits de poids (Le poids est la force de pesanteur, d'origine gravitationnelle et inertielle, exercée par la Terre sur un corps massique en raison uniquement du voisinage de la Terre. Elle est...) 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.

Page générée en 0.270 seconde(s) - site hébergé chez Amen
Ce site fait l'objet d'une déclaration à la CNIL sous le numéro de dossier 1037632
Ce site est édité par Techno-Science.net - A propos - Informations légales
Partenaire: HD-Numérique