“偏心”如何ķķk攻擊”（EC）DSA 工作？
我最近再次偶然發現了Thomas Pornin關於確定性 (EC)DSA 的舊答案。他在那裡陳述如下：
注意 $ k $ 必須在 $ [1, q-1] $ 範圍（其中 $ q $ 是子群階）。關於任何資訊 $ k $ , 甚至是部分的（如：值之間 $ 1 $ 和 $ 2^{160}-q $ 的機率是介於之間的值的兩倍 $ 2^{160}-q $ 和 $ q $ )，可以被攻擊者利用。
當被問及對此的澄清時，他回復了Vaudenay (PS) 的“繞過標準橢圓曲線認證計劃的 DSA 和 ECDSA 的安全性”的連結，其中提到 Bleichenbacher 發現了該攻擊並在與作者的私下交流中提到了它。
現在這篇論文有一個簡短的段落（第 2.2 節），它基本上說明了偏差的近似方程，並說
Bleichenbacher 實際上使用它是為了通過簽名越來越精確地近似密鑰。
現在我的問題是：
**這種攻擊如何在更詳細的描述中起作用？**或以不同的方式表述：如何利用這種微小的偏差來恢復密鑰，以及為此需要多少簽名（即預言機查詢）以及近似的計算工作量（如果它不可忽略）？
論文中的相關部分是（為了您的方便）：
DSA 中的初始標準偽隨機生成器 $ k $ 只是一個 160 位偽隨機數減少模 $ q $ . Bleichenbacher 觀察到， $ k $ 在裡面 $ [0, 2^{160} − q] $ 範圍的機率是其他範圍的兩倍。這會導致偏見
$$ E\left(e^{\frac{2i\pi k}q}\right)\approx \frac{q e^{i\pi\frac{N-1}q}}{\pi N} \times \sin\left(\frac{\pi N}q\right) $$ 在哪裡 $ N=2^{160} $ . 自從 $ q \approx N $ ，這可能很大，具體取決於 $ \frac{\pi N}q $ 角度。Bleichenbacher 實際上使用它是為了通過簽名更精確地逼近密鑰。
Nguyen 和 Shparlinski 在The Insecurity of the Elliptic Curve Digital Signature Algorithm with Partially Known Nonce 中詳細介紹了該方法。我將在很大程度上遵循該論文中的符號。
這個想法是將私鑰的確定從有偏見的 $ k $ 將幾個 ECDSA 簽名中的 nonce 轉換為隱藏數問題(HNP)的實例，然後將 HNP 求解為最接近向量問題的約簡。
因此，您收集大量簽名並從中構造一個格，並使用LLL或BKZ減少該格，然後您可以從減少的基向量中提取私鑰。
估計所需的計算工作量
我使用在具有 2GB RAM 的 Ubuntu 16.04 VM 上執行的手工製作的 LLL Python 實現（它非常慢，它肯定構成了性能的上限……）對此進行了測試，並且我有以下範例執行：
- 96 位偏差，5 個簽名：（失敗）31 秒
- 64 位偏差，10 個簽名：（成功）4 分鐘
- 32位偏差，12個簽名：（成功）12分鐘
- 16 位偏差，17 個簽名：（成功）49 分鐘
- 8 位偏差，19 個簽名：（失敗）79 分鐘
- 8 位偏差，21 個簽名：（成功）244 分鐘
- 8 位偏差，20 個簽名：（成功）177 分鐘
我停在那裡。Nguyen 和 Shparlinski 顯然能夠用 100 個簽名的 3 位偏差恢復密鑰，並認為只有 2 位已知就可以恢復。
更多問題詳情和設置
所以假設你知道低 $ \ell $ 位 $ k $ . （本文描述了一種恢復這些位的方法。）然後你可以寫 $ k $ 作為
$$ k = a + 2^\ell b $$ 換句話說，你知道 $ a \in [0, 2^\ell -1] $ . 為簡單起見，讓 $ a = 0 $ . 那麼方程為 $ s $ 在 ECDSA 簽名中 $ (r,s) $ 變成
$$ s = (h + rx) \cdot (2^\ell b)^{-1} $$ 在哪裡 $ h $ 是您的散列消息和 $ x $ 是你的私鑰，一切都是模數 $ q $ ，你的基點的順序。將其重寫為
$$ xr \cdot (2^\ell s)^{-1} = -h \cdot (2^\ell s)^{-1} + b $$ 定義 $ t \equiv r\cdot (2^\ell s)^{-1} $ 和 $ u \equiv -h \cdot (2^\ell s)^{-1} $ 你有
$$ xt = u + b $$ 記住那個 $ 0 \lt b \lt q/2^\ell $ ， 你有
$$ xt - u \lt q/2^\ell $$ 所以這基本上是HNP。 $ b $ 小了一個因子 $ 1/2^\ell $ 比 $ x $ , $ t $ ， 和 $ u $ ，所以近似這個方程：
$$ xt - u \approx 0 \longrightarrow xt - u - jq \approx 0 $$ 因為一切都是mod $ q $ . 所以先收藏 $ n $ 簽名，給你幾個元組 $ t_i $ , $ u_i $ ， 和 $ j_i $ ，你可以用基向量構造一個矩陣：
$$ \begin{pmatrix} q & 0 & 0 & \cdots & 0 \ 0 & q & 0 & \cdots & 0 \ \vdots & \vdots & \vdots & \ddots & \vdots \ 0 & 0 & 0 & \cdots & q \ t_0 & t_1 & t_2 & \cdots & t_n \ u_0 & u_1 & u_2 & \cdots & u_n \ \end{pmatrix} $$ （首先 $ n $ 行包含全零和一 $ q $ , 每個未知數一個 $ j_i $ 。） 這是個 $ (n+2) \times n $ 矩陣。現在讓 $ T \equiv (t_0, t_1, \cdots, t_n) $ 和 $ U \equiv (u_0, u_1, \cdots, u_n) $ . 然後是感興趣的短向量， $ X $ 會是這樣的
$$ U - xT + \text{(other stuff)} $$ 您可以修改矩陣以包含“哨兵值” $ s_T $ 和 $ s_U $ 以便您辨識 $ X $ ; 如果你看到一個縮小的向量 $ T’ $ 和 $ s_T $ 作為它的最後一個插槽，您很可能會看到倒數第二個條目包含 $ -x\cdot s_U $ 您可以從中恢復 $ x $ . 免責聲明：我首先在密碼學問題中看到了這個技巧，它讓事情變得比猜測更容易。修改後的矩陣如下：
$$ \begin{pmatrix} q & 0 & 0 & \cdots & 0 & 0 & 0\ 0 & q & 0 & \cdots & 0 & 0 & 0\ \vdots & \vdots & \vdots & \ddots & \vdots & 0 & 0\ 0 & 0 & 0 & \cdots & q & 0 & 0\ t_0 & t_1 & t_2 & \cdots & t_n & s_T & 0 \ u_0 & u_1 & u_2 & \cdots & u_n & 0 & s_U\ \end{pmatrix} $$ 現在您可以使用NTL或fplll的 LLL 實現，找到標記值，然後提取 $ x $ .