乱数生成

乱数生成は、多くの場合乱数生成器( RNG )によって、偶然の偶然よりも合理的に予測できない数字または記号のシーケンスを生成するプロセスです。つまり、特定の結果シーケンスには、後から見れば検出できるが予測できないパターンが含まれます。真の乱数生成器はハードウェア乱数生成器(HRNG) であり、各生成は、モデル化が実質的に不可能な方法で絶えず変化する物理環境の属性の現在の値の関数です。これは、疑似乱数生成器(PRNG) によって実行されるいわゆる「乱数生成」とは対照的です。PRNGは、ランダムに見えるだけで実際には事前に決定された数字を生成します。これらの生成は、PRNG の状態を知るだけで再現できます。^[1]

ランダム性のさまざまな応用により、ランダムデータを生成するためのさまざまな方法が開発されました。これらの方法のいくつかは古代から存在しており、よく知られている例としては、サイコロを振る、コインを投げる、トランプをシャッフルする、易経におけるノコギリソウの茎の使用(占い用)などがあります。その他、数え切れないほど多くの手法があります。これらの手法は機械的な性質上、十分にランダムな数値 (統計で重要) を大量に生成するには、多くの作業と時間が必要でした。そのため、結果は乱数表として収集され、配布されることもありました。

疑似乱数生成には、いくつかの計算方法があります。いずれも真のランダム性という目標には達していませんが、結果がどの程度予測不可能であるか (つまり、パターンがどの程度識別可能か) を測定するためのランダム性の統計テストのいくつかは、程度の差はあるものの、ある程度は合格しています。このため、一般に、これらの方法は暗号化などの用途には使用できません。ただし、暗号化用に特別に設計された特別な機能を備えた、慎重に設計された暗号的に安全な疑似乱数生成器(CSPRNGS) も存在します。

乱数ジェネレーターは、ギャンブル、統計的サンプリング、コンピューター シミュレーション、暗号化、完全ランダム化設計、および予測不可能な結果を​​生成することが望ましいその他の分野で使用されます。一般に、セキュリティ アプリケーションなど、予測不可能性が最も重要な機能であるアプリケーションでは、実行可能な場合は、疑似乱数アルゴリズムよりもハードウェア ジェネレーターが一般的に好まれます。

疑似乱数ジェネレータは、 同じ乱数シードから開始して同じ乱数シーケンスを再度実行できるため、デバッグが容易になるため、モンテカルロ法のシミュレーションの開発に非常に役立ちます。シードが秘密である限り、暗号化にも使用されます。送信者と受信者は、キーとして使用するために同じ数字セットを自動的に生成できます。

疑似乱数の生成は、コンピュータ プログラミングにおいて重要かつ一般的なタスクです。暗号化や特定の数値アルゴリズムでは非常に高度なランダム性が要求されますが、他の多くの操作では、予測不可能性が中程度で十分です。簡単な例としては、ユーザーに「今日のランダムな名言」を提示したり、コンピュータ ゲームでコンピュータ制御の敵がどの方向に移動するかを判断したりすることが挙げられます。より弱い形式のランダム性は、ハッシュ アルゴリズムや、償却 検索およびソート アルゴリズムの作成で使用されます。

一見ランダム化に適しているように見えるアプリケーションの中には、実際にはそれほど単純ではないものもあります。たとえば、バックグラウンド ミュージック システムの音楽トラックを「ランダムに」選択するシステムは、ランダムに見えるだけでよく、音楽の選択を制御する方法さえある場合があります。真にランダムなシステムでは、同じ項目が 2 回または 3 回続けて表示されても制限はありません。

乱数を生成するために使用される主な方法は 2 つあります。最初の方法は、ランダムであると予想される何らかの物理現象を測定し、測定プロセスで起こり得る偏りを補正します。例として、大気ノイズ、熱ノイズ、その他の外部電磁気現象や量子現象の測定が挙げられます。たとえば、短い時間スケールで測定される宇宙背景放射線や放射性崩壊は、自然エントロピーの源を表します(数値生成プロセスの予測不可能性や意外性の尺度として)。

