關於格子攻擊中ECDSA係數的問題
更新：我的格子攻擊終於奏效了。由於實際原因非常複雜，我決定在下面寫一個答案來描述它是如何工作的，這樣任何有類似問題的人都可以從我的工作中獲得靈感。問題未修改。
我最近在研究晶格攻擊。我嘗試使用來自TPM-FAIL的數據來幫助我理解這種攻擊，並嘗試使用“教科書方法”來實施攻擊（TPM-FAIL 攻擊腳本中有一些優化）。我在閱讀材料時遇到了一些我自己無法弄清楚的問題。如果您有任何想法，請幫助我。
- DSA 簽名公式最終可以轉換為以下等式：
$ k_i-s_i^{-1}r_id-s_i^{-1}H(m)\equiv 0 \pmod{n} $
其中 k 是臨時密鑰，(r,s,) 是簽名對，d 是私鑰，H(m) 是像往常一樣的消息摘要……你知道演習。
然後它可以轉化為格子形式。類似於以下等式：
$ k_i+A_id+B_i\equiv 0\pmod n $ ， 在哪裡 $ A_i=-s_i^{-1}r_i $ 和 $ B_i=-s_i^{-1}H(m) $
我不明白的是，為什麼它必須是負面的？實際嘗試修改TPM-FAIL數據集中提供的攻擊腳本，發現去掉A_i和B_i中的-1會使攻擊失敗。但是我們可以將第一個方程改寫為：
$ s_i^{-1}r_id+s_i^{-1}H(m)\equiv k_i\pmod{n} $
格攻擊的概念應該仍然成立：如果格向量很小，則基約約算法應該生成答案。我做錯了什麼？ 2. 第二件事是我嘗試使用未優化的方法，SVP lattice 的建構如下：
$ \begin{bmatrix}n&&&&&\&n&&&&\&&\ddots&&&\&&&n&&\A_1&A_2&\dots&A_t&K/n&\ B_1&B_2&\dots&B_t&&K\\end{bmatrix} $
但我們可以清楚地看到，K/n 將是一個小數，不能在 sagemath 中使用 BKZ() 或 LLL() 方法。我的理解是，我們可以將這個矩陣中的所有東西都乘以 n，所以這個矩陣中的所有東西都是整數。在應用 BKZ() 之後，我們將所有內容除以 n 以恢復原始結果：私鑰應該在第一行的倒數第二列。但是我未能恢復私鑰。即使我使用了 100 個帶有 8 位洩漏的簽名。我的方法正確嗎？
提前謝謝你的幫助！
- 簡短的回答是：這個想法沒有錯。更改符號後我沒有成功攻擊的主要原因是因為TPM-FAIL論文中有一個優化。它通過某種轉換消除了第一個簽名。這可以將晶格的維度減少 1，從而略微提高計算速度。轉換的結果是 $ B_i $ 有兩個術語而不是一個。我只更改了一個學期的符號，因此攻擊沒有成功。
順便說一句，我想進一步指出，在一些論文中，這個方程被轉換為 CVP（最近向量問題），它的形式為 $ |\alpha \mathbf{t}-\mathbf{u}|_q < K $ . 因此在這種情況下 $ A_i=\mathbf{t}=s_i^{-1}r_i $ 和 $ B_i=\mathbf{u}=-s_i^{-1}H(m) $
其次，有人擔心該標誌可能會影響重新定位。我實際上沒有看到它是如何應用於 TPM-FAIL 方法的。最後我使用了不同的格子結構，所以我在那裡停止了我的研究。 2. 我選擇的最後一個格子與這個有點不同。它基於這個等式：
$ |ds_i^{-1}r_i - (-s_i^{-1}H(m))|_n = k_i < n/2^l $
去掉 mod 操作後，我們可以建構 lattice：
$ d|s_i^{-1}r_i|_n - |(-s_i^{-1}H(m))|_n + C_i n=k_i < n/2^l $
為了使格攻擊起作用，我們只需要 $ |k| $ 小而作為 $ k $ 總是積極的，我們可以應用重新定位：
$ d|s_i^{-1}r_i|_n - |(-s_i^{-1}H(m))|_n + C_i n - n/2^{l+1} =k_i - n/2^{l+1} $ 在哪裡 $ -n/2^{l+1} < k_i - n/2^{l+1} < n/2^{l+1} $
為了確保晶格中的每個元素都是整數，以便我們可以應用 LLL 或 BKZ，我們通常要做的是將兩邊都乘以 $ 2^{l+1} $
$ d[2^{l+1}\times |s_i^{-1}r_i|_n] - [2^{l+1}\times |(-s_i^{-1}H(m))|_n + n] + C_i\times 2^{l+1}n =k_i - n/2^{l+1} $
第一個方括號將是 $ A_i $ 第二個將是 $ B_i $ . 請注意，重新定位項被合併到 $ B_i $ 所以符號發生了變化。
有幾點需要指出：
- 我們需要注意乘以 $ 2^{l+1} $ 和 $ |s_i^{-1}r_i|_n $ 是一個正常的乘法，而不是模數。如果你寫在 sagemath
a = Mod(s_inv * r, n) c = a * b二行也將成為模乘法。為了讓它正常，我們需要寫= Mod(s_inv * r, n) = a.lift() * b正確答案不一定出現在第一行。根據數量和算法，答案可能出現在第二行或倒數第二行。因此最好的方法是檢查每一行的對應列，看是否有正確的答案。 由於重新定位，結果可能不是積極的。有時可能是 $ n-d \pmod n $ . 所以對於每一行，我們需要同時檢查`Mod(answer , n)`和`n- Mod(answer ,n)`r row in range(lattice.nrows()): the column number depends on how you construct the lattice, in a normal SVP with kanaan embedding technique, the corresponding column is the second last one lution = Mod(lattice[row, -2], modulo).lift() check_answer(solution): turn solution check_answer(modulo - solution): turn modulo - solution `如果所有這些都被正確處理，你應該有一個成功的攻擊。