從 Secp256k1 簽名中恢復私鑰
我在這裡看到了很多答案，還有很多文章說我們可以從重複使用的R 簽名中恢復私鑰。但是，如果r,s 簽名在比特幣交易中不同，那麼我們有沒有辦法找到兩種情況下使用的臨時密鑰 k並找到私鑰？
在 ECDSA 中，每個簽名都有自己的臨時密鑰 $ k $ . 如果 $ k $ 如果生成正確，那麼再多的簽名也無法幫助您恢復私鑰。這裡的“正確”生成是指在適當範圍內的隨機統一選擇，或適當的去隨機化過程，例如RFC 6979中描述的過程。
如果完全一樣 $ k $ value 用於兩個簽名，兩個不同的消息，但使用相同的私鑰 $ x $ ，然後私鑰就暴露了。這是索尼在 2011 年初犯下的致命錯誤（順便說一句，這也是 RFC 6979 的最初動機）。事實上，如果這兩個消息是 $ m_1 $ 和 $ m_2 $ ，並且兩個值使用相同的 $ k $ 值，那麼這兩個簽名是 $ (r,s_1) $ 和 $ (r,s_2) $ : $$ \begin{eqnarray} s_1 &=& (h(m_1) + xr) / k \ s_2 &=& (h(m_2) + xr) / k \ \end{eqnarray} $$ 短暫的鑰匙 $ k $ , 和私鑰 $ x $ , 然後可以計算為： $$ \begin{eqnarray} k &=& \frac{h(m_1) - h(m_2)}{s_1 - s_2} \ x &=& \frac{ks_1 - h(m_1)}{r} \ \end{eqnarray} $$
如果值 $ k $ 沒有被重用，但產生了一些偏差（即不是所有的值在 $ [1,q-1] $ 範圍以相同的機率選擇），然後是私鑰 $ x $ 仍然可以從一組簽名中恢復。如果例如 $ q $ 大小為 256 位，但值為 $ k $ 總是低於 $ 2^{253} $ （即前三位總是零），那麼幾百個簽名就足夠了。
如果值 $ k $ 使用強大的、加密安全的源生成，並且沒有偏見，則沒有已知的針對 ECDSA 的攻擊可以恢復私鑰 $ x $ ，即使已知許多簽名。第一次重用 $ k $ 出於純粹的運氣，預計會在平均 $ 2^{n/2} $ 簽名 $ n $ -位曲線，即如果您使用體面的曲線，則永遠不會在實踐中。
此外，在比特幣中，人們往往不會使用任何給定的密鑰進行大量簽名。出於隱私原因，不鼓勵地址重用。
所以，讓我回顧一下關於 ECDSA 的一些細節：
ECDSA 簽名是一對整數 $ (r,s) $ .
為了生成給定消息的簽名 $ m $ , 給定的雜湊函式 $ H $ , 曲線參數 $ (\mathcal{C}, G, n) $ 為了 $ \mathcal{C} $ 一條曲線， $ G $ 質數基點 $ n $ 的 $ \mathcal{C} $ , 一個私鑰整數 $ d $ 和一個公鑰點 $ Q = d\times G $ ， 一罐：
- 計算 $ e = H(m) $ ， 在哪裡 $ H $ 是一個密碼散列函式，讓 $ z $ 是表示的最左邊位的整數 $ e $ ， 什麼時候 $ e $ 被截斷為組序的位長。
- 隨機均勻地選取一個值 $ k $ 在哪裡 $ 0 < k < n-1 $ ;
- 計算點 $ (x, y) = k G $ ;
- 計算 $ r = x,\bmod,n $ . 如果 $ r = 0 $ , 回到 2 ;
- 計算 $ s = k^{-1}(z + r d_A),\bmod,n $ . 如果 $ s = 0 $ , 回到第 2 步。
然後，當一個人簽署了消息 $ m $ , 可以傳輸元組 $ (m, r,s) $ 任何人都可以驗證簽名 $ (r, s) $ 通過執行以下步驟：
- 計算 $ e = H(m) $ 然後讓 $ z $ 就像在簽名過程中一樣；
- 計算 $ w = s^{-1},\bmod,n $ ;
- 計算 $ u_1 = zw,\bmod,n $ 和 $ u_2 = rw,\bmod,n $ ;
- 計算點 $ (x, y) = u_1 G + u_2 Q $ .
如果 $ r \equiv x \mod n $ ，則簽名有效，否則無效。
請注意，ECDSA 關鍵依賴於唯一性（就像在PS3 fail中一樣），但也依賴於用於選擇 $ k $ ，因為那裡的偏見也可能導致攻擊者恢復私鑰，只有她可以使用的公共簽名，參見例如這篇論文$$ 1 $$.
現在，當你重複使用兩次相同的東西時實際會發生什麼 $ k $ 價值？
假設您獲得了兩個不同消息的兩個簽名 $ m_1 $ 和 $ m_2 $ ，那麼你有兩個簽名 $ (r_1,s_1) $ 和 $ (r_2,s_2) $ 和 $ s $ - 值的計算如上面的步驟 5 所示。這意味著您可以輕鬆恢復 $ k $ 通過計算：
$$ k = (z_1 - z_2)(s_1-s_2)^{-1} \bmod{n} $$ 我們正在使用曲線的階數取反模。從 $ k $ ，也很容易計算秘密整數的值 $ d $ ，在兩個簽名中的任何一個的幫助下： $$ d= (ks-z)r^{-1} \bmod{n} $$ 完成此操作後，您可以通過將公鑰與 $ d\times G $ , 因為如果你有正確的 $ d $ ，兩者都是一樣的。
最後，請注意這適用於任何 ECDSA 實例，而不僅僅是使用 Secp256k1。
參考
$$ 1 $$德穆德、埃爾克等人。“使用 Bleichenbacher 解決隱藏數字問題的方法來攻擊 384 位 ECDSA 中的 nonce 洩漏。” 密碼硬體和嵌入式系統國際研討會。施普林格，柏林，海德堡，2013 年。