セキュリティ – 疑似乱数と真の乱数はどう違うのか？

私はこれを理解したことがありません。サイコロを振る小さなプログラムをどんな言語でも書くとしましょう（サイコロを例にしています）。60万回転がした後、それぞれの数字は10万回くらい転がっているでしょう

なぜ「真のランダム性」に特化したウェブサイトがあるのでしょうか？確かに、上記の観察結果を考えると、どのような数字であっても、その中からどれだけ多くの数字を選択しても、その数字を得る確率はほぼ正確に1になります

Pythonで試してみました：6000万ロールの結果がこちら。最高の変動は0.15のようです。これはランダムなのではないでしょうか？

1 - 9997653 2347.0
2 - 9997789 2211.0
3 - 9996853 3147.0
4 - 10006533 -6533.0
5 - 10002774 -2774.0
6 - 9998398 1602.0

　 672　 community wiki　 None

ベストアンサー

コンピューターポーカーをしよう君と僕と信頼のおけるサーバーでねサーバーは疑似乱数発生器を使っているプレイする直前に32ビットのシードで初期化される40億の可能性のあるデッキがあるとすると

私の手には５枚のカードがある–どうやらテキサスホールデムではないようだ。カードが１枚ずつ私に配られ、１枚ずつあなたに配られ、１枚ずつ私に配られ、１枚ずつあなたに配られたとする。私はデックの中に１枚目、３枚目、５枚目、７枚目、９枚目のカードを持っています

先ほど、私は疑似乱数発生器を40億回実行しました、それぞれのシードで1回ずつ、そしてそれぞれについて生成された最初のカードをデータベースに書き留めました。最初のカードがスペードのクイーンだとします。そうすると、可能性のあるデックのうち52枚に1枚しか最初のカードが出てこないので、可能性のあるデックを40億から8000万枚くらいに減らしました

私の２枚目のカードがハートの３だとします。スペードのクイーンを最初の数字にする8000万のシードを使って、さらに8000万回RNGを実行します。これには数秒かかります．手札の２枚目のカードを３枚目のカードとしてハートの３を出すデッキを全て書き出します。これでまたデッキの２％くらいしかないので、これで２００万のデッキになりました

私の手札の３枚目のカードがクラブの７だとします．私は２枚のカードを配る２００万のシードのデータベースを持っています．

これがどうなるかわかるだろうRNGをさらに40000回実行して4枚目のカードを生み出す種をすべて見つけると，800枚のデックになり，さらに800回実行して5枚目のカードを生み出す〜20枚の種を得ると，その20枚のデックのカードを生成するだけで，あなたは20枚の可能性のある手札のうちの1枚を持っていることがわかる．さらに、次に何を引こうとしているのか、非常に良い考えがあるのです

なぜ真のランダム性が重要なのかわかりましたか？君は分布が重要だと考えているが分布はプロセスをランダムにするものではない予測不可能性がプロセスをランダムにするんだ

UPDATE

これを読んだ人の少なくとも0.3%は、私の主張が何なのか混乱していると思います。私が主張していない点について反論されたり、もっと悪いことに、私が主張した点について、私が主張していないことを前提に反論されたりしたとき、私はもっと明確に丁寧に説明する必要があることを知っています

特に言葉の分布には混乱があるようなので、用法を丁寧に呼びかけていきたいと思います

手元の質問は

疑似乱数と本当に乱数はどう違うのか？
なぜその違いが重要なのか？
この違いはPRNGの出力の分布と関係があるのでしょうか？

まず、ポーカーをプレイするためのランダムなカードのデッキを生成する完璧な方法を考えることから始めましょう。次に，他のデックを生成するテクニックがどのように違うのか，そしてその違いを利用することが可能かどうかを見てみよう．

まず、TRNGと書かれたマジックボックスがあるとしましょう。この箱の入力には1以上の整数nを与え、その出力には1からnまでの間の本当に乱数を与えます。このボックスの出力は、（1以外の数値が与えられた場合）全く予測できず、1からnの間のどの数値も他の数値と同じくらいの確率で与えられます。これは分布が一様であることを意味します（他にももっと高度な統計的なランダム性のチェックがありますが、この点は私の議論には関係ないので無視します）。TRNGは仮定の上では完全に統計的にランダムです。)

まず，シャッフルされていないカードの山から始める．ボックスに１から５２までの数字を尋ねます．箱から返ってくる数字が何であれ，ソートされたデックからその数だけのカードを数え，そのカードを取り除きます．そのカードはシャッフルされたデックの最初のカードになる．次に、TRNG(51)を求め、同じようにして2枚目のカードを選びます

これは、大体2²²⁶である。私たちはそのうちの1つを本当にランダムに選んでいます

カードを配ろう私が持っているカードを見ても、あなたが持っているカードが何なのか全く分からない。私が持っているカードのどれも持っていないという明らかな事実を除けば）同じ確率でどんなカードでもあり得る

そこで、このことを明確に説明しておきましょう。我々は、TRNG(n)の個々の出力の一様分布を持っていて、それぞれが確率1/nで1からnまでの数字を選びます。また、この処理の結果、52個の可能なデックの中から1個を1/52の確率で選んだことになるので、可能なデックの集合の分布も一様である

