Criptografia

Algoritmo Blum Blum Shub

Criptografía

2011

Creado a mediados de la década de 1980 por Lenore Blum, Manuel Blum y Michael Shub, es un
algoritmo basado en congruencias lineales cuadráticasque 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. La ecuación encongruencias se establece como
������������ = (������������−1 )2 mod ������������

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

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

•

•

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

se toma el bit menos significativo de ������������ .
se toma el bit más significativo de ������������ ; en este caso es necesario considerarcuantos bits
representan al número más grande de la secuencia.
se toma el bit de paridad de ������������ .

•
•
•

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

2������ mod(������−1)(������−1)

1

Ing. Aldo Jiménez Arteaga

mod ������������...