Blum-Blum-Shubのソースを表示

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

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

:''x''<sub>''n''+1</sub> = (''x<sub>n</sub>'')<sup>2</sup> [[合同式|mod]] ''M''

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

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

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

:<math> x_i = \left( x_0^{2^i \bmod (p-1)(q-1)} \right) \bmod M </math>

== セキュリティ ==
[[暗号論的擬似乱数生成器]]であるため、[[情報セキュリティ]]や[[暗号]]目的で使われる。計算量的に不利なためシミュレーションなどには向かない。セキュリティ目的での強度としては、[[素因数分解]]の[[計算複雑性理論|複雑さ]]を利用した暗号の品質に匹敵する。適切な素数を選べば、各 ''x<sub>n</sub>'' の [[ランダウの記号|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'' <sub>-1</sub>=''s'' として ''x''<sub>0</sub> を求めるところから始め、''x''<sub>0</sub>, ''x''<sub>1</sub>, ''x''<sub>2</sub>, ... ''x''<sub>5</sub>= 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''. [http://dsns.csie.nctu.edu.tw/research/crypto/HTML/PDF/C82/61.PDF PDF]形式
* Martin Geisler, Mikkel Krøigård, and Andreas Danielsen. "About Random Bits", December 2004. [http://daimi.au.dk/~mg/mamian/random-bits.pdf PDF]形式、[http://daimi.au.dk/~mg/mamian/random-bits.ps.gz Gzipped Postscript]形式

== 外部リンク ==
* [http://firefly.is-a-geek.org/gmpbbs/ GMPBBS] - [[GNU Multi-Precision Library|GMP]]ベースの Blum-Blum-Shub の実装
* [https://code.google.com/archive/p/javarng Javaでの実装例]
* [http://www.ciphersbyritter.com/NEWS2/TESTSBBS.HTM Randomness tests]

[[Category:乱数]]
[[Category:エポニム]]