乱数ジェネレーター

このジェネレーターについて

コンピュータは決定論的な機械なので、「ランダム性」を生成するのは奇妙です。コンピュータ上の擬似乱数生成器(PRNG)の歴史は、John von Neumann の1946年のミドルスクエア法から始まります、前の数値を二乗、中間の桁を新しい値として取得、繰り返し。von Neumann 自身、ミドルスクエアには明らかな失敗モード(ゼロにロックされたサイクル、短い周期)があるので、完全に理解せずに乱数生成器を使うことを「罪深い状態」と特徴付けました。Lehmer の線形合同法生成器(LCG、1951)、x_(n+1) = (a × x_n + c) mod m、は妥当な統計特性を持つ最初の PRNG ファミリーです、C 標準ライブラリの rand() は依然として通常 LCG 変種を使用します。Mersenne Twister(Matsumoto と Nishimura、1997-1998)は周期 2¹⁹⁹³⁷−1(はい、6,000 桁の数)と優れた統計特性を持つ生成器を私たちに与えました、Python、R、MATLAB、PHP、その他多くの言語のデフォルトになりました。Marsaglia のxorshift ファミリー(2003)はより高速でハードウェアレジスタに収まるほど小さい、現代の V8(Chrome の JavaScript エンジン)は Math.random() に xorshift128+ 変種を使用します。Melissa O'Neill のPCG(Permuted Congruential Generator)(2014)は非暗号 PRNG の現在の統計の最先端で、低コストで優れた統計特性のために LCG スタイルの状態前進と出力順列を組み合わせます。

暗号的に安全な PRNG(CSPRNG)は別の獣です。定義特性:攻撃者が生成器によって生成されたすべての過去の出力を知っていても、無視できる利点より良く次の出力を予測できません。Linux の getrandom() システムコール(カーネル 3.17、2014年10月で追加)と基礎の /dev/urandom はハードウェアエントロピーソース(RDRAND、割り込みタイミング、音声ノイズ)からシードされた ChaCha20 ベースの生成器を使用します。Windows の BCryptGenRandom は複数のエントロピーソースからシードされた AES-CTR-DRBG 構築(NIST SP 800-90A)を使用します。macOS / iOS は Fortuna から派生した CSPRNG を使用します。PRNG と CSPRNG の違いは大きく重要です:PRNG はゲームランダム性、A/B テストバケッティング、シミュレーションに適しています、攻撃者が予測しようとするかもしれないあらゆるもの(セッショントークン、パスワード生成、セキュリティ識別子)には、CSPRNG のみが安全です。

JavaScript の 2 つのランダム API

Math.random() は古いシンプルな API で、[0, 1) でほぼ均一に分布する浮動小数点数を返します。ECMAScript 仕様は基礎となるアルゴリズムを意図的に未指定のままにしました("approximately uniform distribution between 0 and 1, exclusive")、エンジンは何年もの間使用するものを変更してきました。V8(Chrome)は2015年まで Park-Miller LCG を使用、その後より良い統計特性のために xorshift128+ に切り替えました。SpiderMonkey(Firefox)と JavaScriptCore(Safari)は同様の高速非暗号生成器を使用します。Math.random() はゲームメカニクス、シミュレーション、予測不可能性がセキュリティ要件ではないあらゆるアプリケーションに十分高速で均一です。暗号的に安全ではありません、周期は実装定義、状態は少数の出力から復元可能、シーケンスはパスワード生成やセキュリティ機微なユースケースには安全ではありません。crypto.getRandomValues() は Web Crypto API の CSPRNG です。OS の CSPRNG(TLS セッションキーのために TLS が使用するのと同じソース)から引き出された暗号的に安全なランダムバイトで型付き配列を埋めます。約2014年からすべての現代のブラウザで利用可能、単一呼び出しの最大バッファサイズは 65,536 バイト。重要なあらゆる乱数の正しい選択、トークン生成、セキュリティ識別子、パスワード生成、攻撃者が予測しようとするかもしれないあらゆるもの。

モジュロバイアスの罠

