如果公鑰不同，為兩個簽名重用 ECDSA 隨機數是否安全？

我們表示 ECDSA 簽名的 s 值 $ (r, s) $ 在一條消息上 $ m $ 作為： $ s=\frac{H(m)+xr}{k} $

假設兩個 ECDSA 簽名共享相同的 nonce $ (r, s_1) , (r, s_2) $ 在兩條消息上 $ m_1, m_2 $ ，在兩個公鑰下驗證 $ x_1G, x_2G $ .

如果兩個公鑰相等，那麼密鑰應該相等 $ x_1 = x_2 $ 我們可以很容易地恢復 $ k $ 對隨機數重用使用標準攻擊。一旦我們知道 $ k $ 我們可以恢復密鑰。

$ \frac{H(m_1)-H(m_2)}{(s_1 - s_2)} =\frac{k(H(m_1)-H(m_2))}{H(m_1)-H(m_2)+x_1r - x_2r} $

$ x_1 = x_2 \rightarrow x_1r - x_2r = 0 $

$ \frac{H(m_1)-H(m_2)}{(s_1 - s_2)} =\frac{k(H(m_1)-H(m_2))}{H(m_1)-H(m_2)} = k $

我的問題是，如果密鑰不相等，這種攻擊能否起作用，即 $ x_1 \ne x_2 $ :

$ \frac{H(m_1)-H(m_2)}{(s_1 - s_2)} =\frac{k(H(m_1)-H(m_2))}{H(m_1)-H(m_2)+x_1r - x_2r} = \frac{k(H(m_1)-H(m_2))}{H(m_1)-H(m_2)+ (x_1 - x_2)r} $

如果你知道 $ x_1 - x2 $ 或者 $ \frac{x_1}{x_2} $ 你應該能夠計算 $ k $ 只要 $ s_1 \ne s_2 $ .

你可以計算 $ x_1 - x_2 = \frac{H(m_2) - H(m_1)}{r} $ 萬一 $ s_1 - s_2 = 0 $ . 然而，這種情況似乎降低了 ECDSA 的難度，因為任何人都可以計算新消息的公鑰 $ m_2 $ 在第一個簽名下驗證 $ (s, r) $ 使用公鑰恢復。

如果 $ s_1 \ne s_2 $ 你可以計算 $ \frac{x_1 - x_2}{k} $ 它允許您轉換 $ s_1 $ 進入 $ s_2 $ 反之亦然。

假設您有兩個消息簽名對，並且隨後的值是公開的，即您知道 -

• 公鑰： $ Q_1 (= x_1G) $ , $ Q_2 (= x_2G) $
• 消息及其雜湊： $ m_1 $ , $ m_2 $ , $ H(m_1) $ , $ H(m_2) $
• 簽名： $ (r_1, s_1) $ , ( $ r_2, s_2 $ )

以下未知——

• 私鑰： $ x_1 $ , $ x_2 $
• 隨機數： $ k $

以下關係也是已知的 -

• $ s_1 = k^{-1}(H(m_1) + r_1x_1) $
• $ s_2 = k^{-1}(H(m_2) + r_2x_2) $

請注意，我們在三個未知數中有兩個方程。為了解決這些問題，我們需要消除至少一個未知數，以便我們可以僅根據一個未知數編寫一個方程並將其代入另一個方程（產生一個可以通過基本代數求解的具有一個未知數的方程）。

使用的技巧 $ k $ 與相同的使用 $ x $ （IE $ x_1 = x_2 $ ) 是它消除了兩個未知數 ( $ x_1 $ 和 $ x_2 $ ) 產生一個容易求解的方程。

那麼當我們如何處理這個問題時 $ x_1 \ne x_2 $ ? 我看到的唯一方法是嘗試劃分 $ s_1 $ 經過 $ s_2 $ 消除 $ k^{-1} $ . 消除 $ x_1 $ 或者 $ x_2 $ 似乎它需要索引演算，這意味著解決 ECDLP，這將違反 ECDSA 所基於的安全假設。

那麼讓我們看看是什麼 $ \frac{s_1}{s_2} $ 產量 -

$$ \frac{s_1}{s_2} = \frac{k^{-1}(H(m_1) + r_1x_1)}{k^{-1}(H(m_2) + r_2x_2)} $$ $$ \frac{s_1}{s_2} = \frac{H(m_1) + r_1x_1}{H(m_2) + r_2x_2} $$ $$ \frac{s_1(H(m_2) + r_2x_2)}{s_2} = H(m_1) + r_1x_1 $$ $$ \frac{s_1(H(m_2) + r_2x_2) - s_2H(m_1)}{s_2} = r_1x_1 $$ $$ \frac{s_1(H(m_2) + r_2x_2) - s_2H(m_1)}{r_1s_2} = x_1 $$

請注意，我們現在可以刪除 $ x_1 $ 從方程定義 $ s_1 $ 我們剩下一個由兩個變數組成的方程組，只要它們不是線性相關的，就可以通過線性代數求解。

（從這裡開始，我將使用 $ h_n = H(m_n) $ 為了簡潔起見）