All right.

さて、PRNGというラベルのついた、あまりマジックのない箱があるとしましょう。これを使うには、32ビットの符号なし数字をシードにしなければなりません

ASIDE.なぜ32なのか？64ビットや256ビットや10000ビットの数字でシードすることはできないのでしょうか？しかし、(1)実際にはほとんどの市販のPRNGは32ビットの数字でシードされていますが、(2)もし10000ビットのランダム性があるなら、なぜPRNGを使うのでしょうか？あなたはすでに10000ビットのランダム性のソースを持っています!

とにかく、PRNGがどのように動作するかに戻ります: PRNGがシードされた後は、TRNGと同じように使用できます。つまり、nという数値を渡すと、1からnまでの間の数値を返してくれます。さらに、その出力の分布は多かれ少なかれ一様です。つまり、PRNGに1から6の間の数を求めると、シードが何であったとしても、1, 2, 3, 4, 5, 6が大体6分の1ずつ返ってきます

この点を何度か強調したいのは、特定のコメンターを混乱させているように見えるからです。PRNGの分布は少なくとも2つの方法で一様です。第一に、任意の特定の種を選んだとします。私たちは、PRNG(6), PRNG(6), PRNG(6)...を100万回繰り返すと、1から6までの数の分布が一様になると期待しています。次に、100万個の異なる種を選び、それぞれの種に対してPRNG(6)を1回ずつ呼ぶと、1から6までの数の分布が一様になると予想できます。これらの操作のいずれかでPRNGが一様であることは、私が説明している攻撃には関係ありません

このプロセスは、箱の振る舞いが実際には完全に決定論的であるため、疑似ランダムと言われています。つまり、一度種を蒔くと、PRNG(6), PRNG(6), PRNG(6), ...は一様な分布を持つ数列を生成しますが、その数列は完全に種によって決定されます。例えば、PRNG(52), PRNG(51)……などのように、与えられた呼び出しのシーケンスに対して、可能なシーケンスは2³²しかありません。シードは基本的にどのシーケンスを取得するかを選択します

デッキを生成するために、サーバはシードを生成します。(どのようにして？) その後、PRNG(52), PRNG(51)などをコールしてデッキを生成しますが、これは以前と同様です

このシステムは、私が説明した攻撃の影響を受けやすいです。サーバを攻撃するには、まず、前もって、自分のコピーを0でシードして、PRNG(52)を要求して、それを書き出します。次に、1で再シードして、PRNG(52)を求め、それを書き留めて、2³²-1にします

さて、PRNGを使ってデッキを生成しているポーカーサーバーは、どうにかしてシードを生成しなければなりません。その方法は問題ではありません。本当にランダムなシードを得るためにTRNG(2^32)を呼び出すこともできる。あるいは、現在の時刻をシードとして使うこともできますが、これはまったくランダムではありません。私の攻撃のポイントは、私がデータベースを持っているので、それは問題ではないということです。最初のカードを見たとき，可能性のある種の98%を除外することができます．私の２枚目のカードを見たとき、私は可能性のある種を９８％以上除去することができ、最終的には可能性のある種を一握りの手札に収めることができ、あなたの手札に何があるかを高確率で知ることができるようになるまで

さて、繰り返しになりますが、ここで強調しておきたいのは、PRNG(6)を100万回呼んだ場合、それぞれの数値はおよそ6分の1の確率で得られるという仮定です。この分布は（多かれ少なかれ）一様であり、分布の一様性が気になるのであれば、それはそれで構いません。質問のポイントは、私たちが気にするのはPRNG(6)の分布以外にもあるのか、ということでした。我々は予測不可能性にも関心があります

別の見方をすれば、PRNG(6)への100万回の呼び出しの分布は問題ないかもしれませんが、PRNGは2つの³²の可能な動作の中から選択しているだけなので、すべての可能性のあるデッキを生成することはできません。PRNGは2つの²²⁶可能なデッキのうち2つの³²しか生成できません。そのため、すべてのデッキの集合に対する分布は非常に悪いものとなります。しかし、ここでの根本的な攻撃は、PRNGの出力の小さなサンプルからPRNGの過去と未来の振る舞いを予測することに成功したことに基づいています

3回目か4回目に言って確認させてくれここには3つの分布がある第一に、ランダムな32ビットシードを生成するプロセスの分布。これは完全にランダムで、予測不可能で、一様である可能性があり、攻撃はまだ機能します。第二に、PRNG(6)への100万回の呼び出しの分布です。これは完全に一様である可能性があり、攻撃はまだ機能します。三つ目は、私が説明した疑似ランダムプロセスによって選ばれたデッキの分布です。この分布は非常に貧弱です。攻撃は、PRNG の出力の部分的な知識に基づく PRNG の動作の予測可能性に依存します

