問題タブ [prng]

私はキッド シスター暗号化関数を作成しています。OS 間で一貫した結果を生成する PRNG が必要です (ハードウェアやシステム レベルのソフトウェアを利用した浮動小数点演算は必要ありません)。PRNG の期間が 2 ³⁰よりも長いため、必要ではありません。

現在、32ビットのXorshiftを使用しています:

でも仕組みがよくわからないので不安です。たとえば、元のソースにはシードを設定する機能がなかったため、シードを追加しましたが、シードに正しい変数を選択したかどうかはわかりません。

要約すると、

1. 私のニーズに合った CPAN のモジュールを知っていますか?
2. そうでない場合、私のニーズに合ったアルゴリズムを知っていますか?

32 ビット整数演算では、加算と乗算の基本的な演算は暗黙的に mod 2^32 で計算されます。つまり、結果は加算または乗算の最下位ビットになります。

異なるモジュラスで結果を計算したい場合は、異なる言語で任意の数の BigInt クラスを使用できます。値 a,b,c < 2^32 の場合、中間値を 64 ビット long int で計算し、組み込みの % 演算子を使用して正しい答えに減らすことができます。

しかし、C が (2^N)-1 または (2^N)+1 の形式の場合に a*b mod C を効率的に計算するための特別なトリックがあり、64 ビット演算またはBigInt ライブラリであり、任意のモジュラス評価よりも非常に効率的であり、中間乗算を含めた場合に通常 32 ビット int をオーバーフローするケースも適切に計算します。

残念ながら、そのような特殊なケースには迅速な評価方法があると聞いていますが、実際には方法の説明を見つけていません。「それはクヌースにありませんか？」「それはウィキペディアのどこかにありませんか？」私が聞いたつぶやきです。

2147483647 は 2^31 -1 に等しい素数であるため、これは a*b mod 2147483647 の乗算を行う乱数発生器では明らかに一般的な手法です。

そこで専門家に聞いてみます。私が議論を見つけることができないこの巧妙な特殊なケースの乗算と mod の方法は何ですか?

いくつかの目的のために、自然な入力を支持して、アルゴリズムによって生成されたあらゆる種類の乱数をバイパスできると便利です---たとえば、サイコロの目。たとえば、暗号化キーの生成は、必要なランダムデータがほとんどなく、データが本当にランダムであるという要件が十分に高いため、実行可能で望ましいことであると私は思います。

だから、私が行って手を汚す前に知りたいのは、これですか？ランダムな数字の入力から直接エントロピープールを構築するためのソフトウェアはありますか？基数rから基数2に単純に変換するだけでは十分ではないことに注意してください。たとえば、3と2は互いに素であるため、元の入力の最大エントロピーを保持しながら、基数3（または基数6）の数値を2進数に変換するのは完全に簡単ではありません。

私は一日中これに苦労してきました.CUDAコードでスレッド用の乱数ジェネレーターを取得しようとしています. 私はすべてのフォーラムを調べましたが、このトピックはかなり出てきますが、あらゆる種類のコードを解明しようとして何時間も費やしましたが、役に立ちませんでした. 誰かが簡単な方法を知っていれば、おそらくデバイスカーネルを呼び出して、0 から 1 の間のランダムな浮動小数点数、または変換できる整数を返すことができます。

ここでも、たとえば rand() のように、カーネルで乱数を使用したいと考えています。

前もって感謝します

与えられた関数y=f（A、X）：

'x'のすべての値に対してx=g（A、f（A、x））となる逆関数x = g（A、y）をどのように見つけますか？

f（）が'x'のすべての値に対して反転可能ではない場合、逆行列に最も近いものは何ですか？

（Fは廃止されたPRNGであり、このような関数をどのように反転させるかを理解しようとしています）。

• 更新
  Aが（2 ^ N）-1に対して互いに素である場合、g（A、Y）はちょうどf（A-1、y）です。
  Aが互いに素でない場合、yの範囲は制限されます...その範囲に制限されている場合、g（）はまだ存在しますか？

疑似乱数ジェネレーターを実行ごとに2回以上シードしないようにするための推奨事項をかなり多く見てきましたが、完全な説明を伴うことはありませんでした。もちろん、次の（C / C ++）の例が適切でない理由は簡単に理解できます。

get_rand1秒間に数回呼び出すと、結果が繰り返されるためです。

しかし、次の例はまだ許容できる解決策ではないでしょうか？

MyRand.h

MyRand.cpp

main.cpp

つまり、MyRand：sコンストラクターが連続して数回呼び出されても、への呼び出しごとsrandに異なるパラメーターがあります。明らかに、これはスレッドセーフではありませんが、やはりどちらもスレッドセーフではありませんrand。

Unix システムの c で srandom() と random() を使用して乱数を生成しています。複数の RNG が必要です。同じシードを指定すると、それぞれが同じシーケンスを出力するはずです。また、それぞれの状態を保存して復元したいと思います。擬似コードの例を次に示します。

どうすればいいですか？RNG が別のスレッドに分岐する場合があり、新しいスレッドを作成するときにも RNG の状態を複製する必要があります。

ランダム アクセス モード (ファイルの任意の部分にアクセス) で機能する必要がある AES に基づくファイル暗号化を構築しています。たとえば、カウンターの AES を使用できますが、2 度使用されない一意のシーケンスが必要であることはよく知られています。この場合、単純化された Fortuna PRNG (特定のファイルに固有のランダムに選択された一意のキーでカウンターを暗号化する) を使用しても問題ありませんか? このアプローチに弱点はありますか?

したがって、暗号化/復号化は次のようになります

オフセットでのブロックの暗号化:

オフセットでのブロックの復号化:

1 つの観察。フォルトゥナで使われているアイデアは自分で思いついたのですが、後になってそれがすでに発明されていることを発見したのは確かです。しかし、どこでも重要なポイントはセキュリティですが、別の良い点があります。いわば（簡略化された形式で）優れたランダムアクセス疑似乱数ジェネレーターです。したがって、PRNG は非常に優れたシーケンスを生成するだけでなく (Ent と Die Hard でテストしました)、ステップ番号がわかっている場合は任意のサブシーケンスにアクセスできます。では、Fortuna をセキュリティ アプリケーションの「ランダム アクセス」PRNG として使用することは一般的に問題ないのでしょうか?

編集：

言い換えれば、私が提案するのは、Fortuna PRNG を微調整として使用して、ランダム アクセス機能を備えた微調整可能な AES 暗号を形成することです。Liskov、Rivest、Wagner の著作を読みましたが、動作モードの暗号と微調整可能な暗号の主な違いは何かを理解できませんでした。彼らは、このアプローチを暗号自体の内部の高レベルから導入することを提案したと述べましたが、たとえば、私の場合、微調整でプレーンテキストを xor する場合、これは微調整ですか?

UNIXタイムスタンプを適切な乱数に変換するアルゴリズムが必要です。これにより、タイムスタンプを「再生」すると、同じ乱数が得られます。

そして、これが私が適切に意味することです：

1. ほとんどの人間は、乱数のループやパターンを検出しません。
2. 暗号的に安全である必要はありません。
3. すべての番号は生成可能でなければなりません。（LFSRはこれを行わないことがわかりました）
4. 数値は32ビット整数です

そして、私はそれがかなり速いことを望みます。

これまでのところ、私の考えはPRNGを何度もシードすることですが、それがこれを処理するための最良の方法であるかどうかはわかりません。

どんな考えやアイデアも大歓迎です。

ありがとう。

最初に任意のバイト配列でシードするPRNG（疑似ランダム性）を探しています。

聞いたことありますか？