自然のソースからエントロピーを得られる速度は、測定される基礎となる物理現象に依存します。したがって、自然に発生する「真の」エントロピーのソースはブロッキングしていると言われます 。つまり、需要を満たすのに十分なエントロピーが収穫されるまで、レートが制限されます。ほとんどのLinux ディストリビューションを含む一部の Unix 系システムでは、環境から十分なエントロピーが収穫されるまで、疑似デバイス ファイル/dev/random が^{ブロックされます。 [2]}このブロッキング動作のため、ハードディスク ドライブをランダム ビットで埋めるなど、/dev/randomからの大量の読み取りは、このタイプのエントロピー ソースを使用するシステムでは遅くなることがよくあります。

2 番目の方法では、一見ランダムな結果の長いシーケンスを生成できる計算アルゴリズムを使用します。これらのシーケンスは、実際にはシード値またはキーと呼ばれる短い初期値によって完全に決定されます。その結果、シード値がわかっていれば、一見ランダムなシーケンス全体を再現できます。このタイプの乱数ジェネレーターは、疑似乱数ジェネレーターと呼ばれることがよくあります。このタイプのジェネレーターは、通常、自然に発生するエントロピーのソースに依存しませんが、自然のソースによって定期的にシードされる場合があります。このタイプのジェネレーターは非ブロッキングであるため、外部イベントによってレート制限されず、大量の一括読み取りが可能になります。

一部のシステムでは、ハイブリッド アプローチを採用しており、利用可能な場合は自然ソースから収集した乱数を提供し、定期的に再シードされるソフトウェア ベースの暗号的に安全な疑似乱数ジェネレータ(CSPRNG) にフォールバックします。フォールバックは、必要な乱数の読み取り速度が、自然収集アプローチの要求に対応できる能力を超えた場合に発生します。このアプローチでは、より低速で純粋に環境的な方法に基づく乱数ジェネレータの速度制限ブロッキング動作を回避できます。

決定論的論理のみに基づく擬似乱数生成器は、言葉の最も純粋な意味で「真の」乱数源とみなすことは決してできないが、実際には、要求の厳しいセキュリティクリティカルなアプリケーションでも一般的に十分である。慎重に設計および実装された擬似乱数生成器は、yarrowアルゴリズムやfortunaの場合のように、セキュリティクリティカルな暗号化目的に認定される可能性がある。前者は、 FreeBSD、AIX、macOS、NetBSDなどのエントロピーの/dev/randomソースの基礎である。OpenBSDは、arc4randomと呼ばれる擬似乱数アルゴリズムを使用している。^{[疑わしい-議論] [3]}

サイコロ、コイン投げ、ルーレットなどの乱数を生成する最も初期の方法は、統計や暗号化のほとんどの用途には遅すぎる傾向があるため、主にゲームやギャンブルで今日でも使用されています。

ハードウェア乱数ジェネレータは、本質的にランダムな原子または亜原子物理現象に基づくことができ、その予測不可能性は量子力学の法則にまで遡ることができます。^{[4] [5]}エントロピーの発生源には、放射性崩壊、熱雑音、ショット雑音、ツェナーダイオードのアバランシェ雑音、クロックドリフト、ハードディスクの読み書きヘッドの実際の動きのタイミング、無線雑音などがあります。ただし、物理現象とそれを測定するために使用されるツールは、一般に非対称性と体系的な偏りを特徴としており、その結果は均一にランダムではありません。暗号ハッシュ関数などのランダム性抽出器を使用すると、ビットレートは低くなりますが、非均一にランダムなソースからビットの均一な分布に近づくことができます。