aside.この攻撃は、攻撃者が PRNG が使用する正確なアルゴリズムを知っているか、推測できることを必要とします。それが現実的かどうかは未解決の問題です。しかし、セキュリティシステムを設計する際には、攻撃者がプログラムのすべてのアルゴリズムを知っていたとしても、攻撃に対して安全であるように設計しなければなりません。別の言い方をすれば、セキュリティシステムの中で、システムが安全であるために秘密にしておかなければならない部分を「鍵」と呼びます。もしあなたのシステムが、あなたが使用するアルゴリズムが秘密であることにその安全性が依存しているならば、あなたの鍵にはそのアルゴリズムが含まれていることになります。それは非常に弱い立場です

Moving on.

さて、CPRNGというラベルのついた3つ目のマジックボックスがあるとしましょう。これはPRNGの暗号強度バージョンである。32ビットシードではなく256ビットシードを使用する。PRNGと共通しているのは、シードが2つの²⁵⁶の可能な動作の中から1つを選択するという特性です。また、他のマシンと同様に、CPRNG(n)への多数の呼び出しが1からnの間の結果を一様に分布させるという性質を持っています: それぞれの結果は時間の1/nの間で起こります。これに対して攻撃を実行できますか?

我々のオリジナルの攻撃では、シードからPRNG(52)へのマッピングを2³²格納する必要があります。しかし、2²⁵⁶はもっと大きな数です

しかし、CPRNG(52)の値を取り、そこからシードに関する事実を推理する他の方法があるとしましょうか？これまでのところ、可能な組み合わせをすべてブルートフォースしているだけで、かなり馬鹿にしていました。魔法の箱の中を見て、それがどのように動作するのかを理解し、出力に基づいてシードに関する事実を推理することはできますか?

いや、詳細は複雑すぎて説明できませんが、CPRNGは巧妙に設計されているので、CPRNG(52)の最初の出力から、あるいは出力のどの部分集合からでも、シードに関する有用な事実を推論することは不可能です

では、サーバがCPRNGを使ってデッキを生成しているとしましょう。これには256ビットのシードが必要だ。そのシードはどうやって選ぶのだろうか?もし攻撃者が予測できる値を選んでしまうと、突然攻撃が可能になってしまいます。もし、2²⁵⁶の可能性のあるシードのうち、40億個のシードがサーバに選ばれる可能性があると判断できれば、また再開することができます。私たちは、生成されうる種の数が少ないことに注意を払うだけで、この攻撃を再び実行することができます

したがって、サーバは、256ビットの数が一様に分布していることを保証するための作業をしなければなりません — すなわち、各可能なシードが1/2²⁵⁶の確率で選ばれることです。基本的に、サーバはTRNG(2^256)-1を呼び出してCPRNGのシードを生成しなければなりません

サーバーをハッキングして、どのシードが選ばれたかを覗き見できるとしたらどうでしょうか？その場合、攻撃者はCPRNGの完全な過去と未来を知っていることになります。サーバーの作者は、この攻撃から守る必要があります。(もちろん、もしこの攻撃を成功させることができれば、私の銀行口座に直接お金を振り込むこともできるので、それほど面白くはないかもしれませんが。ポイントは、種は推測しにくい秘密でなければならないことと、本当にランダムな256ビットの数字を推測するのはかなり難しいということです)

防御の深さについての以前のポイントに戻ると、256ビットのシードがこのセキュリティシステムの鍵となる。たとえアルゴリズムに関する他のすべての事実が知られていたとしても、鍵を秘密にしておくことができる限り、相手のカードは予測不可能である

OK、つまり、シードは秘密で均一に分布していなければならないのですが、そうでなければ攻撃が可能です。CPRNG(n)の出力の分布は一様であると仮定しています。すべての可能なデッキの集合に対する分布はどうでしょうか?

このシステムでは、すべての可能性のあるIRLデッキが（高確率で）可能になっています。このような場合、「このシステムでは、すべての可能なIRLデッキが（高い確率で）可能になっています。このシステムでは、すべての可能なIRLデッキが（高い確率で）可能になっています

2²²⁶は52の近似値でしかない！？割り算してみましょう。2²⁵⁶/52！は整数にはなりえません。2²⁵⁶/52！は整数ではありえないからです

もしそれがよくわからない場合は、より小さい数の場合を考えてみましょう。例えば、A, B, Cの3枚のカードがあるとします。種子によってPRNG(3)の出力は256通りありますが、そのうちの1/3がA、1/3がB、1/3がCになることはありません。 256は3で均等に割り切れないので、そのうちの1つに少し偏りがあるはずです

同様に、52は2²⁵⁶に均等に分割されていないので、最初に選ばれたカードとして一部のカードに偏りがあり、他のカードに偏りがあるはずです

32ビットシードのオリジナルのシステムでは、大きな偏りがあり、可能性のあるデッキの大部分が作られることはありませんでした。このシステムでは、すべてのデッキが生成される可能性がありますが、デッキの分布にはまだ欠陥があります。一部のデッキは他のデッキに比べて非常にわずかに可能性が高い

ここで問題は、この欠陥に基づく攻撃があるのかということです。答えは、実際にはないでしょう。CPRNGは、シードが本当にランダムな場合、CPRNGとTRNGの違いを見分けることが計算上不可能になるように設計されています

