Blum Blum Shub 與 AES-CTR 或其他 CSPRNG
繼 DW 對上一個問題的評論之後，Blum Blum Shub 有哪些特性使其比其他 PRNG 更好/更差？BBS 是否存在重大的實施困難或安全問題？
Blum-Blum-Shub是一種流密碼：給定一個短密鑰，它會產生一個有效的無限長度的偽隨機比特流。其他著名的流密碼範例包括 AES-CTR 和 RC4。
Blum-Blum-Shub 經常被非專業密碼學家提及。我懷疑這是因為它帶有安全“證明”，這聽起來是一件很棒的事情。應用密碼學中提到 BBS 可能並沒有什麼壞處，一些開發人員可能已經擺脫了 BBS 是蜜蜂膝蓋的想法。
不過，我個人不推薦BBS。事實證明，安全性證明具有高度誤導性，並且帶有一些精美的印刷品，使證明在實踐中幾乎毫無用處。您最好使用 AES-CTR（計數器模式下的 AES）。AES 已經過仔細審查並受到廣泛信任。AES-CTR 應該提供出色的安全性——同時還提供出色的性能。
BBS有兩個問題：
- BBS非常慢——慢得令人難以忍受。
- 此外，“安全證明”的存在具有高度誤導性，並且通常會被誤解。實際的人幾乎總是從“安全證明”中得出錯誤的結論。
這兩個問題是聯繫在一起的。標準的安全證明表明，如果您選擇一個足夠大的模數N ，那麼任何攻擊者都無法有效地破壞 BBS。**然而，標准證明並沒有說明N必須有多大才能達到任何所需的安全級別。最近，研究人員已經計算出您需要多大的模數，並且（這裡是細則：）事實證明，N需要非常大才能獲得任何可證明的安全水平。我將在下面總結他們的一些結果：
結果 1.假設您使用具有 768 位模數的 BBS。您已經讀過 768 位足以使因式分解不可行，所以這聽起來很美妙。您已經讀過在每次迭代中提取O (lg n ) 位是安全的；這裡n = 768，lg n = 9.58，因此您決定在每次迭代中提取 9 位。你用它來生成一個 10 7位的偽隨機流（大約 1MB 的偽隨機數據）。你有多少安全感？答案：安全證明保證對任何使用最多 2 -264的對手的安全性計算步驟。是的，這是一個非常荒謬和無用的說法！用簡單的英語來說，安全證明絕對保證沒有任何用處。
經驗教訓是：使用自然大小的參數，並不能保證您在實踐中使用 BBS 是安全的。“安全證明”對於普通大小的參數是沒有用的。
*結果 2。*假設您了解了這個結果，並決定使用更長的模數。假設您決定使用具有 6800 位模數的 BBS，並在每次迭代中提取 5 位。假設您從 BBS 生成器中提取的偽隨機位不超過一百萬。然後，有一個證據表明至少需要2100步計算才能打破 BBS（給定合理的假設）。這意味著您應該具有合理的安全級別。我的估計是，在我的機器上，使用 BBS 生成 100 萬位 (128KB) 的輸出大約需要 5-10 分鐘，而使用 AES-CTR 只需不到一秒。
換句話說，為了在實踐中實現輕微的安全性，BBS 需要一個巨大的模數——比你在 RSA 中使用的任何東西都要長。這種大的模量使 BBS 非常慢。它比 AES 慢得多——而且可能也弱得多，因為即使您提取超過一百萬位的偽隨機輸出，AES 也被認為可以安全使用。
*結果 3.*這是另一種思考方式。第三位研究人員計算了 BBS 和保理之間的安全級別比率。他發現有可能存在破壞 BBS 的攻擊，並且比任何因式分解算法（用於分解 BBS 模數）的算法快10 54 n 3倍。例如，對於 1024 位模數 ( n = 1024)，有人可能能夠以最快的速度破壞 BBS 10 63倍。因為我們知道你可以用少於 10 24步的計算來分解一個 1024 位模數，所以這種關於 1024 位 BBS 的保證完全沒有用：它根本不能保證安全。
再舉一個例子，對於 8192 位模數，結果表明可能有一些聰明的算法可以將 BBS 分解速度比我們知道如何分解 8192 位模數的速度快10 65倍。這是一個巨大的比例。它說 BBS 可能比 RSA 更容易破解。這意味著我們的 BBS 安全性證明只有在我們使用巨大的模數時才有意義，並且只有當我們相信分解這種大小的模數非常困難時。如果我們願意假設分解這樣一個模數非常困難，我們可以推斷出打破 BBS 非常困難；但是因為我們需要使用如此巨大的模數，所以生成的 BBS 方案將非常緩慢。
有關詳細資訊，請參閱以下研究論文：
- 再看Tightness，Sanjit Chatterjee、Alfred Menezes 和 Palash Sarkar，2011 年密碼學選定領域。
- Blum-Blum-Shub 偽隨機發生器的具體安全性，Andrey Sidorenko 和 Berry Schoenmakers，密碼學和編碼 2005。
- 而且，這個來自 Dan Bernstein 的 sci.crypt 文章：回复：BBS PRNG 強度推薦參數
術語腳註：理論家有時將流密碼稱為“偽隨機生成器”（PRG）。令人困惑的是，這與“偽隨機數生成器”（PRNG）不同。
術語“偽隨機數生成器”（PRNG）並不總是一致地使用。有兩種可能的意思。有些人將其用作流密碼的同義詞。就個人而言，我更喜歡為用於生成偽隨機數的方案保留 PRNG，不使用顯式輸入（但以某種方式從環境中收集熵）。使用我喜歡的術語，您可以使用 PRNG 生成一個簡短的加密密鑰；然後您使用流密碼（PRG）將短加密密鑰拉伸成非常長的偽隨機位密鑰流。但其他人使用這個詞的方式不同。
考慮到這個混淆的機會，如果從上下文中該術語的含義不清楚，最好避免使用 PRNG 一詞。