ここで乱数とは、Linux の乱数発生器のような疑似乱数を意味します。たとえば、Linux 疑似乱数ジェネレーターによって生成された 10000 個のランダムな整数をそれぞれ含む 100 ～ 1000 個の配列があります。そして、新しい整数シーケンスが与えられた場合、分類やクラスタリングなどの機械学習アルゴリズムが、この整数シーケンスが以前のトレーニング データのような疑似乱数シーケンスであるかどうかを検出できるとしたら?
何らかの理由で、実際には特定のシーケンスの実際のランダム性は気にしません。この特定のシーケンスが特別な Linux 疑似ランダム整数ジェネレーターによって生成されているかどうかを知りたいだけです。Linux RNG が疑似ランダム整数シーケンスを生成する誘導関数を 1 つ持っているとします。この RNG によって生成された既存のランダム シーケンスに基づいて、この RNG によって既存の整数シーケンスが生成されるかどうかを予測できますか?
この回答で推奨されているように、実際には「/dev/urandom」を意味すると仮定して、「linux PRNG」の意味を明確にしましょう。
現在、その背後にあるアルゴリズムはよく知られています-ソースコメントでそれについて読んでみましょう:
ランダムなバイトが必要な場合は、「エントロピー プール」の内容の SHA ハッシュを取得して取得します。SHA ハッシュは、エントロピー プールの内部状態の公開を回避します。SHA の入力に関する有用な情報をその出力から導き出すことは、計算上不可能であると考えられています。巧妙な方法で SHA を分析できたとしても、ジェネレーターから返されるデータの量がプール内の固有のエントロピーよりも少ない限り、出力データはまったく予測できません。このため、ルーチンは、乱数を出力するときに、エントロピー プールに含まれる「真のランダム性」のビット数の内部推定値を減らします。
この推定値がゼロになっても、ルーチンは乱数を生成できます。ただし、攻撃者は (少なくとも理論上は) 以前の出力からジェネレーターの将来の出力を推測できる可能性があります。これには SHA の暗号解読の成功が必要であり、これは実行可能であるとは考えられていませんが、わずかな可能性があります。それにもかかわらず、これらの数値は、ほとんどの目的に役立つはずです。
したがって、さまざまなソースから取得され、定期的に更新されるランダム性のプールがあります。典型的なサイズは 4096 ビットのようです。「攻撃者」を「機械学習」に置き換えると、答えが得られます。
プールが空の場合 (つまり、プールが補充されずにランダムなバイトの非常に長いシーケンスが要求された場合)、問題は SHA-1 の出力を特定することと同じです。
数字の抽選の間にプールが補充されている場合、数字がどのように生成されたかについての仮説をテストするための実行が短くなるため、問題はさらに難しくなります。
SHA-1 を逆にする方法、または SHA-1 出力と非 SHA-1 出力を区別する方法は知られていません。標準的な分類とクラスタリングは、このタスクでは確実に失敗します。成功したアルゴリズムを見つけることは非常に驚くべきことです。なぜなら、SHA-1 自体に対して実行可能な攻撃を提示するからです。SHA-1 が完璧であるというわけではありません (衝突攻撃については既に説明されているため、既に廃止されており、改善されるだけです)。
これは、人々が尋ねてきた伝統的な質問です。古典的な分析については、Donald Knuth 著 The Art of Computer Programming の第 2 巻「Seminumerical Algorithms」を参照してください。
より最先端のテストが必要な場合は、http://csrc.nist.gov/groups/ST/toolkit/rng/index.htmlで入手できるソフトウェア スイートがあり、十分なドキュメントも含まれています。
ウィキペディアのページ ( http://en.wikipedia.org/wiki/Statistical_randomness )を読んで、フィールドの概要を理解することも検討してください。