では、まとめてみましょう

疑似乱数と本当に乱数はどう違うのか？

彼らは、彼らが示す予測可能性のレベルに違いがあります

本当に乱数は予測できません
疑似乱数は、シードが決定できるか、推測できる場合はすべて予測可能です

なぜその違いが重要なのか？

なぜなら、システムのセキュリティが予測不可能性に依存しているアプリケーションがあるからです

TRNGでカードを1枚1枚選ぶのであれば、システムの安全性は確保できません
CPRNGで1枚1枚を選択する場合、シードが予測不可能なものと未知のものの両方であれば、システムは安全です
シードスペースが小さい普通のPRNGを使うと、シードが予測できないか不明かにかかわらず、システムは安全ではありません

この違いはPRNGの出力の分布と関係があるのでしょうか？

RNG(n)への個々の呼び出しに対する分布の均一性やその欠如は、私が説明した攻撃とは関係ありません

ここまで見てきたように、PRNGもCPRNGも、可能なデッキの中から任意の個別のデッキを選択する確率の分布が悪くなります。PRNGはかなり悪いが、どちらも問題がある

もう一つ質問があります

TRNGがCPRNGよりも、PRNGよりも、これだけ優れているのなら、なぜCPRNGやPRNGを使う人がいるのでしょうか？

Two reasons.

まず、費用。TRNGはお金がかかる。真に乱数を生成するのは難しい。CPRNGは、任意に多くの呼び出しをしても、種のためにTRNGを1回呼び出すだけで良い結果が得られます。欠点は、もちろんその種を秘密にしておかなければならないことです

第二に、予測可能性が欲しくなることがありますが、私たちが気にするのは良い分布だけです。テストスイートのプログラム入力として「ランダム」なデータを生成していて、それがバグを示した場合、テストスイートをもう一度実行すると、またバグが発生するのがいいでしょう!

これでだいぶスッキリしたかな

最後に、もしこれを楽しんでいただけたならば、ランダム性と順列のテーマについてさらに読み進めることができるかもしれません

1389　 community wiki　 2019-05-22

エリック・リパートが言うように、それは分布だけではありません。ランダム性を測る方法は他にもあります

初期の乱数発生器の1つは、最下位ビットにシーケンスを持っています – それは0と1を交互にします。したがって、LSBは100％予測可能でした。しかし、それ以上のことを心配する必要があります。各ビットは予測不可能でなければならない

ここで、この問題について考えてみましょう。64ビットのランダム性を生成しているとしましょう。各結果について，最初の32ビット(A)と最後の32ビット(B)を取り，配列x[A,B]にインデックスを作ります．さて，このテストを100万回実行し，各結果について，その数だけ配列をインクリメントします．

ここで、数字が大きいほど、その場所のピクセルが明るくなるような2次元図を描きます

本当にランダムであれば、色は均一なグレーになるはずです。しかし、パターンを得ることができるかもしれません。例えば、Windows NT システムの TCP シーケンス番号の「ランダム性」の図を見てみましょう

Windows NT

またはWindows 98のこれも

Windows 98

そして、ここにCiscoルータ(IOS)の実装のランダム性があります。 Cisco ISO です

これらの図は、Michał Zalewskiの論文からの引用です。この場合、あるシステムのTCPシーケンス番号を予測できれば、別のシステムに接続する際に、そのシステムになりすますことができ、接続の乗っ取りや通信の傍受などが可能になります。また、次の番号を100％予測することができなくても、自分のコントロール下で新しい接続を発生させることができれば、成功する可能性を高めることができる。そして、コンピュータが数秒で10万の接続を生成できるようになれば、攻撃が成功する確率は天文学的なものから、可能性のあるもの、あるいは可能性のあるものへと変化します

164　 community wiki　 2017-04-02

コンピュータで生成された疑似乱数は、コンピュータユーザーが遭遇する大多数のユースケースでは許容されますが、全く予測不可能な乱数を必要とするシナリオもあります

暗号化のようなセキュリティ上重要なアプリケーションでは、疑似乱数発生器(PRNG)が、見た目はランダムだが、実際には攻撃者が予測可能な値を生成することがあります。暗号化システムをクラックしようとする者が、PRNG が使用されていて、攻撃者が PRNG の状態に関する情報を持っている場合、暗号化キーを推測することができるかもしれません。したがって、このようなアプリケーションでは、本当に推測できない値を生成する乱数発生器が必要となります。一部のPRNGは暗号的に安全な設計になっており、そのようなセキュリティに敏感なアプリケーションで使用できることに注意してください

RNG 攻撃に関する詳細な情報は、このウィキペディアの記事にあります

94　 community wiki　 2014-02-05

Pythonで試してみました。6000万ロールの結果がこちら。最高の変動は0.15のようです。これはランダムではないのか？

実際には「良い」と言っても過言ではないほど…。既存のすべての回答は、小さな初期値のシーケンスを与えられた予測可能性に焦点を当てています。別の問題を提起したいと思います

あなたの分布はランダムロールよりも標準偏差が小さいです

