Clever Geek Handbook

RFLOSに基づく疑似乱数ジェネレータ

今日、多くのアプリケーションはランダムな数値を生成する機能を必要とします。明らかに、解決されている特定の問題に応じて、ランダム番号ジェネレーターに異なる要件が課せられます。たとえば、ランダム番号ジェネレーターは、取得した番号の一意性のみを必要とする場合がありますが、特に暗号化の分野では、そのような要件が必要になることがよくあります。デバイス/アルゴリズムははるかに厳格です。





特定の決定論的アルゴリズムの出力で得られ、ランダム性の特性を持つ数は疑似ランダムと呼ばれ、対応するジェネレーターは疑似ランダム数ジェネレーター（PRNG）と呼ばれることをすぐに明らかにする価値があります。





この記事の目的は、線形フィードバックを備えたシフトレジスタに基づくPRNG、それらの変更のいくつか、および実際に使用される暗号的に強力なPRNGのいくつかに精通することです。





疑似乱数発生器の構造

PRNGの一般的な構造を見て、少し離れたところから始めましょう。構造は基礎として採用されており、[2]の著者によって推奨され、より詳細に検討されています。





https://nvlpubs.nist.gov/nistpubs/SpecialPublications/NIST.SP.800-90Ar1.pdf、11ページ
https://nvlpubs.nist.gov/nistpubs/SpecialPublications/NIST.SP.800-90Ar1.pdf、11ページ

各ブロックを簡単に見てみましょう。





  1. - , , , ( ), .





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





  3. - , , ;





  4. nonce , , ;





  5. , . , ;





  6. , ;





  7. ( ) ;





  8. .





(), .. .





リニアフィードバックシフトレジスタ。 出典：[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] . , , , .





, , "" , .





, , , . : :





左側は説明図であり、右側は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] , .





"-": , , , . :





ゴルマンのカスケード、出典：[6、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 , .. .





アルゴリズム図A5 / 1、出典：[3、113ページ]
5/1, : [3, 113]
ジェネレーター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. 疑似ランダム番号ジェネレータ：チュートリアル、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. AppliedCryptography。C言語のプロトコル、アルゴリズム、ソーステキスト。-トライアンフ、2013 .-- 816秒





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











More articles:


All Articles