光カオスや増幅された自然放出ノイズなどの広帯域光エントロピー源の出現は、物理乱数発生器の開発に大きく貢献しています。その中でも、光カオス^{[6] [7]}は、その高帯域幅と大振幅により、高速乱数を物理的に生成する可能性を秘めています。カオスレーザーをベースにした高速リアルタイム物理乱数ビット発生器のプロトタイプが2013年に構築されました。^[8]

このエントロピー情報を収集するためのさまざまな独創的な方法が考案されています。1つの手法は、予測できないソースからのビデオストリームのフレームに対してハッシュ関数を実行することです。Lavarandは、この手法を多数の溶岩ランプの画像に使用しました。HotBitsはガイガーミュラー管で放射性崩壊を測定しました^[9] 。一方、Random.orgは通常のラジオで記録された大気ノイズの振幅の変化を使用しています。

もう一つの一般的なエントロピー源は、システムを使用する人間の行動です。人間は要求に応じて優れたランダム性を生成するとは考えられていませんが、混合戦略ゲームをプレイする状況では、ランダムな行動をかなりうまく生成します。^{[10]セキュリティ関連のコンピュータソフトウェアの中には、ランダム}キーを生成したり、疑似乱数ジェネレータを初期化したりするために必要な十分なエントロピーを生成するために、ユーザーがマウスの動きやキーボード入力を長時間繰り返すことを要求するものもあります。^[11]

コンピュータで生成される乱数のほとんどはPRNGを使用しています。PRNGは、ランダムな特性を持つ長い連続した数値を自動的に生成できるアルゴリズムですが、最終的にはシーケンスが繰り返されます（またはメモリ使用量が無制限に増加します）。これらの乱数は多くの状況で問題ありませんが、エントロピーのソースとして使用される電磁大気ノイズから生成される数値ほどランダムではありません。^{[12]このようなアルゴリズムによって生成される一連の値は、通常、}シードと呼ばれる固定数によって決定されます。最も一般的なPRNGの1つは、再帰を使用する 線形合同型ジェネレータです。

${\displaystyle X_{n+1}=(aX_{n}+b)\,{\textrm {mod}}\,m}$

数値を生成する。ここで、a、b、mは大きな整数で、 はX内の次の数値である。式が生成できる数値の最大数は、法、mである。再帰関係を行列に拡張して、はるかに長い周期とより優れた統計的特性を持たせることができる。^{[13]単一の線形合同型ジェネレータの特定の非ランダムな特性を回避するために、乗数係数}a の値がわずかに異なる複数の乱数ジェネレータを並列に使用し、複数の異なるジェネレータの中から選択する「マスター」乱数ジェネレータを使用することができる。 ${\displaystyle X_{n+1}}$

乱数を生成するための単純なペンと紙の方法は、ジョン・フォン・ノイマンが提案したいわゆるミドルスクエア法である。実装は簡単だが、その出力は質が悪い。周期が非常に短く、出力シーケンスがほぼ常にゼロに収束するなどの重大な弱点がある。最近の革新は、ミドルスクエアとワイルシーケンスを組み合わせることである。この方法は、長い周期にわたって高品質の出力を生成する。^[14]

ほとんどのコンピュータ プログラミング言語には、乱数ジェネレーターを提供する関数またはライブラリ ルーチンが含まれています。これらは、ランダムなバイトまたはワード、または0 から 1 の間で均一に分布する浮動小数点数を提供するように設計されることがよくあります。

このようなライブラリ関数の品質、すなわちランダム性は、完全に予測可能な出力から暗号的に安全なものまで、幅広く異なります。Python、Ruby、R、IDL、PHP など多くの言語のデフォルトの乱数生成器はメルセンヌツイスターアルゴリズムに基づいており、言語のドキュメントに明示的に記載されているように、暗号化の目的には不十分です。このようなライブラリ関数は統計特性が貧弱であることが多く、数万回の試行でパターンを繰り返すものもあります。これらの関数は、コンピューターのリアルタイムクロックをシードとして使用して初期化されることがよくあります。これは、そのようなクロックが 64 ビットでナノ秒単位で測定され、人間の精度をはるかに超えるためです。これらの関数は、特定のタスク (たとえば、ビデオゲーム) には十分なランダム性を提供しますが、暗号化アプリケーションや統計など、高品質のランダム性が要求される場合には適していません。^[15]

