Clever Geek Handbook

Generadores de números pseudoaleatorios basados ​​en RFLOS

Hoy en día, muchas aplicaciones requieren la capacidad de generar números aleatorios. Obviamente, dependiendo del problema específico que se esté resolviendo, se impondrán diferentes requisitos al generador de números aleatorios: por ejemplo, a veces el generador de números aleatorios puede necesitar solo la unicidad del número obtenido, mientras que a menudo, especialmente en el campo de la criptografía, los requisitos para tal el dispositivo / algoritmo es mucho más rígido.





Vale la pena aclarar de inmediato que los números obtenidos a la salida de un determinado algoritmo determinista y que poseen la propiedad de aleatoriedad se denominan pseudoaleatorios, y los generadores correspondientes se denominan generadores de números pseudoaleatorios (PRNG).





El propósito de este artículo es familiarizarse con PRNG basado en registros de desplazamiento con retroalimentación lineal, varias de sus modificaciones, así como varios PRNG criptográficamente fuertes que se utilizan en la práctica.





Estructura generadora de números pseudoaleatorios

Comencemos desde una pequeña distancia observando la estructura general del PRNG. Se toma como base la estructura, que es recomendada y considerada con más detalle por los autores en [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

Echemos un vistazo rápido a cada bloque:





  1. - , , , ( ), .





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





  3. - , , ;





  4. nonce , , ;





  5. , . , ;





  6. , ;





  7. ( ) ;





  8. .





(), .. .





Registro de desplazamiento de retroalimentación lineal. Fuente: [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] . , , , .





, , "" , .





, , , . : :





A la izquierda hay un diagrama explicativo, a la derecha una representación de una función en forma de polinomio 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] , .





"-": , , , . :





Cascada de Gollman, fuente: [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, fuente: [3, página 113]
5/1, : [3, 113]
Sistema de ecuaciones para el generador 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. Generadores de números pseudoaleatorios: un 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. Criptografía aplicada. Protocolos, algoritmos, textos fuente en lenguaje C. - Triumph, 2013.- 816 s





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











More articles:


All Articles