CSPRNG から特定の範囲で均一な整数を生成するのは見た目より難しいです。素朴なアプローチ、サイコロロールの crypto.getRandomValues(new Uint8Array(1))[0] % 6、はバイアスのかかった分布を生成します、256 が 6 で均等に割れないからです。値 0-3 は範囲 0-255 でそれぞれ 43 回現れます、値 4-5 は 42 回現れます。バイアスは小さい範囲で小さいですが実際で、長い実行で検出可能です。標準的な修正はリジェクションサンプリングです:ランダムバイトを生成、それが範囲のフィットする最大の倍数(ここでは 252 = 42 × 6)に入るかをテスト、入るなら使用、入らないなら捨ててリトライ。リジェクションレートは(範囲 / 次の 2 のべき乗)で制限されます、つまり「1-6」では約 1.5 % のバイトを浪費します、32 ビットのランダム整数に対する「1-1000000」では約 0.02 % を浪費します。あらゆる本格的なランダムライブラリはリジェクションサンプリングを実装します、Math.random() ベースの Math.floor(Math.random() * (max - min + 1)) + min はバイアスを避けます、Math.random() の精度が十分に高い(53 ビット仮数)ので、合理的な範囲でバイアスは人間が検出可能なレベル以下です。この生成器はリジェクションサンプリングで CSPRNG 出力を使用します、要求された任意の整数範囲で均一な出力。

ユースケースとそれぞれに必要なランダム性レベル

• 抽選とくじ。 非金銭抽選(オフィスデスク交換、ハッカソンチーム割り当て、教室席表)には Math.random() で十分です。金銭抽選または規制されたものには CSPRNG を使用、検証可能性のためにシードを公開するのが理想的です。
• ゲームメカニクス。 サイコロロール、カードシャッフル、ルート、手続き的生成。Math.random() が標準的な選択、高速、十分に均一、プレイヤーがパターンに気付かない程度に予測不可能。CSPRNG はサーバーが不正行為を防ぐ必要があるオンラインカードゲーム用に予約されています。
• A/B テストバケット割り当て。 各ユーザーを決定論的にバケットに配置するために、安定した秘密でユーザー識別子をハッシュします、Math.random() を使うと、ユーザーがページロード間で異なるバケットに着地し、実験を台無しにします。ハッシュ割り当てが正しいパターン、ランダム性は実験のシードを選ぶためにのみ使われ、一度だけです。
• 調査のためのランダムサンプリング。 母集団から代表的なサブセットを引き出します。Math.random() で十分、統計的な質問はサンプルが十分に大きいかどうかであり、ランダムソースが暗号的かどうかではありません。
• テストデータ生成。 Faker、モックデータ、合成データベースフィクスチャ。固定シード(再現性のため)を持つ Math.random() が正しい選択です。
• 暗号鍵、セッショントークン、パスワード生成。 CSPRNG のみ、ブラウザでは crypto.getRandomValues()、Python では secrets モジュール、Go では crypto/rand、決して言語のデフォルトランダム性ではありません。この層のバグは依存するすべてを侵害します、結果は「全員のセッションがハイジャック可能」から「暗号化キーが回復可能」まで。

RANDOM.ORG と真のランダム性の区別

RANDOM.ORG は1998年に Trinity College Dublin の Mads Haahr によってローンチされ、オンラインの「真のランダム性」のリファレンスのままです。すべての CSPRNG が最終的にハードウェアシードされた状態のアルゴリズム的変換からビットを派生する(攻撃者にとって予測不可能でも、決定論的プロセス)のに対し、RANDOM.ORG はラジオ受信機によって取得された大気ノイズを測定し、そのアナログノイズを直接ビットに変換します。これにより擬似乱数生成器ではなく真の乱数生成器(TRNG)になります、ビットは決定論的アルゴリズムではなく真の非決定論的物理プロセスから来ます。RANDOM.ORG は宝くじオペレーター、二重盲検研究を実施する学術研究者、検証可能なランダム性が重要なゲームによって使用されます。トレードオフ:リクエストごとのネットワークラウンドトリップ、無料層の毎日のクォータ、RANDOM.ORG の主張するエントロピーソースをローカル CSPRNG より信頼するかという哲学的質問。ほとんどの使用には、ローカル CSPRNG で十分です、第三者がランダム性を独立して検証する必要があるケース(規制された宝くじ、二重盲検科学研究)には、RANDOM.ORG は有料サービスとして署名されたランダム性証明書を提供します。

置換なしのサンプリング、Fisher-Yates シャッフル

