Blum Blum Shub

Blum Blum Shub (B.B.S.) es un generador de números pseudoaleatorios propuesto en 1986 por Lenore Blum, Manuel Blum y Michael Shub que se deriva de Michael O. Rabin's función unidireccional.

Blum Blum Shub toma la forma

xn+1=xn2modM{displaystyle x_{n+1}=x_{n}{2}{2}{bmod {M}},

donde M = pq es el producto de dos números primos grandes p y q. En cada paso del algoritmo, parte de la salida se deriva de x_n+1; la salida suele ser la paridad de bits de x_n+1 o uno o más de los bits menos significativos de x_n+1.

La semilla x₀ debe ser un número entero coprimo de M (es decir, p y q no son factores de x₀) y tampoco 1 o 0.

Los dos números primos, p y q, deben ser congruentes con 3 (mod 4) (esto garantiza que cada residuo cuadrático tenga una raíz cuadrada que también es un residuo cuadrático), y deben ser primos seguros con un mcd pequeño ((p-3)/2, (q-3)</2) (esto hace que la duración del ciclo sea grande).

Una característica interesante del generador Blum Blum Shub es la posibilidad de calcular cualquier valor de x_i directamente (a través de Euler's). teorema):

xi=()x02imodλ λ ()M))modM{displaystyle x_{i}=left(x_{0}{2^{i}{bmod {lambda }} {m)}right){bmod {M}}}}},

Donde λ λ {displaystyle lambda } es la función Carmichael. (Aquí tenemos) λ λ ()M)=λ λ ()p⋅ ⋅ q)=lcm⁡ ⁡ ()p− − 1,q− − 1){displaystyle lambda (M)=lambda (pcdot q)=operatorname {lcm} (p-1,q-1)}).

Seguridad

Existe una demostración que reduce su seguridad a la dificultad computacional de la factorización. Cuando los números primos se eligen correctamente y se emiten O(log log M) bits de orden inferior de cada x_n, entonces en el límite a medida que M crece, distinguir los bits de salida de los aleatorios debería ser al menos tan difícil como resolver el problema de residuosidad cuadrática módulo M.

Ejemplo

Vamos p=11{displaystyle p=11}, q=23{displaystyle q=23} y s=3{displaystyle s=3} (donde) s{displaystyle s} es la semilla). Podemos esperar conseguir un largo ciclo para esos números pequeños, porque gcd()()p− − 3)/2,()q− − 3)/2)=2{displaystyle {rm {gcd}(p-3)/2,(q-3)/2)=2}. El generador comienza a evaluar x0{displaystyle x_{0} utilizando x− − 1=s{displaystyle x_{-1}=s} y crea la secuencia x0{displaystyle x_{0}, x1{displaystyle x_{1}}, x2{displaystyle x_{2}, ...... {displaystyle ldots } x5{displaystyle x_{5} = 9, 81, 236, 36, 31, 202. La siguiente tabla muestra la salida (en bits) para los diferentes métodos de selección de bits utilizados para determinar la salida.

La siguiente implementación de Common Lisp proporciona una demostración simple del generador, en particular con respecto a los métodos de selección de tres bits. Es importante señalar que los requisitos impuestos a los parámetros p, q y s (seed) no se comprueban.

()defun get-number-of-1-bits ()bits) "Retorna el número de bits de 1 valor en los BITS codificados por enteros." ()Declara ()Tipo ()entero 0 *) bits) ()el ()entero 0 *) ()Cuenta de registro bits))()defun get-even-parity-bit ()bits) "Retorna el pedazo de paridad de los TBIs codificados por enteros." ()Declara ()Tipo ()entero 0 *) bits) ()el bit ()mod ()get-number-of-1-bits bits) 2))()defun get-least-significant-bit ()bits) "Retorna el pedazo menos significativo de los TBI codificados por enteros." ()Declara ()Tipo ()entero 0 *) bits) ()el bit ()ldb ()byte 1 0) bits))()defun make-blum-blum-shub ()> ()p 11) ()q 23) ()s 3) "Retorna una función de ningún argumento que represente un simple Generador de número de pseudopremio Blum-Blum-Shub, configurado para utilizar el parámetros del generador P, Q y S (semilla) y devolviendo tres valores: (1) el número x[n+1], (2) el bit parity del número, (3) la parte menos significativa del número. -... Tenga en cuenta que los parámetros P, Q y S no se registran según las condiciones descritas en el artículo." ()Declara ()Tipo ()entero 0 *) p q s) ()Deja ()M ()* p q) ; M = p * q ()x[n] s) ; x0 = semilla ()Declara ()Tipo ()entero 0 *) M x[n]) # '()lambda () ; x[n+1] = x[n]^2 mod M ()Deja ()x[n+1] ()mod ()* x[n] x[n]) M)) ()Declara ()Tipo ()entero 0 *) x[n+1]) ;; Computar el bit(s) aleatorio basado en x[n+1]. ()Deja ()incluso-paridad-bit ()get-even-parity-bit x[n+1]) ()menos significativo-bit ()get-least-significant-bit x[n+1])) ()Declara ()Tipo bit incluso-paridad-bit) ()Declara ()Tipo bit menos significativo-bit) ; Actualizar el estado tal que x[n+1] se convierte en el nuevo x[n]. ()setf x[n] x[n+1]) ()valores x[n+1] incluso-paridad-bit menos significativo-bit))))); Imprimir los resultados ejemplares.()Deja ()bbs ()make-blum-blum-shub :p 11 :q 23 : 3)) ()Declara ()Tipo ()función () ()valores ()entero 0 *) bit bit) bbs) ()formato T E = paridad, L = menos significativa) ()formato T "~2%") ()formato T "~ limitadax[n+1] Silencio E Silencio L") ()formato T "...) ()bucle repetición 6 do ()multivalor-bind ()x[n+1] incluso-paridad-bit menos significativo-bit) ()funcall bbs) ()Declara ()Tipo ()entero 0 *) x[n+1]) ()Declara ()Tipo bit incluso-paridad-bit) ()Declara ()Tipo bit menos significativo-bit) ()formato T "## ############################################################################################################################################################################################################################################################# x[n+1] incluso-paridad-bit menos significativo-bit)))