メインコンテンツまでスキップ

6.1.3. Traditional Pseudo-random Sequences (従来の擬似ランダムシーケンス)

6.1.3. Traditional Pseudo-random Sequences (従来の擬似ランダムシーケンス)​

このセクションでは, 決定論的または "擬似ランダム" 数の従来の源について説明します。これらは通常 "シード" 数量から始まり, 単純な数値または論理演算を使用して値のシーケンスを生成します。このセクションで議論されている技術は, 暗号使用に適していないことに注意してください。それらは一般的な情報のために提示されています。

[KNUTH]には擬似乱数に関する古典的な説明があります。彼が言及しているアプリケーションは, 自然現象のシミュレーション, サンプリング, 数値解析, コンピュータプログラムのテスト, 意思決定, ゲームです。これらのいずれも, 私たちが話しているセキュリティ使用の種類と同じ特性を持っていません。最後の2つでのみ, ランダムな数量を見つけようとする敵対者がいる可能性があります。しかし, これらの場合, 敵対者は通常, 推測された値を使用する機会が1回しかありません。パスワードを推測したり, 暗号化スキームを破ろうとしたりする場合, 敵対者は通常, 正しい値を推測する機会が多数, おそらく無制限にあります。時々, 敵対者は破られるべきメッセージを保存し, 繰り返し攻撃することができます。敵対者はまた, コンピュータによって支援されると仮定されます。

数の "ランダム性" をテストするために, Knuthは統計的およびスペクトル的なものを含むさまざまな尺度を提案しています。これらのテストは, "ランダム" シーケンスの異なる部分間の自己相関またはその値の分布などをチェックします。しかし, これらのテストは, CRC Standard Mathematical Tables [CRC]に印刷された "ランダム" シーケンスなどの定数保存ランダムシーケンスによって満たされる可能性があります。Knuthによって提案されたすべてのテストを満たすにもかかわらず, そのシーケンスは暗号使用には不適切です, 敵対者は一般的に公開されたすべての "ランダム" シーケンスのコピーを持っていると仮定されなければならず, 源を特定して将来の値を予測できます。

典型的な擬似乱数生成技術は, 線形合同擬似乱数生成器です。この技術はモジュラー算術を使用し, N+1番目の値はN番目の値から次のように計算されます:

        V    = ( V  * a + b )(Mod c)
         N+1      N

上記の技術は, 暗号学的によく理解されている線形シフトレジスタ擬似乱数生成器と強い関係があります [SHIFT*]。そのような生成器では, ビットはレジスタへの選択された固定タップからのビットのExclusive Or (キャリーなしの二進和) としてシフトレジスタの一端に導入されます。たとえば, 次を考えてみましょう:

      +----+     +----+     +----+                      +----+
      | B  | <-- | B  | <-- | B  | <--  . . . . . . <-- | B  | <-+
      |  0 |     |  1 |     |  2 |                      |  n |   |
      +----+     +----+     +----+                      +----+   |
        |                     |            |                     |
        |                     |            V                  +-----+
        |                     V            +----------------> |     |
        V                     +-----------------------------> | XOR |
        +---------------------------------------------------> |     |
                                                              +-----+

       V    = ( ( V  * 2 ) + B  XOR  B ... )(Mod 2^n)
        N+1         N         0       2

従来の擬似乱数生成器アルゴリズムの品質は, そのようなシーケンスの統計的テストによって測定されます。慎重に選択された値a, b, c, および初期V, または上記の単純なプロセスでのシフトレジスタタップの慎重に選択された配置は, 優れた統計を生成できます。

これらのシーケンスは, シーケンスが探索されている空間の構造に直交する限り, シミュレーション (モンテカルロ実験) で適切である可能性があります。そこでも, 微妙なパターンが問題を引き起こす可能性があります。しかし, そのようなシーケンスは明らかにセキュリティアプリケーションでの使用には悪いです。それらは, 初期状態がわかっている場合は完全に予測可能です。擬似乱数生成器の形式によっては, シーケンスの短い部分の観察からシーケンスを決定できる場合があります [SCHNEIER, STERN]。たとえば, 上記の生成器では, V(n)の知識が与えられればV(n+1)を決定できます。実際, これらの技術では, 擬似ランダム値の1ビットのみが解放された場合でも, 短いシーケンスからシードを決定できることが示されています。

線形合同生成器が破られただけでなく, すべての多項式合同生成器を破る技術が現在知られています [KRAWCZYK]。

に最終更新