Blum Blum Shub
# Blum Blum Shub

Blum Blum Shub (BBS) es un generador pseudoaleatorio de números propuesto por Lenore Blum, Manuel Blum y Michael Shub en 1986.

El algoritmo BBS es:

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

donde M=pq es el producto de dos números primos muy grandes p y q. En cada paso del algoritmo, se obtiene un resultado para $x_n;$ el resultado es por lo general o bien el bit de paridad de $x_n$ ó uno o más de los bits menos significativos de $x_n.$

Los dos números primos, p y q, deben ser ambos congruentes a 3 (mod 4) (esto asegura que cada residuo cuadrático posee una raíz cuadrada que también es un residuo cuadrático) y mcd(φ(p-1), φ(q-1)) debe ser pequeña (esto hace que la longitud del ciclo sea extensa).

Una característica interesante del generador BBS es la posibilidad de calcular todo valor $x_i$ en forma directa:

    $x_{i}=\left(x_{0}^{2^{i}{\bmod {}p-1)(q-1)}\right){\bmod {M}}.$

## Seguridad

El generador es apropiado para ser utilizado en criptografía, aunque no en simulaciones, ya que no es muy rápido. Sin embargo, es muy resistente desde el punto de vista de su seguridad, lo que se relaciona con la calidad del generador en cuanto a la complejidad computacional de la factorización de enteros. Cuando se eligen los primos en forma adecuada, y los bits menos significativos O(log log M) de cada $x_n$ se eligen como resultado, entonces en el límite cuando M se hace muy grande, distinguir los bits resultado de una secuencia aleatoria será por lo menos tan difícil como factorizar M.

Si la factorización de enteros es difícil (como es de esperar) entonces BBS con grandes M tendrán un resultado libre de todo patrón no aleatorio que puede ser descubierto mediante una cantidad razonable de cálculos. Esto hace que el método sea tan seguro como otras tecnologías de cifrado asociadas al problema de factorización, como por ejemplo el cifrado RSA.

## Ejemplo

Sea p=11, q=19 y s=3. Podemos esperar obtener un ciclo largo para estos números pequeños, porque mcd(φ(p-1), φ(q-1))=2. El generador comienza a evaluar $x_0$ utilizando x $_{-1}=s$ y crea la sucesión $x_0,$ $x_1,$ $x_2,...$ $x_5=$ 9, 81, 82, 36, 42, 92. Si se utiliza el bit de paridad para definir el resultado, entonces los bits resultados son 1 1 0 0 0 0.

