Blum-Blum-Shub

Blum-Blum-Shub（B.B.S.）は、マヌエル・ブラムとLenore BlumとMichael Shubが提案した暗号論的擬似乱数生成器である。1986年に発表された (Blum et al, 1986)。

漸化式は次のような形をしている。

x_n+1 = (x_n)² mod M

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

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

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

$x_{i}=\left(x_{0}^{2^{i}{\bmod {(}}p-1)(q-1)}\right){\bmod {M}}$

セキュリティ

暗号論的擬似乱数生成器であるため、情報セキュリティや暗号目的で使われる。計算量的に不利なためシミュレーションなどには向かない。セキュリティ目的での強度としては、素因数分解の複雑さを利用した暗号の品質に匹敵する。適切な素数を選べば、各 x_n の O(log log M) ビットの下位ビット列が出力となり、M を無限大に近づけると、そのビット列と乱数を見分けることは、M を素因数分解するのと同程度かそれ以上に困難となる。

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

周期に関する注意点

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

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

例

p=11、q=19、s=3 とする。gcd(φ(p-1), φ(q-1))=2 であるため、生成される擬似乱数列が反復する周期は長いことが期待できる。x _-1=s として x₀ を求めるところから始め、x₀, x₁, x₂, ... x₅= 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形式

外部リンク

• GMPBBS - GMPベースの Blum-Blum-Shub の実装
• Javaでの実装例
• Randomness tests