乱数生成器は実際どう動いているのか
乱数のコードのほとんどは、微妙に偏っています。どこで偏るのか、なぜ普段は問題にならないのか。
擬似乱数と暗号学的乱数
PRNG は内部状態を持つ決定論的なアルゴリズムです。同じシードを与えれば同じ列を返します。シミュレーションでは利点、パスワードでは致命的な欠陥です。Math.random() はその一種で、ページごとに 1 度シードされ、出力を十分観察すれば予測できます。
CSPRNG は OS のエントロピープールから引き、過去の出力を観察しても将来の出力を予測できないように設計されています。ブラウザは crypto.getRandomValues() として公開しています。
modulo bias という問題
よくある近道が randomUint32() % n です。正しく見えますが、2^32 はほとんどの n で割り切れません。n が 3 なら、0・1・2 に割り当てられる機会はそれぞれ 1,431,655,765、1,431,655,765、1,431,655,766 回です。2 へのごくわずかな偏りで、試行回数をいくら増やしても消えません。
修正は rejection sampling です。2^32 に収まる n の最大倍数を求め、それを超える値は捨て、残った値だけを n で割ります。まれに引き直す代わりに、偏りが完全に消えます。
浮動小数点はさらに悪くする
Math.floor(Math.random() * n) も大きい n で同じ種類の問題を抱えます。加えて double の仮数部は 53 bit なので、2^53 を超えると表現できない整数が出てきます。それより広い範囲では、値が黙って失われます。
小数を扱うなら、整数に拡大して引いてから割り戻すのが確実です。最初から最後まで浮動小数点で計算すると、丸めによって結果が要求した範囲の外へ押し出されることがあります。
抽選で一様性が問題になる理由
0.00000002% の偏りはサイコロでは無意味で、抽選でも無意味です。しかし同じ偏った関数をセッショントークンや暗号鍵の生成に使うと話が変わります。偏りとは、攻撃者が探索空間を狭めるのに利用できる構造そのものです。
実務的な原則はこうです。見た目の演出には Math.random()、誰かが予測すると得をする可能性のあるものには、rejection sampling を伴う CSPRNG を使ってください。
よくある質問
ランダム抽選に Math.random() で足りますか？
飲食店を選ぶなら足ります。景品のある抽選なら、ページを見ている誰にも予測も再現もできないよう、暗号学的な乱数源を使ってください。
modulo bias を 1 文で言うと？
乱数の整数範囲が生成器の出力範囲を割り切れないとき、一部の結果が他よりわずかに出やすくなる現象です。
ブラウザは真の乱数を生成できますか？
できません。真の乱数には物理的なエントロピー源が必要です。OS がハードウェアイベントからエントロピーを集めて CSPRNG をシードする方法が、セキュリティ上の実務標準です。