計算sss在 ECDSA 中高飛_(2米)GF(2米)GF(2^m)

我正在實施 ECDSA $ GF(2^n) $ . 我遵循RFC 6979並將我的結果與附錄 A 中的範例（使用曲線SECT163K1）進行比較。

我的計算 $ r $ 是正確的，但我正在努力 $ s $ . 幾個參數決定 $ s $ 我不確定哪個是對的，哪個是錯的。

$ s=k^{-1} * (m + r * d_A) \mod q $

$ q $ 是曲線生成器的階數（在其他來源中稱為 $ n $ ). $ r $ 是正確的/被給予並且 $ d_A $ 被給予，留下 $ k^{-1} $ 和 $ m $ .

米

消息的散列是h1 = AF2B DBE1 AA9B 6EC1 E2AD E1D6 94F4 1FC7 1A83 1D02 68E9 8915 6211 3D8A 62AD D1BF，縮寫為bits2int(h1, 163)。我認為它是正確的。

m = 5795 edf0 d54d b760f 156f 0eb4 a7a0 fe38 d418 e813

$ k^{-1} $

的價值 $ k $ 在範例中給出了2 3AF4 074C 90A0 2B3F E61D 286D 5C87 F425 E6BD D81B. 我計算了 $ k^{2^{162}-2} \mod q $ 要得到。我檢查了它 $ k^{-1}*k = 1 $ . 該算法也適用於其他曲線和 $ k $ 的。我還對照 Python 包BitVector檢查了結果，該包還實現了模組化反轉 $ GF(2^n) $ .

k^-1 = 3 759d 2532 cdd0 d539 5f03 eaed b650 3045 d218 9bad

我在“二進制”中實現了所有操作（即加法為異或，模為多項式除法，…）。

其他中間結果：

$ r * d_A $ :14d1 14fe1 04b4 a34f 3bf6 fd30 02aa f767 3ed8 c786

$ m + r * d_A $ :4 344f 90ec 506f d540 2e99 f384 a50a 095f eac0 2f95

$ s $ :b957 16f7 2680 def2 d19f d596 6a2e 93fe 8c0c fea9

問題

出了什麼問題，錯誤在哪裡？

我也可以發布我的（Python）程式碼，但我必須先清理它。

由於您正在計算標量乘法值，並且基點具有順序 $ q $ , 你應該計算 $ s $ 在該領域 $ \mathbb{Z}/q\mathbb{Z} $ ，不在 $ GF(2^m) $ . 特別是，這意味著你不能使用異或或多項式除法來實現加法和模約簡，而應該使用正則加法和​​除法。

例如，這應該給你的價值 $ k^{-1} $ 作為：

$$ k^{-1} \equiv 2315871241563531210130617073628712209517930583176 \pmod q $$ 這是1 95A7 4210 396D 0D19 E522 8C83 6815 E728 EFD7 9488十六進製表示法。

自從 $ q $ 是素數，階數 $ \mathbb{Z}/q\mathbb{Z} $ 是 $ q-1 $ , 所以你可以很容易地計算出 $ k $ ，然後計算 $ s $ . 這給出了正確的輸出：

>>> q = int('4000000000000000000020108A2E0CC0D99F8A5EF', 16)
>>> x = int('09A4D6792295A7F730FC3F2B49CBC0F62E862272F', 16)
>>> k = int('23AF4074C90A02B3FE61D286D5C87F425E6BDD81B', 16)
>>> m = int('5795edf0d54db760f156f0eb4a7a0fe38d418e813', 16)
>>> r = int('113A63990598A3828C407C0F4D2438D990DF99A7F', 16)
>>> k_inverse = pow(k, q-2, q)
>>> s = (k_inverse * (m + r * x)) % q
>>> '%X' % s
'1313A2E03F5412DDB296A22E2C455335545672D9F'

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