Générateurs de nombres pseudo-aléatoires basés sur RFLOS

Aujourd'hui, de nombreuses applications nécessitent la capacité de générer des nombres aléatoires. Évidemment, en fonction du problème spécifique résolu, différentes exigences seront imposées au générateur de nombres aléatoires: par exemple, parfois le générateur de nombres aléatoires peut seulement avoir besoin de l'unicité du nombre obtenu, alors que souvent, en particulier dans le domaine de la cryptographie, les exigences pour un tel le dispositif / algorithme est beaucoup plus rigide.

Il vaut la peine de préciser tout de suite que les nombres obtenus à la sortie d'un certain algorithme déterministe et possédant la propriété d'aléatoire sont appelés pseudo-aléatoires, et les générateurs correspondants sont appelés générateurs de nombres pseudo-aléatoires (PRNG).

Le but de cet article est de se familiariser avec le PRNG basé sur des registres à décalage avec rétroaction linéaire, plusieurs de leurs modifications, ainsi que plusieurs PRNG cryptographiquement forts qui sont utilisés dans la pratique.

Structure du générateur de nombres pseudo-aléatoires

Commençons un peu plus loin en examinant la structure générale du PRNG. La structure est prise comme base, ce qui est recommandé et examiné plus en détail par les auteurs dans [2].

Jetons un coup d'œil à chaque bloc:

1. - , , , ( ), .

   
   
   
   
   

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

   
   
   
   
   

3. - , , ;

   
   
   
   
   

4. nonce , , ;

   
   
   
   
   

5. , . , ;

   
   
   
   
   

6. , ;

   
   
   
   
   

7. ( ) ;

   
   
   
   
   

8. .

   
   
   
   
   

(), .. .

n b₁, b₂, . . . , b_n C₁ = 1, C₂, C₃ , . . . , C_n ∈ {0, 1}. ( [8]). GF(2), . 2:

C(x) = ₁xⁿ + C₂x^n-1 + . . . + C_nx + 1,

.

1. 2 , , .. C_i 1;

   
   
   
   
   

2. ;

   
   
   
   
   

3. , 1.

   
   
   
   
   

b₁ . 2ⁿ-1, , .

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

, : . , , , ( ).

:

1. , , ;

   
   
   
   
   

2. ;

   
   
   
   
   

3. 2 ;

   
   
   
   
   

4. .

   
   
   
   
   

, , , , .

, , .

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

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

, , "" , .

, , , . : :

.. 2 , . , - . , . .

L₁ . . . L_M , , .

i- L_i , , - , .. (L_i, L_j) = 1 i≠j. f , .. f = . . . + x_i + . . . , . 2^L, L - , .

"-"

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

, , , , -1.

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

"-": , , , . :

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

: . [9] . 15 .

5/1

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

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

.

: , ( 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. Générateurs de nombres pseudo-aléatoires: un didacticiel, 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. Cryptographie appliquée. Protocoles, algorithmes, textes sources en langage C. - Triomphe, 2013 .-- 816 s

   
   
   
   
   

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