CSPRNG 的定義
我對定義加密安全偽隨機數生成器 (CSPRNG) 的必要條件和充分條件感興趣。
維基百科列出了兩個定義特徵：
- 它滿足下一位測試。
- 它可以承受“狀態妥協擴展”——所有被妥協狀態的一部分不允許重建先前的隨機數流。
我知道條件 1 相當於說不存在可以區分輸出流和隨機流的多項式時間算法（成功機率為 1/2 + $ \epsilon $ ），由於姚（1982）。然而，我無法為第二個標準找到任何正式的理由，維基百科推測這是“它們在嚴重的攻擊下能很好地承受，即使它們的部分初始或執行狀態可供攻擊者使用。” 有沒有人有這方面的可靠來源？
而且，這個條件還合乎情理嗎？如果您考慮像 RC4 之類的東西（好吧，不是我所知道的 CSPRNG 的最佳範例），如果您在任何時候都知道整個狀態，那麼可以完全確定地向前或向後步進 PRGA 並且獨立於密鑰的知識，對？那麼，這是否意味著 RC4 不滿足維基百科作為 CSPRNG 的第二個條件？
有沒有人有這方面的可靠來源？
好吧，您在詢問 CSPRNG 的定義，以及第二個標準是否是必要的部分。
好吧，它歸結為“CSPRNG”一詞的準確定義。
如果我們將 CSPRNG 定義為生成與隨機（您的第一個標準）無法區分的輸出的東西，那麼 CSPRNG 不需要滿足第二個標準。這可以通過觀察看出，這個定義只依賴於輸出，而第二個標準也是根據內部狀態來定義的。採用 CSPRNG（滿足第一個標準）並添加允許某人重建先前輸出的內部狀態將很容易；這個修改後的生成器將繼續滿足第一個標準（我們沒有更改輸出），但它會阻止它滿足第二個標準。
另一方面，如果“CSPRNG”一詞包括第二個標準，那顯然是必要的部分。
當我使用“CSPRNG”這個詞時，我個人的意思是符合第一個標準的東西（如果我還需要第二個標準，我會使用一個額外的術語，比如“回溯阻力”來描述它）。
維基百科文章似乎將此作為其來源。我要指出的是，在它的標準化 CSPRNG 列表中，它包括 X9.31 生成器，其明顯的實現不符合他們的標準（如果攻擊者恢復了內部密鑰，並且對以前的時間戳有很好的猜測）。
這種條件是否合理？
當然是的; 如果您處於存在危險的情況下，它很有用，在某些時候，內部狀態實際上可能會暴露出來。
如果你考慮像 RC4 這樣的東西；這是否意味著 RC4 不滿足維基百科作為 CSPRNG 的第二個條件？
嗯，眾所周知，RC4 不符合第一個標準，所以它不是最好的例子。然而，忽略這一點，RC4 的明顯實現肯定不符合第二個標準。可以想像（也就是說，我不知道有什麼反駁）RC4 的替代實現會產生相同的輸出，並且會滿足第二個標準。