Gerador Blum-Blum-Shub e sua aplicação

Introdução

Atualmente, os números aleatórios são usados ​​em vários campos da ciência. Por exemplo, para simular vários processos reais, muitas vezes é necessário levar em consideração não apenas o comportamento da quantidade investigada, mas também a influência de vários fenômenos imprevisíveis. Além disso, alguns métodos de análise de dados experimentais também usam números aleatórios. Na teoria dos jogos, o acaso também desempenha um grande papel. E, claro, em criptografia. Muitos algoritmos de criptografia ou assinatura eletrônica usam números aleatórios.





Mas como você consegue um número aleatório? Na natureza, existem muitos fenômenos aleatórios diferentes, com base nos quais os geradores foram inventados. Os geradores de números aleatórios de hardware podem ser baseados em processos aleatórios macroscópicos usando itens como moedas, dados ou roda de roleta. Mas esses geradores são muito lentos e não adequados para resolver problemas. Para obter números aleatórios mais rapidamente, fenômenos físicos de natureza quântica, como ruído em circuitos elétricos, podem ser usados. Mas a principal desvantagem dos geradores de números aleatórios de hardware é sua falta de confiabilidade associada a defeitos frequentes. Para evitar a falta de confiabilidade, eles começaram a usar tabelas pré-obtidas de números aleatórios. No entanto, eles também tinham uma grande desvantagem - eles ocupavam muita memória.





Como nem o método de hardware nem as tabelas de números aleatórios satisfaziam a necessidade de obtenção rápida e confiável de números aleatórios, os cientistas começaram a procurar métodos algorítmicos para obter números aleatórios. É óbvio que a sequência obtida por meio de tais métodos não é mais aleatória, pois é totalmente determinada por uma determinada fórmula e dados iniciais. Mas se o valor inicial for mantido em segredo e o algoritmo for resistente (um algoritmo é considerado resistente se um ataque bem-sucedido exigir que o invasor tenha uma quantidade inatingível de recursos de computação), então os resultados que o gerador produz serão imprevisíveis. Esse algoritmo para obter uma sequência de números, cujas propriedades se aproximam de uma sequência de números aleatórios, é chamado de gerador de números pseudo-aleatórios.





- BBS (Blum-Blum-Shub generator) - .





BBS :





  • - ,





  • – ,  





  • – , ,





  • () - , n l(n), . ,  





    , « ». , , , , . , , .





  • x n n, y, y ^ 2 \ equiv x \ mod \ n. x - n.





  • p , p \ equiv 3 \ mod \ 4, .





2 :





  • , , , 1/2.





  • , , , r≤l(n)−1 s  (r+1)- s  1/2.





BBS (Blum-Blum-Shub generator)

  1. p q





  2. n: = p \ cdot q





  3. s \ in Z_n ^ * ( n)





  4. x_0: = s ^ 2 \ mod \ n





  5. x_i: = x_ {i-1} ^ 2 \ mod \ n b_i: = x_i \ mod \ 2





  6. : b_0, b_1, b_2, ...





:





n = p \ cdot q = 7 \ cdot 19 = 133   s = 100. x_0 = 100 ^ 2 \ equiv 25 \ mod \ 133 . : x_1 = 25 ^ 2 \ equiv 93 \ mod \ 133 b_1 = 93 \ equiv 1 \ mod \ 2, x_2 = 93 ^ 2 \ equiv 4 \ mod \ 133 b_2 = 4 \ equiv 0 \ mod \ 2, x_3 = 4 ^ 2 = 16 \ mod \ 133 b_3 = 16 \ equiv 0 \ mod \ 2, x_4 = 16 ^ 2 \ equiv 123 \ mod \ 133 b_4 = 123 \ equiv 1 \ mod \ 2





1,0,0,1.





, BBS, , \ lambda (\ lambda (x)), \ lambda (n) = \ {\ min {m}: a ^ m \ equiv 1 \ mod n \} - . 





BBS , n .  





i- , x_0, n, \ lambda (n).





BBS

, , .





BBS , :





  • , x \ em Z_n ^ * .





  • A (n, x)- , , 1 , x 0 .





.





, BBS ( )  .





. BBS. , .  BBS ,





, , , . : , RSA, ( ), , . , , . , . .





. — , . . , . , . , . 





(Password-Based Key Derivation Function, PBKDF) — , - . , , -. 





PBKDF . PRF. , , . , S - , , - MK_Length.





- MK , MK = PBKDF _ {(PRF, C)} (P, S, MK \ _ Comprimento)





, , , , . - C.   2 ^ {Sal \ _ Comprimento},   Salt_Length - .





:









Dummy _ Bits _ Number , BBS, -. , BBS, .  - .  a.





T U i : T_i, U_0 S i, Binary(). BBS T_i C. - . r .





, , , . , BBS , , .





  • Barker, Elaine; Barker, William; Burr, William; Polk, William; Smid, Miles (July 2012). "Recommendation for Key Management" (PDF). NIST Special Publication 800-57. NIST. Retrieved 19 August 2013.





  • Pascal Junod, «Cryptographic Secure Pseudo-Random Bits Generation: The Blum-Blum-Shub Generator», August 1999





  • ..; ‘’ ’’, 2017





  • A. C. Yao. Theory and application of trapdoor functions. In Proc. 23rd IEEE Symp. on Foundations of Comp. Science, pages 80–91, Chicago, 1982. IEEE.





  • M. Blum and S. Micali. How to generate cryptographically strong se- quences of pseudo-random bits. SIAM J. Computing, 13(4):850–863, November 1984.





  • Lenore Blum, Manuel Blum, and Michael Shub. Comparison of two pseudo-random number generators. In R. L. Rivest, A. Sherman, and D. Chaum, editors, Proc. CRYPTO 82, pages 61–78, New York, 1983. Plenum Press.





  • A. J. (Alfred J.) Menezes, Paul C. Van Oorschot, and Scott A. Van- stone. Handbook of applied cryptography. The CRC Press series on discrete mathematics and its applications. CRC Press, 2000 N.W. Cor- porate Blvd., Boca Raton, FL 33431-9868, USA, 1997.





  • E. Kranakis. Primality and Cryptography. Wiley-Teubner Series in Computer Science, 1986.





  • S. Goldwasser e S. Micali. Criptografia probabilística e como jogar pôquer mental mantendo todas as informações parciais secretas. Em Proc. 14th ACM Symp. on Theory of Computing, páginas 365-377, San Francisco, 1982. ACM.





  • Vybornova, Yu.D. Implantação do gerador Blum-Blum-Shub e estudo de suas principais características / Yu.D. Vybornova // IN SITU.





  • Brassard, J. Modern cryptology / J. Brassard. - Moscou: Polimed, 1999 .-- 107 p.





  • Yu.D. Vybornova, Desenvolvimento de uma função de geração de chave baseada em senha como um aplicativo gerador de Blum-Blum-Shub, nova técnica, 2017





  • Turan, M. Recomendação para derivação de chave baseada em senha / M. Turan, E. Barker, W. Burr, L. Chen - NIST, 2010. - 18 p. 












All Articles