疑似乱数ジェネレータ

疑似乱数生成器( PRNG ) は、決定論的乱数ビット生成器( DRBG ) ^[1]とも呼ばれ、乱数列の特性に近い特性を持つ数列を生成するアルゴリズムです。PRNG によって生成された数列は、PRNG のシードと呼ばれる初期値 (真にランダムな値が含まれる場合があります) によって完全に決定されるため、真にランダムではありません。ハードウェア乱数生成器を使用すれば、より真にランダムな数列を生成できますが、疑似乱数生成器は、数値生成の速度と再現性のために実用上重要です。^[2]

PRNG は、シミュレーション(例:モンテカルロ法)、電子ゲーム(例:手続き型生成)、暗号化などのアプリケーションで中心的な役割を果たします。暗号化アプリケーションでは、出力が以前の出力から予測できないことが必要であり、より単純な PRNG の線形性を継承しない、より複雑なアルゴリズムが必要です。

優れた統計特性は、PRNG の出力にとって中心的な要件です。一般に、PRNG が意図した用途に適したランダムに十分近い数値を生成するという確信を得るには、慎重な数学的分析が必要です。ジョン・フォン・ノイマンは、PRNG を真のランダム ジェネレーターと誤解することについて警告し、「ランダムな数字を生成する算術的方法を考える人は、もちろん罪深い状態にある」と冗談を言っています。^[3]

実際には、多くの一般的な PRNG の出力には、統計パターン検出テストに失敗する原因となる アーティファクトが見られます。これには次のものが含まれます。

• いくつかのシード状態の期間が予想よりも短い（このようなシード状態は、この文脈では「弱い」と呼ばれることがあります）。
• 生成された大量の数値の分布が均一でない。
• 連続する値の相関。
• 出力シーケンスの次元分布が不十分です。
• 特定の値が発生する場所間の距離は、ランダム シーケンス分布の場合とは異なる分布になります。

欠陥のある PRNG によって生じる欠陥は、気付かない (または知られていない) ものから非常に明白なものまでさまざまです。一例として、メインフレーム コンピューターで数十年にわたって使用されてきたRANDU乱数アルゴリズムが挙げられます。このアルゴリズムには重大な欠陥がありましたが、その不適切さは長い間検出されませんでした。

多くの分野において、21 世紀以前の研究では、ランダム選択やモンテカルロシミュレーション、またはその他の方法で PRNG に依存していましたが、低品質の PRNG を使用していたため、信頼性は理想よりもはるかに低かったです。^{[4]今日でも、}国際統計科学百科事典(2010)の次の警告に示されているように、注意が必要な場合もあります。^[5]

広く使用されているジェネレーターのうち、廃棄すべきもののリストは [良質なジェネレーターのリストよりも] はるかに長いです。ソフトウェア ベンダーを盲目的に信用しないでください。お気に入りのソフトウェアのデフォルトの RNG を確認し、必要に応じて交換できるように準備してください。この最後の推奨事項は、過去 40 年間に何度も繰り返されてきました。驚くべきことに、これは 40 年前と同じように今日でも当てはまります。

例として、広く使用されているプログラミング言語Javaを考えてみましょう。2020年まで、JavaはPRNGに線形合同法（LCG）に依存していましたが、 ^{[6] [7]}品質は低かったです（下記参照）。JavaのサポートはJava 17でアップグレードされました。

大きな問題を回避しながらもかなり高速に実行できる有名な PRNG の 1 つに、1998 年に公開されたMersenne Twister (後述) があります。計算パフォーマンスと統計パフォーマンスの両方の点で、より高品質な他の PRNG がこの日付の前後に開発されました。これらは、擬似乱数ジェネレータの一覧で確認できます。

