乱数生成器

昨日の調査で分かってきたこと。
システムが提供する（可能性のある）乱数生成器には次の４種類がある。

情報理論的な'真'の乱数生成器

各ビットが１ビットのエントロピーを持つ乱数を生成する。OSなどがハードウエアを通して外部のエントロピー源から情報を得て生成する。

暗号理論的な擬似乱数生成器 (CSPRNG)

暗号理論的に予測不可能な乱数を生成する。乱数生成のアルゴリズムは既知であっても、乱数種が暗号理論的に推測不可能なため、生成される乱数が予測不可能。たとえば、Blum-Blum-Shab法は、RSAなどと同じく素因数分解をベースにしている。

統計学的な擬似乱数生成器

統計学的に健全な乱数を生成する。しかし、セキュリティ用途には不適。たとえば、Mersenne Twisterの標準的な実装であるMT19937の場合は、624個の出力を観察すれば、それ以降の出力を予測可能になる。

不完全な擬似乱数生成器

統計学的に不健全な乱数を生成する。高速であること以外にメリットは無い。線形合同法が代表的で、標準的なCの擬似乱数生成関数はこれを利用していることが多い。

なお、擬似乱数生成器を略して PRNG (Pseudorandom number generator) と呼ぶ。