Clever Geek Handbook

Geradores de números pseudo-aleatórios baseados em RFLOS

Hoje, muitos aplicativos requerem a capacidade de gerar números aleatórios. Obviamente, dependendo de qual problema específico está sendo resolvido, diferentes requisitos serão impostos ao gerador de números aleatórios: por exemplo, às vezes o gerador de números aleatórios pode precisar apenas da unicidade do número obtido, enquanto muitas vezes, especialmente no campo da criptografia, os requisitos para tal o dispositivo / algoritmo é muito mais rígido.





Cabe esclarecer de imediato que os números obtidos na saída de um determinado algoritmo determinístico e possuindo a propriedade de aleatoriedade são chamados de pseudo-aleatórios, e os geradores correspondentes são chamados de geradores de números pseudo-aleatórios (PRNG).





O objetivo deste artigo é familiarizar-se com o PRNG baseado em registradores de deslocamento com feedback linear, várias de suas modificações, bem como vários PRNGs criptograficamente fortes que são usados ​​na prática.





Estrutura geradora de número pseudoaleatório

Vamos começar um pouco mais, examinando a estrutura geral do PRNG. A estrutura é tomada como base, o que é recomendado e considerado mais detalhadamente pelos autores em [2].





https://nvlpubs.nist.gov/nistpubs/SpecialPublications/NIST.SP.800-90Ar1.pdf, página 11
https://nvlpubs.nist.gov/nistpubs/SpecialPublications/NIST.SP.800-90Ar1.pdf, página 11

Vamos dar uma olhada rápida em cada bloco:





  1. - , , , ( ), .





  2. ( ) . (nonce). , , , .. .





  3. - , , ;





  4. nonce , , ;





  5. , . , ;





  6. , ;





  7. ( ) ;





  8. .





(), .. .





Registro de deslocamento de feedback linear. Fonte: [3, p. 105]
. : [3, . 105]

n b1, b2, . . . , bn C1 = 1, C2, C3 , . . . , Cn ∈ {0, 1}. ( [8]). GF(2), . 2:





C(x) = 1xn + C2xn-1 + . . . + Cnx + 1,





.





  1. 2 , , .. Ci 1;





  2. ;





  3. , 1.





b1 . 2n-1, , .





, , .. , , n . , 2n , , .





, : . , , , ( ).





:





  1. , , ;





  2. ;





  3. 2 ;





  4. .





, , , , .





, , .





, - , , (). , [9, . 2.8], .. , , , , .





, , , . [1], [10] . , , , .





, , "" , .





, , , . : :





À esquerda está um diagrama explicativo, à direita está uma representação de uma função na forma de um polinômio de Zhegalkin
- , -





.. 2 , . , - . , . .





L1 . . . LM , , .





i- Li , , - , .. (Li, Lj) = 1 i≠j. f , .. f = . . . + xi + . . . , . 2L, L - , .





"-"

"-" ( -1 -2). -2 , -1 1. -2 , .. , -1 -2.





, , , , -1.





, "-", 3 . -2 1 -1, -3 0. -2 -3. [4] , .





"-": , , , . :





Cascata de Gollman, fonte: [6, página 50]
, : [6, 50]

-1 1, -2. -2 1 - -3 .. .





: . [9] . 15 .





5/1

, , , , GSM. 5, 1987 5/1, .. 5/2 5/3.





: , 19, 22 23 . . 5 , .. .





Diagrama de algoritmo A5 / 1, fonte: [3, página 113]
5/1, : [3, 113]
Sistema de equações para o gerador A5 / 1
5/1

.





: , ( C1 , C2, C3- ). m = majotiry (C1, C2, C3) , .. 0 1. , .





, , . . , [10].





:

  1.  .. ( 2. )





  2. nvlpubs.nist.gov/nistpubs/SpecialPublications/NIST.SP.800-90Ar1.pdf





  3.  . .,  . .,  . . : — .: , 2019





  4. C.G. Gunter, “Alternating Step Generators Contolled by de Bruijn Sequenc-es”, Advances in Cryptology EUROCRYPT ’87 Proceedings, Springer-Verlag, 1988





  5. . . – .: . — 1989





  6. Slepovichev I.I. Geradores de números pseudo-aleatórios: um tutorial, 2017





  7. https://software.intel.com/sites/default/files/m/d/4/1/d//441IntelR_DRNGSoftwareImplementationGuidefinalAug7.pdf





  8. https://www.xilinx.com/support/documentation/application_notes/xapp052.pdf





  9. Schneier B. Applied Cryptography. Protocolos, algoritmos, textos-fonte na linguagem C. - Triumph, 2013 .-- 816 s





  10. https://csrc.nist.gov/publications/detail/sp/800-22/rev-1a/final











More articles:


All Articles