Blum Blum Shub

Blum Blum Shub (BBS) es un algoritmo capaz de producir números pseudoaleatorios . Fue propuesto en 1986 por Lenore Blum , Manuel Blum y Michael Shub , de ahí su nombre.

Definición

Calculamos la salida de BBS iterando lo siguiente: $x _ {{n + 1}} = (x_ {n}) ^ {2} \! \ mod M$ donde "mod" es el operador restante al dividir por , el producto de dos números primos grandes y . La salida del algoritmo es el bit menos significativo o los últimos bits de . $M = p \, q$ $pag$ $q$ $x _ {{n + 1}}$

Los dos números primos, y , deben ser congruentes con 3 módulo 4 (esto asegura que cada residuo cuadrático tenga una raíz cuadrada que también es un residuo cuadrático) y el MCD de y debe ser pequeño (para que el ciclo sea largo). $pag$ $q$ $\ varphi$ ${\ Displaystyle (p-1)}$ $\ varphi$ $(q-1)$

La semilla es aleatoria y debe ser principal entre sí (es decir, y no debe ser un factor de ), y no debe ser 0 o 1. $x _ {{0}}$ $METRO$ $pag$ $q$ $x _ {{0}}$ $x _ {{0}}$

Seguridad del algoritmo

El generador no es apto para simulaciones, sino más bien para criptografía , ya que es bastante lento.

Sin embargo, tiene una seguridad inusual, ya que se demostró por primera vez que era criptográficamente seguro bajo el supuesto de que es difícil determinar si, módulo un entero compuesto, un número es un cuadrado o no ( problema del residuo cuadrático ). Posteriormente, se demostró que era criptográficamente seguro, bajo el supuesto de que el problema de la factorización es difícil y que al menos los bits significativos de cada uno se generan en cada iteración. En este caso, no es posible diferenciar la secuencia producida de una secuencia verdaderamente aleatoria. $\ log (\ log (M))$ $x_ {n}$

Generador

Lavarand (en) es un dispositivo que utiliza lámparas de lava para obtener la semilla de un algoritmo BBS, y así generar números pseudoaleatorios muy seguros e incluso números verdaderamente aleatorios.

Notas y referencias

Blum, Blum y Shub 1986 .
(en) Landon Curt Noll (en) , Robert G. Mende y Sanjeev Sisodiya para Silicon Graphics, Inc. , Patente de EE . UU. 5.732.138: Método para sembrar un generador de números pseudoaleatorios con un hash criptográfico de una digitalización de un sistema caótico , presentada el 29 de enero de 1996, publicada el 24 de marzo de 1998, en Google Patents.
Audrey Oeillet, " Cuando una pared de lámparas de lava sirve para asegurar Internet en San Francisco " , PLUGIN ( 01net ) ,8 de noviembre de 2017(consultado el 6 de enero de 2018 ) .
(en) Joshua Liebow-Feeser, " LavaRand en producción: Detalles técnicos esenciales " , Blog de Cloudflare ,6 de noviembre de 2017(consultado el 6 de enero de 2018 ) .

Apéndices

Bibliografía

(en) Lenore Blum , Manuel Blum y Michael Shub , “ Un generador de números pseudoaleatorios simple e impredecible ” , SIAM Journal on Computing , vol. 15, n o 2Mayo de 1986, p. 364-383 ( DOI 10.1137 / 0215025 ).
Pascal Junod, "Cryptographic Secure Pseudo-Random Bits Generation: The Blum-Blum-Shub Generator", agosto de 1999. PDF de 21 páginas
Martin Geisler, Mikkel Krøigård y Andreas Danielsen. "Acerca de los bits aleatorios", diciembre de 2004. Disponible en PDF y PostScript comprimido con Gzip .
Umesh Vazirani , Vijay V. Vazirani . "Generación de números pseudoaleatorios eficiente y segura", Crypto'84 , Lecture Notes in Computer Science Volume 196, p. 193-202, Springer-Verlag (1985)

enlaces externos

"GMPBBS" ( Archivo de Internet versión 17 de febrero de 2015 ) : una implementación GNU del algoritmo Blum Blum Shub.