20 世紀後半、PRNG に使用される標準的なアルゴリズムは線形合同法でした。LCG の品質が不十分であることは知られていましたが、よりよい方法は存在しませんでした。Press ら (2007) は、その結果を次のように説明しています。「[LCG および関連] のせいで結果が疑わしい科学論文がすべて図書館の棚から消えるとしたら、各棚に拳ほどの隙間ができるでしょう。」^[8]

疑似乱数生成器の構築における大きな進歩は、2 要素体上の線形再帰に基づく手法の導入でした。このような生成器は線形フィードバック シフト レジスタに関連しています。

1997年に発明されたメルセンヌツイスター^[9]は、特に、以前のジェネレーターが抱えていた多くの問題を回避しました。メルセンヌツイスターの周期は2 ^{19 937}  − 1 反復（≈ 4.3 × 10⁶⁰⁰¹ ) は、(最大) 623 次元 (32 ビット値の場合) に均等に分散されていることが証明されており、導入当時は他の統計的に妥当なジェネレータよりも高速に実行されていました。

2003年、ジョージ・マルサリアは、やはり線形回帰に基づいた^XORシフトジェネレータのファミリーを発表しました。このようなジェネレータは非常に高速で、非線形演算と組み合わせることで強力な統計テストに合格します。^{[11] [12] [13]}

2006年に、WELLファミリーのジェネレータが開発されました。^[14] WELLジェネレータは、状態空間が大きすぎることと、多数のゼロを持つ状態空間からの回復が非常に遅いというメルセンヌツイスターの品質をいくつかの点で改善しています。

暗号化アプリケーションに適した PRNG は、暗号的に安全な PRNG (CSPRNG)と呼ばれます。CSPRNG の要件は、シードを知らない攻撃者が、ジェネレータの出力シーケンスをランダム シーケンスと区別する上でわずかな 利点しか持たないことです。言い換えると、PRNG は特定の統計テストに合格するだけでよいのに対し、CSPRNG はシードのサイズの多項式時間に制限されるすべての統計テストに合格する必要があります。この特性の証明は、現在の最先端の計算複雑性理論の範囲を超えていますが、整数因数分解などの困難であると想定される問題を CSPRNG に還元することで、強力な証拠が得られる可能性があります。^[15]一般に、アルゴリズムが CSPRNG として認定されるまでには、何年ものレビューが必要になる場合があります。

CSPRNG のクラスには次のものがあります。

• ストリーム暗号
• カウンター^[16]または出力フィードバックモードで実行されるブロック暗号
• 暗号的に安全であるように特別に設計されたPRNG。例えば、Microsoftの暗号化アプリケーションプログラミングインターフェース関数CryptGenRandom、Yarrowアルゴリズム（ Mac OS XとFreeBSDに組み込まれている）、Fortunaなど。
• 検出可能な非ランダム性を排除することを目的として、複数のPRNG基本アルゴリズムを組み合わせようとする組み合わせPRNG
• 数学的困難性仮定に基づく特別な設計：例としては、ミカリ・シュノア生成器、^[17] ナオル・ラインゴールド擬似乱数関数、ブルーム・ブルーム・シューブアルゴリズムなどがあり、これらは強力なセキュリティ証明を提供する（このようなアルゴリズムは従来の構成に比べてかなり遅く、多くのアプリケーションでは実用的ではない）
• 汎用PRNG: （暗号的に）安全なPRNGは任意の一方向関数から汎用的に構築できることが示されているが、^[18]この汎用的な構築は実際には非常に遅いため、主に理論的な関心の対象となっている。

NSAがNIST認定の疑似乱数生成器Dual_EC_DRBGに非対称 バックドアを挿入した可能性が高いことが示されている。^[19]

