程序員易懂的 ECDSA 原理簡述

在《比特幣極速入門指南》一書裏，我闡述了公私鑰究竟是什麼：

  • 私鑰的本質： 私鑰的本質是一個數字，這個數字用 16 進製表示的話，長度是 64；轉換爲字節，是 32 字節。
  • 公鑰的本質： 用私鑰生成Secp256k1曲線上的一個點，將 x 與 y 拼接起來，再在開頭加上 <<04>> 後得到一個數字，這個數字就是公鑰。用 16進製表示的話，長度是 130；轉換爲字節，是 65 字節。

地址：

閱讀版—— http://dwz.date/a8dY

互動版 —— https://xue.cn/hub/app/books/3

由於是「入門指南」，所以沒有對 ECDSA 具體的簽名過程進行詳細闡述，只做黑箱處理。但是，對於進階讀者而言，瞭解 ECDSA 簽名的實現邏輯還是有其必要的。

在一般介紹 ECDSA 原理的文章中，普遍使用數學語言。雖然非常嚴謹，但讀起來還是比較費勁。所以，今天我在這裏，通過僞代碼的形式，介紹 ECDSA 的原理，以便大家更好的理解。

首先我們定義這件事兒裏有幾個角色：

  • 私鑰小姐與公鑰先生

    我們稱其爲 priv 與 pub。

  • 要加密的信息 m

    在區塊鏈裏一般 m = 交易，不過理論上只要是個東西就能加密。

  • G 點

    G.x0x79……98

    G.y0x48……B8

    G.order0xFF……41

    具體的數值我們可以從網上搜到，但在這裏我們不用管它，只要知道 G 點有三個參數：x, y, order 就行了！

接着我們定義兩個操作：

  • Point.mult(num, Point)

    點的乘法，參數是一個數字與一個 (x, y) 點，結果是一個點。我們可以把這個操作看做黑箱，而不用去深究這個操作究竟做了些啥。

  • calculate_rem(num1, num2)

    取餘操作

  • hash_and_sth(m)

    我們對信息 m 做一些處理，具體咋處理的不用管，結果就是我們能拿 m 驗證出來出來的內容是否正確，但不能拿處理出來的內容反推 m —— 傳說中的 hash 函數。

我們現在來用僞代碼愉快地生成數字簽名吧！

數字簽名生成過程

  1. gen_k()

我們首先用 gen_k() 函數生成一個取值範圍爲[1, order-1] 的隨機數，稱之爲 k。

  1. Point.mult(k, G)

Point.mult(k, G) = Q_point = (x, y)。

  1. calculate_rem(x, order)

    calculate_rem(x, order) = r，如果 r 爲 0，則回到第一步，重新生成 k。

  2. calculate_s(k, hash_and_sth(m), priv)

    calculate_s(k, hash_and_sth(m), priv) = s，如果 s 爲 0，再次重新生成 k。

  3. v = 27 + calculate_rem(y, 2)

    有了 v，我們驗籤就更快了，不然要遍歷好幾個點去找哪一個點是對的。具體怎麼做的可以暫且不理，有興趣的話看：

    http://www.secg.org/sec1-v2.pdf

  4. r & s & v = signature

    把三個東西連起來，得到數字簽名！

    和比特幣存在差異，比特幣在 ECDSA 簽名後採用了 DER 編碼模式，所以比特幣的簽名長度是不定的，在71 - 73 個字節之前。但是以太坊則使用的標準 ECDSA 流程，所以簽名固定爲 r（35字節）+ s（35字節）+v （1字節）=71字節。

    此處 1 字節爲 8 個二進制位，即 2 個十六進制位，即 0x00 - 0xFF，用十進制表示則是 0 - 255。

    此外，由於簽名中存在隨機數 k，所以對同一信息用同一私鑰，每次簽出來的簽名也是不一樣的！

把上述過程用僞代碼表示，則是：

@spec gen_sig(byte32, string) return byte71
def gen_sig(priv, m) do
	q_point=
   		 gen_k()
    		|> Point.mult(G)
  r = calculate_rem(q_point, G.order)

  s = calculate_s(k, hash_and_sth(m), priv)

  v = 27 + calculate_rem(q_point.y, 2)
  
  return r & s & v
end

數字簽名驗簽過程……嗯，明日再談吧（懶~