真のランダム性は、あなたが品質の指標として使用している「今までに何個の数字から選ぶことができるかよりも、ほぼ正確に1個」を平均化することには、それほど近くには来ていません

複数のサイコロを振ったときの確率分布についてのこのStack Exchangeの質問を見ると、N個のサイコロを振ったときの標準偏差の計算式が出てきます（純粋にランダムな結果を想定しています）

 sqrt(N * 35.0 / 12.0).

その式を使用して、標準偏差のための

100万巻は1708巻
6000万巻は13229

結果を見てみると

100万ロール：stddev(1000066, 999666, 1001523, 999452, 999294, 999999)は804
6000万ロール：stddev(9997653, 9997789, 9996853, 10006533, 10002774, 9998398)は3827

有限サンプルの標準偏差が数式と正確に一致することは期待できませんが、かなり近い値になるはずです。しかし、100万ロールでは適切な標準偏差の半分以下、6000万ロールでは3分の1以下になっています – それはますます悪化しており、これは偶然ではありません

疑似RNGは、シードから始まり、特定の期間は元の数値を再訪しないようにして、異なる数値の列を移動する傾向があります。例えば、古いC言語ライブラリのrand()関数の実装は、一般的に2^32の周期を持っており、シードを繰り返す前に0から2^32-1の間のすべての数字を正確に一度だけ訪れます。したがって、2^32個のサイコロをシミュレーションした場合、プレモジュラス(%)の結果には0から2^32までの各数値が含まれ、1から6までの各結果のカウントは715827883または715827882となります(2^32は6の倍数ではありません)。上の式を使うと、2^32個のサイコロの正しい標準偏差は111924となります。いずれにしても、擬似乱数の数が増えるにつれて、標準偏差は0に収束していきます。この問題は、ロールの数が期間のかなりの割合である場合に重要であると予想されますが、いくつかの疑似RNGは他のものよりも悪い問題を示すかもしれません – またはサンプル数が少ない場合でも問題を示すかもしれません

暗号の脆弱性を気にしなくても、アプリケーションによっては、過度に人為的に不均等な結果をもたらさない分布を持つことを気にすることがあるかもしれません。シミュレーションの種類によっては、個々にランダムな結果の大規模なサンプルで自然に起こる不均一な結果の結果を計算しようとしているものがありますが、pRNGの結果ではそのような結果が十分に表現されていないものもあります。巨大な集団が何かのイベントにどのように反応するかをシミュレーションしようとしている場合、この問題は結果を根本的に変えてしまう可能性があり、結果は非常に不正確なものになる可能性があります

具体的な例を挙げよう。ある数学者がポーカーマシンのプログラマーに、6000万回のシミュレーションロールの後、画面の周りに何百もの小さな「ライト」を点滅させて、10,013,229個以上の「6」が出た場合、平均値から1stddev離れていると数学者が予想した場合、少額のペイアウトがあるはずだと伝えたとします。68-95-99.7 ルール (Wikipedia)によれば、これは約 16% の確率で起こります (~68% が標準偏差内に収まる / 半分だけが標準偏差外に収まる)。あなたの乱数発生器では、これは平均値の上に約3.5標準偏差からです。0.025%以下の確率で、この恩恵を受けている顧客はほとんどいません。具体的には、先ほどのページの高偏差表を参照してください

| Range    | In range   | Outside range | Approx. freq. for daily event  |
| µ ± 1σ   | 0.68268... | 1 in 3        | Twice a week                   |
| µ ± 3.5σ | 0.99953... | 1 in 2149     | Every six years                |

77　 community wiki　 2017-04-13

サイコロのロールを生成するための乱数発生器を書いただけです

def get_generator():
next = 1
def generator():
next += 1
if next > 6:
next = 1
return next
return generator

こんな風に使うんですね

>> generator = get_generator()
>> generator()
1
>> generator()
2
>> generator()
3
>> generator()
4
>> generator()
5
>> generator()
6
>> generator()
1

などなど。サイコロゲームを実行するプログラムにこのジェネレータを使ってもいいと思いますか？覚えておいてください、その分布はあなたが “本当にランダムな “ジェネレータに期待するものと全く同じです!

疑似乱数発生器は基本的には同じことをします – 正しい分布を持つ予測可能な数値を生成します。上記の単純な乱数発生器が悪いのと同じ理由で、これらの乱数発生器も悪いのです

51　 community wiki　 2014-02-05

コンピュータが実行できる乱数生成は、ほとんどのニーズに適しており、本当に乱数が必要な時に出くわすことはほとんどありません

しかし、真の乱数生成には目的があります。コンピュータセキュリティ、ギャンブル、大規模な統計的サンプリングなどで

乱数の応用に興味があれば、Wikipediaの記事をチェックしてみてください

27　 community wiki　 2014-02-05

ほとんどのプログラミング言語の代表的な関数で生成される乱数は、純粋な乱数ではありません。擬似乱数です．純粋な乱数ではないので、以前に生成された数値に関する十分な情報があれば推測することができます。したがって、これは暗号技術のセキュリティにとっては災いのもととなるでしょう

