Blum Blum Shub 偽隨機發生器要求
我試圖理解最初在A Simple Unpredictable Pseudo-random Number Generator中描述的 Blum Blum Shub 偽隨機數生成器
據我所知，要求是：
- 對於任何 $ x_i $ ， 只要 $ x_i^2 \bmod 2 $ 使用（僅最低有效位）
- $ x_{i+1} = x_i^2 \bmod N $
- $ N = p\cdot q $
- $ p \ne q $
- $ p $ 和 $ q $ 是等長素數
- $ p \equiv 3 \pmod 4 $
- $ q \equiv 3 \pmod 4 $
- $ \gcd(pq, (p-1)(q-1)) = 1 $
我不打算推出自己的加密貨幣。只是好奇。
您對要求的理解是正確的。詳細地說，您指定的第一個要求可以解釋為採用奇偶校驗 $ x_i $ . 此外，這兩個素數稱為Blum 素數，模數稱為Blum 整數，這意味著 $ p,q \in \mathbb P $ , $ p \equiv q \equiv 3 \pmod 4 $ ， 和 $ N = p \cdot q $ .
還有一些其他要求，例如選擇隨機 $ p $ 和 $ q $ 大小大致相等。就像 RSA 一樣。如果你想要一個 $ 2n $ -位模數 $ p\cdot q $ ， 您可以選擇 $ p $ 和 $ q $ 範圍內隨機 $ [2^{n-1},2^n) $ . 你自然想要 $ p $ 和 $ q $ 很難預測，但間隔非常大，您可以安全地在其中的任何隨機點開始搜尋，而不會讓攻擊者更容易。為了確保你沒有得到一個模數 $ 2n-1 $ 一半的時間，一個常見的技巧是選擇範圍內的素數 $ (\sqrt{2}\cdot 2^{n-1},2^n) $ 反而。這確保了 $ \lceil\log_2(p)\rceil=\lceil\log_2(q)\rceil $ ，這簡化了程式（ $ \sqrt{2}\approx 1.5 $ ，所以你可以只設置每個素數的兩個最高有效位）。
最初的種子， $ x_0 $ , 也必須足夠大，並且必須與素數一起保密。最後， $ p $ 和 $ q $ 通常選擇這樣 $ \gcd(\varphi(p),\varphi(q)) $ 很小以使循環長度最大化。它們必須是強素數，通常通過選擇安全素數（整數 $ p $ 是一個安全素數，如果 $ p,\frac{p-1}{2} \in \mathbb{P} $ ) 隨著時間的推移 $ \lambda(\lambda(N)) $ ，如果順利的話，會有短週期的風險。
如果你想計算任何 $ x_i $ 直接取值 $ x_0 $ 無需先計算 $ x_1 \cdots x_{i-1} $ ，可以用歐拉定理來做 $ x_i = (x_0^{2^i \bmod \lambda(N)}) \bmod N $ . 因為 $ \lambda $ ，你需要保持 $ p $ 和 $ q $ .
按照慣例， $ \varphi $ 指歐拉函式和 $ \lambda $ 指 Carmichael 函式。
請注意，BBS 不是一個好的 CSPRNG。從學術的角度來看，這很有趣，因為它可以被證明可以簡化為QRP，但是如果沒有不切實際的大模量，證明並不能提供有意義的可證明安全性水平。正確使用時它也很慢，因為它一次只能輸出一位。安全“證明”對從業者完全無用，並且被行家忽略。它最終成為天真的陷阱，讓他們以堂吉訶德式的方式尋求完美的安全。