乱数の仕組み - 疑似乱数（PRNG）と暗号論的乱数（CSPRNG）を実装して確かめる

Math.random() でパスワードリセット用のトークンを作ってはいけない、というのは広く知られたルールです。ただ「なぜダメなのか」を、実際に手を動かして確かめたことがある人はそう多くありません。この記事では、線形合同法を自分で書いて壊し、Mersenne Twister の内部状態を 624 個の出力から復元して次の出力を完全に当て、sort(() => Math.random() - 0.5) によるシャッフルがどれだけ偏るかをヒストグラムで測ります。

一次ソースは V8 のソースコード、ECMAScript 仕様、Python / Go / PHP / Java の公式ドキュメント、Linux man-pages、NIST SP 800-90A / 800-22、RFC 9562 です。数値は自分の手元で実行して得たものだけを載せ、確認できなかったことは「未確認」と明示します。

乱数には2種類ある

まず用語を整理します。

TRNG（True Random Number Generator、真の乱数生成器）は、物理現象からビットを取り出します。熱雑音、回路のメタスタビリティ、放射線崩壊、あるいはユーザーのキー入力や割り込みのタイミングのジッタなどです。原理的に再現できません。CPU 内蔵のものとしては Intel の RDSEED がこれにあたります。

PRNG（Pseudo Random Number Generator、疑似乱数生成器）は、決定論的なアルゴリズムです。内部状態を持ち、状態から次の出力と次の状態を計算します。同じシード（種）から始めれば、何度実行してもまったく同じ数列が出ます。乱数「らしく」見えるだけで、乱数ではありません。

state_0 = seed
出力_n  = output(state_n)
state_n+1 = next(state_n)

ここから3つの帰結が出ます。

1. 周期がある。状態が有限ビットなので、いつか同じ状態に戻り、そこから先は同じ数列の繰り返しになります。状態が k ビットなら周期は最大でも 2 の k 乗です
2. シードが分かれば全部分かる。シードを当てられれば、過去も未来も再現できます
3. 出力から状態が逆算できることがある。これが後で見る Mersenne Twister の話です

そして PRNG のうち、出力を観測しても次の出力を予測できないように設計されたものを CSPRNG（Cryptographically Secure PRNG、暗号論的疑似乱数生成器）と呼びます。「乱数」と一括りにされがちですが、シミュレーション用の PRNG と CSPRNG は設計目標がまったく違います。

実務で問題になるのは、ほぼ例外なく2段目を3段目のつもりで使ってしまうケースです。

線形合同法（LCG）を書いて壊す

最も古典的な PRNG が線形合同法（Linear Congruential Generator, LCG）です。式はこれだけです。

X(n+1) = (a * X(n) + c) mod m

a が乗数、c が増分、m が法。実装は数行で済み、速く、状態も小さい。だからこそ長く使われてきましたが、致命的な弱点があります。

下位ビットの周期を測る

m が 2 の冪のとき、下から k 番目のビットの周期は 2 の (k+1) 乗にしかなりません。理屈ではなく、実際に測ってみます。

M = pow(2, 32)
A, C = 1664525, 1013904223   # Numerical Recipes のパラメータ
 
def gen(seed, n):
    s = seed
    out = []
    for _ in range(n):
        s = (A * s + C) % M
        out.append(s)
    return out
 
seq = gen(12345, 40000)
 
def period_of_bit(seq, k, maxp=20000):
    bits = [(v >> k) & 1 for v in seq]
    for p in range(1, maxp + 1):
        if all(bits[i] == bits[i + p] for i in range(len(bits) - p)):
            return p
    return None
 
print("bit k  観測した周期   2^(k+1)")
for k in list(range(0, 14)) + [20, 31]:
    print(f"{k:5d}  {str(period_of_bit(seq, k)):>12}   {pow(2, k+1)}")

bit k  観測した周期   2^(k+1)
    0             2   2
    1             4   4
    2             8   8
    3            16   16
    4            32   32
    5            64   64
    6           128   128
    7           256   256
    8           512   512
    9          1024   1024
   10          2048   2048
   11          4096   4096
   12          8192   8192
   13         16384   16384
   20          None   2097152
   31          None   4294967296

観測した周期が 2 の (k+1) 乗と完全に一致しています（bit 20 と bit 31 は探索上限 20000 を超えるので None）。とくに bit 0 は周期 2、つまり 0, 1, 0, 1, ... と交互に並ぶだけです。

01010101010101010101010101010101

出現頻度は 0 と 1 でちょうど五分五分なので、単純な頻度検定は通ります。しかし次の値は100%予測できます。ここに「統計的に均等であること」と「予測できないこと」がまったく別物だという、この記事の核心が現れています。

だから LCG で 0 か 1 を得たいときに x % 2 と書くのは最悪です。上位ビットを使えば周期はぐっと長くなります。これは後述する V8 の Math.random() が下位11ビットを捨てているのと同じ発想です。

RANDU と「15枚の平面」

もうひとつの弱点が格子構造（スペクトル的な弱さ）です。LCG の出力を d 個ずつ組にして d 次元空間にプロットすると、点は少数の平行な超平面の上にしか乗りません。

歴史的に有名な悪例が、IBM が 1960 年代に配布した RANDU（a = 65539、c = 0、m = 2^31）です。この生成器には次の恒等式が成り立ちます。

9 * X(k) - 6 * X(k+1) + X(k+2) ≡ 0 (mod 2^31)

本当かどうか、30万点で確かめます。

from collections import Counter
 
M, A = pow(2, 31), 65539
s, seq = 1, []
for _ in range(300000):
    s = (A * s) % M
    seq.append(s)
 
