本文へ移動
myowchick

剰余バイアスでAからHだけが1.2倍出る

ランダム文字列生成ツールは、乱数を文字プールの長さで割った余りで1文字ずつ選んでいる。

ただし余りを取るまえに、割り切れない端に当たった乱数は捨てて引き直している。

この引き直しを外すとどれくらい偏るのか、2000万回引いて数えてみた。答えは乱数の幅しだいだった。

1バイトの乱数なら特定の8文字が1.21倍出る。32bitの乱数なら2000万回では偏りが見えない。

割り切れない端が偏りを作る

実装はsrc/lib/tools/random.tsにある。

export const cryptoRandomInt: RandomInt = (maxExclusive) => {
  // 引数の検査と maxExclusive === 1 の分岐は省略

  const limit = Math.floor(0x1_0000_0000 / maxExclusive) * maxExclusive
  const buffer = new Uint32Array(1)

  for (;;) {
    crypto.getRandomValues(buffer)
    const value = buffer[0] ?? 0

    if (value < limit) {
      return value % maxExclusive
    }
  }
}

limitは、乱数の全パターン数4294967296（2の32乗）をmaxExclusiveで割り切れるところまで切り下げた値。それより上に出た乱数は使わずに引き直す。

端を捨てるのは、2の32乗がたいていのmaxExclusiveで割り切れないから。

英大小文字と数字で62文字のプールなら、62 × 69273666 + 4 = 4294967296。

引き直しなしで% 62だけすると、この端の4個が余り0から3に上乗せされる。0から3は69273667通りの乱数から作られ、残りの58文字は69273666通り。この差が剰余バイアス。

1バイトの乱数だと目に見える

同じことを幅の狭い乱数でやると、比が一気に効いてくる。

1バイト（0から255）を% 62すると、62 × 4 + 8 = 256。端が8個ある。先頭8文字は256通り中5通り、残りの54文字は4通り。上と下で1.25倍の差になる。

数えてみた。

const alphabet = 'ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789'
const counts = new Float64Array(alphabet.length)
const buf = new Uint8Array(65536)

for (let done = 0; done < 20_000_000; done += buf.length) {
  crypto.getRandomValues(buf)
  for (const b of buf) counts[b % alphabet.length] += 1
}

2000万回引いた結果がこれ。期待値は20000000 / 62 = 322580.6で、比はその期待値に対する倍率。

多い順
  D  391976  1.215
  G  391826  1.215
  E  390871  1.212
  H  390797  1.211
  C  390788  1.211
  B  390609  1.211
  A  390570  1.211
  F  389394  1.207
少ない順
  J  311388  0.965
  Y  311302  0.965
  4  311254  0.965
  f  311246  0.965
  0  311089  0.964

chi2 = 132801.1 (df = 61)

上位8件がアルファベットのAからHで、きれいに切れている。プールの先頭8文字だ。

比が1.25ではなく1.211と0.969に割れているのは、期待値が上と下のあいだ（256 / 62 = 4.129）にあるから。5 / 4.129 = 1.211、4 / 4.129 = 0.969。上下の比を取れば1.25で、理屈どおり。

カイ二乗が自由度61に対して13万。偶然では説明がつかない。

32bitだと2000万回では見えない

同じ数え方をUint32Arrayに替えて3回まわした。

trial 1: chi2=65.0  最大比=1.0035 最小比=0.9949
trial 2: chi2=64.8  最大比=1.0041 最小比=0.9954
trial 3: chi2=71.4  最大比=1.0036 最小比=0.9962

自由度61に対してカイ二乗が65前後。ただのばらつきの範囲で、偏りは検出できない。

そのはずで、32bitでの端はたった4個だった。0から3の確率は他の58文字の1.000000014倍。1バイトのときの1.25倍とは桁が違う。

どれくらい引けば見えるのか計算してみた。カイ二乗の期待値は1サンプルあたり1.258e-17しか増えない。自由度ぶん（61）押し上げるのに必要なサンプル数は4.85e+18回。

毎秒100万回引いても15万年かかる。実質的に測れない。

つまり、32bitの乱数を% 62する実装の偏りは、実用上は問題にならない。

それでも引き直しを残す理由

引き直しがどれくらい走るのかも数えた。

max=62           n=5000000  引き直し 0回
max=26           n=5000000  引き直し 0回
max=3000000000   n=1000000  引き直し 432002回 (0.43回/1回の取得)
max=2147483649   n=1000000  引き直し 999406回 (1.00回/1回の取得)

62文字でも26文字でも、500万回引いて1回も引き直していない。当たり前で、端に落ちる確率が5.1e-9とか9.3e-10のオーダーだから。ループはあるが実質1回で抜ける。

