2

私は最近、次の場合に PRNG の結果を予測できることを読みました。

  1. どのアルゴリズムが使用されているかを把握します。
  2. 連続したデータ ポイントがあります。

データポイントのみから PRNG に使用されるシードを把握することは可能ですか?

4

3 に答える 3

2

さまざまな種類の攻撃を詳しく説明し、実際の例をいくつかまとめたKelsey らの論文をなんとか見つけました。ほとんどの攻撃は、暗号システムに対するものと同様の手法に依存しているようであり、ほとんどの場合、PRNG が暗号システムで使用されているという事実を実際に利用しています。

于 2011-10-06T14:34:14.660 に答える
1

PRNGによって生成された絶対的な最初のデータポイントである「十分な」データポイントがあれば、ギャップはありません。ほとんどの PRNG 関数は可逆であるため、逆方向に作業するだけでシードを取得できます。

たとえば、典型的なreturn seed=(seed*A+B)%Nは の逆ですreturn seed=((seed-B)/A)%N。

于 2011-10-06T14:32:32.663 に答える
0

シードのすべての可能な値をブルートフォースすることが「許可」されていて、その出力を生成できたシードが1つしかないほど十分なデータポイントがある場合は、常に理論的に可能です。PRNGが時間とともにシードされ、それがいつ発生したかを大まかに知っている場合、試行する妥当な値が多くないため、これは非常に高速である可能性があります。PRNGに、64ビットのエントロピーを持つ真にランダムなソースからのデータがシードされている場合、このアプローチは計算上実行不可能です。

他の手法があるかどうかは、アルゴリズムによって異なります。たとえば、Blum Blum Shubに対してこれを行うことは、整数因数分解と同等であり、これは一般に難しい計算問題であると考えられています。他の、より高速なPRNGは、この意味で「安全性」が低い可能性があります。暗号化の目的で使用されるPRNG、たとえばストリーム暗号では、それを実行するための既知の実行可能な方法がほとんどない必要があります。

于 2011-10-06T15:55:41.253 に答える