Pseudozufallszahlengeneratoren basierend auf RFLOS

Heutzutage erfordern viele Anwendungen die Fähigkeit, Zufallszahlen zu generieren. Abhängig davon, welches spezifische Problem gelöst wird, werden offensichtlich unterschiedliche Anforderungen an den Zufallszahlengenerator gestellt: Beispielsweise benötigt der Zufallszahlengenerator manchmal nur die Eindeutigkeit der erhaltenen Zahl, während häufig, insbesondere auf dem Gebiet der Kryptographie, die Anforderungen für solche Das Gerät / der Algorithmus ist viel starrer.

Es ist gleich zu klären, dass die Zahlen, die am Ausgang eines bestimmten deterministischen Algorithmus erhalten werden und die Eigenschaft der Zufälligkeit besitzen, als Pseudozufallsgeneratoren bezeichnet werden und die entsprechenden Generatoren als Pseudozufallszahlengeneratoren (PRNG) bezeichnet werden.

Der Zweck dieses Artikels besteht darin, sich mit PRNG vertraut zu machen, das auf Schieberegistern mit linearer Rückkopplung, einigen ihrer Modifikationen sowie mehreren kryptografisch starken PRNGs basiert, die in der Praxis verwendet werden.

Pseudozufallszahlengeneratorstruktur

Beginnen wir etwas weiter mit einem Blick auf die allgemeine Struktur des PRNG. Die Struktur wird als Grundlage genommen, die von den Autoren in [2] empfohlen und ausführlicher betrachtet wird.

Werfen wir einen kurzen Blick auf jeden Block:

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. Pseudozufallszahlengeneratoren: Ein 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. Angewandte Kryptographie. Protokolle, Algorithmen, Quelltexte in der Sprache C. - Triumph, 2013. - 816 s

   
   
   
   
   

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