つまりこのfor (;;)は、ツールが使う範囲では性能に何も影響していない。

効いてくるのはmaxExclusiveが2の32乗に近づいたとき。2147483649（2の31乗+1）だと端が半分を占めるので、1回取るのに平均2回引く。ここまで来ると剰余バイアスも2倍で、無視できるものではなくなる。

ここが引き直しを残す判断の分かれ目だと思う。文字プールの長さでしか呼ばないと決めれば要らないコードだけど、cryptoRandomIntは範囲を引数で受け取る汎用の入り口として置いてある。呼び出し側が何を渡しても正しくなるほうが、条件付きで正しいより扱いやすい。

代償が500万回で0回の引き直しなら、払っておいていい。

Math.randomは偏っていない、予測できるだけ

「乱数といえばMath.random」を避ける理由も、偏りの話だと思われがちだけど、実測すると違う。

Math.floor(Math.random() * 62): chi2=74.7 df=61 最大比 1.0038 最小比 0.9954

2000万回引いて自由度61にカイ二乗74.7。分布としては何も問題ない。

問題は再現できてしまうこと。V8のMath.randomは内部状態を持つ疑似乱数生成器で、状態が同じなら同じ列が出る（V8のブログにxorshift128+を採用した経緯がある）。

Node.jsは--random_seedでその種を指定できるので、そのまま観察できる。

// pw.mjs
const alphabet = 'ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789'
let s = ''
for (let i = 0; i < 16; i += 1) s += alphabet[Math.floor(Math.random() * alphabet.length)]
console.log(s)
$ node --random_seed=42 pw.mjs
xgV7hew6CvD56S21
$ node --random_seed=42 pw.mjs
xgV7hew6CvD56S21
$ node --random_seed=12345 pw.mjs
4jDd9m7HlMHNskR8

16文字のパスワードが、種を揃えるだけで完全に一致する。

ブラウザで種を指定する手段は無いけれど、「種が分かれば列が決まる」構造そのものは変わらない。パスワードの生成に使うものではない。

crypto.getRandomValuesはここが違う。だから%が偏らない幅でも、まずgetRandomValuesを選ぶ。

整理すると、Math.randomと%はどちらもだめだけど、だめな理由は別々だ。Math.randomは分布ではなく予測可能性で落ちる。%は予測可能性ではなく分布で落ちる。そして%の分布の崩れは、乱数の幅が広ければ測れないほど小さい。

ついでにシャッフルも数えた

同じrandom.tsにはFisher-Yatesのshuffleが入っていて、雑談ペア作成がこれでメンバーを混ぜている。

sortのコンパレータで乱数を返すやり方と比べた。4要素の並べ替えを200万回、24通りの出方を数える。

import { shuffle } from './src/lib/tools/random.ts'

const items = ['A', 'B', 'C', 'D']
const fastInt = (max) => Math.floor(Math.random() * max)

// 比較対象
items.toSorted(() => Math.random() - 0.5)

Fisher-Yatesのほう。

chi2 = 32.5 (df = 23)  最多 ACDB 1.009  最少 DACB 0.991

sortのほう。

chi2 = 2303979.0 (df = 23)

ABCD:4.50 DCBA:4.12 DABC:1.50 ABDC:1.50 ADBC:1.50 CBDA:1.13 CDBA:1.13 CBAD:1.12
BDAC:0.75 BADC:0.75 DBAC:0.75 BACD:0.75 DBCA:0.38 BCAD:0.38 CABD:0.38 CDAB:0.38
BDCA:0.38 DCAB:0.38 BCDA:0.38 ACDB:0.38 ADCB:0.38 DACB:0.38 ACBD:0.37 CADB:0.37

入力のままのABCDが4.5倍、逆順のDCBAが4.1倍。他の22通りは0.37倍から1.5倍にばらけている。

比較関数が一貫していないと、ソートのアルゴリズムが何回どこを比べたかがそのまま結果に残る。剰余バイアスの1.25倍が可愛く見える崩れ方だ。

こっちは実測しなくても壊れていると言えるけど、数えると壊れ方の形まで見える。

まとめ

  • % maxの偏りは、乱数の幅とmaxの比で決まる。1バイトで62文字を選ぶと1.25倍、32bitなら1.000000014倍
  • 32bitの偏りを検出するには4.85e+18回引く必要がある。実用上は測れない
  • 端を捨てて引き直すコストは、62文字なら500万回で0回。範囲を引数で受け取る関数なら入れておく
  • Math.randomは分布ではなく予測可能性でだめ。--random_seedを揃えると同じパスワードが出る
  • sortのコンパレータで混ぜるのは、剰余バイアスより桁違いに壊れる
← 一覧へ戻る