5

MD5 / SHA256 / SHA512などをPRNGとして使用できますか？たとえば、整数シードが与えられた場合、擬似コードは次のようになります。

random_number = truncate_to_desired_range(
    sha512( seed.toString() + ',' + i.toString() )

…まともなPRNG？（iは増加する整数です。たとえば、出力は次のとおりです。

convert(sha512("<seed>,0"))
convert(sha512("<seed>,1"))
convert(sha512("<seed>,2"))
convert(sha512("<seed>,3"))
…

この質問の文脈では、「まともな」とは、出力の分散のみを指します。このように使用した場合、暗号化ハッシュ関数の出力は均一ですか？（ハッシュ関数に依存すると思いますが、すべての暗号化ハッシュも均一な出力を持つ必要がありますよね？）

注：暗号化ハッシュを使用しているため、これはメルセンヌツイスターと比較して遅いPRNGになることを認めます。私は速度には興味がなく、結果が安全であることに興味はありません。ただ、分布が正しいというだけです。

私の特定のユースケースでは、XKCDのジオハッシュに似たものを探しています。これは、分散したパーティによって簡単に実装され、全員が同じ答えに到達するという点です。Mersenne-Twisterは代用できますが、多くのターゲット言語ではあまり利用できません。（一部の言語には完全に欠けているものもあれば、生のU32出力にアクセスできないものもあります。SHA512は組み込みであるか、簡単に利用できます。）

4

2 に答える 2

4

暗号化ハッシュ関数がその設計目標を満たしていると仮定すると、ハッシュ関数へのすべての入力は設計上一意であるため、出力は（おそらく）その期間にわたって均一な分布に従います。

ハッシュ関数の目標の1つは、ランダムオラクルを近似することです。つまり、任意の2つの異なる入力AとBの場合、出力H（A）とH（B）は（真のランダムオラクルの場合）無相関である必要があります。ハッシュ関数はそれにかなり近づきますが、もちろん弱点は時間と暗号解読とともに忍び寄ります。

とは言うものの、暗号化プリミティブは、品質に関しては基本的に私たちが利用できる最高の数学的アルゴリズムであるため、問題を解決できない場合は何も解決しないと言っても過言ではありません。

于 2013-01-22T21:06:36.143 に答える
0

（他の回答/コメントで述べられているように、適切なサイズの入力、パディングなどで）動作させることができ、かなり良い結果が得られますが、遅くなるので、シミュレーションを行っている場合やPRNGを大量に使用する必要があるもの...

于 2013-01-22T21:10:39.227 に答える