ほとんどのオペレーティング システムでは、はるかに高品質の乱数ソースが利用できます。たとえば、さまざまな BSD フレーバー、Linux、Mac OS X、IRIX、Solaris の/dev/random 、または Microsoft Windows のCryptGenRandomなどです。上記の言語を含むほとんどのプログラミング言語では、これらの高品質のソースにアクセスする手段が提供されています。

乱数生成は、エンドユーザーからさまざまな入力を収集し、それをランダム化ソースとして使用するという形で、人間によって実行されることもあります。しかし、ほとんどの研究では、人間の被験者は、数字や文字などのランダムなシーケンスを生成しようとすると、ある程度の非ランダム性があることがわかっています。優れたランダムジェネレータと比較すると、選択肢を頻繁に切り替える場合があります。^[16]そのため、このアプローチは広く使用されていません。しかし、人間がこのタスクでうまく機能しないという理由から、人間の乱数生成は、他の方法ではアクセスできない脳機能に関する洞察を得るためのツールとして使用できます。^[17]

たとえ、もっともらしい乱数のソース（おそらく量子力学に基づくハードウェア ジェネレーターからのもの）が与えられたとしても、完全に偏りのない数値を取得するのは面倒です。さらに、これらのジェネレーターの動作は、温度、電源電圧、デバイスの経年変化、またはその他の外部干渉によって変化することがよくあります。

生成された乱数は、基礎となるソースがまだ機能していることを確認するために使用前に統計テストを受けることがあり、その後、統計特性を改善するために後処理されます。一例として、TRNG9803 ^[18]ハードウェア乱数ジェネレーターが挙げられます。これは、エントロピー測定をハードウェアテストとして使用し、その後、シフトレジスタストリーム暗号を使用してランダムシーケンスを後処理します。生成された乱数を統計テストを使用して検証することは通常困難です。Wang と Nicol ^{[19] は、}いくつかの乱数ジェネレーターの弱点を識別するために使用される距離ベースの統計テスト手法を提案しました。Li と Wang ^{[20] は}、ブラウン運動特性を使用してレーザーカオスエントロピーソースに基づいて乱数をテストする方法を提案しました。

統計テストは、乱数ジェネレータからの後処理された最終出力が本当に偏りがないことを確信するためにも使用され、多数のランダム性テストスイートが開発されています。

ほとんどの乱数生成器は整数または個々のビットをネイティブに処理するため、0から1の間の「標準的な」均一分布に到達するには追加の手順が必要です。実装は整数をその最大値で割るほど簡単ではありません。具体的には、次のようになります。^{[21] [22]}

1. 変換に使用される整数は、意図した精度に十分なビットを提供する必要があります。
2. 浮動小数点演算の性質上、数値がゼロに近いほど精度が高くなります。必要なビット数が膨大であるため、この余分な精度は通常使用されません。
3. 除算の丸め誤差により、結果に偏りが生じる可能性があります。最悪の場合、実数計算に基づく予想に反して、除外されるはずの境界が描画される可能性があります。

OpenJDK、Rust、NumPyで使用されている主流のアルゴリズムは、C++のSTLの提案で説明されています。このアルゴリズムは余分な精度を使用せず、偶数への丸めにより最後のビットにのみ偏りが生じます。 ^[23]この「標準的な」均一分布を別の範囲に移す場合は、他の数値的な懸念が正当化されます。^[24] Swiftプログラミング言語の提案された方法は、どこでも完全な精度を使用すると主張しています。^[25]

