Blum Blum Shub ( BBS ) es un generador de números pseudoaleatorios propuesto en 1986 por Lenore Blum , Manuel Blum y Michael Shub [1] que se deriva de la función unidireccional de Michael O. Rabin .
Blum Blum Shub toma la forma
donde M = pq es el producto de dos números primos grandes p y q . En cada paso del algoritmo, se deriva alguna salida 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 0 debe ser un número entero coprimo de M (es decir, p y q no son factores de x 0 ) y no 1 o 0.
Los dos 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 x i directamente (mediante el teorema de Euler ):
¿Dónde está la función Carmichael ? (Aquí tenemos ).
Existe una prueba que reduce su seguridad a la dificultad computacional del factoring. [1] Cuando los números primos se eligen apropiadamente 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 resolviendo el problema de residualidad cuadrática módulo M.
El rendimiento del generador de números aleatorios BBS depende del tamaño del módulo M y del número de bits por iteración j . Si bien reducir M o aumentar j hace que el algoritmo sea más rápido, hacerlo también reduce la seguridad. Un artículo de 2005 proporciona una prueba de seguridad concreta, a diferencia de asintótica, de BBS, para M y j dados . El resultado también se puede utilizar para guiar la elección de los dos números equilibrando la seguridad esperada con el costo computacional. [2]
Sea , y (dónde está la semilla). Podemos esperar obtener una duración de ciclo grande para esos números pequeños, porque . El generador comienza a evaluar usando y crea la secuencia , , , = 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 es una implementación de Python que verifica la primalidad.
importar sympy def blum_blum_shub ( p1 , p2 , semilla , iteraciones ): afirmar p1 % 4 == 3 afirmar p2 % 4 == 3 afirmar sympy . isprime ( p1 // 2 ) afirmar sympy . isprime ( p2 // 2 ) n = p1 * p2 numeros = [] para _ en rango ( iteraciones ): semilla = ( semilla ** 2 ) % n si semilla en numeros : print ( f "El RNG ha caido en un bucle en { len ( números ) } pasos" ) devuelve números números . agregar ( semilla ) números de retorno imprimir ( blum_blum_shub ( 11 , 23 , 3 , 100 ))La siguiente implementación de Common Lisp proporciona una demostración sencilla del generador, en particular en lo que respecta 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 (semilla) no se verifican.
( defun get-number-of-1-bits ( bits ) "Devuelve el número de bits con valor 1 en los BITS codificados con enteros." ( declara ( escribe ( entero 0 * ) bits )) ( el ( entero 0 * ) ( bits de recuento de registros ))) ( defun get-even-parity-bit ( bits ) "Devuelve el bit de paridad par de los BITS codificados con enteros." ( declara ( escribe ( entero 0 * ) bits )) ( el bit ( mod ( get-number-of- bits de 1 bits ) 2 ))) ( defun get-least-significant-bit ( bits ) "Devuelve el bit menos significativo de los BITS codificados con enteros." ( declara ( escribe ( entero 0 * ) bits )) ( el bit ( ldb ( byte 1 0 ) bits ) )) ( defun make-blum-blum-shub ( &key ( p 11 ) ( q 23 ) ( s 3 )) "Devuelve una función sin argumentos que representa un generador de números pseudoaleatorios simple de Blum-Blum-Shub, configurado para usar los parámetros del generador P, Q y S (semilla) y devuelve tres valores: (1) el número x[n+1], (2) el bit de paridad par del número, (3) el bit menos significativo del número . -- Tenga en cuenta que los parámetros P, Q y S no se verifican de acuerdo con las condiciones descritas en el artículo." ( declare ( type ( integer 0 * ) p q s )) ( let (( M ( * p q )) ;; M = p * q ( x[n] s )) ;; x0 = semilla ( declarar ( tipo ( entero 0 * ) M x[n] )) #' ( lambda () ;; x[n+ 1] = x[n]^2 mod M ( let (( x[n+1] ( mod ( * x[n] x[n] ) M ))) ( declarar ( tipo ( entero 0 * ) x[n +1] )) ;; Calcule los bits aleatorios en función de x[n+1]. ( let (( bit de paridad par ( obtener bit de paridad par x[n+1] )) ( mínimo -bit-significativo ( obtener-bit-menos-significativo x[n+1] ))) ( declarar ( escribir bit bit -paridad-par )) ( declarar ( escribir bit bit -menos-significativo )) ;; Actualice el estado de modo que x[n+1] se convierta en el nuevo x[n]. ( setf x[n] x[n+1] ) ( valores x[n+1] bit de paridad par bit menos significativo )))))) ;; Imprima los resultados ejemplares. ( let (( bbs ( make-blum-blum-shub :p 11 :q 23 :s 3 ))) ( declarar ( tipo ( función () ( valores ( entero 0 * ) bit bit )) bbs )) ( formato T "~&Claves: E = paridad par, L = menos significativo" ) ( formato T "~2%" ) ( formato T "~&x[n+1] | E | L" ) ( formato T "~&--- -----------" ) ( repetición de bucle 6 hacer ( enlace de valor múltiple ( x [n + 1] bit de paridad par bit menos significativo ) ( funcall bbs ) ( declarar ( tipo ( entero 0 * ) x[n+1] )) ( declarar ( escriba bit de paridad par )) ( declarar ( escriba bit menos significativo )) ( formato T "~&~6d | ~d | ~ d" x[n+1] bit de paridad par bit menos significativo ))))