比特幣區塊鏈上 ECDSA 中的一項弱交易，在 Lattice Attack 的幫助下，我們收到了 BTC 硬幣的私鑰

 

我們對網格攻擊了解多少？

首先， 橢圓曲線數字簽名算法 (ECDSA) 是我們在許多代碼審查中看到的常見數字簽名方案。它具有一些理想的特性，但也可能非常脆弱，無法通過側通道攻擊恢復私鑰，該攻擊揭示了不到一位的秘密隨機數。

ECDSA 是數字簽名算法的一種特殊形式 (DSA)。 DSA 是一種相當常見的數字簽名方案，由三種算法定義：密鑰生成、簽名和驗證。 密鑰生成算法生成私鑰和公鑰； 私鑰負責創建簽名； 公鑰負責驗證簽名。 簽名算法將消息和私鑰作為輸入並生成簽名。驗證算法以消息、簽名和公鑰作為輸入，返回值 true or  false，表示簽名是否有效。

DSA 是為任何數學群定義的，只要離散對數問題對於該群來說是困難的，這個方案就是安全的。一個常用的群是以素數 p 為模的整數。

除了這個組，我們還有一個組生成器 g 和一些密碼安全的 散列 函數 H。我們可以假設 p , g 並且 H 將是常識。

密鑰生成首先 x 從模整數 中隨機選擇一個值p 。然後計算值 y = g^x mod p

簽名的私鑰是 x ，公鑰是 y 。簽名密鑰必須保密，因為它允許進行簽名。

m 簽名算法根據消息和密鑰 x創建簽名 。首先，生成一個隨機群元素 k 。這被稱為隨機數，這在攻擊方面很重要。

然後計算值 r = g^k mod p 並 s = ( k^-1 ( H ( m ) + xr )) mod p

這裡 k^- 1 , 是逆群，並且 H ( m ) 是計算哈希 m 的結果，並將結果解釋為整數模 p 。

簽名定義為一對 ( r , s ). （注意：如果 r 或 值之一s等於 0，則算法以 的新值重新開始 k ）。

驗證算法接收簽名 ( r , s )、消息 m 和公鑰 y 作為輸入。讓 ŝ = s^-1 ，然後算法返回真當且僅當 r , s ≠ 0 и r = ( g H ( m ) y r ) ŝ 。

此驗證檢查有效，因為 g^H( m ) y^r = g^H(m)+ xr = g^ks，因此 (g^H(m)y^r)^ŝ = g^k = r

如果數字簽名方案不能被偽造，則它被認為是安全的。

不變性具有正式的加密含義，但在較高級別上，它意味著您無法在不知道密鑰的情況下創建簽名（除非您複製了從密鑰創建的現有簽名）。在離散日誌的假設下被證明是 DSA不可能偽造的  。

DSA 是在一個數學群上定義的。當 DSA 與橢圓曲線群作為這個數學群時，我們稱它為 ECDSA。 橢圓曲線組 由橢圓曲線點組成，它們是成對的 ( x , y )，滿足 y^2 = x^3 + ax + b 一些 的方程a , b 。對於這篇博文，您只需要知道使用橢圓曲線可以定義一個有限群，這意味著您可以獲得群生成器 g (橢圓曲線點)，以及與  您完全一樣的加法 和 點乘運算可以用整數。因為它們形成一個有限群，生成器，g , 將有一個有限的順序,  p。這篇博文不會解釋或要求您了解這些 橢圓曲線操作的工作原理。

ECDSA 與 相同 DSA，但使用不同的組。 密鑰 x 仍然是一個模整數的隨機值 p 。現在公鑰 y 仍然計算為 y = g^x ，除了 g 現在是橢圓曲線上的一個點。這意味著 y 也將是橢圓曲線上的一個點（以前 y 是一個模 p 的整數）。另一個區別是我們如何計算 r 的值。我們仍然像以前一樣生成一個隨機數 k 作為整數模 p。我們將計算 g^k ，但同樣，g 它是橢圓曲線的一個點，因此 g^k 也是。因此，我們可以計算 ( x^k , y^k ) = g^k 和設置 r = x^k 。現在的意思 s 可以像以前一樣計算，我們得到我們的簽名 ( r , s )，它仍然是一個整數模 p ，和以前一樣。r 為了檢查，我們需要糾正我們計算略有不同的事實 。

