algorithm - 真の乱数発生器

Question

これは「本当の」質問ではないことを申し訳ありませんが、疑似ランダムだけでなく、真の乱数を生成するためにランダマイザーをランダムにランダム化することについての投稿をここで見たことを覚えています。探しても見当たりません。

その記事について知っている人はいますか？

score 27 · Accepted Answer

この質問に対する多くの回答には同意できません。

コンピュータ上でランダムなデータを収集することは可能です。それができなければ、SSL、SSH、および VPN は安全ではありません。

ソフトウェア乱数ジェネレーターの動作方法には、クロックドリフト、割り込みタイミングなど、さまざまな場所から収集されたランダムデータのプールがあります。

これらのスキームの秘訣は、エントロピー(ランダム性の高級な名前) を正しく推定することにあります。エントロピーを正しく推定する限り、ソースがバイアスであるかどうかは問題ではありません。

これを説明するために、このコメントで文字eを押す可能性はzの可能性よりもはるかに高いため、キー割り込みをエントロピーのソースとして使用する場合、それはバイアスになりますが、まだランダム性が必要です。その入力で。この段落で次に来る文字列を正確に予測することはできません。この不確実性からエントロピーを抽出し、ランダムバイトの一部として使用できます。

Yarrowのような高品質の実乱数ジェネレーターには、非常に高度なエントロピー推定が組み込まれており、「乱数プール」にあると確実に言える数のバイトのみを出力します。

score 17 · Accepted Answer

それはthedailywtf.comにあったと思います-つまり。あなたがしたいことではありません。

randomize() を何度呼び出しても、疑似乱数から真の乱数を取得することはできません。

特別なハードウェアから「真の」乱数を取得できます。マウスの動きなどからエントロピーを収集することもできます。

score 10 · Accepted Answer

乱数の定義は次のとおりであるため、真の乱数のアルゴリズムは存在できません。

予測できない結果があり、理想的な場合は、すべての結果が同じように発生する可能性があります。そのような選択の結果; 統計的相関がない。

より良いまたはより悪い疑似乱数ジェネレータ（PRNG）があります。つまり、シードと呼ばれる情報を知らなければ予測するのが難しい、完全に予測可能な数のシーケンスです。

現在、シードを推測するのが非常に難しいPRNGは、暗号的に安全です。それがあなたが探しているものであるならば、あなたはグーグルでそれらを調べたいかもしれません。

別の方法（これが本当にランダムであるかどうかは哲学的な質問です）は、ランダムなデータソースを使用することです。たとえば、ノイズや放射性崩壊の測定など、予測できない物理量。

これらは、独立して測定したり、バイアスをかけたりすることができるため、依然として攻撃の対象になります。ですから、それは本当にトリッキーです。これは、通常はかなり高価なカスタムハードウェアを使用して行われます。どれだけ優れているかはわかりませ/dev/randomんが、暗号化には十分ではないでしょう（ほとんどの暗号化プログラムには独自のRNGが付属しており、Linuxは起動時にハードウェアRNGも探します）。

score 10 · Accepted Answer

投稿の最後で、「ランダム性を高める」ために複数の乱数ジェネレーターを使用する理由についての質問にお答えします。

ランダム性が何を意味するかについては、哲学的な議論があります。ここでは、「抽出されたサンプル全体の均一な (0,1) iid 分布とあらゆる点で見分けがつかない」ことを意味します。ランダムとは何かという哲学的な問題を完全に無視しています。

Knuth 第 2 巻には、あなたが提案するように乱数ジェネレーターを作成しようとする分析があり、次に、それが失敗する理由と、真のランダムプロセスとは何かを分析します。第 2 巻では、RNG について詳しく説明します。

他の人は、ランダムな物理プロセスを使用して乱数を生成することを推奨しています。ただし、Espo/vt の相互作用でわかるように、これらのプロセスには、決定論的な動作を伴う外部要因の一部が原因で、微妙な周期的要素やその他の非ランダム要素が含まれる場合があります。一般に、ランダム性を仮定しないことが最善ですが、常にそれをテストしてください。通常、そのようなアーティファクトを認識している場合は修正できます。

決定論的に完全にランダムに見える「無限」のビットストリームを作成することが可能です。残念ながら、このようなアプローチは、要求されたビット数に応じてメモリ内で成長するため (サイクルの繰り返しを避けるために必要になるため)、その範囲は制限されます。

実際には、ほとんどの場合、既知のプロパティを持つ疑似乱数ジェネレーターを使用する方が適切です。探すべき重要な数値は、位相空間の次元 (一様に分布していると見なすことができるサンプル間のおおよそのオフセット) とビット幅 (各サンプル内で互いに一様にランダムなビットの数) です。 )、およびサイクルサイズ (分布が繰り返される前に取得できるサンプル数)。

ただし、特定のジェネレーターからの乱数は決定論的に既知のシーケンスにあるため、ジェネレーターを検索して整列シーケンスを見つける誰かによって手順が公開される可能性があります。したがって、2 つのジェネレーターを保持している場合、ディストリビューションが特定の乱数ジェネレーターからのものであるとすぐに認識されることを回避できる可能性があります。最初から、i をサンプリングし、これを 1 から n に一様にマッピングします。ここで、n は最大でも位相次元です。次に、2 番目に i 回サンプリングし、i 番目の結果を返します。これにより、最悪の場合、サイクルサイズが (元のサイクルサイズ/n) に縮小されますが、そのサイクルでも一様な乱数が生成され、n でアライメント指数の検索が行われるようになります。また、独立した位相の長さも短くなります。ドン'

score 5 · Accepted Answer