一例として、glibcで使用する以下の乱数生成関数は、純粋な乱数を生成しません。これによって生成された擬似乱数を推測することができます。これはセキュリティ上の問題で失態です。これが悲惨なことになった歴史があります。暗号に使うべきではない

glibc random():
r[i] ← ( r[i-3] + r[i-31] )  % (2^32)
output  r[i] >> 1

このタイプの擬似乱数発生器は、統計的にははるかに有意であるにもかかわらず、セキュリティ上重要な場所では決して使用されるべきではありません

疑似ランダムキーに対する有名な攻撃の一つは、802.11b WEP に対する攻撃です。WEP は 104 ビットの長期鍵を持ち、24 ビットの IV(カウンタ)と連結して 128 ビットの鍵を作り、これを RC4 アルゴリズムに適用して擬似ランダム鍵を生成します

( RC4( IV + Key ) ) XOR (message)

キーは互いに密接に関連していた。ここでは、IVだけが各ステップで1ずつ増加し、他はすべて同じままであった。これは純粋にランダムではなかったので、悲惨な結果となり、簡単に破壊されてしまった。鍵は約40000フレームを解析することで回復できたが、これは数分の問題である。WEPが純粋にランダムな24ビットIVを使用した場合、約2^24（約1680万）フレームまでは安全であった

そのため、可能な限りセキュリティ上の問題がある場合には、純粋な乱数発生器を使用する必要があります

27　 community wiki　 2014-02-05

疑似乱数の違いは、真の乱数がそうではないのに対し、疑似乱数が生成された数値は時間が経てば予測可能（繰り返し）になるということです。繰り返しの長さは、その生成に使用されるシードの長さに依存します

その話題についてのかなり素敵な動画があります。http://www.youtube.com/watch?v=itaMNuWLzJo

13　 community wiki　 2014-02-07

擬似乱数が発生する前に誰でも推測できると仮定します

些細なアプリケーションでは、あなたの例のように擬似的なランダム性は問題ありません、あなたはいくつかの小さな変化（あなたが600k回サイコロを振る場合に表示されます）で、ほぼ正しい割合（結果セット全体の約1/6）を得るでしょう

しかし、コンピュータのセキュリティのようなものになると、真のランダム性が求められます

例えば、RSAアルゴリズムはコンピュータが2つの乱数(PとQ)を選び、それらの乱数に対していくつかのステップを踏むことで、公開鍵と秘密鍵として知られる特別な数値を生成するところから始まります。(秘密鍵の重要な部分は、それが秘密であり、他の誰にも知られていないということです)

攻撃者があなたのコンピュータが選ぼうとしている2つの「乱数」が何であるかを知ることができれば、彼らはあなたの秘密鍵を計算するために同じ手順を行うことができます（他の誰も知らないはずのもの！）

あなたの秘密鍵を使えば、攻撃者は次のようなことができます。 a) あなたになりすまして銀行に話しかける、b) あなたの「安全な」インターネットのトラフィックを聞き、それを解読することができる、c) インターネット上であなたと他の関係者の間で仮装する、などです

そこに真のランダム性（＝当てられない・計算できない）が求められます

11　 community wiki　 2014-02-05

最初に使った乱数は、どの2つの連続した乱数のうち、2番目の乱数の方が確率0.6で大きくなるという優れた性質を持っていたのですが、この乱数は0.6ではありませんでした。0.5ではない。そして3番目の乱数は2番目の乱数よりも確率0.6で大きい、というような性質を持っていました。これがシミュレーションにどのような影響を与えるか想像できるでしょう

乱数が均等に分布しているのにこんなことが可能だとは信じない人もいるでしょうが、2つの数字のうち2番目の数字が0.6の確率で大きくなる順序(1, 3, 5, 2, 4, 1, 3, 5, 2, 4, …. )を見れば、明らかに可能です

一方、シミュレーションでは、乱数を再現できることが重要な場合があります。例えば、交通シミュレーションを行っていて、どのような行動をとれば交通量が改善されるかを知りたいとします。その場合、全く同じ交通データ（町に入ろうとしている人など）を、交通改善のために試したアクションを変えて再現できるようにしたいとします

11　 community wiki　 2014-02-07

簡単に言うと、普通の人は「真のランダム性」を悪い理由、つまり暗号を理解していないということで必要としているのです

ストリーム暗号やCSPRNGなどの暗号プリミティブは、一度予測不可能なビットを数ビット送り込んだら、予測不可能なビットの巨大なストリームを生成するために使用されます

注意深い読者は、ここにブートストラップの問題があることに気付いたでしょう。そして、それらをCSPRNGに供給することができます。したがって、CSPRNGをシードするためにはハードウェアRNGが必要です。これは、真実にエントロピーが必要とされる唯一のケースです

(これはセキュリティか暗号に投稿すべきだったと思います)

編集：最終的には、想定されたタスクに十分に適した乱数発生器を選択しなければなりませんし、乱数発生に関する限り、ハードウェアが必ずしも良いとは限りません。ちょうど悪いPRNGのように、ハードウェアのランダムなソースは通常バイアスを持っています

