SHA-1 如何“餵養”Blum Blum Shub
Lavarand（專利）是最著名的硬體派生隨機數生成器之一。它用時髦的熔岩燈做到了。燈的圖像經過雜湊處理並輸入 Blum Blum Shub (BBS) 以生成加密比特流。
如何？該專利提到使用 NIST SHS-1 (SHA-1) 輸出 160 位雜湊。這似乎減少到多個 140 位散列，然後“ 140 字節值通過 Blum Blum Shub
$$ sic $$“。我認為 BBS 的種子是通過素數乘法計算的。種子（通常是 pq）如何只是任意散列輸出並仍然執行它的整數分解？BBS 通常使用 1000 位的單個狀態，而不是 140 位組. 他們這樣做了，這在細節上有點少*，*存檔網站上的第3 步和第 4 步並沒有清除任何…
我意識到這都是很久以前的事了。上述步驟600和605如何連接在一起？
我認為 BBS 的種子是通過素數乘法計算的。
這不是 BBS 的工作方式。為了幫助更好地理解種子，有必要解釋一下 BBS。
Blum Blum Shub以以下形式實現 $ x_{i+1} = x^2_i \bmod N $ . 最初的種子， $ x_0 $ , 只需與 Blum 素數互質 $ p $ 和 $ q $ （在哪裡 $ N = p\cdot q $ ， 製造 $ N $ 一個Blum 整數），並且不能是 $ 0 $ 或者 $ 1 $ . 種子是 $ x_0 $ ， 不是 $ p $ 和 $ q $ （很可能生成一次以創建硬編碼 $ N $ 然後扔掉* )。他們很可能使用原始雜湊輸出作為種子，因為它不太可能不會是共同的 $ N $ . 他們給你連結頁面上的模數，但不是素數：
5360751114622011236087979022735306713592537659947455285353148181 8526455500785383194936281698585494806464721601253386562653528822 5543322562532917886396992291116815877218495559211688377961466145 0857446201926232198015028137924055146650866097197909406089918491 4133568666470293429076893274969016410915119621659901793350665953這是一個 1062 位模數。不幸的是，BBS 似乎可以分解† $ 10^{54} n^3 $ 比考慮因素要快幾倍 $ n $ 位模數。這意味著可以破壞與其參數一起使用的 BBS $ 10^{54} \times 1062^3 \approx 1.20 \times 10^{63} $ 比考慮模數要快幾倍，這是一個足夠顯著的加速，證明完全沒用。此外，該證明假設僅從每個位中提取一個位 $ x_i $ （官方採用平價 $ x_i $ ）。如果一次提取更多位，它會變得更弱。看起來可以接受的參數對於 BBS 來說是可怕的。
BBS 的安全證明只是對沒有已知解決方案的問題的*簡化。*也就是說，一個正確的實現（即從每個 $ x_i $ ，並且只有當模量“足夠”大時）才能在二次剩餘問題（QRP）得到解決的情況下被打破。‡它是“被證明是安全的”，就像 RSA 被“證明是安全的”一樣，因為正確的實現可以證明可以減少到 RSA 問題的安全性（找到 $ e^\mathrm{th} $ 整數的根，模半素 $ N $ )，但沒有人認為 RSA 具有完美的安全性。換句話說，BBS 對一個尚未證實的問題具有安全性，並且不是資訊論安全的。
上述步驟600和605如何連接在一起？
您是在問 140 字節種子是如何來自 160 位雜湊的？這實際上在您提供的連結中得到了回答。有七個 SHA-1。第七個散列每七個字節，第六個散列每六個字節，等等。這些字節來自熔岩燈本身的圖像。最終的雜湊值連接起來形成一個 140 字節（1120 位）的值。該值直接用作 $ x_0 $ .
*您唯一失去的就是無法訪問 $ p $ 和 $ q $ 是計算任何 $ x_i $ 直接取值 $ x_0 $ 無需計算 $ x_1 \cdots x_{i-1} $ 第一的。歐拉定理可以用來做 $ x_i = (x_0^{2^i \bmod \lambda(N)}) \bmod N $ 在哪裡 $ \lambda $ 是Carmichael 函式。如果攻擊者因素 $ N $ ，他們也可以這樣做，打破安全性降低。
† 在此上下文中的損壞不是指預測隨機流或恢復種子的能力。相反，這意味著安全證明無效，並且該算法不再可簡化為已知的難題，並且可能存在不依賴於解決 QRP 的中斷。至關重要的是，它並不自動暗示這種中斷確實存在。
‡ 儘管二次殘差問題通常被認為與整數分解一樣困難，但這尚未得到證實。有可能存在一種打破 BBS 的方法，它在不解決整數分解的情況下解決 QRP。