6.2. Cryptographically Strong Sequences (暗号学的に強力なシーケンス)

一連のランダム量が生成されなければならないケースでは, 敵はシーケンス内のいくつかの値を学習する可能性があります。一般的に, 敵は知っている値から他の値を予測できないようにする必要があります。

正しい技術は, 強力なランダムシードから始め, そのシードから暗号学的に強力なステップを踏み [FERGUSON, SCHNEIER], シーケンス要素で生成器の完全な状態を明らかにしないことです。シーケンス内の各値が前の値から固定された方法で計算できる場合, 任意の値が危険にさらされると, すべての将来の値を決定できます。これは, たとえば, 各値が以前に使用された値の定数関数である場合に当てはまります。関数が非常に強力で非可逆的なメッセージダイジェスト関数であっても同様です。

(鍵値のシーケンスを生成する技術が十分に高速である場合, それは機密性システムの基礎として自明に使用できることに注意してください。2 つの当事者が同じシーケンス生成技術を使用し, 同じシード素材から始める場合, 同一のシーケンスを生成します。これらは, たとえば, 送信されるデータと XOR して暗号化し, 受信したこのデータと XOR して復号化できます。これは XOR 操作の可逆特性によるものです。これは一般に単純なストリーム暗号と呼ばれます。)

6.2.1. OFB and CTR Sequences (OFBおよびCTRシーケンス)

強力なシーケンスを生成する 1 つの方法は, シード値を取り, シードと連続する整数などを連結することによって生成される量をハッシュし, 敵が利用できる生成器状態の量を制限するために取得した値をマスクすることです。

また, ランダム鍵とシード値を使用して連続する整数を暗号化することも可能です。これはカウンタ (CTR) モード暗号化のようです。または, 暗号化からのすべての出力値を次のイテレーションで暗号化される値にフィードバックすることもできます。これは出力フィードバックモード (OFB) の特定の例です [MODES]。

以下に, シフトとマスキングを使用して出力フィードバックの一部を古い入力の一部と組み合わせる例を示します。このタイプの部分フィードバックは, 以下で説明する理由により回避する必要があります。

        +---------------+
        |       V       |
        |  |     n      |--+
        +--+------------+  |
              |            |     +---------+
         shift|            +---> |         |      +-----+
           +--+                  | Encrypt | <--- | Key |
           |           +-------- |         |      +-----+
           |           |         +---------+
           V           V
        +------------+--+
        |      V     |  |
        |       n+1     |
        +---------------+

1 のシフトが使用される場合, これはセクション 6.1.3 で説明されたシフトレジスタ技術と同じですが, フィードバックがいくつかのビット位置タップからの出力の単純な線形または多項式の組み合わせではなく, すべてのビットの複雑な非線形関数によって決定されるという重要な違いがあります。

Donald W. Davies は, このようなシフトされた部分出力フィードバックが, すべての出力ビットを入力としてフィードバックするのと比較して, アルゴリズムを大幅に弱めることを示しました。特に, DES の場合, 完全な 64 ビット量を繰り返し暗号化すると, 約 2^63 回の反復で予想される繰り返しが得られます。64 未満 (および 0 より大きい) ビットをフィードバックすると, 2^31 から 2^32 の間の反復で予想される繰り返しが得られます!

これらの技術によってシーケンスが生成された場合にシーケンスの他の値から値を予測することは, 暗号システムを破ることまたは部分的な情報のみが利用可能な場合に "非可逆的" ハッシュを反転することと同等です。各イテレーションで明らかにされる情報が少ないほど, 敵がシーケンスを予測することは難しくなります。したがって, 各値から 1 ビットのみを使用するのが最善です。一部のケースでは, これにより, 暗号システムが可逆的であり, 生成された各値のすべてが明らかにされた場合に破られる可能性がある場合でも, システムを破ることが不可能になることが示されています。

6.2.2. The Blum Blum Shub Sequence Generator (Blum Blum Shubシーケンス生成器)

現在, 強度の最も強力な公開証明を持つ生成器は, 発明者にちなんで Blum Blum Shub 生成器と呼ばれています [BBS]。それは非常に単純で, 二次剰余に基づいています。その唯一の欠点は, セクション 6.1.3 で示された従来の技術と比較して計算集約的であることです。これは, セッション鍵の生成などの適度に頻繁でない目的に使用される場合, 大きな欠点ではありません。

単に 2 つの大きな素数 (たとえば, p と q) を選択します。各々は 4 で割ると 3 の余りを与えます。n = p * q とします。次に, n と互いに素なランダムな数 x を選択します。生成器の初期シードと後続の値を計算する方法は次のとおりです:

                2
     s    =  ( x  )(Mod n)
      0
                2
     s    = ( s   )(Mod n)
      i+1      i

各 s の下位から数ビットのみを使用するように注意してください。最下位ビットのみを使用することは常に安全です。以下を超えない数を使用する場合:

     log  ( log  ( s  ) )
        2      2    i

下位ビットを使用すると, この方法で生成されたシーケンスから追加のビットを予測することは, n を因数分解することと証明可能に同じくらい困難です。初期 x が秘密である限り, 望むなら n を公開できます。

この生成器の興味深い特性は, s 値のいずれかを直接計算できることです。特に:

           ( (2^i) (Mod ((p-1)*(q-1)) ) )
  s  = ( s                                )(Mod n)
   i      0

これは, この方法で多くの鍵が生成されるアプリケーションでは, それらすべてを保存する必要がないことを意味します。各鍵は効果的にインデックス化され, その小さなインデックスと初期 s および n から回復できます。