Blub Blub Shub

Criptografía – Generadores de Números Pseudoaleatorios

Blum Blum Shub

Creado a mediados de la década de 1980 por Lenore Blum, Manuel Blum y Michael Shub, es
un algoritmo basado en congruenciascuadráticas que permite generar una secuencia de
números pseudoaleatorios.
El algoritmo es recursivo; es decir, se utiliza el resultado de una iteración para calcular el
siguiente número. Laecuación en congruencias se establece como
𝑋 𝑖 = (𝑋 𝑖−1 )2 mod 𝑝𝑞

Las consideraciones para generar una secuencia óptima y larga son:




𝑝 y 𝑞 son dos números primos muy grandes, tales que 𝑝 = 3mod 4 y 𝑞 = 3 mod 4;
esto permite asegurar que cada residuo posee una raíz cuadrada. Además el máximo
común divisor entre 𝜑(𝑝) = 𝑝 − 1 y 𝜑(𝑞) = 𝑞 − 1 debe ser mínimo.
la semilla 𝑋0 debe ser primorelativo con el producto 𝑝𝑞.

El algoritmo se utiliza para generar una secuencia binaria pseudoaleatoria, tomando como
criterios para la elección de los bits los siguientes puntos:




setoma el bit menos significativo de 𝑋 𝑖 .
se toma el bit más significativo de 𝑋 𝑖 ; en este caso es necesario considerar cuántos bits
representan al número más grande de la secuencia.
se toma el bitde paridad de 𝑋 𝑖 .

Este generador es muy eficaz, puesto que cuando se eligen adecuadamente los parámetros
de generación la secuencia pseudoaleatoria tendrá período grande, será imprevisible yprobabilísticamente uniforme. La gran desventaja es el alto costo computacional que plantea,
puesto que existen productos y potencias cuadradas de números muy grandes.
Un aspecto interesante es quecada elemento de una secuencia BBS se puede calcular con
base en la semilla y los números 𝑝 y 𝑞 sin necesidad de depender directamente del elemento
anterior:
𝑋 𝑖 = 𝑋0

2 𝑖 mod(𝑝−1)(𝑞−1)

1Ing. Aldo Jiménez Arteaga

mod 𝑝𝑞

2014

EJEMPLO. Si son considerados 𝑝 = 199, 𝑞 = 151 y 𝑋0 = 317 las restricciones para

obtener una secuencia óptima son satisfechas. Se tomará el bit menos...