編集: ここでは、攻撃者が CSPRNG の内部状態を読み取ることができる脅威モデルを想定し、そこから CSPRNG は安全な解決策ではないと結論づけている人がいます。これは、不適切なスレッドモデリングの例です。もし攻撃者があなたのシステムを所有していたら、ゲームは終わりです。この時点では、TRNG を使おうが CSPRNG を使おうが違いはありません

編集: 結論から言うとエントロピーはCSPRNGのシードに必要です。これができれば、CSPRNGは、（通常は）エントロピーを集めるよりもはるかに速く、セキュリティアプリケーションに必要な予測不可能なビットをすべて提供することができます。シミュレーションのように予測不可能性を必要としない場合は、メルセンヌツイスターを使えば、統計的特性の良い数値をより高い速度で提供することができます

編集: 安全な乱数生成の問題を理解しようとする人は、これを読むべきです。http://www.cigital.com/whitepapers/dl/The_Importance_of_Reliable_Randomness.pdf

9　 community wiki　 2014-02-19

すべてのPRNGがすべての用途に適しているわけではありません。例えば、Java.util.SecureRandomはSHA1ハッシュを使用しており、出力サイズは160ビットです。つまり、2¹⁶⁰の可能性のある乱数のストリームがあるということです。単純な話です。内部状態の値は2¹⁶⁰を超えることはできません。したがって、シードがどこから来たものであっても、1つのシードから2¹⁶⁰以上のユニークな乱数のストリームを得ることはできません。Windows CryptGenRandomは40バイトの状態を使用していると考えられており、2つの³²⁰の可能な乱数ストリームを持っています

標準的な52枚のカードの山札をシャッフルする方法の数は52です！これは約2²²⁶です。したがって、シードに関係なく、Java.util.SecureRandomを使ってカードの山をシャッフルすることはできません。約2⁶⁶のシャッフルが可能で、それができないのです。もちろん、それがどれなのかはわかりませんが

そこで、例えば256ビットの真のランダム性のソース（例えばQuantis RNGカード）があれば、CryptGenRandom()のようなPRNGにそのシードを与えて、そのPRNGを使ってカードの山をシャッフルすることができます。シャッフルのたびに真のランダム性で再シードすれば、予測不可能で統計的にランダムになります。Java.util.SecureRandomで同じことをした場合、256ビットのエントロピーでシードすることができず、内部状態がすべての可能なシャッフルを表すことができないため、生成することができないシャッフルが発生することになります

java.util.SecureRandom の結果は、予測不可能なものと統計的にランダムなものの両方であることに注意してください。統計的なテストで問題を特定することはありません。しかし、RNGの出力は、カードの山をシミュレートするのに必要なすべての可能な出力の完全な領域をカバーするのに十分な大きさではありません

そして、ジョーカーを入れると54！をカバーしなければならないので、約2²³⁸の可能性を必要とすることを覚えておいてください

8　 community wiki　 2014-02-06

擬似乱数は数学関数と初期値（シードと呼ばれる）を使って生成されますが、乱数はそうではありません。その予測可能性は、シードとプレイヤーの入力を保存するだけで、AIが毎回全く同じ「ランダム」な方法で反応してくれるので、ゲームのリプレイに非常に役立ちます

7　 community wiki　 2014-02-08

真」乱数と「疑似」乱数の違いは、予測可能性です。この答えはすでに出ています

しかし、多くの例が示しているように、予測可能性が必ずしも悪いことではありません。ここでは、予測可能性が良いとされる稀なケースの一つの実践例を紹介します。全地球測位システムです

各衛星は、信号伝搬時間の測定に必要な自己相関や相互相関に適したPRNコード（ゴールドコード）を使用しています。これらのゴールドコードでは、お互いの相関関係が特に弱く、衛星を明確に識別することができますが、放出されたシーケンスと受信機の間の相関関係による距離計算を可能にしています

7　 community wiki　 2016-06-25

ランダム性の高速なチェックのために、[0;1]のランダムな座標を持つ点を取り、それらをk次元の立方体に入れます。そして、この立方体をサブキューブにスライスする手順を行います

どこで出会うかはランダム性の質が重要です

セキュリティ上の理由からです。キー生成のパラメータとして使用する番号を生成し、それが予測可能であれば、100%の確率で敵に発見され、検索のフィールドを大幅に狭くすることができます
科学的な目的のために科学では、平均値が良い状態であるだけでなく、様々な乱数の間の相関を排除しなければなりません。したがって，(a_i – a)(a_{i+1}-a)をとってその分布を求めれば，それは統計学に対応しなければならない．

ペア相関はいわゆる「弱いランダム性」です。真のランダム性を求めるならば、2つ以上の分散を持つ高次相関が必要です

今日では量子力学の発電機だけが真のランダム性を提供しています

3　 community wiki　 2014-02-06

なぜ真のランダム性が重要なのか？

真のランダム性が必要な理由は、基本的に大きく分けて2つあります

