Generator nomor pseudo-random berdasarkan RFLOS

Saat ini, banyak aplikasi membutuhkan kemampuan untuk menghasilkan angka acak. Jelas, tergantung pada masalah spesifik apa yang sedang dipecahkan, persyaratan yang berbeda akan diberlakukan pada generator bilangan acak: misalnya, terkadang hanya keunikan dari bilangan yang diperoleh yang mungkin diperlukan dari pembuat bilangan acak, sementara seringkali, terutama di bidang kriptografi, persyaratan untuk itu perangkat / algoritme jauh lebih kaku.

Perlu diklarifikasi segera bahwa bilangan yang diperoleh pada keluaran dari algoritme deterministik tertentu dan memiliki sifat keacakan disebut pseudo-random, dan generator yang sesuai disebut pseudo-random number generator (PRNG).

Tujuan artikel ini adalah untuk membiasakan dengan PRNG berdasarkan register geser dengan umpan balik linier, beberapa modifikasinya, serta beberapa PRNG yang kuat secara kriptografik yang digunakan dalam praktik.

Struktur pembangkit bilangan acak semu

Mari kita mulai sedikit lebih jauh, dengan melihat struktur umum PRNG. Struktur tersebut diambil sebagai dasar, yang direkomendasikan dan dipertimbangkan secara lebih rinci oleh penulis di [2].

Mari kita lihat sekilas setiap blok:

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. Generator Nomor Pseudo-Acak: 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. Kriptografi Terapan. Protokol, algoritma, teks sumber dalam bahasa C. - Kemenangan, 2013. - 816 d

   
   
   
   
   

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