Loading article…
乱数生成とは、多くの場合乱数発生器（RNG）を用いて、ランダムな偶然よりも合理的に予測できない数値または記号のシーケンスを生成するプロセスです。つまり、特定の結果シーケンスには、後から検出できるが予測不可能なパターンが含まれます。真の乱数発生器は、ハードウェア乱数発生器（HRNG）であり、各生成は、モデル化が事実上不可能な方法で常に変化する物理環境の属性の現在の値の関数です。これは、擬似乱数発生器（PRNG）によって行われるいわゆる乱数生成とは対照的です。擬似乱数は、実際にはあらかじめ決定されており、これらの数値は、PRNGの初期状態と数値を生成するために使用する方法を知るだけで再現できます。[ 1 ]また、コンピュータシステムに存在するエントロピーを収集することによって、専用のハードウェアソースにアクセスせずに真の乱数を生成する非物理的真の乱数発生器（NPTRNG）のクラスもあります。 [ 2 ]詳細は「真の乱数と擬似乱数」を参照してください。
ランダム性の様々な応用により、ランダムデータを生成するための様々な方法が開発されてきました。これらの方法の中には、サイコロを振る、コインを投げる、トランプをシャッフルする、易経で蓍草の茎（占いに）を用いるなど、古代から存在するものもあり、その他にも数え切れないほどの技法があります。これらの技法は機械的な性質を持つため、統計学において重要な、十分な量のランダムな数値を生成するには、多くの労力と時間を要しました。そのため、結果は乱数表として収集・配布されることもありました。
擬似乱数生成のための計算手法はいくつか存在する。いずれも真のランダム性という目標には達していないが、結果の予測不可能性（つまり、パターンがどの程度識別可能か）を測定するための統計的ランダム性テストには、程度の差こそあれ合格する可能性がある。そのため、一般的にこれらの手法は暗号化などの用途には使用できない。しかし、暗号化での使用を目的とした特別な機能を備えた、慎重に設計された暗号的に安全な擬似乱数生成器（CSPRNG）も存在する。
乱数発生器は、ギャンブル、統計的サンプリング、コンピュータシミュレーション、暗号化、完全ランダム化設計など、予測不可能な結果を生み出すことが望ましい分野で応用されています。一般的に、セキュリティアプリケーションのように予測不可能性が最重要視されるアプリケーションでは、可能な限り擬似乱数アルゴリズムよりもハードウェア乱数発生器が好まれます。
擬似乱数生成器は、モンテカルロ法シミュレーションの開発において非常に有用です 。同じ乱数シードから開始することで、同じ乱数列を再度実行できるため、デバッグが容易になります。また、シードが秘密にされている限り、暗号化にも使用されます。送信者と受信者は、鍵として使用する同じ乱数セットを自動的に生成できます。
擬似乱数の生成は、コンピュータプログラミングにおいて重要かつ一般的なタスクです。暗号化や特定の数値アルゴリズムでは非常に高いレベルの見かけ上のランダム性が求められますが、他の多くの操作では、ある程度の予測不可能性があれば十分です。簡単な例としては、ユーザーに「今日のランダムな名言」を表示したり、コンピュータゲームでコンピュータ制御の敵がどちらの方向に動くかを予測したりすることが挙げられます。ハッシュアルゴリズムや、償却型の検索・ソートアルゴリズムの作成には、より弱い形式のランダム性が用いられます。
一見ランダム化に適しているように見えるアプリケーションでも、実際にはそれほど単純ではない場合があります。例えば、BGMシステムで音楽トラックを「ランダムに」選択するシステムは、ランダムに見えるだけでよく、音楽の選択を制御する仕組みを備えている場合もあります。真にランダムなシステムであれば、同じ曲が2回、3回と連続して再生されることに制限はありません。
乱数を生成するには、主に2つの方法があります。1つ目の方法は、ランダムであると予想される物理現象を測定し、測定プロセスにおける潜在的なバイアスを補正する方法です。例としては、大気ノイズ、熱ノイズ、その他の外部電磁気現象や量子現象の測定が挙げられます。例えば、短時間スケールで測定された宇宙背景放射や放射性崩壊は、自然エントロピー（乱数生成プロセスの予測不可能性や意外性の尺度）の源となります。
自然界からエントロピーを取得できる速度は、測定対象となる物理現象に依存します。そのため、自然界に存在する真のエントロピー源はブロッキングであると言われます。つまり、需要を満たすのに十分なエントロピーが収集されるまで、速度が制限されます。ほとんどのLinux ディストリビューションを含む一部の Unix ライクなシステムでは、擬似デバイス ファイル/dev/randomは、環境から十分なエントロピーが収集されるまでブロックされます。[ 3 ]このブロッキング動作のため、ハードディスク ドライブをランダム ビットで埋めるなど、/dev/randomからの大規模な一括読み取りは、このタイプのエントロピー ソースを使用するシステムでは遅くなることがよくあります。
2つ目の方法は、一見ランダムに見える結果の長いシーケンスを生成できる計算アルゴリズムを使用します。これらのシーケンスは実際には、シード値またはキーと呼ばれる短い初期値によって完全に決定されます。結果として、シード値がわかっている場合は、一見ランダムに見えるシーケンス全体を再現できます。このタイプの乱数生成器は、擬似乱数生成器と呼ばれることがよくあります。このタイプの生成器は通常、自然発生的なエントロピー源に依存しませんが、自然発生源によって定期的にシードされることがあります。このタイプの生成器は非ブロッキングであるため、外部イベントによってレートが制限されず、大量の読み取りが可能になります。
標準的な暗号設計では、自然発生源から得られたランダム性を使用して暗号的に安全な擬似乱数発生器(CSPRNG) のシードを生成するハイブリッドアプローチを採用しています。ハードウェア乱数発生器は、一般的に毎秒生成できるランダムビット数が限られています。利用可能な出力データレートを上げるために、より高速な PRNG の「シード」を生成するためによく使用されます。PRNG は、ノイズ源の「匿名化」（ノイズ源の識別特性をホワイトニング）とエントロピー抽出にも役立ちます。適切な PRNG アルゴリズム (暗号的に安全な擬似乱数発生器、CSPRNG)を選択すれば、この組み合わせは連邦情報処理標準および共通基準の要件を満たすことができます。[ 4 ]
サイコロ、コイン投げ、ルーレットなど、乱数を生成する最も初期の方法は、統計学や暗号学におけるほとんどの用途には処理速度が遅すぎるため、現在でも主にゲームやギャンブルで使用されている。
多くの自然現象は、熱雑音やショット雑音、電子回路のジッターやメタステーブル性、ブラウン運動、大気雑音など、低レベルで統計的にランダムな「ノイズ」信号を生成します。[ 5 ]研究者たちは、ビームスプリッターを含む光電効果、その他の量子現象、[ 6 ] [ 7 ] [ 8 ][9] [ 10 ]さらには核崩壊も利用しました（実際的な考慮事項から、後者は、大気雑音と同様に、かなり限定されたアプリケーションやオンライン配信サービスを除いては実現不可能です）。[ 5 ]「古典的」（非量子的）現象は真にランダムではありませんが、予測不可能な物理システムは通常、ランダム性の源として受け入れられるため、「真の」と「物理的な」という修飾語は互換的に使用されます。[ 11 ]
ハードウェア乱数発生器は、ほぼ完璧な乱数（「完全なエントロピー」）を出力することが期待されます。[ 12 ]物理プロセスは通常この特性を持たず、実用的なTRNGは通常いくつかのブロックを含みます。[ 13 ]
パフォーマンスとセキュリティ上の理由から、ほとんどの乱数発生器は、その構造に擬似乱数発生器（PRNG）を使用しています（このアーキテクチャは、NIST SP 800-90Aなどの業界標準で実際に義務付けられています）。
擬似乱数発生器（PRNG）は、決定論的乱数ビット発生器（DRBG）とも呼ばれ、[ 14 ]乱数列の特性に近似する特性を持つ数列を生成するアルゴリズムです。PRNG で生成された数列は、初期値または状態（通常は PRNG のシードと呼ばれる、真の乱数値に基づく場合もある）によって完全に決定されるため、真の乱数ではありません。ハードウェア乱数発生器を使用すれば、真の乱数に近い数列を生成できますが、擬似乱数発生器は、乱数生成の速度と再現性の高さから、実際には重要です。[ 15 ]
擬似乱数生成器（PRNG）は、シミュレーション（モンテカルロ法など）、電子ゲーム（プロシージャル生成など）、暗号化といったアプリケーションにおいて中心的な役割を果たします。暗号化アプリケーションでは、出力が以前の出力から予測できないことが求められるため、より単純なPRNGの線形性を継承しない、より高度なアルゴリズムが必要となります。
適切な統計的特性は、擬似乱数発生器の出力にとって中心的な要件です。特定の擬似乱数発生器が、意図された用途に適した、十分にランダムに近い数値を生成するという合理的な確信を持つためには、慎重な数学的分析が必要です。ジョン・フォン・ノイマンは、擬似乱数発生器を真の乱数発生器と誤解する可能性について警告し、「乱数を生成する算術的方法を考える人は、もちろん罪深い状態にある」と冗談を言いました。[ 16 ]
乱数生成は、エンドユーザーからさまざまな入力を集めてそれをランダム化ソースとして使用するという形で、人間によっても実行できます。しかし、ほとんどの研究では、人間が数字や文字などのランダムなシーケンスを生成しようとする際に、ある程度の非ランダム性があることがわかっています。優れた乱数生成器と比較すると、選択が頻繁に交互になる可能性があります。 [ 17 ]そのため、この方法は広く使用されていません。しかし、人間がこのタスクでうまく機能しないというまさにその理由から、人間の乱数生成は、通常ではアクセスできない脳機能についての洞察を得るためのツールとして使用できます。[ 17 ]
もっともらしい乱数源（例えば量子力学に基づいたハードウェア乱数発生器）があったとしても、完全に偏りのない乱数を得るには注意が必要です。さらに、これらの乱数発生器の動作は、温度、電源電圧、デバイスの経年劣化、その他の外部干渉によって変化することがよくあります。
生成された乱数は、基となるソースがまだ機能していることを確認するために、使用前に統計的テストにかけられることがあり、その後、統計的特性を改善するために後処理されます。例としては、ハードウェアテストとしてエントロピー測定を使用し、その後、シフトレジスタストリーム暗号で乱数シーケンスを後処理するハードウェア乱数発生器 TRNG9803 [ 18 ]があります。一般的に、統計的テストを使用して生成された乱数を検証することは困難です。Wang と Nicol [ 19 ]は、いくつかの乱数発生器の弱点を特定するために使用される距離ベースの統計的テスト手法を提案しました。Li と Wang [ 20 ]は、ブラウン運動特性を使用してレーザーカオスエントロピーソースに基づく乱数をテストする方法を提案しました。
統計的検定は、乱数発生器からの後処理された最終出力が真に偏りのないものであることを確認するためにも使用され、数多くの乱数性検定スイートが開発されている。
ほとんどの乱数生成器は、整数または個々のビットをネイティブに扱うため、 0 から 1 の間の標準的な一様分布に到達するには追加の手順が必要です。実装は、整数をその最大値で割るほど単純ではありません。具体的には次のようになります。[ 21 ] [ 22 ]
OpenJDK、Rust、NumPyで使用されている主流のアルゴリズムは、C++の STLの提案で説明されています。これは追加の精度を使用せず、半分を偶数に丸めるため最後のビットのみにバイアスが発生します。[ 23 ]この標準的な一様分布を別の範囲にシフトすると、他の数値的な懸念が生じます。 [ 24 ] Swift プログラミング言語の提案された方法は、すべての場所で完全な精度を使用すると主張しています。[ 25 ]
フィッシャー・イェーツ・シャッフルなどのアルゴリズムでは、一様分布整数がよく使用されます。ここでも、単純な実装では結果に剰余バイアスが生じる可能性があるため、より複雑なアルゴリズムを使用する必要があります。除算をほとんど行わない方法は、2018年にダニエル・レミールによって説明されました[ 26 ]。現在の最先端は、Apple Inc.のスティーブン・キャノンによる、算術符号化に着想を得た2021年の「最適アルゴリズム」です[ 27 ]。
ほとんどの0から1までの乱数生成器は0を含み1を除外するが、中には0と1の両方を含むものや除外するものもある。
一様乱数の発生源が与えられた場合、確率密度関数に対応する新しい乱数発生源を作成する方法はいくつかあります。 1 つの方法は反転法と呼ばれ、乱数（適切な分布のためには 0 から 1 の間で生成される必要があります）以上の面積まで積分します。 2 番目の方法は受理拒否法と呼ばれ、x と y の値を選択し、x の関数が y の値より大きいかどうかをテストします。大きい場合は、x の値が受理されます。そうでない場合は、x の値が拒否され、アルゴリズムが再度試行します。[ 28 ] [ 29 ]
棄却サンプリングの例として、統計的に独立した標準正規分布乱数 ( x、y ) のペアを生成するには、まず極座標( r、θ ) を生成することができます。ここで、r 2 ~ χ 2 2およびθ ~ UNIFORM(0,2π)です (ボックス-ミュラー変換を参照)。
複数の独立した乱数生成器の出力を組み合わせることで（例えば、ビット単位のXOR演算を用いるなど）、使用する乱数生成器の中で最も優れたものと同等以上の性能を持つ合成乱数生成器を生成できます。これはソフトウェアホワイトニングと呼ばれます。
計算機式乱数発生器とハードウェア式乱数発生器は、両方の利点を活かすために組み合わせられることがある。計算機式乱数発生器は、一般的に物理式乱数発生器よりもはるかに高速に擬似乱数を生成できる一方、物理式乱数発生器は真の乱数を生成できる。
乱数発生器を用いる計算の中には、モンテカルロ法による積分の計算のように、合計値や平均値の計算として要約できるものがあります。このような問題に対しては、いわゆる低不一致数列（準乱数とも呼ばれる）を用いることで、より正確な解を見つけることができる場合があります。このような数列は、定性的に言えば、欠落部分を均等に埋める明確なパターンを持っています。一方、真のランダム数列は、より大きな欠落部分を残すことが多く、実際にもそうなります。
以下のサイトでは、乱数サンプルを入手できます。
暗号化の多くは、鍵と暗号的ナンスの生成に暗号学的に安全な乱数生成器に依存しているため、乱数生成器が予測可能であれば、攻撃者はそれをバックドアとして利用して暗号化を破ることができる。
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の安全な乱数発生器コンピューターにバックドアマルウェアを密かにインストールした。 [ 36 ]このハッキングにより、この男は複数年にわたり合計1650万ドルを獲得した。
{{cite conference}}: CS1 maint: bot: 元の URL の状態が不明です (リンク)