暗号（リアルマネーギャンブルや宝くじのようなものを含む）にRNGを使用している場合、PRNGを使用すると、（TRNGを前提とした）数学的な解析よりもはるかに弱い暗号になります。PRNGは実際にはランダムではなく、パターンを持っています – 敵はそのパターンを悪用して、暗号を解読できなかったはずの暗号を解読することができます
RNGを使って「ランダム」な入力をシミュレートする場合、例えばバグテストやシミュレーションのためにPRNGを使うと、PRNGはアプローチを弱くしてしまいます。PRNGのパターンでは目立たないが、TRNGだけを使っていたら現れていたであろうバグがあるのだろうか？私のシミュレーションの発見は現実を正確に表現しているのか、それとも私が発見した現象はPRNGのパターンの人工物に過ぎないのか？

これらの領域以外では、それは本当に重要ではありません。警告: PRNGが非常に、非常に悪い場合、それはまだ適していないかもしれません – サイコロが常に偶数で出てくるようなクラップスゲームを作りたくないでしょう、プレイヤーはそれを好まないでしょう

PythonのPRNGがダメなのはなぜ？

このような単純な方法論を使って、実際のPRNGの落とし穴を発見できる可能性は非常に低いです。RNGの統計解析はそれ自体が科学の一分野であり、アルゴリズムの「ランダム性」をベンチマークするための非常に洗練されたテストがいくつか利用できます。これらは、あなたの単純な試みよりもはるかに高度なものです

Pythonの開発者のような実世界のライブラリを作成するソフトウェア開発者は皆、PRNGの実装が十分に良いかどうかを判断するために、これらの統計テストをヤードスティックとして使用しています。つまり、実際の開発者が見落としている場合を除いて、実世界のPRNGのパターンを簡単に検出できる可能性は非常に低いということです。だからといって、パターンがないわけではありません – PRNGは定義上パターンを持っています

2　 community wiki　 2014-02-07

基本的には、数学的に出力を解析してもソースがランダムであることを証明することはできないので、例えば、ソースがランダムであるという物理モデル（放射性崩壊のように）が必要です

バッチテストを実行して出力データの統計的相関を見つけることができます。その場合、データは非ランダムであることが証明されます（しかし、ランダムなソースは非ランダムな出力を持つこともできますし、特定の出力を与えることができない場合は真のランダムではありません）。そうでなければ、テストに合格していれば、データは疑似ランダムであると言えます

いくつかのランダム性テストに合格するということは、PRNG（疑似乱数発生器）が優れているということであり、セキュリティが関係しないアプリケーションでは便利です

セキュリティが関係している場合（暗号化、キーソルトの生成、ギャンブルのための乱数生成など）、良いPRNGを持つだけでは十分ではなく、関数の出力が以前の出力から容易に推測されないこと、関数は望ましい計算コスト（使用可能な程度に制限されているが、ブルートフォースの試みを打ち破るのに十分な高さ）を持つ必要があること、関数を実行するハードウェア（あるいはデバイス、今日の奇妙なケースではアナログデバイス）が容易に改ざんされないこと、などが必要です

良いPRNGを持つことは、新しい予測不可能なパターンを作成するために、ゲームや暗号化で有用であることができます – 1つの記事で説明するにはあまりにも面倒なので、ちょうど親指の役割として考えて、暗号化手順の出口が擬似ランダムであるべきであるか、次の暗号化されたデータと以前の暗号化されたデータを関連付けることができるパターンを示していない、または暗号化されたデータに平文データを関連付けるか、または2つの異なる暗号文を関連付けることができるパターンを表示していません（だから、推測は平文上で行うことができます）

1　 community wiki　 2014-07-16

Short story:

システムの現在のマイクロ秒を使用してランダムシードを生成します

この仕掛けはかなり古くからあるもので、今でも機能しています

私はすべての可能な数字で “賭け “によってすべての組み合わせを決定することができます力のブルートファクターを除いて、それは特別にほとんどの乱数は彼の使用前に丸められているときに、この質問のポイントではありません

例えば、10個の値だけを使って、使用した種を判断することができるとします。つまり、シードがわかれば、次の値を推測することができます

seed=1を使えば、次のシーケンスを得ることができます

1, 2, 3, 4, 5, 6, 7, 8, 9…(そして私はシードがid 1と次の値10を使用したことを控除します)

しかし、もし “n番目 “の値ごとに送信を変更した場合はどうなりますか？現在のマイクロ秒でシードを変更するのは、安いトリックです（つまり、多くのCPUサイクルを必要としません）

ということで、現在の配列は以下の通りです。(シード=1) 1, 2, 3, 4, 5, (シード=2), 7, 9, 11, 13…(15?)

この場合は

A)どの種を使ったかは控除できない

b) エルゴ、次の値を推測できない

C)次のシードがメジャーナンバーになる可能性があることを差し引いてもいいくらいの推測しかできません

いずれにしても、最新のランダムジェネレータのアルゴリズムのほとんどは、すでにこのトリックをフードの下で使用しています

本当のところ、「真の」乱数を作るために量子コンピュータは必要ないのですが、コンピュータの水晶振動子の不正確さが乱数発生器として機能し、また、CPUのランダム効率も、CPUが同時に複数のタスクを行うことを考慮しなくても変動するのです

-5　 community wiki　 2016-06-25