一様分布の整数は、フィッシャー・イェイツ・シャッフルなどのアルゴリズムでよく使用されます。ここでも、単純な実装では結果にモジュロバイアスが生じる可能性があるため、より複雑なアルゴリズムを使用する必要があります。ほとんど除算を行わない方法は、2018年にダニエル・ルミールによって説明されました。^[26]現在の最先端技術は、算術符号化に触発された2021年の「最適アルゴリズム」であり、Apple Inc.のスティーブン・キャノンによって開発されました^。[27]

ほとんどの 0 対 1 RNG には 0 が含まれますが 1 は含まれません。一方、両方が含まれるか除外される RNG もあります。

一様乱数のソースが与えられた場合、確率密度関数に対応する新しい乱数ソースを作成する方法はいくつかあります。1つは反転法と呼ばれ、乱数（適切な分布のためには0と1の間で生成される必要があります）以上の領域まで積分するものです。2つ目の方法は受け入れ拒否法と呼ばれ、xとyの値を選択し、xの関数がyの値より大きいかどうかをテストします。大きい場合は、xの値が受け入れられます。そうでない場合は、xの値が拒否され、アルゴリズムが再試行されます。^{[28] [29]}

棄却標本抽出の例として、統計的に独立した 標準正規分布乱数のペア（x、y ）を生成するには、まず極座標（r、θ ）を生成します。ここで、r ² ~ χ ₂ ²およびθ ~ UNIFORM(0,2π) です（ボックス・ミュラー変換を参照）。

複数の独立した RNG の出力を組み合わせることで (たとえば、ビット単位のXOR演算を使用)、使用される最良の RNG と同等以上の結合 RNG を提供できます。これはソフトウェア ホワイトニングと呼ばれます。

計算による乱数ジェネレータとハードウェアによる乱数ジェネレータは、両方の利点を生かすために組み合わせられることがあります。計算による乱数ジェネレータは通常、物理的なジェネレータよりもはるかに高速に疑似乱数を生成できますが、物理的なジェネレータは「真のランダム性」を生成できます。

乱数ジェネレータを使用する計算の中には、モンテカルロ法による積分の計算など、合計値または平均値の計算として要約できるものがあります。このような問題では、いわゆる低乖離数列 (準乱数とも呼ばれます) を使用することで、より正確な解を見つけることができる場合があります。このような列には、定性的に言えば、ギャップを均等に埋める明確なパターンがあります。真にランダムな列では、より大きなギャップが残る可能性があり、通常はそうなります。

以下のサイトでは乱数サンプルが提供されています。

• SOCRリソース ページには、 Java アプレットを使用した乱数生成の実践的なインタラクティブ アクティビティとデモンストレーションが多数含まれています。
• ANUの量子光学グループは、量子真空から乱数を生成します。乱数のサンプルは、量子乱数ジェネレータの研究ページで入手できます。
• Random.org は、大気ノイズのランダム性から生成される乱数を提供します。
• Ruđer Bošković 研究所の量子ランダム ビット ジェネレーター サービスは、半導体の光子放出の量子プロセスからランダム性を獲得します。このサービスでは、複数のプログラミング言語のライブラリを含む、データを取得するためのさまざまな方法を提供しています。
• 太原理工大学のグループは、カオスレーザーから乱数を生成します。乱数のサンプルは、物理乱数生成器サービスで入手できます。

多くの暗号化は、キーと暗号ノンスの生成に暗号的に安全な乱数ジェネレータに依存しているため、乱数ジェネレータが予測可能であれば、攻撃者がそれをバックドアとして使用して暗号化を解読することができます。

NSA は、NIST認定の暗号的に安全な疑似乱数生成器 Dual EC DRBGにバックドアを挿入したと報じられている。たとえば、この乱数生成器を使用して SSL 接続が作成されると、Matthew Greenによると、NSA は乱数生成器の状態を判断でき、最終的には SSL 接続を介して送信されるすべてのデータを読み取ることができるようになる。^[30] Dual_EC_DRBG は、2013 年に NSA のバックドアが確認されるずっと前から、非常に貧弱でバックドアが仕掛けられている可能性のある疑似乱数生成器であることは明らかだったが、2013 年まで、たとえば著名なセキュリティ会社RSA Securityによって、実際にかなり使用されていた。^{[31]その後、RSA Security が、おそらく}Bullrun プログラムの一環として、NSA のバックドアを自社製品に故意に挿入したとの非難が高まった。RSAは、自社製品に故意にバックドアを挿入したことを否定している。^[32]

