Blum-Blum-Shub

出典: フリー百科事典『ウィキペディア(Wikipedia)』
移動: 案内検索

Blum-Blum-ShubB.B.S.)は、1986年にマヌエル・ブラム、Lenore Blum、Michael Shub が発表した擬似乱数発生器である (Blum et al, 1986)。

次のような形式である。

xn+1 = (xn)2 mod M

ここで M=pq は2つの素数 pq の積である。アルゴリズムの各ステップにおいて、xn から何らかの出力が得られる。この出力は一般に xnビットパリティを使うか、または xn の1ビット以上の最下位ビット列を使う。

2つの素数 pq は共に、(mod 4 で)3 と合同で(これにより、それぞれの平方剰余が1つの平方根を持ち、それ自身も平方剰余となる)、かつ gcd(φ(p-1), φ(q-1)) が小さいのが望ましい(これにより、反復周期が長くなる)。

Blum-Blum-Shub の興味深い性質として、任意の xi の値を次のように直接計算することができる。

 x_i = \left( x_0^{2^i \bmod (p-1)(q-1)} \right) \bmod M

セキュリティ[編集]

この擬似乱数生成法はあまり高速とは言えないため、シミュレーションには向かず、暗号理論でのみ使われる。しかし、セキュリティ的な強さがあることが知られており、素因数分解複雑さを利用した暗号の品質に匹敵する。適切な素数を選べば、各 xnO(log log M) ビットの下位ビット列が出力となり、M を無限大に近づけると、そのビット列と乱数を見分けることは、M を素因数分解するのと同程度かそれ以上に困難となる。

素因数分解が困難であれば、十分に大きな M の B.B.S. の出力から、ランダムでないパターンを適切な量の計算で検出することはできない。このため、RSA暗号のような素因数分解問題を利用した暗号技術と同程度に安全とされている。

周期に関する注意点[編集]

gcd(φ(p-1), φ(q-1))=2を満たすような素数の組pqであっても、短い周期を持つことがある。

例えば、p=839q=5119139の場合ではその周期は最長で129124380となるのに対し、 p=887q=4842091の場合では、M=pqの値がほとんど同じであるにもかかわらず、その周期は最長でも437580となる。

[編集]

p=11q=19s=3 とする。gcd(φ(p-1), φ(q-1))=2 であるため、生成される擬似乱数列が反復する周期は長いことが期待できる。x -1=s として x0 を求めるところから始め、x0, x1, x2, ... x5= 9, 81, 82, 36, 42, 92 という数列が得られる。最下位ビットを出力とする場合、出力されるビット列は 1 1 0 0 0 0 となる。

参考文献[編集]

  • Lenore Blum, Manuel Blum, and Michael Shub. "A Simple Unpredictable Pseudo-Random Number Generator", SIAM Journal on Computing, volume 15, pages 364–383, May 1986.
  • Lenore Blum, Manuel Blum, and Michael Shub. "Comparison of two pseudo-random number generators", Advances in Cryptology: Proceedings of Crypto '82. PDF形式
  • Martin Geisler, Mikkel Krøigård, and Andreas Danielsen. "About Random Bits", December 2004. PDF形式、Gzipped Postscript形式

外部リンク[編集]