Blum Blum Shub 中的 M 需要多大？
我讀過 Blum Blum Shub 是一個 CSPRNG，由 $ x_{n+1} = x_n^2 \bmod M $ . 我不明白，也找不到關於多大的任何來源 $ M $ 應該。
32位夠嗎？64位？還是需要更多位？
Blum-Blum-Shub (BBS) 生成器的通常定義如下：
讓 $ N $ 是未知因式分解的Blum-Integer。讓 $ j $ 是“提取率”。讓 $ x_0 $ 是一個均勻隨機的非負整數，小於 $ N $ . 定義 $ x_{i+1}=x_{i}^2\bmod N $ . 請求 $ M=jk $ 隨機位，計算所有 $ x_i $ 至少直到 $ x_k $ 並連接 $ j $ 每個值的最低有效位作為隨機輸出。
經典的原始 BBS 構造使用 1 的提取率。後來的分析( PDF ) 表明 $ j $ 可以安全有序 $ O(\log\log N) $ . 後續具體分析( PDF ) 提出以下界限（定理 3）：
BBS 生成器是 $ (T_A,\varepsilon) $ -安全如果$$ T_A\leq \frac{L(n)}{35\delta^{-2}n\log_2 n}-2^{2j+9}n\delta^{-4} $$在哪裡 $ \delta=(2^j-1)^{-1}M^{-1}\varepsilon $ , n 是位長 $ N $ , $ L(n) $ 努力考慮因素 $ N $ ， 和 $ (T_A,\varepsilon) $ -安全意味著對手可以努力區分輸出和隨機輸出 $ T_A $ 和成功機率 $ \varepsilon $ .
現在讓我們挑選 $ n=3072 $ 為了好玩，標準估計是 $ L(n)\approx 2^{128} $ 工作努力。我們也來挑選 $ j=4 $ 和 $ k=32 $ 從每個平方中提取 4 位並需要 128 位。我們還假設我們想要 $ \varepsilon=2^{-1} $ 對手的成功機率。這給了我們 $ \delta=(2^{1}\cdot 31\cdot 128)^{-1}\approx 2^{-13} $ . 這反過來又給了我們 $ 2^{2\cdot 4+9}\cdot n\cdot 2^{52}\approx 2^{79} $ 和 $ \frac{2^{128}}{35\cdot 2^{26}\cdot n\cdot \log_2 n}\approx 2^{81} $ . 因此，這種情況下的對手需要大約 $ 2^{81} $ 努力以成功的機率打破這個 BBS 生成器 $ 1/2 $ .
使用上述方法，您還可以嘗試估計其他參數值，但我想您已經註意到，為了使 BBS 安全，您需要相當大的模量或以非常慢的速率提取和/或僅從種子中提取幾位. 一般來說，你最好使用像AES-CTR DRBG這樣的生成器。