ウィキペディアによると /dev/random、Unix ライクなオペレーティングシステムでは、真の乱数ジェネレータとして機能する特別なファイルです。

/dev/random ドライバーは、オペレーティングシステム環境内で発生するキーボード間のタイミングや割り込み間のタイミングなど、さまざまな非決定論的なソースから環境ノイズを収集します。ノイズデータはサンプリングされ、CRC のようなミキシング関数を使用して、継続的に更新される「エントロピープール」に結合されます。ランダムなビット文字列は、このプールのコンテンツの MD5 ハッシュを取得することによって取得されます。一方向ハッシュ関数は、プールデータから真のランダムビットを抽出し、敵からプールの状態を隠します。

/dev/random ルーチンは、プール内の真のランダム性の見積もりを維持し、ランダムな文字列の使用が要求されるたびにそれを減らします。見積もりがゼロになると、ルーチンはロックされ、非決定論的イベントが発生してプールが更新されるのを待ちます。

/dev/random カーネルモジュールは、別のインターフェイス /dev/urandom も提供します。これは、エントロピープールが再充電されるのを待たずに、要求されたバイト数を返します。その結果、/dev/urandom は、非常に高品質のランダム性が必要な場合にのみ使用される /dev/random と比較して、生成時にかなり高速です。

score 4 · Accepted Answer

ジョン・フォン・ノイマンはかつて、「アルゴリズム的手段を介して乱数を生成しようとする人は、もちろん、罪の中に生きている」という趣旨の何かを言いました。

数学者や物理学者の言葉の意味では、/ dev/randomでさえランダムではありません。放射性同位元素の崩壊測定でさえランダムではありません。（減衰率はです。測定はそうではありません。ガイガーカウンターは、検出された各イベントの後にリセット時間が短く、その間、新しいイベントを検出できません。これにより、微妙なバイアスが発生します。これを大幅に軽減する方法はありますが、完全に排除するわけではありません。）

真のランダム性を探すのはやめましょう。優れた疑似乱数ジェネレータは、本当にあなたが探しているものです。

score 3 · Accepted Answer

決定論的な宇宙を信じるなら、真のランダム性は存在しません。:-) たとえば、誰かが放射性崩壊は本当にランダムであると示唆していますが、科学者がまだパターンを解明していないからといって、解明すべきパターンが存在しないというわけではありません。通常、「乱数」が必要な場合、必要なのは、他の誰も推測できない暗号化用の数字です。

ランダムに最も近いのは、敵が測定できない自然なものを測定することです。通常、測定値から最も重要なビットを捨てて、数字を残して、均等に分散する可能性が高くなります。筋金入りの乱数ユーザーは、放射性イベントを測定する特別なハードウェアを取得しますが、コンピューターを使用する人間がキーを押す間隔やマウスの動きなどからランダム性を取得できます。コンピューターに直接ユーザーがいない場合は、CPU 温度センサーから、およびネットワークトラフィックから。サウンドカードに接続された Web カメラやマイクなどを使用することもできますが、実際に使用する人がいるかどうかはわかりません。

score 3 · Accepted Answer

通常、コンピューターには、すぐに利用できるランダムノイズの物理的な発生源が多数あります。

マイク（できれば騒がしい場所で）
Web カメラからの圧縮ビデオ (溶岩ランプや街路など、変化するものを指している)
キーボードとマウスのタイミング
ネットワークパケットの内容とタイミング (全世界が貢献)

そして時折

クロックドリフトベースのハードウェア
ガイガーカウンターおよびその他のまれなイベントの検出器
A/Dコンバーターに付属する各種センサー

難しいのは、これらのソースのエントロピーを推定することです。データレートが高く、非常に変動しやすいにもかかわらず、ほとんどの場合、エントロピーは低くなります。しかし、エントロピーは、保守的な仮定で推定するか、少なくとも無駄にしないで、Yarrow や Fortuna などのシステムに供給することができます。

score 3 · Accepted Answer

言われていることのいくつかを要約すると、ランダム性の安全なソースとは何かについての私たちの作業定義は、暗号学的に安全な定義に似ています。 t 完全に予測不可能です。

解読できないと考えられる暗号が存在しないのと同様に、予測できないと考えられる乱数を生成するシステムもありません。重要な作業に使用される信頼できるソリューションは、これまでのところ、打ち負かすのが難しいことが証明されているものにすぎません。誰かがあなたに別のことを言うなら、彼らはあなたに何かを売っています。

暗号化では、賢さが報われることはめったにありません。実証済みの真のソリューションを使用してください。

score 2 · Accepted Answer

「真の」乱数を取得することはできません。コンピューターは、「真に」ランダムなものを作成することはできず、疑似乱数のみを作成できる論理構造です。ただし、疑似乱数アルゴリズムには、より良いものと悪いものがあります。

「真の」乱数を取得するには、物理的なランダムソースが必要です。一部のギャンブルマシンには実際にこれらが組み込まれています。多くの場合、それは放射性ソースであり、放射性崩壊 (私が知る限り、これは本当にランダムである) を使用して生成されます。数字。

score 1 · Accepted Answer

乱数を生成する最良の方法の 1 つは、Clock Driftを使用することです。これは主に 2 つのオシレーターで動作します。

これがどのように機能するかの類推は、単純な楕円形のサーキットで、ラップの開始時に while ラインがあり、タイヤの 1 つにも while ラインがあるレースカーを想像することです。車が 1 周を完了すると、道路上の白線とタイヤ上の白線の位置の差に基づいて番号が生成されます。

生成するのは非常に簡単で、予測することは不可能です。

algorithm - 真の乱数発生器

11 に答える 11

Related

Reference