c = Counter()
for k in range(len(seq) - 2):
    v = 9 * seq[k] - 6 * seq[k + 1] + seq[k + 2]
    assert v % M == 0            # 常に 2^31 の倍数になる
    c[v // M] += 1
 
for k in sorted(c):
    print(' 平面', k, ':', c[k], '点')
print('相異なる平面数:', len(c))

 平面 -5 : 2730 点
 平面 -4 : 8493 点
 平面 -3 : 13829 点
 平面 -2 : 19673 点
 平面 -1 : 24931 点
 平面 0 : 30090 点
 平面 1 : 33287 点
 平面 2 : 33523 点
 平面 3 : 33131 点
 平面 4 : 30702 点
 平面 5 : 25266 点
 平面 6 : 19403 点
 平面 7 : 13757 点
 平面 8 : 8378 点
 平面 9 : 2805 点
相異なる平面数: 15

30万個の3点組が、たった 15 枚の平面の上にしか存在しません。assert が一度も落ちていないので、恒等式も成立しています。3次元のモンテカルロ積分にこれを使えば、結果は静かに壊れます。

まだ現役の LCG

「昔の話でしょう」で済まないのが厄介なところです。Java の java.util.Random は公式 javadoc に次のように書かれています。

The class uses a 48-bit seed, which is modified using a linear congruential formula.

シードは 48 ビット、更新式は (seed * 0x5DEECE66D + 0xB) & ((1 << 48) - 1) とjavadoc 本文に定数まで明記されています。同 javadoc は「Instances of java.util.Random are not cryptographically secure」と述べ、SecureRandom を使うよう促しています。C の rand() も多くの libc 実装が LCG です。

Mersenne Twister とその後継

MT19937 の性質

Mersenne Twister（MT19937）は 1998 年に松本眞・西村拓士が発表した生成器です。論文タイトルがそのまま性質を表しています。「Mersenne twister: a 623-dimensionally equidistributed uniform pseudo-random number generator」（ACM Transactions on Modeling and Computer Simulation, Vol.8 No.1, 1998）。

• 周期は 2^19937 - 1（メルセンヌ素数）
• 623 次元まで均等分布（32 ビット精度で）。RANDU の3次元での惨状とは比べものになりません
• 作業領域は 624 語（32 ビット x 624 = 19968 ビット）

品質が良く速く、実装が広く配布されたため、Python・Ruby・PHP・R・MATLAB など多数の言語の標準乱数になりました。Python 公式ドキュメントは「Python uses the Mersenne Twister as the core generator. It produces 53-bit precision floats and has a period of 2^19937-1」と明記しています。

一方で、MT の公式ページ（広島大学・松本研）には次の一文があります。

Mersenne Twister is basically for Monte-Carlo simulations - it is not cryptographically secure "as is".

624語の出力から内部状態を復元する

なぜ暗号用途に使えないのか。答えは出力から内部状態が完全に逆算できるからです。

MT19937 は内部状態の 1 語を取り出すとき、tempering と呼ばれる可逆な変換をかけて出力します。

y1 = y  ^ (y  >> 11)
y2 = y1 ^ ((y1 << 7)  & 0x9D2C5680)
y3 = y2 ^ ((y2 << 15) & 0xEFC60000)
y4 = y3 ^ (y3 >> 18)         ← これが出力

各段はビット単位の全単射なので、逆写像（untempering）が存在します。624 語ぶん逆写像を適用すれば、内部状態配列 mt[0..623] がそのまま手に入ります。実際にやってみます。

import random
 
def unshift_right(y, shift):
    x = y
    for _ in range(32 // shift + 1):
        x = y ^ (x >> shift)
    return x & 0xFFFFFFFF
 
def unshift_left_mask(y, shift, mask):
    x = y
    for _ in range(32 // shift + 1):
        x = y ^ ((x << shift) & mask)
    return x & 0xFFFFFFFF
 
def untemper(y):
    y = unshift_right(y, 18)
    y = unshift_left_mask(y, 15, 0xEFC60000)
    y = unshift_left_mask(y, 7, 0x9D2C5680)
    y = unshift_right(y, 11)
    return y
 
rng = random.Random()                                   # OSエントロピーで初期化
observed = [rng.getrandbits(32) for _ in range(624)]    # 624語だけ観測する
 
state = tuple(untemper(y) for y in observed)
clone = random.Random()
clone.setstate((3, state + (624,), None))               # 復元した状態を注入
 
real = [rng.getrandbits(32) for _ in range(5)]
pred = [clone.getrandbits(32) for _ in range(5)]
print("観測した出力数:", len(observed))
print("実際の次の5個:", real)
print("予測した次の5個:", pred)
print("一致:", real == pred)
 
ok = all(rng.getrandbits(32) == clone.getrandbits(32) for _ in range(100000))
print("さらに100000個先まで完全一致:", ok)
print("random() 実際:", [round(rng.random(), 12) for _ in range(3)])
print("random() 予測:", [round(clone.random(), 12) for _ in range(3)])

観測した出力数: 624
実際の次の5個: [3919739630, 4218073838, 2042088880, 2508544555, 780072704]
予測した次の5個: [3919739630, 4218073838, 2042088880, 2508544555, 780072704]
一致: True
さらに100000個先まで完全一致: True
random() 実際: [0.333743340511, 0.316364599078, 0.475621907597]
random() 予測: [0.333743340511, 0.316364599078, 0.475621907597]

シードを一切知らずに、出力を 624 個観測しただけで、以降 10 万個の出力が 1 個も外れずに一致しました。random.random() の浮動小数点値まで完全に同じです。

観測にはシードの推測すら要りません。「ゲームのガチャの結果」「くじの当選番号」「発行済みのトークン」など、同じ生成器から出た値を十分な個数集められるだけで成立します。MT を使ってセッション ID を発行しているサービスなら、自分でログインを繰り返して自分のセッション ID を集めるだけで、他人のセッション ID が計算できてしまう、という構図です。

xorshift / xoshiro / PCG

MT の弱点は暗号強度だけではありません。状態が 19968 ビットと大きく、キャッシュに優しくない。線形性が強く、TestU01 の線形複雑度テスト（LinearComp）に落ちる。そこで 2000 年代以降、もっと小さく速い生成器が提案されました。

• xorshift（Marsaglia, 2003）: シフトと XOR だけ。極めて高速
• xorshift128+（Vigna）: xorshift に加算を足したもの。V8 が採用（後述）
• xoshiro / xoroshiro（Blackman & Vigna）: 出力に回転と加算・乗算の「スクランブラ」をかける系列。xoshiro256++ が Vigna の第一推奨、32 ビット用途には xoshiro128++
• PCG（O'Neill, 2014）: LCG の状態に「置換」出力関数（permuted congruential）をかぶせる。状態 64 ビットで 32 ビット出力の PCG32 が標準

これらが LCG とどう違うのか、同じ「下位ビットの周期」で測ってみます。

function lcg32(seed) {
  let s = seed >>> 0;
  return () => { s = (Math.imul(1664525, s) + 1013904223) >>> 0; return s; };
}
 
// xoshiro128++ 1.0 (Blackman & Vigna) 状態128ビット / 周期 2^128 - 1
function xoshiro128pp(a, b, c, d) {
  const rotl = (x, k) => ((x << k) | (x >>> (32 - k))) >>> 0;
  let s0 = a >>> 0, s1 = b >>> 0, s2 = c >>> 0, s3 = d >>> 0;
  return () => {
    const result = (rotl((s0 + s3) >>> 0, 7) + s0) >>> 0;
    const t = (s1 << 9) >>> 0;
    s2 ^= s0; s3 ^= s1; s1 ^= s2; s0 ^= s3; s2 ^= t;
    s3 = rotl(s3, 11);
    s0 >>>= 0; s1 >>>= 0; s2 >>>= 0; s3 >>>= 0;
    return result;
  };
}
 
// PCG32 (O'Neill) 状態64ビット / 出力32ビット
function pcg32(seed, seq = 1n) {
  const MASK = (1n << 64n) - 1n, MULT = 6364136223846793005n;
  const inc = ((seq << 1n) | 1n) & MASK;
  let state = 0n;
  const step = () => { state = (state * MULT + inc) & MASK; };
  step(); state = (state + seed) & MASK; step();
  return () => {
    const old = state; step();
    const xorshifted = Number((((old >> 18n) ^ old) >> 27n) & 0xFFFFFFFFn);
    const rot = Number(old >> 59n);
    return ((xorshifted >>> rot) | (xorshifted << ((-rot) & 31))) >>> 0;
  };
}

生成器                           bit0     bit1     bit2     bit10
LCG (a=1664525, m=2^32)       2        4        8        2048
xoshiro128++                  20000超   20000超   20000超   20000超
PCG32                         20000超   20000超   20000超   20000超
 
LCG の bit0 先頭32個         : 01010101010101010101010101010101
xoshiro128++ の bit0 先頭32個 : 11100001100101100010000001000000
PCG32 の bit0 先頭32個        : 10010000100011001111101010010010

xoshiro128++ と PCG32 では、最下位ビットにも短い周期が現れません。「下位ビットは使うな」という LCG 時代の民間伝承は、これらの生成器には当てはまらない、ということです。

ただし Vigna 自身がページで明言しているとおり、これらは cryptographically secure な生成器ではありません。同ページは暗号用途には ChaCha20 や AES といったストリーム暗号を使えと書いています。速いシミュレーション用の生成器の系譜であって、CSPRNG ではないのです。

Math.random() の中身を V8 のソースで確かめる

仕様は品質を何も規定していない

まず ECMAScript 仕様（21.3.2.28 Math.random）を見ます。

This function returns a Number value with positive sign, greater than or equal to +0 but strictly less than 1, chosen randomly or pseudo randomly with approximately uniform distribution over that range, using an implementation-defined algorithm or strategy. Each Math.random function created for distinct realms must produce a distinct sequence of values from successive calls.

規定しているのは「範囲」と「おおよそ一様」と「realm ごとに別の系列」だけ。アルゴリズムは implementation-definedで、品質・予測不可能性・周期については一言もありません。つまり Math.random() が安全かどうかは仕様上の保証がゼロです。

V8 の実装を読む

では実装はどうか。V8 のソース src/base/utils/random-number-generator.h の冒頭コメントが明快です。

This class uses a 64-bit seed, which is passed through MurmurHash3 to create two 64-bit state values. This pair of state values is then used in xorshift128+. The resulting stream of pseudo-random numbers has a period length of 2^128-1.

同ファイルの実装本体も短いものです。

static inline uint64_t XorShift128(uint64_t* state0, uint64_t* state1) {
  uint64_t s1 = *state0;
  uint64_t s0 = *state1;
  *state0 = s0;
  s1 ^= s1 << 23;
  s1 ^= s1 >> 17;
  s1 ^= s0;
  s1 ^= s0 >> 26;
  *state1 = s1;
  return s0 + s1;
}

Math.random() 本体は Torque で書かれています（src/builtins/math.tq）。

macro RandomToDouble(random: uint64): float64 {
  // 64ビット出力の下位11ビットを落として [0, 2^53) の整数値を得る
  const random0to2pow53: uint64 = random >>> Convert<uint64>(11);
  const randomDouble: float64 = ChangeUint64ToFloat64(random0to2pow53);
  // 2^53 (= 9007199254740992.0) で割って [0,1) に写す
  return randomDouble / 9007199254740992.0;
}

ここから分かることが3つあります。

1. 返る値は k / 2^53（k は 0 以上 2^53 未満の整数）。取りうる値は 2^53 通りです
2. 64 ビット出力の下位11ビットを捨てて上位53ビットを使う。xorshift128+ は「下位ビットの線形複雑度が低い」ことが Vigna 自身によって指摘されており、上位ビットを使う設計はその弱点を避けています
3. 64 ビット環境では呼び出しごとにその場で状態を進める（32 ビット環境のみ kCacheSize = 64 のキャッシュを使い、src/numbers/math-random.cc を見るとキャッシュは末尾から先頭に向かって埋められる）

1 番を実際に確かめます。

const xs = [Math.random(), Math.random(), Math.random()];
console.log(xs.join(' '));
const k = xs.map(x => x * 9007199254740992);
console.log('x * 2^53 が整数か:', k.every(Number.isInteger), k.join(' '));

0.7939112874678715 0.5254990606499601 0.3518347850388237
x * 2^53 が整数か: true 7150917156811074 4733274747453412 3169046013593650
0.7939112874678715 0.5254990606499601 0.3518347850388237
x * 2^53 が整数か: true 7150917156811074 4733274747453412 3169046013593650
0.7939112874678715 0.5254990606499601 0.3518347850388237
x * 2^53 が整数か: true 7150917156811074 4733274747453412 3169046013593650

0.5784274652605829 0.7327206334176868 0.8880500555231851
0.6726087647619555 0.3802654634721817 0.13146518767246196

x * 2^53 が常に整数であること、そして V8 フラグ --random_seed=42 を与えると Math.random() が完全に再現可能になることが確認できました。ソースの if (v8_flags.random_seed != 0) の分岐がそのまま観測できたわけです。浮動小数点の刻み幅が気になる方は浮動小数点数とIEEE 754入門も合わせてどうぞ。

CSPRNG に求められるもの

CSPRNG が満たすべき性質は、大きく2つに整理できます。NIST SP 800-90A Rev.1（Recommendation for Random Number Generation Using Deterministic Random Bit Generators, 2015年6月）は DRBG（Deterministic Random Bit Generator）の要件として次の2つを定義しています。

• backtracking resistance（後戻り耐性）: 現在の内部状態が漏れても、それ以前に出力したビット列を復元できない
• prediction resistance（予測耐性）: 現在の内部状態が漏れても、その後に出力するビット列を予測できない（実現には新しいエントロピーの再投入が必要）

前者は「状態危殆化後方安全性（forward secrecy）」とも呼ばれます。サーバが侵害されてメモリをダンプされたときに、過去に発行したセッショントークンまで芋づるで復元されない、という保証です。LCG も MT も、状態が分かれば逆算で過去に遡れるので、この性質を満たしません。

もうひとつ、理論的な定式化として次ビット予測不可能性（next-bit test）があります。出力の先頭 k ビットを見て k+1 ビット目を 1/2 より有意に高い確率で当てられる多項式時間アルゴリズムが存在しない、という条件です。

実装としては、ブロック暗号やハッシュ関数を「進む一方の」構造で回す形になります。SP 800-90A が規定するのは Hash_DRBG、HMAC_DRBG、CTR_DRBG の3方式で、Linux カーネルや BSD 系は ChaCha20 ベースの構成を使っています。同じ「一方向に進む」性質を秘密の保存側で使うのがパスワードハッシュで、こちらはArgon2 によるパスワードハッシュにまとめています。

OS のエントロピー源

CSPRNG も PRNG である以上、最初のシードだけは外からもらう必要があります。それを担うのが OS のエントロピープールです。

getrandom(2) と /dev/urandom

Linux では 3 つの入口があります。man-pages の記述を確認します。

getrandom(2) の man ページ:

By default, getrandom() draws entropy from the urandom source (i.e., the same source as the /dev/urandom device). If the urandom source has been initialized, reads of up to 256 bytes will always return as many bytes as requested and will not be interrupted by signals.

random(4) の man ページ:

The /dev/random interface is considered a legacy interface, and /dev/urandom is preferred and sufficient in all use cases, with the exception of applications which require randomness during early boot time; for these applications, getrandom(2) must be used instead, because it will block until the entropy pool is initialized.

つまりアプリケーションが選ぶべきは getrandom(2)で、/dev/urandom はほぼ同等、/dev/random は「legacy interface」です。

/dev/random のブロッキングはどう変わったか

古い記事には「/dev/random はエントロピーが尽きるとブロックするから、サーバでは使うな」と書かれています。これは過去の話です。random(4) の man ページに明記されています。

Since Linux 5.6, the O_NONBLOCK flag is ignored as /dev/random will no longer block except during early boot process.

さらに、random.c のメンテナである Jason Donenfeld による 5.17 / 5.18 の作業レポートには、より踏み込んだ記述があります。

The most significant outward-facing change is that /dev/random and /dev/urandom are now exactly the same thing, with no differences between them at all, thanks to their unification in random: block in /dev/urandom Now the only way to extract "insecure" randomness is by explicitly using getrandom(GRND_INSECURE)

中身は BLAKE2s + ChaCha

同レポートによれば、5.17 で SHA-1 が BLAKE2s に置き換えられ、エントロピープールへの入力の前方安全性が 80 ビットから 128 ビットに改善されました。抽出はこう書かれています。

τ         = blake2s(key=last_key, entropy1 ‖ entropy2 ‖ … ‖ entropyN)
κ1        = blake2s(key=τ, RDSEED ‖ 0x0)
κ2        = blake2s(key=τ, RDSEED ‖ 0x1)
last_key  = κ1
crng_seed = κ2

κ1 がプールの再初期化（前方安全性）に、κ2 が ChaCha ベースの crng のシードになります。割り込みからのエントロピー混合（fast_mix()）は SipHash-1-x / HalfSipHash-1-x に置き換えられました。

起動直後・VM・コンテナの問題

エントロピーが足りないのは、ほぼ起動直後の数秒だけです。ここで seed を取ってしまうと予測可能な鍵が生まれます。歴史的には、組み込み機器が起動直後に生成した SSH ホスト鍵が衝突する事故が知られています。

Linux 5.4 でこの問題への対策が入りました。同レポートいわく、他のエントロピー源で初期化されていない場合、カーネルは RDTSC のサイクルカウンタのジッタを使って 1 秒程度で自力でシードを作ります（haveged に似た手法）。

それでも、VM のクローンやコンテナイメージから起動したインスタンスは注意が必要です。スナップショットから復元すると、複製されたインスタンス同士が同じ内部状態を持ちうるからです。Linux には VM 世代 ID を検出してプールを再初期化する仕組みがありますが、対応はハイパーバイザ依存です。

確認用のコマンドを挙げておきます（筆者環境は macOS のため、以下の実行結果は本記事には載せていません）。

# 利用可能なエントロピー（ビット）。0 から 4096 の範囲
cat /proc/sys/kernel/random/entropy_avail
 
# プールのサイズ
cat /proc/sys/kernel/random/poolsize
 
# CPU が RDRAND / RDSEED を持っているか
grep -o -E 'rdrand|rdseed' /proc/cpuinfo | sort -u

RDRAND と RDSEED

Intel の DRNG 実装ガイドは、2つの命令をはっきり区別しています。

• RDRAND: SP 800-90A 準拠の DRBG から値を取る。実体は「AES を CTR モードで回すハードウェア CSPRNG」
• RDSEED: SP 800-90B / C 準拠のエントロピー源（ENRNG）からシード用の値を取る

同ガイドは RDRAND について「attempt 10 retries in a tight loop」（キャリーフラグが立たない場合は10回までリトライ）を推奨しています。

Linux カーネルがこれをどう扱っているかが重要です。前掲レポートによれば、RDSEED はプールを構成する暗号学的ハッシュ関数への入力のひとつとして混ぜられます。つまり CPU の乱数命令にバックドアがあったとしても、他のエントロピー源が生きていれば出力は汚染されません。「CPU を信じるかどうか」の議論に対する、設計としての答えです。

言語ごとの実際

一次ソースで確認できた範囲をまとめます。

JavaScript / Node.js

MDN は Crypto.getRandomValues() について、TypedArray の byteLength が 65536 バイトを超えると QuotaExceededError になること、Float32Array などは受け付けないことを明記しています。また「Do not use Math.random() for cryptographic purposes」と警告しています。

Node.js の crypto.randomBytes(size) は size が 2^31 - 1 以下、crypto.randomInt(min, max) は範囲が 2^48 未満という制約があり、ドキュメントに「This implementation avoids modulo bias」とあります。crypto.randomUUID() は RFC 4122 の v4 を返し、既定では128 個ぶんの乱数をキャッシュします（disableEntropyCache: true で無効化）。Node.js 26.1.0 / 24.16.0 では RFC 9562 の v7 を返す crypto.randomUUIDv7() も追加されています。ID 設計そのものは UUID と ULID 入門 にまとめてあります。

Python

random は MT19937 で、公式ドキュメントに「The pseudo-random generators of this module should not be used for security purposes. For security or cryptographic uses, see the secrets module.」と警告があります。random.SystemRandom は os.urandom() を使うので安全側です。

secrets は「generating cryptographically strong random numbers suitable for managing data such as passwords, account authentication, security tokens」のためのモジュールで、token_bytes / token_hex / token_urlsafe はバイト数を省略すると DEFAULT_ENTROPY を使います。トークン長については「As of 2015, it is believed that 32 bytes (256 bits) of randomness is sufficient」と書かれています。secrets.randbelow() はモジュロバイアスのない整数を返し、secrets.compare_digest() はタイミング攻撃を避ける定数時間比較です。

Go

Go は乱数まわりの整理を段階的に進めてきました。手元の Go 1.25.6 で挙動を確かめます。

package main
 
import (
	crand "crypto/rand"
	"encoding/hex"
	"fmt"
	"math/rand"
	randv2 "math/rand/v2"
)
 
func main() {
	fmt.Println("math/rand 先頭3個 (自動シード):", rand.Intn(1000), rand.Intn(1000), rand.Intn(1000))
	fmt.Println("math/rand/v2 先頭3個:", randv2.IntN(1000), randv2.IntN(1000), randv2.IntN(1000))
 
	r := rand.New(rand.NewSource(42))
	fmt.Println("rand.New(NewSource(42)):", r.Intn(1000), r.Intn(1000), r.Intn(1000))
	r2 := randv2.New(randv2.NewPCG(1, 2))
	fmt.Println("rand/v2 PCG(1,2):", r2.IntN(1000), r2.IntN(1000), r2.IntN(1000))
 
	b := make([]byte, 16)
	crand.Read(b)
	fmt.Println("crypto/rand.Read 16バイト:", hex.EncodeToString(b))
	fmt.Println("crypto/rand.Text():", crand.Text())
}

math/rand 先頭3個 (自動シード): 457 864 883
math/rand/v2 先頭3個: 813 114 342
rand.New(NewSource(42)): 305 987 668
rand/v2 PCG(1,2): 769 616 784
crypto/rand.Read 16バイト: 3f722dc2c51d63a64ccda811b9421581
crypto/rand.Text(): XM5YGYV4ARV3MOXDYXIGV2MTO7
 
math/rand 先頭3個 (自動シード): 669 501 81
math/rand/v2 先頭3個: 183 289 499
rand.New(NewSource(42)): 305 987 668
rand/v2 PCG(1,2): 769 616 784
crypto/rand.Read 16バイト: 2e5779c2934d5048027bfe11c1e5bed0
crypto/rand.Text(): EXABPKT2HLCYU4GSW6L2RH57X5

math/rand 先頭3個 (自動シード): 81 887 847
math/rand/v2 先頭3個: 324 65 768
 
math/rand 先頭3個 (自動シード): 81 887 847
math/rand/v2 先頭3個: 115 779 588

観測できたことを整理します。

• トップレベルの math/rand は実行のたびに違う値を返します。math/rand の godoc に「If Seed is not called, the generator is seeded randomly at program startup.」「Deprecated: As of Go 1.20 there is no reason to call Seed with a random value.」とあるとおりです
• GODEBUG=randautoseed=0 を付けると math/rand は決定論的になり（2回とも 81 887 847）、math/rand/v2 は影響を受けません（毎回違う）。これは v2 の「The global generator is unconditionally randomly seeded with no fixed sequence」という設計どおりです
• 明示的にシードした rand.New(rand.NewSource(42)) と randv2.NewPCG(1, 2) は完全に再現可能です

math/rand/v2 は Go 1.22 で追加された標準ライブラリ初の "v2" パッケージで、リリースノートには生成器として ChaCha8 と PCG が挙げられています。さらに「As of Go 1.22, math/rand's top-level functions (when not explicitly seeded) and the Go runtime also use ChaCha8 for randomness.」とあります。つまり Go 1.22 以降、シード指定なしの math/rand は暗号学的に強い生成器を裏で使っていることになります。

crypto/rand 側は、Linux では getrandom(2)（3.17 未満のカーネルでは /dev/urandom）、macOS / iOS / OpenBSD では arc4random_buf(3)、Windows では ProcessPrng API を使うと godoc に明記されています。crypto/rand.Read は「It never returns an error, and always fills b entirely」、Go 1.24 で追加された crypto/rand.Text() は「at least 128 bits of randomness」を持つ RFC 4648 base32 文字列を返します。上の実行結果の 26 文字がそれです。

PHP

PHP は歴史的に事故が多かった言語です。手元の PHP 8.5.10 で確かめます。

<?php
mt_srand(42);
echo "mt_srand(42) 後の mt_rand(): ", mt_rand(), " ", mt_rand(), " ", mt_rand(), PHP_EOL;
srand(42);
echo "srand(42) 後の rand():       ", rand(), " ", rand(), " ", rand(), PHP_EOL;
echo "mt_getrandmax(): ", mt_getrandmax(), " / getrandmax(): ", getrandmax(), PHP_EOL;
echo "random_int(1, 100) 5回:      ";
for ($i = 0; $i < 5; $i++) echo random_int(1, 100), " ";
echo PHP_EOL;
echo "bin2hex(random_bytes(16)):   ", bin2hex(random_bytes(16)), PHP_EOL;

mt_srand(42) 後の mt_rand(): 804318771 1710563033 2041643438
srand(42) 後の rand():       804318771 1710563033 2041643438
mt_getrandmax(): 2147483647 / getrandmax(): 2147483647
random_int(1, 100) 5回:      58 97 88 8 58
bin2hex(random_bytes(16)):   a5fe51170f5944da1a4b6e7942e49f80

srand(42) 後の rand() と mt_srand(42) 後の mt_rand() がまったく同じ値を返しました。マニュアルどおり「PHP 7.1.0 以降、rand() は mt_rand() のエイリアス」です。mt_getrandmax() は 2147483647、つまり 2^31 - 1 でした。

random_int() については、マニュアルが OS ごとの乱数源（Linux では getrandom() と /dev/urandom、macOS では CCRandomGenerateBytes() など）を列挙し、取得に失敗した場合は Random\RandomException を投げると定めています。

この「PHP の乱数の弱さ」を体系的に攻撃した研究が、Argyros と Kiayias による USENIX Security '12 の論文「I Forgot Your Password: Randomness Attacks Against PHP Applications」です。アブストラクトはパスワードリセットトークンの予測に焦点を当て、PHP のコア乱数生成器を予測または脱ランダム化することでアカウントを乗っ取れることを示しています。「トークンに mt_rand() を使うな」は、机上の理屈ではなく実証済みの攻撃です。

実務での落とし穴

Math.random() で作ったトークンの実力

よく見かける書き方の中身を測ります。

const N = 1_000_000;
const lens = new Map();
const chars = new Set();
for (let i = 0; i < N; i++) {
  const t = Math.random().toString(36).slice(2);
  lens.set(t.length, (lens.get(t.length) || 0) + 1);
  if (i < 200000) for (const c of t) chars.add(c);
}

Math.random().toString(36).slice(2) の長さ分布 (100万回):
  長さ  7: 6 回 (0.001%)
  長さ  8: 209 回 (0.021%)
  長さ  9: 7317 回 (0.732%)
  長さ 10: 263311 回 (26.331%)
  長さ 11: 704589 回 (70.459%)
  長さ 12: 23956 回 (2.396%)
  長さ 13: 601 回 (0.060%)
  長さ 14: 11 回 (0.001%)
  使われた文字種: 36
  例: s3dqvk91f7 3rbeek9srsb kpo284kwjbm
  2つ連結: oa02drog4ag31oo40h9ek (見た目 21 文字)
 
crypto.randomBytes(32).toString("base64url"):
  例: meWGbJn3oID1vVRirHnfhMEqidX2fI3g1MO0AV2Qvs8 (長さ 43 )

問題が3つ見えます。

1. 長さが一定しない。7 文字のものが 100 万回中 6 回出ました。最短ケースは探索空間が桁で小さくなります
2. 見た目の文字数がエントロピーではない。11 文字でも中身は 53 ビット以下です。36 文字種 x 11 文字なら理論上 56.9 ビットぶんの見た目ですが、元が 2^53 通りなので53 ビットを超えることは絶対にありません
3. 連結しても増えない。2 個つなげて 21 文字にしても、内部状態は 128 ビットのままです。同じ生成器から出た値をつないでも独立な乱数にはなりません

そして最大の問題は、これらの数字以前に予測可能性です。crypto.randomBytes(32) は 256 ビットで、base64url にして 43 文字。トークンはこちらで作ってください。生成したトークンをどう保持するかについてはCookie とセッション、SameSite の実務を参照してください。

モジュロバイアス

「0 から n-1 の整数がほしい」ときに random_byte % n と書くのは、n が 256 の約数でないかぎり偏ります。実測します。

import { randomBytes, randomInt } from 'node:crypto';
 
// 1バイト(0..255) を n で割った余りの理論出現回数
function theory(n) {
  const c = new Array(n).fill(0);
  for (let b = 0; b < 256; b++) c[b % n]++;
  return c;
}
 
// 棄却法: はみ出す値を捨ててから余りを取る
const n = 200;
const limit = 256 - (256 % n);   // 200
// b が limit 以上なら捨てて引き直す

n=10: 1バイト % n の理論出現回数 max=26 min=25 比=1.040 (最頻値は最小値の4.0%出やすい)
n=100: 1バイト % n の理論出現回数 max=3 min=2 比=1.500 (最頻値は最小値の50.0%出やすい)
n=200: 1バイト % n の理論出現回数 max=2 min=1 比=2.000 (最頻値は最小値の100.0%出やすい)
 
[実測] randomBytes(1)[0] % 200 を 6000000 回 (期待値 30000)
  0..55  の平均出現数: 46919.4
  56..199 の平均出現数: 23420.2
  比: 2.0034  (理論値 2.0000)
  例: 0 -> 46529, 1 -> 46762, 100 -> 23205, 199 -> 23567
 
[実測] 棄却法 (b >= 200 を捨てる) 同回数
  0..55 平均: 30013.8  56..199 平均: 29994.7  比: 1.0006
  棄却率: 21.88%
 
[実測] crypto.randomInt(200) を 2000000 回
  0..55 平均: 10001.4  56..199 平均: 9999.5  比: 1.0002

600 万回の実測で、0 から 55 の値は 56 から 199 の値のちょうど 2 倍出ました（比 2.0034、理論値 2.0）。乱数源は暗号学的に強い crypto.randomBytes です。乱数源が完璧でも、使い方を間違えれば分布は壊れます。

正しい直し方が棄却法（rejection sampling）です。乱数の範囲を n の倍数に切り詰め、はみ出た値は捨てて引き直します。実測では比が 1.0006 まで戻り、代償として 21.88% の棄却率が発生しました。

Node.js の crypto.randomInt() は内部でこれをやっています。ソース（lib/internal/crypto/random.js）のコメントが親切です。

// For (x % range) to produce an unbiased value greater than or equal to 0 and
// less than range, x must be drawn randomly from the set of integers greater
// than or equal to 0 and less than randLimit.
const randLimit = RAND_MAX - (RAND_MAX % range);

自分で書くなら、32 ビット乱数から作るのが実用的です。

import { webcrypto as crypto } from 'node:crypto';
 
function randomBelow(n) {
  if (!Number.isInteger(n) || n <= 0 || n > 0x100000000) throw new RangeError('n');
  const limit = Math.floor(0x100000000 / n) * n;  // 2^32 を n の倍数に切り詰める
  const buf = new Uint32Array(1);
  let x;
  do {
    crypto.getRandomValues(buf);
    x = buf[0];
  } while (x >= limit);                            // はみ出したぶんは捨てる
  return x % n;
}

n ごとの棄却率（2^32 を使う場合の理論値）
  n=         6  棄却率 0.000000%
  n=        10  棄却率 0.000000%
  n=        52  棄却率 0.000001%
  n=       100  棄却率 0.000002%
  n=3000000000  棄却率 30.150807%

32 ビットから作れば、実用的な n では棄却率は実質ゼロです。1 バイトから作ろうとするから 21.88% も捨てる羽目になるのであって、広い範囲から取れば棄却法のコストはほぼ消えます。

シャッフルは Fisher-Yates を使う

配列をシャッフルするとき、arr.sort(() => Math.random() - 0.5) は使ってはいけません。比較関数が推移律を満たさないため、結果はソートアルゴリズムの実装依存になり、しかも大きく偏ります。n=6 の配列を 20 万回シャッフルして、各値が各位置に来た回数を数えます。

function sortShuffle(arr) {
  return arr.slice().sort(() => Math.random() - 0.5);
}
 
function fisherYates(arr) {
  const a = arr.slice();
  for (let i = a.length - 1; i > 0; i--) {
    const j = Math.floor(Math.random() * (i + 1));
    [a[i], a[j]] = [a[j], a[i]];
  }
  return a;
}

== sort(() => Math.random() - 0.5)
値\位置        0       1       2       3       4       5
   0      57271   32041   20298   22392   28870   39128
   1      21469   53650   38352   39791   36059   10679
   2      28812   28330   36494   41617   32883   31864
   3      37984   36176   30296   34554   32975   28015
   4      24783   26404   27312   38058   45945   37498
   5      29681   23399   47248   23588   23268   52816
値0が位置0に残った割合: 28.64%  (理想 16.67%)
最大偏差: 71.81%
 
== Fisher-Yates
値\位置        0       1       2       3       4       5
   0      33223   33374   33655   33137   33484   33127
   1      33583   33257   33325   33486   33146   33203
   2      33332   33571   33122   33448   33162   33365
   3      33337   33422   33104   33134   33590   33413
   4      33186   32887   33470   33652   33313   33492
   5      33339   33489   33324   33143   33305   33400
値0が位置0に残った割合: 16.61%  (理想 16.67%)
最大偏差: 1.34%

一目瞭然です。sort 版では先頭の要素が先頭に残る確率が 28.64%（理想は 16.67%）で、期待値からの最大偏差は 71.81%。Fisher-Yates は最大偏差 1.34% に収まりました。V8 の Array.prototype.sort は TimSort なので、この偏りのパターンはソートアルゴリズムの内部構造がそのまま漏れているものです。ソートアルゴリズムそのものはソートアルゴリズム入門にまとめてあります。

さらに、シャッフルには状態空間の問題もあります。

52!        = 80658175170943878571660636856403766975289505440883277824000000000000
log2(52!)  = 225.58 ビット

52 枚のシャッフルには 225.58 ビットの乱数が必要です。ところが Math.random() の内部状態は 128 ビットしかありません。到達できる並べ方は理論上 52! のうち 4.2 x 10^-30 にすぎません。32 ビットシードの LCG なら 5.3 x 10^-59。MT19937 は状態 19937 ビットあるので 225.58 ビットを楽に上回りますが、シードを 32 ビット整数で与えたら結局 2^32 通りに戻ります。オンラインのカードゲームで実際に問題になった論点です。

テストのためのシード固定

再現性が必要なテストでは、意図してシードを固定した PRNG を使います。CSPRNG は再現できないので、ここは用途が逆になります。

// テスト・シミュレーション専用。秘密の生成には絶対に使わないこと
function mulberry32(seed) {
  let a = seed >>> 0;
  return function () {
    a = (a + 0x6D2B79F5) >>> 0;
    let t = a;
    t = Math.imul(t ^ (t >>> 15), t | 1);
    t ^= t + Math.imul(t ^ (t >>> 7), t | 61);
    return ((t ^ (t >>> 14)) >>> 0) / 4294967296;
  };
}

言語標準の仕組みもあります。Python は random.Random(42)、Go は rand.New(rand.NewSource(42)) や randv2.New(randv2.NewPCG(1, 2))、PHP は mt_srand(42)。前掲の実行結果のとおり、いずれも同じシードから同じ数列が出ます。V8 なら node --random_seed=42 で Math.random() 自体を固定できます（これも上で実測済みです）。

UUIDv4 の乱数品質

RFC 9562 は UUIDv4 について、ランダム部が合計 122 ビットであることを定めています。そして 6.9 節「Unguessability」でこう述べています。

Implementations SHOULD utilize a cryptographically secure pseudorandom number generator (CSPRNG) to provide values that are both difficult to predict

SHOULD であって MUST ではない点に注意してください（CSPRNG が使えない実行環境を例外として認めています）。実装によっては Math.random() ベースのものが混ざりうる、ということです。ブラウザや Node.js の crypto.randomUUID() は CSPRNG を使うと明記されているので、まずこちらを使ってください。

速度は言い訳にならない

「CSPRNG は遅いから Math.random() で」という主張を測ってみます。

Math.random() 1値ずつ                                      449.1 ms     22.27 M値/秒
crypto.getRandomValues() 1値ずつ                          6074.1 ms      0.33 M値/秒
crypto.getRandomValues() 64KBまとめ取り                       39.9 ms    250.44 M値/秒
crypto.randomBytes(65536) まとめ取り                          44.2 ms    226.09 M値/秒
crypto.randomInt(100)                                   254.2 ms      3.93 M値/秒
crypto.randomUUID()                                     146.1 ms      6.85 M値/秒

読み取れることは次のとおりです。

• 1 値ずつ呼ぶと CSPRNG は約 67 倍遅い（22.27 対 0.33 M値/秒）。呼び出しごとのオーバーヘッドが支配的です
• まとめて取ると逆転して 11 倍速い（250.44 対 22.27 M値/秒）。ChaCha 系のストリーム生成はバルクで非常に速く、Math.random() の呼び出しオーバーヘッドのほうが重くなります
• crypto.randomUUID() は毎秒 685 万個。トークン生成が律速になる場面は現実にはまずありません

秘密の生成でまとめ取りできない場面はほぼないので、速度は Math.random() を選ぶ理由になりません。逆に、モンテカルロ法で毎秒何億個も乱数がいる、といった場面では Math.random() や xoshiro / PCG が正解です。用途で選び分けるのが本筋です。

乱数の品質検定

自作の PRNG や、既存生成器の評価に使われる検定スイートを挙げておきます。

• NIST SP 800-22 Rev.1a（2010年4月）「A Statistical Test Suite for Random and Pseudorandom Number Generators for Cryptographic Applications」。暗号用途向けの統計検定集で、周波数検定、ラン検定、累積和検定などを含みます。NIST は 2022年4月19日付の planning note で「NIST has decided to REVISE it」としており、改訂予定です
• Dieharder: Marsaglia の Diehard を拡張したテストスイート（Robert G. Brown, Duke University）
• TestU01（L'Ecuyer & Simard）: SmallCrush / Crush / BigCrush の3段階のバッテリ。現在の事実上の標準で、V8 のソースにも「NOTE: Any changes to the algorithm must be tested against TestU01.」というコメントが入っています

これらの使いどころには、はっきりした限界があります。SP 800-22 自身が、統計検定は暗号解析の代わりにはならない（"cannot serve as a substitute for cryptanalysis"）と述べています。

理由は本記事の最初の実測が示しています。LCG の最下位ビットは 0,1,0,1,... と並び、0 と 1 の出現頻度は完全に五分五分です。単純な頻度検定は通ります。それでも次の値は 100% 予測できます。統計検定を通ることは、CSPRNG であることの必要条件であって十分条件ではありません。

まとめ

• PRNG は決定論的アルゴリズム。シードが同じなら同じ数列が出る。「統計的に均等」と「予測できない」はまったく別の性質
• LCG は m が 2 の冪のとき、下から k 番目のビットの周期が 2 の (k+1) 乗になる。実測でも bit0 の周期は 2、bit13 の周期は 16384 と理論値に完全一致した。RANDU の3点組は 30 万点すべてが 15 枚の平面にしか乗らなかった
• MT19937 は周期 2^19937-1・623 次元均等分布と品質は高いが、624 語の出力から内部状態を完全復元できる。実測では以降 10 万個の出力が 1 個も外れずに一致した。Python random、PHP mt_rand() はこれ
• xoshiro128++ / PCG32 は下位ビットにも短い周期が現れない。ただし Vigna 自身が「cryptographically secure ではない」と明言している
• Math.random() は ECMAScript 仕様が implementation-defined としており、品質保証はゼロ。V8 は xorshift128+（状態128ビット）で、64 ビット出力の下位11ビットを捨てて k / 2^53 を返す。node --random_seed=42 で再現可能になることを実測で確認した
• CSPRNG の要件は backtracking resistance と prediction resistance（NIST SP 800-90A）。Linux は 5.17 以降 BLAKE2s で抽出し ChaCha ベースの crng を回す。5.18 で /dev/random と /dev/urandom は「exactly the same thing」になった。アプリからは getrandom(2) を使う
• Go 1.22 以降、シード指定なしの math/rand トップレベル関数と runtime は ChaCha8 を使う。実測でも GODEBUG=randautoseed=0 が math/rand には効き math/rand/v2 には効かないことを確認した。それでも godoc は crypto/rand を案内し続けている
• モジュロバイアスは実測で 2.0034 倍（理論値 2.0）の偏りとして現れた。棄却法で 1.0006 まで戻る。1 バイトから作ると棄却率 21.88%、32 ビットから作れば実用的な n では実質ゼロ
• sort(() => Math.random() - 0.5) は最大偏差 71.81%、先頭要素が先頭に残る確率 28.64%（理想 16.67%）。Fisher-Yates なら最大偏差 1.34%
• 速度は言い訳にならない。まとめ取りなら CSPRNG のほうが 11 倍速かった（250.44 対 22.27 M値/秒）
• 統計検定（SP 800-22 / Dieharder / TestU01 BigCrush）は必要条件であって十分条件ではない。SP 800-22 自身が暗号解析の代わりにならないと述べている

判断は単純です。秘密になるものは CSPRNG、それ以外は好きな PRNG。迷ったら CSPRNG を使ってください。速度で困る場面はまず来ません。

参考リンク

• ECMAScript 仕様 21.3.2.28 Math.random ( )
• V8 blog: There's Math.random(), and then there's Math.random()
• V8 ソース: src/base/utils/random-number-generator.h（xorshift128+）
• V8 ソース: src/builtins/math.tq（MathRandom / RandomToDouble）
• V8 ソース: src/numbers/math-random.cc
• MDN: Crypto.getRandomValues()
• MDN: Crypto.randomUUID()
• Node.js: crypto.randomInt / randomBytes / randomUUID
• Node.js ソース: lib/internal/crypto/random.js
• Python: random モジュール
• Python: secrets モジュール
• Go: math/rand
• Go: math/rand/v2
• Go: crypto/rand
• Go 1.22 リリースノート
• Go: GODEBUG History
• Java: java.util.Random
• Java: java.security.SecureRandom
• PHP: random_int
• PHP: mt_rand
• Linux man-pages: getrandom(2)
• Linux man-pages: random(4)
• Jason Donenfeld: Random number generator enhancements for Linux 5.17 and 5.18
• LWN: Reworking random.c（block in /dev/urandom）
• Intel Digital Random Number Generator (DRNG) Software Implementation Guide
• NIST SP 800-90A Rev.1: Recommendation for Random Number Generation Using DRBGs
• NIST SP 800-22 Rev.1a: A Statistical Test Suite for Random and Pseudorandom Number Generators
• RFC 9562: Universally Unique IDentifiers (UUIDs)
• Mersenne Twister 公式ページ（広島大学）
• Matsumoto & Nishimura, Mersenne Twister 論文 (PDF)
• Vigna: xoshiro / xoroshiro generators and the PRNG shootout
• Vigna: Further scramblings of Marsaglia's xorshift generators (PDF)
• PCG, A Family of Better Random Number Generators
• TestU01
• Dieharder: A Random Number Test Suite
• Argyros & Kiayias, I Forgot Your Password: Randomness Attacks Against PHP Applications (USENIX Security '12)
• CWE-338: Use of Cryptographically Weak Pseudo-Random Number Generator (PRNG)