Blum Blum Shub

Blum Blum Shub (BBS) é um algoritmo capaz de produzir números pseudo-aleatórios . Foi proposto em 1986 por Lenore Blum , Manuel Blum e Michael Shub , daí o seu nome.

Definição

Calculamos a saída do BBS iterando o seguinte: $x _ {{n + 1}} = (x_ {n}) ^ {2} \! \ mod M$ onde "mod" é o operador de resto ao dividir por , o produto de dois grandes números primos e . A saída do algoritmo é o bit menos significativo ou os últimos bits de . $M = p \, q$ $p$ $q$ $x _ {{n + 1}}$

Os dois números primos, e , devem ser congruentes a 3 módulo 4 (isso garante que cada resíduo quadrático tenha uma raiz quadrada que também é um resíduo quadrático) e o GCD de e deve ser pequeno (de modo que o ciclo seja longo). $p$ $q$ $\ varphi$ ${\ displaystyle (p-1)}$ $\ varphi$ $(q-1)$

A semente é aleatória e deve ser primo entre si (isto é, e não deve ser fatores de ) e não deve ser 0 ou 1. $x _ {{0}}$ $M$ $p$ $q$ $x _ {{0}}$ $x _ {{0}}$

Segurança de algoritmo

O gerador não é adequado para simulações, mas sim para criptografia , pois é bastante lento.

No entanto, ele tem uma segurança incomum, uma vez que primeiro se mostrou criptograficamente seguro sob a suposição de que é difícil determinar se, módulo um inteiro composto, um número é um quadrado ou não ( problema do resíduo quadrático ). Subseqüentemente, ele provou ser criptograficamente seguro, sob a suposição de que o problema de fatoração é difícil e que pelo menos bits significativos de cada são produzidos em cada iteração. Nesse caso, não é possível diferenciar a sequência produzida de uma sequência verdadeiramente aleatória. $\ log (\ log (M))$ $x_ {n}$

Gerador

Lavarand (en) é um dispositivo que usa lâmpadas de lava para obter a semente de um algoritmo BBS e, assim, gerar números pseudoaleatórios muito seguros e até mesmo números verdadeiramente aleatórios.

Notas e referências

Blum, Blum e Shub 1986 .
(em) Landon Curt Noll (em) , Robert G. Mende e Sanjeev Sisodiya para Silicon Graphics, Inc. , Patente dos EUA 5.732.138: Método para semear um gerador de número pseudo-aleatório com um hash criptográfico de uma digitalização de um sistema caótico , depositado em 29 de janeiro de 1996, publicado em 24 de março de 1998, nas patentes do Google.
Audrey Oeillet, " Quando uma parede de lâmpadas de lava serve para proteger a Internet em São Francisco " , PLUGIN ( 01net ) ,8 de novembro de 2017(acessado em 6 de janeiro de 2018 ) .
(in) Joshua Liebow-Feeser, " LavaRand in Production: The Nitty Gritty-Technical Details " , Cloudflare Blog ,6 de novembro de 2017(acessado em 6 de janeiro de 2018 ) .

Apêndices

Bibliografia

(pt) Lenore Blum , Manuel Blum e Michael Shub , “ A Simple Unpredictable Pseudo-Random Number Generator ” , SIAM Journal on Computing , vol. 15, n o 2Maio 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 e Andreas Danielsen. "About Random Bits", dezembro de 2004. Disponível em PDF e Gzipped Postscript .
Umesh Vazirani , Vijay V. Vazirani . "Efficient and Secure Pseudo-Random Number Generation", Crypto'84 , Lecture Notes in Computer Science Volume 196, p. 193--202, Springer-Verlag (1985)

links externos

"GMPBBS" ( Internet Archive versão 17 de fevereiro de 2015 ) - uma implementação GNU do algoritmo Blum Blum Shub.