範囲内でN 個の一意の数が必要なとき、宝くじの 1 〜 49 の 6 つの数字を引く、1,000 のエントリーから 10 人の勝者を選択する、素朴な「生成して重複なら拒否」は小さな N で機能しますが、N が範囲のサイズに近づくとひどく劣化します(プールが縮むにつれて新しい数字を引く可能性が下がる)。標準アルゴリズムはFisher-Yates シャッフルです、Fisher と Yates の1938年の統計表から発信され、1969年に Donald Knuth によってコンピュータサイエンスの現代的な形(時には Knuth シャッフルと呼ばれる)に置かれました。アルゴリズムは非常にシンプルです:数 1 〜 N を配列に書く、i を N-1 から 1 まで、要素 i をインデックス 0 〜 i(包含的)のランダム要素と交換、配列は今や均一にシャッフルされています。K 個のユニークなランダム数のために最初の K 要素を取ります。重要な詳細:ランダムインデックスは [0, i] 包含的でなければなりません、[0, i-1] を使用すると、暗号コミュニティが特徴づけるのに何年もかかった微妙なバイアス(Sattolo 変種、時には真の Fisher-Yates の代わりに誤って使用される)が導入されます。すべての N 値の配列を割り当てることが実用的でない非常に大きな範囲(例えば 1 と 10⁹ の間で 100 のユニーク値を選ぶ)には、リザーバーサンプリング(Vitter、1985)が単一パスで境界付きメモリでストリーミングまたは無境界入力を処理します。

サイコロロール慣習

乱数生成器は変装したサイコロです。D6(6 面サイコロ)はボードゲームの普遍的なデフォルト、範囲 1-6。D20(20 面サイコロ)は能力チェック、攻撃ロール、セービングスローに使用される Dungeons & Dragons の象徴的なサイコロ、D&D の修飾子システムは、単一の D20 ロールにスタットボーナスを加えたものがほとんどのアクションの結果を決定することを意味します。D100(パーセンタイル、1-100)は Call of Cthulhu、Warhammer Roleplay、多くのクリティカルチャンスシステムでパーセンテージロールに使用されます。記法 NdM は「M 面サイコロを N 個振って合計」を意味します、NdM+B はボーナスを加えます。3d6 は 3 つの 6 面サイコロを振って合計します(範囲 3-18、古典的な D&D 能力スコア範囲、10-11 周辺の三角分布)。公平なシミュレーションのために、各サイコロに [1, M] の均一整数を生成して合計するのは物理サイコロを振るのと正確に同等です、基礎となる CSPRNG 分布は購入できるあらゆる物理サイコロより均一です。カジノと規制されたゲームは、規制当局に均一性を証明するために統計バッテリー(TestU01 の BigCrush、NIST SP 800-22)に対してテストされた認証された RNG を使用します、同じ標準が宝くじ RNG に適用されます。

シードと再現性

PRNG の微妙だが重要な特性:与えられたシードに対して決定論的です。シードを既知の値に固定すると、「ランダム」数のシーケンスは正確に再現可能です。これはテストに非常に貴重です(ランダムデータを使用する単体テストは失敗を再現可能にするためにシードを固定すべき)、検証可能な抽選にも(抽選前にシードを公開、その後誰でも結果を検証できる)。Python の random モジュールにはこのために random.seed(value) があります、Java の Random はコンストラクタでシードを取ります。JavaScript の Math.random() は意図的にシード API を公開しません、エンジンはシードを内部状態として扱います、しかしいくつかの純粋 JS ライブラリ(seedrandom、pcg-random)はシード可能な PRNG を提供します。CSPRNG は設計により異なります:意味全体が予測不可能性なのでシードを公開しません。再現性が必要なら、明示的なシードで PRNG を使用してください、セキュリティが必要なら、CSPRNG を使用しその後シーケンスを再現できないことを受け入れてください。

プライバシー、なぜ乱数のためでもブラウザのみか

乱数自体はめったに機微情報を含みません、では純粋なブラウザアーキテクチャがなぜ重要か? 2 つの理由。第一に、乱数がセッショントークン、冪等性キー、認証チャレンジ、その他の秘密のような値として使用されるとき、第三者サーバーで生成することはそのサーバーが使用前に値を見たことを意味します、小さいが実際の露出。第二に、「暗号的なランダム性」を約束するサーバー側生成器はユーザーが検証できません、バグのあるまたは悪意のあるサーバーは見かけ上ランダムだが非ランダムまたはバイアスされた値を返す可能性があり、大規模サンプリングなしにバイアスを検出する方法がありません。ブラウザのみの生成器はアプリケーションがサーバー側で実行するのと同じ crypto.getRandomValues() 呼び出しを実行します、エントロピーは同じ OS ソース(Linux getrandom()、Windows BCryptGenRandom、macOS)から来ます、第三者は出力を見ません。Generate をクリックする間に DevTools の Network タブを開いて確認できます、発信リクエストはありません。ロード後にページをオフライン(機内モード)にしても生成器はまだ動作します。

よくある質問