ほとんどのPRNGアルゴリズムは、いくつかのテストのいずれかによって均一に分布するシーケンスを生成します。高品質のPRNGの出力を真にランダムなシーケンスと区別する方法があるかどうかは未解決の問題であり、暗号の理論と実践の中心となる問題です。この設定では、区別者は、既知のPRNGアルゴリズムが使用されたか（初期化された状態は知らない）、真にランダムなアルゴリズムが使用されたかを知っており、この2つを区別する必要があります。^[20] PRNGを使用するほとんどの暗号化アルゴリズムとプロトコルのセキュリティは、適切なPRNGの使用と真にランダムなシーケンスの使用を区別することは不可能であるという仮定に基づいています。この依存関係の最も単純な例はストリーム暗号で、これは（ほとんどの場合）メッセージの平文とPRNGの出力を排他的論理和して暗号文を生成します。暗号的に適切なPRNGの設計は、追加の基準を満たす必要があるため、極めて困難です。周期の大きさは PRNG の暗号化適合性において重要な要素ですが、唯一の要素ではありません。

ドイツ連邦情報セキュリティ局（ドイツ語：Bundesamt für Sicherheit in der Informationstechnik、BSI）は、決定論的乱数生成器の品質に関する4つの基準を定めています。^[21]以下にそれらを要約します。

• K1 – 生成された乱数列が互いに異なる可能性は高いはずです。
• K2 – 指定された統計テストによれば、数値シーケンスは「真にランダムな」数値と区別がつきません。テストには、モノビットテスト (シーケンス内の 1 と 0 の数が等しい)、ポーカーテスト (カイ 2 乗テストの特殊なインスタンス)、ランテスト (さまざまな長さのランの頻度をカウント)、ロングランテスト (シーケンスの 20,000 ビット内に長さ 34 以上の実行が存在するかどうかをチェック) (どちらもBSI ^[21]とNIST ^[22]による) 、および自己相関テストがあります。本質的には、これらの要件は、ビット シーケンスが 0 と 1 を均等に含むこと、n個の0 (または 1) シーケンスの後、次のビットが 1 (または 0) になる確率が半分であること、および選択されたサブシーケンスにシーケンス内の次の要素に関する情報が含まれないことをテストするものです。
• K3 – 攻撃者が（実際上は）任意のサブシーケンスから、シーケンス内の以前の値や将来の値、またはジェネレーターの内部状態を計算したり推測したりすることは不可能である必要があります。
• K4 – 攻撃者がジェネレーターの内部状態からシーケンス内の以前の数値やジェネレーターの内部状態を計算したり推測したりすることは、実質的に不可能である必要があります。

暗号化アプリケーションの場合、K3 または K4 標準を満たすジェネレーターのみが許容されます。

与えられた条件:

• ${\displaystyle P}$– （実数直線上の標準ボレル集合）上の確率分布${\displaystyle \left(\mathbb {R} ,{\mathfrak {B}}\right)}$${\displaystyle {\mathfrak {B}}}$
• ${\displaystyle {\mathfrak {F}}}$– ボレル集合の空でないコレクション、例： 。 が指定されていない場合は、コンテキストに応じてまたは のいずれかになります。${\displaystyle {\mathfrak {F}}\subseteq {\mathfrak {B}}}$${\displaystyle {\mathfrak {F}}=\left\{\left(-\infty ,t\right]:t\in \mathbb {R} \right\}}$${\displaystyle {\mathfrak {F}}}$${\displaystyle {\mathfrak {B}}}$${\displaystyle \left\{\left(-\infty ,t\right]:t\in \mathbb {R} \right\}}$
• ${\displaystyle A\subseteq \mathbb {R} }$– 空でない集合（必ずしもボレル集合とは限りません）。 は、のサポートとその内部 の間の集合であることが多いです。たとえば、 が区間 上の一様分布である場合、である可能性があります。 が指定されていない場合は、コンテキストに応じて、 のサポートに含まれ、その内部を含む何らかの集合であると想定されます。${\displaystyle A}$${\displaystyle P}$${\displaystyle P}$${\displaystyle \left(0,1\right]}$${\displaystyle A}$${\displaystyle \left(0,1\right]}$${\displaystyle A}$${\displaystyle P}$