在《比特幣極速入門指南》一書裏，我闡述了公私鑰究竟是什麼：

  • 私鑰的本質： 私鑰的本質是一個數字，這個數字用 16 進製表示的話，長度是 64；轉換爲字節，是 32 字節。
  • 公鑰的本質： 用私鑰生成Secp256k1曲線上的一個點，將 x 與 y 拼接起來，再在開頭加上 <<04>> 後得到一個數字，這個數字就是公鑰。用 16進製表示的話，長度是 130；轉換爲字節，是 65 字節。

地址：

閱讀版—— http://dwz.date/a8dY

互動版 —— https://xue.cn/hub/app/books/3

由於是「入門指南」，所以沒有對 ECDSA 具體的簽名過程進行詳細闡述，只做黑箱處理。但是，對於進階讀者而言，瞭解 ECDSA 簽名的實現邏輯還是有其必要的。

在一般介紹 ECDSA 原理的文章中，普遍使用數學語言。雖然非常嚴謹，但讀起來還是比較費勁。所以，今天我在這裏，通過僞代碼的形式，介紹 ECDSA 的原理，以便大家更好的理解。

首先我們定義這件事兒裏有幾個角色：

  • 私鑰小姐與公鑰先生

    我們稱其爲 priv 與 pub。

  • 要加密的信息 m

    在區塊鏈裏一般 m = 交易，不過理論上只要是個東西就能加密。

  • G 點

    G.x0x79……98

    G.y0x48……B8

    G.order0xFF……41

    具體的數值我們可以從網上搜到，但在這裏我們不用管它，只要知道 G 點有三個參數：x, y, order 就行了！

接着我們定義兩個操作：

  • Point.mult(num, Point)

    點的乘法，參數是一個數字與一個 (x, y) 點，結果是一個點。我們可以把這個操作看做黑箱，而不用去深究這個操作究竟做了些啥。

  • calculate_rem(num1, num2)

    取餘操作

  • hash_and_sth(m)

    我們對信息 m 做一些處理，具體咋處理的不用管，結果就是我們能拿 m 驗證出來出來的內容是否正確，但不能拿處理出來的內容反推 m —— 傳說中的 hash 函數。

我們現在來用僞代碼愉快地生成數字簽名吧！

數字簽名生成過程

  1. gen_k()

我們首先用 gen_k() 函數生成一個取值範圍爲[1, order-1] 的隨機數，稱之爲 k。

  1. Point.mult(k, G)

Point.mult(k, G) = Q_point = (x, y)。

  1. calculate_rem(x, order)

    calculate_rem(x, order) = r，如果 r 爲 0，則回到第一步，重新生成 k。

  2. calculate_s(k, hash_and_sth(m), priv)

    calculate_s(k, hash_and_sth(m), priv) = s，如果 s 爲 0，再次重新生成 k。

  3. v = 27 + calculate_rem(y, 2)

    有了 v，我們驗籤就更快了，不然要遍歷好幾個點去找哪一個點是對的。具體怎麼做的可以暫且不理，有興趣的話看：

    http://www.secg.org/sec1-v2.pdf

  4. r & s & v = signature

    把三個東西連起來，得到數字簽名！

    和比特幣存在差異，比特幣在 ECDSA 簽名後採用了 DER 編碼模式，所以比特幣的簽名長度是不定的，在71 - 73 個字節之前。但是以太坊則使用的標準 ECDSA 流程，所以簽名固定爲 r（35字節）+ s（35字節）+v （1字節）=71字節。

    此處 1 字節爲 8 個二進制位，即 2 個十六進制位，即 0x00 - 0xFF，用十進制表示則是 0 - 255。

    此外，由於簽名中存在隨機數 k，所以對同一信息用同一私鑰，每次簽出來的簽名也是不一樣的！

把上述過程用僞代碼表示，則是：

@spec gen_sig(byte32, string) return byte71
def gen_sig(priv, m) do
    q_point=
         gen_k()
            |> Point.mult(G)
  r = calculate_rem(q_point, G.order)

  s = calculate_s(k, hash_and_sth(m), priv)

  v = 27 + calculate_rem(q_point.y, 2)

  return r & s & v
end

數字簽名驗簽過程……嗯，明日再談吧（懶~

本文參與登鏈社區寫作激勵計劃 ，好文好收益，歡迎正在閱讀的你也加入。

  • 發表於 28分鐘前
  • 閱讀 ( 9 )
  • 學分 ( 5 )
  • 分類：FISCO BCOS
相關文章