$$ s_1 = k^{-1}(h_1 + r_1\frac{s_1(h_2 + r_2x_2) - s_2h_1}{r_1s_2}) $$ $$ k = s_1^{-1}(h_1 + \frac{s_1(h_2 + r_2x_2) - s_2h_1}{s_2}) $$

然後做更多的替換 -

$$ s_2 = k^{-1}(h_2 + r_2x_2) $$ $$ k = s_2^{-1}(h_2 + r_2x_2) $$ $$ s_1^{-1}(h_1 + \frac{s_1(h_2 + r_2x_2) - s_2h_1}{s_2}) = s_2^{-1}(h_2 + r_2x_2) $$ $$ s_2(h_1 + \frac{s_1(h_2 + r_2x_2) - s_2h_1}{s_2}) = s_1(h_2 + r_2x_2) $$ $$ s_2(\frac{h_1s_2 + s_1(h_2 + r_2x_2) - s_2h_1}{s_2}) = s_1(h_2 + r_2x_2) $$ $$ (h_1s_2 + s_1(h_2 + r_2x_2) - s_2h_1) = s_1(h_2 + r_2x_2) $$ $$ s_1(h_2 + r_2x_2) = s_1(h_2 + r_2x_2) $$

所以我們留下了一個重言式……為什麼？因為代替 $ x_1 $ 進入第一個方程本質上給我們留下了同一個方程的兩個實例，只是在方程的不同邊有一些額外的項和項。這意味著我們無法解決系統問題。或者更準確地說，我們擁有的系統有無限多的解決方案。看到這一點的一個簡單方法是考慮一個更簡單的系統 -

$$ x = 2y $$ $$ 2x = 4y $$

你可以代替 $ x $ 在第二個等式中，但這對您沒有任何好處。

---

總之，使用不同的密鑰對重複使用 nonce 似乎不允許恢復任何秘密材料。儘管上述證明遠非完整或嚴格的證明，但至少它不會成為使用與使用相同密鑰設置重用的隨機數相同的方法的攻擊的受害者。無論如何，如果您可以選擇避免這種情況，那麼有很多好方法可以生成隨機數。RFC 6979是一個很好的起點。

不！因為如果您使用相同的 K（隨機數），那麼對於同一曲線上的任何簽名，R 將是相同的：R 僅取決於 KG（曲線上的 G 生成點）

例子：我們有兩個簽名 (r1,s1), (r2,s2) 如果 K 相同，那麼密鑰可以計算如下：

1. r1=r2（因為 r=xP modn 和 P=kG（曲線上的 G 生成點）對於兩個簽名都是相同的）。
2. 從 s 的等式： (s1-s2)mod n = K**(-1)(z1-z2) mod n
3. 乘以 K：K*(s1-s2)mod n = (z1-z2)mod n
4. 除以 (s1-s2) 得到 K：k=(z1−z2)*(s1−s2)**(-1)mod n
5. 獲取私鑰 X：s=K**(-1)(z+rX)mod n -> X=R**(-1)(sK−z)mod n

靜態 K 和兩個不同私鑰的範例：

請注意，對於不同的私鑰，分別。不同的公鑰，最重要的是，簽名中的第一個值（相同的 R）對於不同的私鑰、不同的公鑰和不同的消息是相同的。我引用了上面計算密鑰的算法。

   Curve: secp256k1
   static K: 0x6f347e49ec1b25e50dd9bf56b2d0a7e340ad95bde99ac57fb65815742a0f869f

Private key: 0xc2ca56f311dc91cd15fb6b2a9b66b0579fed1f38a8e6fcbfd721a8c720d8d0d9
Public key(x,y): (0x91d1d4188286f780f879800794ea46b68dcfae941f5a76f7161255cd907443ab, 0x59508303be1539be3a2a73ed7867f6db94374cca8b40ccf1c740829d838fb110)
Message: b'Hello!'
Signature(r,s): (0x760eb603ad708e7306d79f9c4c9f7b82c4720eed8051111c46106c5441899abf, 0x9746c29bcc65fad45ddb533978d5a16cbc22a31ddeb98ba4dde5a5cd2b8922d2)
Verification: signature matches 

Private key1: 0xe61144621e67a5d78be714497bcf3777b18e43580b7b84ce49fcd559532b1062
Public key1(x,y): (0xcef0ce622b51c479f09f726172c8e7c28a6147a9cfa170f4242ee4ed70072f24, 0x3f1c6b2096c1d83fdd567a736ed9f760fcd9c89ed1588f5a4b7bf92a586c0122)
Message: b'I do not understand what is not clear'
Signature1(r,s): (0x760eb603ad708e7306d79f9c4c9f7b82c4720eed8051111c46106c5441899abf, 0x98d6440373ecc23e3a538edd5f12e090fd707852d24660b8f8f68a1cc6e2f691)
Verification: signature matches 

加密蟒蛇

這個腳本是Andrea Corbellini寫的，我只是為靜態 K 編輯了一下。

PS 順便說一句，我推薦閱讀他的文章，也許會有額外的清晰。（最後一個連結）

引用自：https://crypto.stackexchange.com/questions/71764