cryptography - CSPRNG: 時間保証はありますか?

Question

暗号的に安全な疑似乱数ジェネレーターは、エントロピーがそのような方法で収集され、異なる時間に生成されたときに値が2回発生しないことも保証しますか?

可能性が非常に低いことはわかっていますが、具体的な保証はありますか?

競合があってはならない CSPRNG から一連の一意の ID を生成する必要があります。

Answer 1

理想的な (CS)PRNG は、特定の値を抽出する確率が一定であり、その値が過去にすでに出力されているかどうかに関係なく、時間の経過とともに変化しないことを保証します。

たとえば、ID の長さが 32 ビットで、今日は0x12345678. 今起こったことは の確率でし1/(2^32)た。

明日 (そして将来のどの時点でも)、1/(2^32)値を抽出する確率は同じです0x12345678。

ただし、誕生日のパラドックスから、 65 536 (=2^(32/2)) 個の値を生成すると、50%の確率で2 つの ID が同じであることがわかります。

つまり、CSPRNG の出力が同じではないという確固たる保証はありません。可能性が十分に小さいかどうかは、ID の長さと、システムの全存続期間中に合計でいくつの ID が予想されるかによって大きく異なります (攻撃者が自由に ID を生成できる場合は、セキュリティ上の懸念に特に注意を払う必要があります)。

完全を期すために、すべての優れた PRNG に適用できます。これには、最も単純なコインの反転も含まれます。暗号学的に強力な PRNG には、特定の出力から将来または過去の出力を予測する複雑さ (難しいはずです)、状態の侵害から回復する能力、およびエントロピーをフィードする能力に関する追加のプロパティがあります。