是否可以計算 DUAL_EC_DRBG 的“萬能鑰匙”？需要什麼？
根據 Bruce Schneier 的說法，規範中使用的常量
DUAL_EC_DRBG可能與一組秘密數字有關，該數字集可以用作在此隨機數生成器上使用的加密主密鑰：它是這樣工作的：在用於定義算法橢圓曲線的標準中有一堆常數——固定數字。這些常數列在 NIST 出版物的附錄 A 中，但沒有說明它們的來源。
舒莫和弗格森表明，這些數字與第二組秘密數字有關，可以作為一種萬能鑰匙。如果您知道秘密數字，您可以在僅收集 32 個字節的輸出後預測隨機數生成器的輸出。實際上，您只需要監控一個 TLS 網際網路加密連接即可破解該協議的安全性。如果您知道秘密數字，則可以完全破壞 Dual_EC_DRBG 的任何實例化。
給定這些常數，是否可以計算出這些秘密數字？計算它們需要什麼？
總的來說，我發現這種攻擊的記錄很差。以下是對此事的技術解釋，如果對細節不感興趣，可以直接跳到結論。
Dual_EC_DRBG
首先，讓我使用 Shumow 和 Ferguson 的符號對 Dual_EC_DRBG 做一個簡短的描述（參見展示文稿）。作為初步，我們正在使用一些素數階橢圓曲線，我們有兩個點 $ P $ 和 $ Q $ 在那條曲線上。由於群是素數，所以 $ P $ 和 $ Q $ 是發電機。
由於我們最終將使用整數，因此我們需要一種將曲線上的點“轉換”為整數的方法。為此，我們將定義 $ \varphi(x, y) = x $ ，即我們只使用 $ x $ - 點的座標。
在任何一輪 $ i $ , 我們有一個起始狀態 $ s_i $ . 接下來，我們計算
$$ r_i = \varphi(s_i P) $$在哪裡 $ s_i P $ 表示重複點加法： $$ s_i P = \underbrace{ P + P + \dots + P.}_{s_i \text{ times}} $$ 這 $ r_i $ 將用於（1）生成輸出和（2）更新生成器的狀態。 輪次輸出 $ i $ 是
$$ t_i = \operatorname{LSB}_{\mathrm{bitlen}-16}(\varphi(r_i Q)). $$ 攻擊者將使用這些值。這裡， $ \operatorname{LSB} $ 意思是“最低有效位”，所以我們在輸出之前砍掉 16 位。 下一輪的狀態定義為
$$ s_{i+1} = \varphi(r_i P). $$ 攻擊
自從 $ P $ 是一個生成器，有一些整數 $ e $ 這樣 $ P = eQ $ . 假設我們知道這一點 $ e $ .
給定任何輸出 $ t_i $ , 我們知道除了 16 位之外的所有值 $ \varphi(r_i Q) $ . 我們可以生成那些失去的 16 位的所有可能組合，這給我們留下了 $ 2^{16} = 65536 $ 可能的值——其中之一是 $ \varphi(r_i Q) $ ，“真實”輸出。由於所有 $ (x,y) $ 橢圓曲線上的點滿足方程 $ y^2 = x^3 + ax + b $ , 如果給我們一些 $ x $ -座標，我們可以解二次方得到兩個可能的 $ y $ 價值觀。也就是說，如果我們有 $ 2^{16} $ 可能是的值 $ \varphi(r_i Q) $ ，我們可以使用前面等式中的每個值，從而獲得 $ 2 \cdot 2^{16} = 2^{17} $ 值，其中之一是真實的 $ r_i Q $ .
如果我們有會發生什麼 $ r_i Q $ ? 因為我們假設我們知道 $ e $ 這樣 $ P = eQ $ ，我們可以簡單地相乘 $ r_i Q $ 經過 $ e $ 要得到：
$$ e(r_i Q) = r_i (e Q) = r_i P. $$ 回想一下，下一輪的狀態被定義為 $$ s_{i+1} = \varphi(r_i P). $$ 所以如果你知道 $ e $ 這樣 $ P = eQ $ ，您可以預測生成器的所有未來狀態，這意味著您可以預測生成器的所有未來輸出。 我們如何確定哪個 $ 2^{17} $ 值是 $ r_i Q $ ? 很簡單：我們嘗試使用上述攻擊來預測多輪的下一輪輸出。當一個值無法預測下一個狀態時，顯然不是真實的 $ r_i Q $ ，所以它可以被扔掉。這個過程消除了除了真正的 $ r_i Q $ . Shumow 和 Ferguson 發現大約 32 字節的輸出足以讓這種攻擊成功。
結論
你的問題：
給定這些常數，是否可以計算出這些秘密數字？計算它們需要什麼？
這是可能的，但不可行。
秘密整數 $ e $ （在哪裡 $ P = eQ $ ) 是找到的必要值。計算這個 $ e $ 從頭開始（任意 $ P,Q $ ) 需要求解橢圓曲線中離散對數問題的一個實例： $ e = \log_Q P $ . 目前，在這種情況下計算離散對數被認為在計算上是不可行的。
但是，如果你是挑剔的人 $ Q $ , 你可以選擇一個隨機整數 $ d $ （再次使用 Shumow 和 Ferguson 的符號）並設置 $ Q = d P $ . 然後 $ e = d^{-1} $ ，這很容易計算。
因此：除非你是那個挑剔的人 $ Q $ ，你基本上沒有希望找到 $ e $ . 另一方面，如果你選擇 $ Q $ ，那麼你可以很容易地選擇 $ Q $ 這樣你就知道 $ e $ . 我認為這幾乎是教科書對後門的定義。
請注意，有兩個問題同時導致了這種攻擊：首先，如果我們選擇了一種更好的方法來整數化橢圓曲線點（一種更好的 $ \varphi $ )，無法使用 $ \varphi(r_i Q) $ 去尋找 $ r_i Q $ . 其次，由於我們在輸出前只砍掉了 16 位，因此很容易對所有失去的 16 位進行暴力測試。如果我們砍掉更多的比特，攻擊可能會被挫敗。