因此，和以前一樣，我們 計算 的值 ( g^H(m)y^r)^ŝ ，但現在該值是橢圓曲線上的一個點，因此我們取 x該點的 - 坐標並將其與 的值進行比較 r 。

 從重複使用的隨機數 中恢復 密鑰NONCES

現在我們了解了它是什麼以及它是 ECDSA 如何工作的，讓我們展示它的 脆弱性。同樣，由於這是一種數字簽名方案，因此  除了簽署消息的人之外，密鑰永遠不會洩露給任何人。

但是，如果簽名者曾經發出簽名並且還發出使用過的 nonce，則 攻擊者 可以立即恢復 密鑰。

假設我發布了 ( r , s ) 一條消息 的簽名m 並意外發現我使用了一個 nonce  k 。

因為 s = ( k^-1 ( H ( m ) + xr )), 我們可以很容易地計算出密鑰：

s = (k^-1(H(m) + xr))

ks = H(m) + xr

ks – H(m) = xr

x = r^-1(ks – H(m))

因此，簽名者不僅要保密他們的 私鑰，而且他們曾經生成的所有隨機數都是保密的。

即使簽名者對每個 nonce NONCES保密，如果他不小心重複了一個 nonce NONCES  （即使對於不同的消息），  也可以 立即恢復密鑰。

讓 ( r , s 1 ) 和 ( r , s 2 ) 是在消息上創建的兩個簽名， m 1 並且 m 2 （分別）來自同一個隨機數 k - 因為它們具有相同的隨機數，所以 r 值將是相同的，因此攻擊者很容易檢測到：

s1 = k^-1(H(m1) + xr) and s2 = k^-1(H(m2) + xr)

s1 – s2 = k^-1(H(m1) – H(m2))

k(s1 – s2) = H(m1) – H(m2)

k = (s1 – s2)^-1(H(m1) – H(m2))

一旦我們 k 使用上述公式恢復了 nonce，我們就可以通過執行前面描述的攻擊來恢復私鑰。

讓我們消化一下。

如果 簽名隨機數 NONCES 被洩露， 密鑰可以立即 恢復，這 破壞了我們的整個簽名方案。

此外，如果兩個隨機數重複，無論消息是什麼， 攻擊者 都可以輕鬆檢測到這一點並立即 恢復密鑰，再次破壞我們的整個方案。

它非常脆弱，只是 輕微的攻擊！

但是有一種 新的 格子攻擊 已經被詳細描述過 （Joachim Breitner 和 Nadia Heninger）Йоахим Брайтнер и Надя Хенингер 

文檔 [PDF]： 有偏見的隨機數感知：針對加密貨幣中弱 ECDSA 簽名的格攻擊

在比特幣區塊鏈中，我們發現了某筆交易：

交易：  08d917f0fee48b0d765006fa52d62dd3d704563200f2817046973e3bf6d11f1f

比特幣地址：  15N1KY5ohztgCXtEe13BbGRk85x2FPgW8E

我們設法增加了假簽名並應用了網格

在GOOGLE COLAB中使用 Python 腳本 algorithmLLL.py 安裝包 

安裝 >> SAGE + ECDSA + BITCOIN + 算法 LLL

 我們 設法 Private Key 從 .Bitcoin WalletECDSA

安裝

運行 Bash 腳本：lattice.sh

結果以十六進制格式找到私鑰！

文件：ONESIGN.txt（ECDSA 簽名 R、S、Z 值）

我們為 Python 腳本 algorithmLLL.py 傳播了假簽名

文件：PRIVATEKEY.txt

文件：地址.txt

在 bitaddress 網站上檢查私鑰

找到私鑰！

https://www.blockchain.com/btc/address/15N1KY5ohztgCXtEe13BbGRk85x2FPgW8E

0.001 比特幣

ADDR: 15N1KY5ohztgCXtEe13BbGRk85x2FPgW8E
WIF:  5JCAmNLXeSwi2SCgNH7wRL5qSQhPa7sZvj8eDwxisY5hJm8Uh92
HEX:  31AFD65CAD430D276E3360B1C762808D1D051154724B6FC15ED978FA9D06B1C1 

該視頻是為 CRYPTO DEEP TECH門戶網站創建的， 以確保數據的財務安全性和 secp256k1 橢圓曲線密碼術對 BITCOIN 加密貨幣中的弱 ECDSA 簽名

視頻：  https ://youtu.be/YP4Xj6gUcf4

電報：  https ://t.me/cryptodeeptech

資料來源：  https ://cryptodeep.ru/lattice-attack