Blum Blum Shub - Blum Blum Shub

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

Blum Blum Shub toma la forma

${\ Displaystyle x_ {n + 1} = x_ {n} ^ {2} {\ bmod {M}}}$,

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 ₀ debe ser un número entero que es co-prime a M (es decir, p y q no son factores de x ₀ ) 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 ):

${\ Displaystyle x_ {i} = \ left (x_ {0} ^ {2 ^ {i} {\ bmod {\ lambda}} (M)} \ right) {\ bmod {M}}}$,

donde está la función de Carmichael . (Aquí tenemos ). ${\ Displaystyle \ lambda}$${\ Displaystyle \ lambda (M) = \ lambda (p \ cdot q) = \ operatorname {lcm} (p-1, q-1)}$

Seguridad

Hay una prueba que reduce su seguridad a la dificultad computacional de factorizar. 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 resolver la cuadrática residuosity problema módulo M .

Ejemplo

Deja , y (donde está 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 tabla siguiente muestra la salida (en bits) para los diferentes métodos de selección de bits utilizados para determinar la salida. ${\ Displaystyle p = 11}$${\ Displaystyle q = 23}$${\ Displaystyle s = 3}$${\ Displaystyle s}$${\ Displaystyle {\ rm {gcd}} ((p-3) / 2, (q-3) / 2) = 2}$${\ Displaystyle x_ {0}}$${\ Displaystyle x _ {- 1} = s}$${\ Displaystyle x_ {0}}$${\ Displaystyle x_ {1}}$${\ Displaystyle x_ {2}}$${\ Displaystyle \ ldots}$ ${\ Displaystyle x_ {5}}$

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)
  "Returns the number of 1-valued bits in the integer-encoded BITS."
  (declare (type (integer 0 *) bits))
  (the (integer 0 *) (logcount bits)))

(defun get-even-parity-bit (bits)
  "Returns the even parity bit of the integer-encoded BITS."
  (declare (type (integer 0 *) bits))
  (the bit (mod (get-number-of-1-bits bits) 2)))

(defun get-least-significant-bit (bits)
  "Returns the least significant bit of the integer-encoded BITS."
  (declare (type (integer 0 *) bits))
  (the bit (ldb (byte 1 0) bits)))

(defun make-blum-blum-shub (&key (p 11) (q 23) (s 3))
  "Returns a function of no arguments which represents a simple
   Blum-Blum-Shub pseudorandom number generator, configured to use the
   generator parameters P, Q, and S (seed), and returning three values:
   (1) the number x[n+1],
   (2) the even parity bit of the number,
   (3) the least significant bit of the number.
   ---
   Please note that the parameters P, Q, and S are not checked in
   accordance to the conditions described in the article."
  (declare (type (integer 0 *) p q s))
  (let ((M    (* p q))       ;; M  = p * q
        (x[n] s))            ;; x0 = seed
    (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]))
          ;; Compute the random bit(s) based on x[n+1].
          (let ((even-parity-bit       (get-even-parity-bit       x[n+1]))
                (least-significant-bit (get-least-significant-bit x[n+1])))
            (declare (type bit even-parity-bit))
            (declare (type bit least-significant-bit))
            ;; Update the state such that x[n+1] becomes the new x[n].
            (setf x[n] x[n+1])
            (values x[n+1]
                    even-parity-bit
                    least-significant-bit))))))

;; Print the exemplary outputs.
(let ((bbs (make-blum-blum-shub :p 11 :q 23 :s 3)))
  (declare (type (function () (values (integer 0 *) bit bit)) bbs))
  (format T "~&Keys: E = even parity, L = least significant")
  (format T "~2%")
  (format T "~&x[n+1] | E | L")
  (format T "~&--------------")
  (loop repeat 6 do
    (multiple-value-bind (x[n+1] even-parity-bit least-significant-bit)
        (funcall bbs)
      (declare (type (integer 0 *) x[n+1]))
      (declare (type bit           even-parity-bit))
      (declare (type bit           least-significant-bit))
      (format T "~&~6d | ~d | ~d"
                x[n+1] even-parity-bit least-significant-bit))))

Referencias

Citas

Fuentes

enlaces externos

• GMPBBS, una implementación de lenguaje C de Mark Rossmiller
• BlumBlumShub, una implementación en lenguaje Java de Mark Rossmiller
• Una implementación en Java
• Pruebas de aleatoriedad