使用 ECDSA over GF(2^m) 的消息簽名問題

我正在嘗試建立一個橢圓曲線的 ECDSA $ \operatorname{GF}(2^m) $ 帶有以下值的玩具範例：

在二進制有限域上使用 Weierstrass 方程。$$ E: y^2 + x*y - [x^3 + a x^2 + b] $$

---

讓 $ E $ 在場上定義 $ \operatorname{GF}(2^7) $ ( $ m = 7 $ ) 與等式

$$ E: y^2 + xy - [x^3 + 0x^2 + 1] $$在哪裡 $ a = 0 $ 和 $ b = 1 $ , 使用不可約多項式 $ P(z) = z^7 + z + 1 \bmod 2 $

這些點是十進制的，具有多項式表示。例子; $ (z^2 + z; z^2 + z + 1) = (0110; 0111) $ 在它的二進製表示和 $ (6, 7) $ 以十進製表示。我正在使用wolframcloud軟體來驗證操作。

• $ d = 17 $
• 發電機 $ G = (124, 68) = (z^6 + z^5 + z^4 + z^3 + z^2, z^6 + z^2) $ ，曲線上的一個點
• $ Q = [d]G = (40, 19) $ ，也是曲線上的一個點。
• $ k = 13 $
• $ P = [k]G = (82, 100) $
• $ r = x(P) = 82 $
• $ e = SHA(m) = 19 $
• $ k^{-1} = 79 $
• $ S = k^{-1} (e + d*r) \pmod{P(z)} $
• $ S = 79 (19 + 17*82) \pmod{P(z)} $
• $ S = 11 $

最後我得到了值 r 和 S ，即消息的簽名： $ (r, S) = (82, 11) $

---

驗證，然後假設第二個實體在不知道 d 和 k 的情況下知道曲線上的相同參數。第二個實體將執行：

$ P = [(S^{-1} * e) * G] + [(S^{-1} * r) * Q] \pmod{P(z)}\ S^{-1} = 74\ P = (74 * 19) * G + (74 * 82) * Q \pmod{P(z)}\ P = 102 * G + 67 * Q \pmod{P(z)}\ P = (80, 87) + (38, 35) \pmod{P(z)}\ P = (30, 92) \pmod{P(z)}\ P.x = 30 $

這不同於 $ r=82 $ : $ P.x $ 應該等於 $ r $ ，但是，它不是。

---

現在，我們假設第二個實體知道 $ d $ 這樣 $ Q = d * G $ 然後：

$ P = (102 * G) + (67 * 17 * G) \pmod{P(z)}\ P = (102 * G) + (107 * G) \pmod{P(z)}\ P = (102 + 107) * G \pmod{P(z)}\ P = 13 * G\pmod{P(z)}\ P = 13 * (124, 68)\ P = (82, 100)\ P.x = 82 = r $

這是正確的，但第二個實體不知道 $ d $ .

有人可以幫助我，請告訴我如何解決這個問題？

---

Wolfram 語言的附件程式碼：為了通過點的總和和點的加倍執行標量乘法，我使用以下程式碼：或者只是線上嘗試！

(* Input example GF(2^7): *)
m=7;
k="10001"; (*BinaQy representation 10001 = 17 in decimal *)
lim = StringLength [k] + 1 ;
a=0; 
Gx=z^6 + z^5 + z^4 + z^3 + z^2;  (* Gx = 124 *)
Gy=z^6 + z^2; (* Gy = 68 *)
IrreduciblePolynomialCCE= z^7 + z + 1;
Qx=Gx;
Qy=Gy;
For [i=2, i<lim , i++,
   c=StringTake [k ,{i}];
   (*Dubling*)
   {d, {inv, u}}=PolynomialMod[PolynomialExtendedGCD[Qx, IrreduciblePolynomialCCE],2];
   Lamda=PolynomialMod[(Qx + Qy*inv ), {IrreduciblePolynomialCCE, 2}] ;
   X3=PolynomialMod[(Lamda^2 + Lamda + a ), {IrreduciblePolynomialCCE, 2}] ;
   Y3=PolynomialMod [ (Qx^2 + Lamda*X3 + X3) , {IrreduciblePolynomialCCE, 2}] ;
   Qx = X3;
   Qy = Y3;
   If [c=="1",{
       (*Sum*)
       {d, {inv2, u}}=PolynomialMod[ PolynomialExtendedGCD[Gx + Qx, IrreduciblePolynomialCCE],2];
       Lamda2=PolynomialMod[(Gy + Qy) * inv2 , {IrreduciblePolynomialCCE, 2}] ;
       XX3=PolynomialMod [(Lamda2^2 + Lamda2 + Gx + Qx + a) , {IrreduciblePolynomialCCE, 2}] ;
       YY3=PolynomialMod [Lamda2*(Gx + XX3) + XX3 + Gy, {IrreduciblePolynomialCCE, 2}] ;
       Qx = XX3;
       Qy = YY3;
       },{0}
   ]
]
Print [Qx]
Print [Qy]

結果 $ Q = (z^5 + z^3, z^4 + z + 1) = (40, 19) $

首先，我要感謝@fgrieu、@kelelaka 和主持人 Maarten Bodewes 對解決我的問題的支持。

我在確定 K^-1, S, y S^-1 時出錯，我還遺漏了一條重要資訊，即 G 的順序 (n = 29)

糾正我的錯誤，我們有：

GF(2^7), m = 7

E: y^2 + x y - [x^3 + a x^2 + b]

y^2 + x y - [x^3 + 0 x^2 + 1] 其中 a = 0 和 b = 1

不可約多項式 P(z) = z^7 + z + 1 mod 2

d = 17

G = (124, 68) = (z^6 + z^5 + z^4 + z^3 + z^2, z^6 + z^2)，生成曲線上的點

問 =

$$ d $$G = (40, 19)，也是曲線上的一個點。 k = 13

P =

$$ k $$G = (82, 100) r = x(P) = 82

e = SHA(m) = 19

n = G 的階數 = 29

k^-1 = 9（這是我使用 P(z) 而不是 n 進行模組化時的第一個錯誤）

S = k^-1 (e + d*r) mod n （這是我在使用 P(z) 而不是 n 進行模組化時的第二個錯誤）

S = 9 (19 + 17 * 82) 模 29

S = 15

最後我們得到值 r 和 S 即消息的簽名(r,S)=(82,15)

驗證簽名：

P =

$$ S^-1 * e mod n $$G +$$ (S^-1 * r mod n) $$問 S^1 = 2

P = (2 * 19 mod 29) G + (2 * 82 mod 29) Q

P =

$$ 9 $$G +$$ 19 $$問 P = 9(124, 68) + 19(40, 19)

P = (76, 50) + (98, 104)

P = (82, 100)

x(P) = r

這就是我們檢查簽名是否有效的方式。

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