PRNG 操作中的測量誤差如何工作？

假設，我有種子密鑰長度為的 PRNG $ |K_s| $ 和輸出序列長度 $ 2^{|K_s|} $ , 所以 PRNG 的複雜度是 $ 2^{|K_s|} $ . 現在，如果 PRNG 的輸出中有任何測量誤差，那麼這個測量誤差在 PRNG 的整體複雜性中是如何起作用的？

除非測量誤差很大（例如，您以機率正確讀取每一位 $ p = 0.5 $ )，它不會顯著增加查找密鑰所需的工作。

舉一個具體的例子，讓我們考慮一個測量誤差，我們以機率正確讀取每個位 $ p = 0.75 $ （為簡單起見，讓我們假設錯誤是相互獨立的，以及正確的位是 0 還是 1）。

然後，攻擊者可以做的是循環遍歷每個可能的密鑰，並使用該密鑰生成 PRNG 的前 1000 位，並檢查這些位中是否至少有 600 位與給他的雜訊樣本的前 1000 位一致。以極高的機率，正確的密鑰會生成一個設置了那麼多位的樣本，而沒有錯誤的密鑰會。

這個過程還需要 $ O(2^{|K_s|}) $ 時間，所以你所做的就是將所需的時間增加一個常數因子。

引用自：https://crypto.stackexchange.com/questions/39590