密碼學系列 - 橢圓曲線 ECDSA - 簽名與驗簽

數字簽名的生成

假設Alice要給Bob發一個經過數字簽名的消息，他們首先需要定義一組共同接受的橢圓曲線加密用參數，簡單的，這組參數可表示為

(CURVE, G, n)

其中，CURVE表示橢圓曲線點域和幾何方程；G是所有點倍積運算的基點；n是該橢圓曲線的可倍積階數(multiplicative order)，作為一個很大的質數，n的幾何意義在于，nG = 0，即點倍積nG的結果不存在，而對于小于n的任何一個正整數 m = [1，n-1]，點倍積mG都可以得到一個合理的處于該橢圓曲線上的點。

其次，Alice要建立一對鑰，即一個私鑰和一個公鑰。私鑰來自于[1, n-1]範圍内一個随機數： d A = r a n d ( 1 , n − 1 ) d_A = rand(1, n-1) dA​=rand(1,n−1)

公鑰如下，它來自私鑰和基點的橢圓曲線點倍積： Q A = d A × G Q_A = d_A \times G QA​=dA​×G

Alice想要對消息m作數字簽名，有以下步驟:

1. 計算

   e = HASH(m)

   ，HASH是一個哈希加密函數，比如SHA-2，或SHA-3。
2. 計算

   z

   ，來自e的二進制形式下最左邊（即最高位）L_n個bits，而L_n是上述橢圓曲線參數中的可倍積階數n的二進制長度。注意z 可能大于n，但長度絕對不會比 n 更長。
3. 從 [1, n-1] 内，随機選擇一個符合加密學随機安全性的整數

   k

   。
4. 計算一個橢圓曲線上點： ( x 1 , y 1 ) = k × G (x_1, y_1) = k \times G (x1​,y1​)=k×G
5. 以下式計算 r 值， 如果r == 0, 則傳回步驟3重新計算 r = x 1   m o d   n r = x_1 \bmod n r=x1​modn
6. 以下式計算 s 值，如果 s == 0，則傳回步驟3重新計算 s = k − 1 ( z + r d A )   m o d   n s=k^{-1}(z+rd_A) \bmod n s=k−1(z+rdA​)modn
7. 生成的數字簽名就是

   (r, s)

Alice 用自己的私鑰和随機數 k 簽名了哈希值 z。Bob 用 Alice 的公鑰來驗證簽名的正确性

特别需要注意的是步驟3中

k

的選擇，它不僅要滿足加密學的随機安全性要求，

要像私鑰一樣保護起來

，更重要的是，在每次生成一個新的數字簽名時，這個 k 必須

每次都要更新

。否則，通過上述數字簽名過程中的算式互相換算，很容易從中破譯出私鑰！具體換算過程可見wiki_ECDSA。

ECDSA簽名可能洩漏私鑰的另一種方式是

k是由錯誤的随機數發生器産生的

。這樣的随機數生成失敗導緻Android比特币錢包的使用者在2013年8月損失了資金

數字簽名的驗證

對于消息的接收方Bob來說，他除了收到數字簽名檔案外，還會有一份公鑰。是以Bob的驗證分兩部分，首先驗證公鑰，然後驗證簽名檔案(r, s)。

公鑰的驗證

1. 公鑰 Q A Q_A QA​的坐标應是有效的，不會等于一個極限值空點 O O O
2. 通過公鑰 Q A Q_A QA​的坐标驗證它必須是處于該橢圓曲線上的點。
3. 應有下式成立，即曲線的可倍積階數 n 與公鑰的點倍積不存在 n × Q A = O n \times Q_A = O n×QA​=O

簽名檔案的驗證

1. 驗證 r 和 s 均是處于[1, n-1]範圍内的整型數；否則驗證失敗
2. 計算

   e = HASH(m)

   ，HASH()即簽名生成過程步驟1中使用的哈希函數。
3. 計算

   z

   ，來自 e的最左邊L_n個bits
4. 計算兩個參數 u 1 u_1 u1​ 和 u 2 u_2 u2​： u 1 = z s − 1   m o d   n u_1 = zs^{-1} \bmod n u1​=zs−1modn u 2 = r s − 1   m o d   n u_2 = rs^{-1} \bmod n u2​=rs−1modn

