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 grandes números primos p y q . En cada paso del algoritmo, parte de la salida se deriva de x n +1 ; la salida es comúnmente 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 que es co-prime a M (es decir, p y q no son factores de x 0 ) y no 1 o 0.
Los dos números primos, p y q , deben ser tanto congruente a 3 (mod 4) (Esto garantiza que cada residuo cuadrático tiene una raíz cuadrada , que es también un residuo cuadrático), y deben ser números primos seguras con un pequeño gcd (( 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 (a través del teorema de Euler ):
- ,
dónde es la función de Carmichael . (Aquí tenemos).
Seguridad
Hay una prueba que reduce su seguridad a la dificultad computacional de factorizar. [1] Cuando los 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 la solución del cuadrática problema residuosity módulo M .
Ejemplo
Dejar , y (dónde es la semilla). Podemos esperar obtener una gran duración de ciclo para esos números pequeños, porque. El generador comienza a evaluar mediante el uso 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.
Bit de paridad | Poco menos significativo |
---|---|
0 1 1 0 1 0 | 1 1 0 0 1 0 |
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 tener en cuenta que los requisitos impuestos a los parámetros p , q y s (de semillas) no se comprueban.
( defun get-number-of-1-bits ( bits ) "Devuelve el número de bits de valor 1 en los BITS codificados como enteros". ( declare ( type ( integer 0 * ) bits )) ( the ( integer 0 * ) ( bits de recuento de registros )))( defun get-even-parity-bit ( bits ) "Devuelve el bit de paridad par de los BITS codificados como enteros." ( declare ( type ( integer 0 * ) bits )) ( the bit ( mod ( get-number-of- Bits de 1 bits ) 2 )))( defun obtener-bit-menos-significativo ( bits ) "Devuelve el bit menos significativo de los BITS codificados con números enteros." ( declare ( tipo ( 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 simple generador de números pseudoaleatorios Blum-Blum-Shub, configurado para usar los parámetros del generador P, Q y S (semilla), y devuelve tres valores: (1) el bit de paridad par del número, (2) el bit menos significativo del número, (3) el número x [n + 1]. - - Tenga en cuenta que los parámetros P, Q y S no se comprueban 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 ( declare ( type ( integer 0 * ) M x [n] )) # ' ( lambda () ;; x [n + 1] = x [n] ^ 2 mod M ( let (( x [n + 1] ( mod ( * x [n] x [n] ) M ))) ( declare ( type ( integer 0 * ) x [n +1] )) ;; Calcule los bits aleatorios basándose en x [n + 1]. ( Let (( paridad-par-bit ( obtener-bit-paridad-par x [n + 1] )) ( mínimo -bit-significativo ( obtener -bit -menos-significativo- x [n + 1] ))) ( declare ( escriba bit paridad-par-bit )) ( declare ( escriba bit menos signo bit 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 las salidas ejemplares. ( let (( bbs ( make-blum-blum-shub : p 11 : q 23 : s 3 ))) ( declare ( type ( function () ( values ( integer 0 * ) bit bit )) bbs )) ( formato T "~ & Teclas: E = paridad par, L = menos significativa" ) ( formato T "~ 2%" ) ( formato T "~ & x [n + 1] | E | L" ) ( formato T "~ & --- ----------- " ) ( repetición de bucle 6 do ( enlace-valor-múltiple ( x [n + 1] bit-paridad-par-bit menos significativo ) ( funcall bbs ) ( declare ( tipo ( entero 0 * ) x [n + 1] )) ( declare ( escriba bit paridad-par bit )) ( declare ( escriba bit bit menos significativo )) ( formato T "~ & ~ 6d | ~ d | ~ d " x [n + 1] bit de paridad par bit menos significativo ))))
Referencias
- ^ a b Blum, Lenore; Blum, Manuel; Shub, Mike (1 de mayo de 1986). "Un simple generador de números pseudoaleatorios impredecibles". Revista SIAM de Computación . 15 (2): 364–383. doi : 10.1137 / 0215025 .
- General
- Blum, Lenore; Blum, Manuel; Shub, Mike (1982). "Comparación de dos generadores de números pseudoaleatorios" . Avances en criptología: Actas de CRYPTO '82. Pleno: 61–78. Cite journal requiere
|journal=
( ayuda ) - Geisler, Martin; Krøigård, Mikkel; Danielsen, Andreas (diciembre de 2004). "Acerca de los bits aleatorios". CiteSeerX 10.1.1.90.3779 . Cite journal requiere
|journal=
( ayuda )disponible como PDF y PostScript comprimido con gzip