為什麼打破 Blum Blum Shub PRNG 不是一個無法確定的問題？
Blum Blum Schub (BBS) 偽隨機數生成器 (PRNG) 歸納定義為 $$ x_{i+1} = x_i^2 \mod N $$ 生成位序列 $ b_0b_1b_2… $ 其中位被視為整數的奇偶校驗 $ x_i $ ， 和 $ N $ 和 $ x_0 $ 必須滿足特定的屬性（例如，參見這篇文章）。
BBS 生成器是一個加密安全的 PRNG，以二次剩餘問題為模；給定整數 $ N $ ; 作者將尋找先驗比特流簡化為尋找兩個主要因素的問題 $ N $ .
我不清楚的是為什麼作者假設對手可以訪問整數 $ N $ 和或 $ x_i $ . 根據Wikipedia上加密安全 PRNG 的定義，給定部分或全部內部狀態，攻擊者不應該能夠重建先前的隨機數流。在這個定義下，聲稱“內部狀態”不是整數還不夠嗎？ $ x_i, N $ ，而是比特流 $ b_0b_1… $ ?
畢竟，如果我沒記錯的話，如果對手獲得了對部分偽隨機比特流的訪問權，那麼唯一確定 $ x_0 $ 和 $ N $ 從這些資訊來看應該是非常困難或無法確定的，所以我不確定為什麼作者將重建先前比特流的挑戰減少到解決二次殘留問題。
特別是，如果不是隨機比特流，PRNG 的“內部狀態”究竟是如何定義的？內部狀態是否定義為隨機種子？隨機種子之後的幾次迭代？如果是這樣，那麼 PRNG“種子”依賴於一組秘密參數 $ a_1, a_2,…a_m $ ，那麼這些參數中應該顯示多少才能構成“內部狀態”？
根據 Wikipedia 上加密安全 PRNG 的定義，給定部分或全部內部狀態，攻擊者不應該能夠重建先前的隨機數流。
這是對實際 CSPRNG 應根據哪些要求進行評估的工程規範。密碼理論中用於**偽隨機發生器（PRG）**的定義比這要弱。例如在Katz & Lindell 的教科書（第 2 版）中，定義 3.14（第 62 頁）：
定義 3.14。讓 $ \ell $ 是一個多項式並讓 $ G $ 是確定性多項式時間算法，使得對於任何 $ n $ 和任何輸入 $ \in {0,1}^n $ ， 結果 $ G(s) $ 是一個長度的字元串 $ \ell(n) $ . 我們說 $ G $ 如果以下條件成立，則為偽隨機生成器：
- **（擴展：）**對於每個 $ n $ 它認為 $ \ell(n) > n $ .
- **（偽隨機性：）**對於任何 PPT 算法 $ D $ , 有一個可以忽略的函式 $ \mathsf{negl} $ 這樣$$ \bigg|\mathrm{Pr}\big[D(G(s)) = 1\big] - \mathrm{Pr}\big[D(r) = 1\big]\bigg| ≤ \mathsf{negl}(n) $$其中第一個機率被接管統一選擇 $ s \in {0,1}^n $ 和隨機性 $ D $ ，並且第二個機率被接管統一選擇 $ r \in {0,1}^{\ell(n)} $ 和隨機性 $ D $ .
這是 Blum Blum Schub 將被評估的那種定義，它甚至不假設 PRG 具有增量更新的狀態。
您正在閱讀的工程要求（我不會稱之為定義）當然是在考慮一系列實際攻擊，而這些攻擊是理論工作抽像出來的。但是您會發現，實用的密碼隨機發生器設計通常會嵌入類似於理論定義的模組。例如，對於Fortuna，它所謂的“生成器”子模組的建議是在 CTR 模式下使用分組密碼，其狀態是密鑰/計數器對，可以輕鬆地重建早期狀態（只需遞減計數器）。但該狀態僅限於對更大的 Fortuna 構造的個人呼叫：
每次數據請求（無論多麼小）後，密鑰也會更改，因此未來的密鑰洩露不會危及先前的生成器輸出。此屬性有時被描述為“快速密鑰擦除”或前向保密。
因此，沒有前向保密（您詢問的屬性的名稱）的生成器被用作建構具有前向保密性的生成器。