関数(ここでは正の整数の集合)を、が与えられた場合に限り に値を取る擬似乱数ジェネレータと呼びます。 ${\displaystyle f:\mathbb {N} _{1}\rightarrow \mathbb {R} }$${\displaystyle \mathbb {N} _{1}=\left\{1,2,3,\dots \right\}}$${\displaystyle P}$${\displaystyle {\mathfrak {F}}}$${\displaystyle A}$

• ${\displaystyle f\left(\mathbb {N} _{1}\right)\subseteq A}$
• ${\displaystyle \forall E\in {\mathfrak {F}}\quad \forall \varepsilon >0\quad \exists N\in \mathbb {N} _{1}\quad \forall n\geq N,\quad \left|{\frac {\#\left\{i\in \left\{1,2,\dots ,n\right\}:f(i)\in E\right\}}}{n}}-P(E)\right|<\varepsilon }$

（ は有限集合 内の要素の数を表します。） ${\displaystyle \#S}$${\displaystyle S}$

が 上の一様分布 の疑似乱数生成器であり、が何らかの与えられた確率分布 のCDFである場合、 は の疑似乱数生成器であることが示されます。ここで はのパーセンタイル、つまりです。直感的に、任意の分布は標準一様分布のシミュレーションからシミュレートできます。 ${\displaystyle f}$${\displaystyle \left(0,1\right)}$${\displaystyle F}$${\displaystyle P}$${\displaystyle F^{*}\circ f}$${\displaystyle P}$${\displaystyle F^{*}:\left(0,1\right)\rightarrow \mathbb {R} }$${\displaystyle P}$${\displaystyle F^{*}(x):=\inf \left\{t\in \mathbb {R} :x\leq F(t)\right\}}$

1946 年にジョン・フォン・ノイマンが提案した初期のコンピュータベースの PRNG は、中間二乗法として知られています。アルゴリズムは次のとおりです。任意の数字を二乗し、結果の数字の中間の桁を「ランダムな数字」として削除し、その数字を次の反復のシードとして使用します。たとえば、「1111」という数字を二乗すると「1234321」になりますが、これは「01234321」と表記でき、8 桁の数字は 4 桁の数字の二乗です。これにより、「ランダムな」数字として「2343」が得られます。この手順を繰り返すと、次の結果として「4896」が得られます。フォン・ノイマンは 10 桁の数字を使用しましたが、プロセスは同じでした。

「中間の正方形」法の問題点は、すべてのシーケンスが最終的に繰り返されることです。「0000」のように、非常に速く繰り返されるシーケンスもあります。フォン ノイマンはこれに気付いていましたが、このアプローチは目的に十分であり、数学的な「修正」ではエラーが除去されるのではなく、単にエラーが隠されるだけになるのではないかと心配していました。

フォン・ノイマンは、ハードウェア乱数生成器は不適切であると判断しました。生成された出力を記録しないと、後でエラーをテストできないからです。出力を記録すると、当時利用可能な限られたコンピュータ メモリを使い果たし、コンピュータの数字の読み取りと書き込みの能力も使い果たしてしまいます。数字がカードに書き込まれると、書き込みと読み取りに非常に長い時間がかかります。彼が使用していたENIACコンピュータでは、「ミドル スクエア」方式により、パンチ カードから数字を読み込むよりも数百倍の速度で数字が生成されました。

それ以来、中間平方法はより複雑なジェネレータに取って代わられました。

最近の革新は、中間の正方形をワイル列と組み合わせることです。この方法は、長期間にわたって高品質の出力を生成します (中間の正方形法を参照)。

非均一な確率分布から選択された数値は、均一分布PRNG と 2 つの分布を関連付ける関数を使用して生成できます。

まず、目標分布の累積分布関数 が必要です。 ${\displaystyle F(b)}$${\displaystyle f(b)}$

${\displaystyle F(b)=\int _{-\infty }^{b}f(b')\,db'}$

注意してください。一様分布からの乱数cを「通過」する確率密度として使用すると、次の式が得られます。 ${\displaystyle 0=F(-\infty )\leq F(b)\leq F(\infty )=1}$

${\displaystyle F(b)=c}$

となることによって

${\displaystyle b=F^{-1}(c)}$

は分布からランダムに選択された数値です。これは逆変換サンプリングに基づいています。 ${\displaystyle f(b)}$

例えば、入力として範囲（0, 1）を持つ理想的な一様PRNGを使用した累積ガウス分布 の逆は、ガウス分布を持つ（正の値のみの）値のシーケンスを生成します。 ${\displaystyle \operatorname {erf} ^{-1}(x)}$${\displaystyle x}$

• 実用的な数値表現を使用する場合、分布の無限の「末尾」を有限の値に切り捨てる必要があります。
• 生成を高速化するために、ジッグラト アルゴリズムなどの手段を使用して、繰り返しの再計算を削減する必要があります。${\displaystyle \operatorname {erf} ^{-1}(x)}$

レイリー分布やポアソン分布などの他の非均一分布の生成にも同様の考慮事項が適用されます。

• Barker E.、Kelsey J.、決定論的ランダムビットジェネレータを使用した乱数生成に関する推奨事項、NIST SP800-90A、2012 年 1 月
• ブレント RP、「シフトと XOR を使用したいくつかの長期乱数ジェネレータ」、ANZIAM Journal、2007; 48:C188–C202
• Gentle JE (2003)、「乱数生成とモンテカルロ法」、Springer。
• Hörmann W.、Leydold J.、Derflinger G. (2004、2011)、「Automatic Nonuniform Random Variate Generation」、Springer-Verlag。
• Knuth DE The Art of Computer Programming、第 2 巻: Seminumerical Algorithms、第 3 版。Addison-Wesley、1997 年。ISBN 0-201-89684-2。第 3 章。[非ランダム性の統計的テストを広範囲にカバーしています。] 
• Luby M., Pseudorandomness and Cryptographic Applications、プリンストン大学出版、1996年。ISBN 9780691025469 
• von Neumann J.、「ランダムな数字に関連して使用されるさまざまな手法」、AS Householder、GE Forsythe、HH Germond 編、『モンテカルロ法』、米国標準局応用数学シリーズ、12 (ワシントン DC: 米国政府印刷局、1951): 36–38。
• ピーターソン、アイヴァース（1997年）。『ランダムネスのジャングル：数学的サファリ』ニューヨーク：ジョン・ワイリー・アンド・サンズ。ISBN 0-471-16449-6。
• Press WH、Teukolsky SA、Vetterling WT、Flannery BP (2007)、「Numerical Recipes」 ( Cambridge University Press ) を出版。
• Viega J.、「ソフトウェアにおける実用的な乱数生成」、Proc. 19th Annual Computer Security Applications Conference、2003 年 12 月。

• TestU01: 無料の最新鋭 ( GPL ) C++乱数テスト スイート。
• DieHarder: 無料 ( GPL ) C乱数テスト スイート。
• 「乱数の生成」（組み込みシステム）Eric Uner（2004）
• 「Linux 乱数ジェネレータの分析」Zvi Gutterman、Benny Pinkas、Tzachy Reinman (2006)
• 「より優れた擬似乱数ジェネレータ」、Parikshit Gopalan、Raghu Meka、Omer Reingold、Luca Trevisan、Salil Vadhan著( Microsoft Research、2012)
• rand() はYouTube上で有害であると考えられる(Stephan Lavavej 著、Microsoft、2013 年)
• Wsphynx はシンプルなオンライン乱数ジェネレータです。乱数は、Javascript 擬似乱数ジェネレータ (PRNG) アルゴリズムによって生成されます。