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

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から回復できます。