使用 ECDSA 中的已知共享組件恢復 ECDSA 中的 nonce
這是共享隨機數問題的一個輕微變化。我們在兩個 nonce 之間確實有更多的共享資訊。
給定一個隨機ķ $ k $ ：
ķ1=ķ一個,ķ2=ķb$$ k_1 = ka, k_2 = kb $$
我現在正在簽署兩條消息，這給了我s1,r1,s2,r2 $ s_1,r_1,s_2,r_2 $
基於我對 ECDSA 中籤名的基本方程的理解（使用給定的生成器G $ G $ , 私鑰d $ d $ )
r=ķG,s=ķ-1(H+rd)$$ r=kG, s=k^-1(h+rd) $$
所以現在我有兩個方程，我可以用它們來解決ķ $ k $ ：
s1-s2=ķ-11(H1+r1d)-ķ-12(H2+r2d)s1-s2=ķ-11H1+ķ-11r1d-ķ-12H2-ķ-12r2d擴張 ķ1,ķ2s1-s2=ķ-1一個-1H1+ķ-1一個-1r1d-ķ-1b-1H2-ķ-1b-1r2d擴張 r1,r2s1-s2=ķ-1一個-1H1+ķ-1一個-1(ķ一個G)d-ķ-1b-1H2-ķ-1b-1(ķbG)ds1-s2=ķ-1一個-1H1+ķ-1ķ一個-1一個Gd-ķ-1b-1H2-ķ-1ķb-1bGds1-s2=ķ-1一個-1H1+ķ-1ķ一個-1一個Gd-ķ-1ķb-1bGd-ķ-1b-1H2s1-s2=ķ-1一個-1H1+Gd-Gd-ķ-1b-1H2s1-s2=ķ-1一個-1H1-ķ-1b-1H2ķ(s1-s2)=一個-1H1-b-1H2ķ=(一個-1H1-b-1H2)(s1-s2)-1$$ \begin{align} s_1-s_2&=k_1^{-1}(h_1+r_1d)-k_2^{-1}(h_2+r_2d) \ s_1-s_2&=k_1^{-1}h_1+k_1^{-1}r_1d-k_2^{-1}h_2-k_2^{-1}r_2d &&\text{expand $k_1,k_2$}\ s_1-s_2&=k^{-1}a^{-1}h_1 + k^{-1}a^{-1}r_1d - k^{-1}b^{-1}h_2 - k^{-1}b^{-1}r_2d &&\text{expand $r_1,r_2$}\ s_1-s_2&=k^{-1}a^{-1}h_1 + k^-1a^{-1}(kaG)d - k^{-1}b^{-1}h_2 - k^{-1}b^{-1}(kbG)d \ s_1-s_2&=k^{-1}a^{-1}h_1 + k^{-1}ka^{-1}aGd - k^{-1}b^{-1}h_2 - k^{-1}kb^{-1}bGd \ s_1-s_2&=k^{-1}a^{-1}h_1 + k^{-1}ka^{-1}aGd - k^{-1}kb^{-1}bGd -k^{-1}b^{-1}h_2 \ s_1-s_2&=k^{-1}a^{-1}h_1 + Gd - Gd -k^{-1}b^{-1}h_2 \ s_1-s_2&=k^{-1}a^{-1}h_1 -k^{-1}b^{-1}h_2 \ k(s_1-s_2)&=a^{-1}h_1 - b^{-1}h_2 \ k&=(a^{-1}h_1 - b^{-1}h_2)(s_1-s_2)^{-1} \end{align} $$
我嘗試在 python 中實現它：
import ecdsa import random import libnum import hashlib import sys G = ecdsa.ecdsa.generator_256 order = G.order() priv1 = random.randrange(1,order) Public_key = ecdsa.ecdsa.Public_key(G, G * priv1) x1 = ecdsa.ecdsa.Private_key(Public_key, priv1) k = random.randrange(1, 2**127) msg1="testmessage one" msg2="testmessage two" h1 = bytes_to_long(hashlib.sha1(msg1.encode()).digest()) h2 = bytes_to_long(hashlib.sha1(msg2.encode()).digest()) a=101 b=197 sig1 = x1.sign(h1, k*a) sig2 = x1.sign(h2, k*b) r1,s1 = sig1.r,sig1.s r2,s2 = sig2.r,sig2.s k_recovered = (((libnum.invmod(int(a),order)*(h1))%order-(libnum.invmod(int(b),order)*(h2)%order))*libnum.invmod( (s1-s2),order))%order print ("\nk: \t\t",k) print ("k recovered \t",k_recovered)這給了我一個錯誤的 k
k: 11380758029406828810642876408403002369 k recovered 92413802760778512715100399489368323379693045694765104020036290177818159224142我一直盯著這種方式太久了，可以用第二雙眼睛。我是在基礎數學中遺漏了什麼還是我搞砸了實現？
（ps，這有點類似於這裡討論的問題
您正在混淆曲線和場算術運算的組運算。乘以X $ x $ - 標量的點座標不會產生相應的X $ x $ - 點的座標乘以相同的標量。所以一般來說，這是不正確的 一個GX=(一個G)X$$ aG_x = (aG)_x $$ 我在哪裡表示X $ x $ - 一個點的座標磷 $ P $ 作為磷X $ P_x $ . 在左側，我們將兩個欄位元素（x 座標和 a）相乘，在右側，我們進行標量點乘法
所以在你的第 3-5 行中，r=(ķ一世G)X $ r = (k_iG)_x $ , 術語簡化不一定是真的。 dķ-1一世r一世=dķ-1一世(ķ一世G)X≠(dG)X$$ dk_i^{-1}r_i = dk_i^{-1}(k_iG)_x \neq (dG)_x $$
這裡需要其他東西來獲得你的最終結果ķ $ k $ .
編輯：要解決這個問題，因為你知道s1,s2,r1,r2,H1,H2,一個,b $ s_1, s_2, r_1, r_2, h_1, h_2, a, b $ ，您需要解決以下系統：
s1=ķ-1一個-1(H1+r1d)$$ s_1 = k^{-1}a^{-1}(h_1 + r_1d) $$ s2=ķ-1b-1(H2+r2d)$$ s_2 = k^{-1}b^{-1}(h_2 + r_2d) $$
編輯2：這是一些程式碼
import ecdsa import random import libnum import hashlib import sys import math from Crypto.Util.number import bytes_to_long G = ecdsa.ecdsa.generator_256 order = G.order() priv1 = random.randrange(1,order) Public_key = ecdsa.ecdsa.Public_key(G, G * priv1) x1 = ecdsa.ecdsa.Private_key(Public_key, priv1) k = random.randrange(1, 2**127) msg1="testmessage one" msg2="testmessage two" h1 = bytes_to_long(hashlib.sha1(msg1.encode()).digest()) h2 = bytes_to_long(hashlib.sha1(msg2.encode()).digest()) a=101 b=197 sig1 = x1.sign(h1, k*a) sig2 = x1.sign(h2, k*b) r1,s1 = sig1.r,sig1.s r2,s2 = sig2.r,sig2.s def inv(x): return libnum.invmod(x, order) d_recovered = (inv(s1*a)*h1 - inv(s2*b)*h2)*inv(inv(s2*b)*r2 - inv(s1*a)*r1) % order print ("d recovered \t",d_recovered) print ("\nd: \t\t",priv1)
如果你避免在方程中有很多逆，你的方程會更容易求解。此外，我發現當將逆寫為除法時，方程式更具可讀性。
所以，這是你開始的兩個等式：
s1一個ķ=H1+r1ds2bķ=H2+r2d$$ s_1 a k = h_1 + r_1 d \ s_2 b k = h_2 + r_2 d \ $$
將第一個乘以r2 $ r_2 $ 第二個是r1 $ r_1 $
r2s1一個ķ=r2H1+r2r1dr1s2bķ=r1H2+r1r2d$$ r_2 s_1 a k = r_2 h_1 + r_2 r_1 d \ r_1 s_2 b k = r_1 h_2 + r_1 r_2 d \ $$
然後減去：
r2s1一個ķ-r1s2bķ=r2H1-r1H2+r2r1d-r1r2d$$ r_2 s_1 a k - r_1 s_2 b k = r_2 h_1 - r_1 h_2 + r_2 r_1 d - r_1 r_2 d $$
收集術語並註意d $ d $ 術語消失。
(r2s1一個-r1s2b)ķ=r2H1-r1H2$$ (r_2 s_1 a - r_1 s_2 b ) k = r_2 h_1 - r_1 h_2 $$
所以： ķ=H1r2-H2r1s1一個r2-s2br1$$ k = {{h_1 r_2 - h_2 r_1} \over {s_1 a r_2 - s_2 b r_1}} $$
同樣，您可以推導出以下等式：
d=s2bH1-s1一個H2s1一個r2-s2br1$$ d = {{ s_2 b h_1 - s_1 a h_2 } \over {s_1 a r_2 - s_2 b r_1}} $$