Blum Blum Shub

On calcule la sortie de BBS en itérant la suite : ${\displaystyle x_{n+1}=(x_{n})^{2}\!\mod M}$ où "mod" est l'opérateur reste (modulo) lors de la division euclidienne par ${\displaystyle M=p\,q}$, le produit de deux grands nombres premiers ${\displaystyle p}$ et ${\displaystyle q}$. La sortie de l'algorithme est le bit le moins significatif ou les derniers bits de ${\displaystyle x_{n+1}}$.

Les deux nombres premiers, ${\displaystyle p}$ et ${\displaystyle q}$, 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 ${\displaystyle \varphi }$${\displaystyle (p-1)}$ et ${\displaystyle \varphi }$${\displaystyle (q-1)}$ doit être petit (ce qui fait que le cycle est long).

La graine aléatoire ${\displaystyle x_{0}}$ et ${\displaystyle M}$ doivent être premiers entre eux (c'est-à-dire que ${\displaystyle p}$ et ${\displaystyle q}$ ne doivent pas être des facteurs de ${\displaystyle x_{0}}$), et ${\displaystyle x_{0}}$ ne doit pas être 0 ou 1.

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 ${\displaystyle \log(\log(M))}$ bits de poids faible de chaque ${\displaystyle 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.