また、ハードウェア RNG は、公表されているよりもエントロピーが低くなるように秘密裏に改造され、ハードウェア RNG を使用した暗号化が攻撃を受けやすくなるという理論もあります。公開されているそのような方法の 1 つは、チップのドーパント マスクを改造することで機能し、光学的なリバース エンジニアリングでは検出されません。^[33]たとえば、Linux での乱数生成では、特に NSA の Bullrun プログラムが暴露されて以来、ハードウェア RNG のバックドアに対抗するために、RDRAND 出力を他のエントロピー ソースと混合せずに Intel のRDRANDハードウェア RNG を使用することは受け入れられないとされています。^{[34] [35]}

2010年、米国の宝くじの抽選は、マルチステート宝くじ協会（MUSL）の情報セキュリティディレクターによって不正に操作された。このディレクターは、定期メンテナンス中にMUSLの安全なRNGコンピュータに密かにバックドアマルウェアをインストールした。 ^[36]ハッキング中に、この男は数年にわたって総額1650万ドルを獲得した。

• ドナルド・クヌース(1997)。「第 3 章 - 乱数」。コンピュータ プログラミングの芸術。第 2 巻: 半数値アルゴリズム (第 3 版)。
• L'Ecuyer, Pierre (2017)。「一様乱数生成の歴史」(PDF)。2017年冬季シミュレーション会議の議事録。IEEE Press。pp. 202–230。
• L'Ecuyer, Pierre (2012)。「乱数生成」(PDF)。JE Gentle、W. Haerdle、Y. Mori (編)。計算統計ハンドブック: 概念と方法。計算統計ハンドブック(第 2 版)。Springer-Verlag。pp. 35–71。doi :10.1007 / 978-3-642-21551-3_3。hdl : 10419 / 22195。ISBN 978-3-642-21550-6。
• Kroese, DP ; Taimre, T.; Botev, ZI (2011)。「第 1 章 – 均一乱数生成」。モンテカルロ法ハンドブック。ニューヨーク: John Wiley & Sons。p. 772。ISBN 978-0-470-17793-8。
• Press, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007)。「第 7 章 乱数」。数値レシピ: 科学計算の技法(第 3 版)。ニューヨーク: Cambridge University Press。ISBN 978-0-521-88068-8。
• 乱数生成に関するNIST SP800-90A、B、Cシリーズ
• M. Tomassini、M. Sipper、M. Perrenoud (2000 年 10 月)。「2 次元セルオートマトンによる高品質乱数の生成について」IEEE Transactions on Computers 49 ( 10): 1146–1151. doi :10.1109/12.888056. S2CID  10139169。

• RANDOM.ORG 真の乱数サービス
• ANU の量子乱数ジェネレータ
• BBCのIn Our Timeにおけるランダムと疑似ランダム
• jRand は、数値の疑似乱数シーケンスを含むシミュレーションシーケンスを生成するための Java ベースのフレームワークです。
• NAG Fortran ライブラリの乱数ジェネレータ
• NISTの Randomness Beacon は、 60 秒ごとに 512 ビットのブロックで完全なエントロピービット文字列をブロードキャストします。予測不可能性、自律性、一貫性を提供するように設計されています。
• 乱数用のシステムコール: getrandom()、専用の Linux システムコールを説明するLWN.net の記事
• 擬似ランダムシーケンスの統計的特性と PHP および Debian OpenSSL での実験
• アバランシェノイズに基づくランダムシーケンスジェネレータ