1. 計算 ( x 1 , y 1 ) (x_1, y_1) (x1​,y1​)，如果 ( x 1 , y 1 ) (x_1, y_1) (x1​,y1​)不是一個橢圓曲線上的點，則驗證失敗： ( x 1 , y 1 ) = u 1 × G + u 2 × Q A (x_1, y_1) = u_1 \times G + u_2 \times Q_A (x1​,y1​)=u1​×G+u2​×QA​
2. 如果下面等式成立, 則簽名有效 r ≡ x 1 ( m o d n ) r \equiv x_1 \pmod n r≡x1​(modn)

公鑰恢複

收到消息

m

和愛麗絲的簽名

r，s

，在該消息上，Bob可以（可能）恢複Alice的公鑰：

1. 驗證

   r

   和

   s

   是整數

   [1，n-1]

   。如果不是，則簽名無效。

2. 計算曲線點 R = ( x 1 , y 1 ) R=(x_1, y_1) R=(x1​,y1​) , x 1 x_1 x1​是r, r+n, r+2n等其中之一（提供的 x 1 x_1 x1​對于字段元素來說不是太大), y 1 y_1 y1​是滿足曲線方程式的值。

   請注意，可能有幾個滿足這些條件的曲線點，每個曲線點都不同

   R

   值将産生一個不同的已恢複密鑰。
3. 計算

   e = HASH(m)

   ，HASH()即簽名生成過程步驟1中使用的哈希函數。
4. 計算

   z

   ，來自 e的最左邊L_n個bits
5. 計算兩個參數 u 1 u_1 u1​ 和 u 2 u_2 u2​： u 1 = − z r − 1   m o d   n u_1 = -zr^{-1} \bmod n u1​=−zr−1modn u 2 = s r − 1   m o d   n u_2 = sr^{-1} \bmod n u2​=sr−1modn

1. 計算曲線點 Q A = ( x A , y A ) = u 1 × G + u 2 × R Q_A = (x_A, y_A) = u_1 \times G + u_2 \times R QA​=(xA​,yA​)=u1​×G+u2​×R
2. 如果 Q A Q_A QA​比對Alice的公鑰, 則簽名有效
3. 如果嘗試了所有可能的R點且沒有比對Alice的公鑰，則簽名無效。

請注意，無效的簽名或來自其他消息的簽名将導緻恢複不正确的公鑰。如果事先知道簽名者的公鑰（或其哈希），則恢複算法隻能用于檢查簽名的有效性。

公式推導請參考: wiki_ECDSA

公鍊簽名與驗簽算法

摘要生成	簽名算法	簽名資料格式	驗簽算法
BTC	SHA256	ECDSA-secp256k1	BIP66之後采用DER編碼. 0x30 [total-length] 0x02 [R-length] [R] 0x02 [S-length] [S]	verify模式 OP_CHECKSIG ECDSA_CheckSignature (pubKeyStr,sigStr, sha256(sha256(verifyThisStr)))
ETH	SHA3-Keccack	ECDSA-secp256k1	(R,S,V) V是recid, 為0或者1, v := sig[0] - 27	recove模式 pub, err := crypto.Ecrecover(sighash[:], sig)
EOS	SHA256	ECDSA-secp256k1|r1	(V,R,S) V中帶了recid v: 27 + 4 + recid , 從簽名中提取出recove id: V - 4 - 27	recove模式 recov = public_key_type( sig, digest )

公鍊 ECDSA 驗簽方式

用公鑰去verify的方式:

1. BTC :

   ECDSA_CheckSignature(pubKeyStr,sigStr,sha256(sha256(verifyThisStr)))

   (參考資料: https://en.bitcoin.it/wiki/File:Bitcoin_OpCheckSig_InDetail.png )

2. Hyperledger Fabric

   valid, err := id.msp.bccsp.Verify([id.pk](http://id.pk/), sig, digest, nil)

   (參考資料: https://blog.csdn.net/idsuf698987/article/details/81677133 )

recove出公鑰的方式:

1. ETH

   pub, err := crypto.Ecrecover(sighash[:], sig) //摘自源碼

2. EOS

   recov = public_key_type( sig, digest ) //摘自源碼

參考: Elliptic Curve Cryptography: ECDH and ECDSA

往期精彩回顧:

區塊鍊知識系列

密碼學系列

共識系列

公鍊調研系列

以太坊系列

EOS系列

智能合約系列

Token系列