原文：

Elliptic Curve Cryptography: ECDH and ECDSA?

andrea.corbellini.name圖標

本文是系列文章 ECC: a gentle introduction的第三篇。本文將會介紹兩種具體的ECC演算法：ECDH和ECDSA

領域參數（Domain parameters）

為了讓我們的橢圓曲線演算法能夠真正的運行起來，首先我們需要一個定義在有限域中的橢圓曲線的循環子羣，需要的參數如下：

  • 一個質數 p 用於描述有限域的大小
  • 橢圓曲線方程的參數 a 和 b
  • 一個用於生成循環子羣的基點 G
  • 子羣的階數 n
  • 子羣的協因子 h （ h=N/n ，其中 N 是橢圓曲線羣的階數）

這六個參數 (p,a,b,G,n,h) 聯合起來定義了一種ECC演算法所用到的橢圓曲線。

隨機曲線（Random curves）

離散對數問題是「困難」的，這一陳述並不總是正確。事實上一些特定參數的橢圓曲線上的離散對數問題是很「容易」的，這使得一些帶有特殊目的的演算法可以有效地解決這些離散對數問題。舉例來說，所有滿足 p=hn （這意味著有限域的階數和橢圓曲線羣的階數相等）的橢圓曲線都是不安全的，存在一種演算法可以在多項式時間內解開這類橢圓曲線上的離散對數問題。

現在假設提供我提供了一組橢圓曲線的領域參數，那麼這就存在一種可能：我私下裡發現了一類新的安全性較差的曲線，這類曲線從未被公開過，我還自己實現了一種針對這類曲線的離散對數問題的快速解法。那麼我該如何讓其他人相信，我不是有意地構造出這條曲線呢？我該如何向你保證，我給出的這條曲線是安全的呢？

為瞭解決上述問題，我們需要一個額外的參數 S ，我們稱之為隨機種子。這是一個隨機的數字，用於生成參數 a,b 或者基點 G 。這些參數都是由 S 的哈希值生成的，我們知道，哈希函數的計算很簡單，但是我們很難通過哈希值反推出函數輸入。

如何從S生成隨機曲線：S的哈希值用於計算曲線的不同參數。
如果我們想作弊，並試圖從特定的參數中構造一個S，我們必須解決一個「難題」：逆哈希

一條通過隨機種子生成的橢圓曲線被認為是可驗證隨機的。這種基於哈希函數來生成參數的原則通常稱之為"nothing up my sleeve"，這在密碼學中是十分常用的方法。

這個技巧可以為橢圓曲線的安全性給與一定的保證，至少這條曲線不是有人特意構造出來，然後在其中隱藏了什麼不為人知的漏洞。事實上，如果我提供了一個隨機種子和對應的參數，這意味著我不能隨意地選擇參數 a,b ，那麼其他人就應該比較確定這條曲線不能被我用於」特殊目的「的攻擊。在下一篇文章中，作者將介紹為什麼這裡要說是」比較確定「，而不是完全保證。

ANSI X9.62中描述了一種用於生成和檢查隨機曲線的標準化演算法，該演算法基於SHA-1。如果你還想了解得更多，你可以看一下這個演算法（請在文檔中查找"Verifiably Random Curves and Base Point Generators"這一節）

作者寫了一個Python腳本用來檢驗OpenSSL當前附帶的所有隨機曲線。讀者可以自己運行一下。

橢圓曲線密碼學（Elliptic Curve Cryptography）

用了這麼多篇幅，現在終於要到我們的正題了，我們開始正式介紹ECC演算法的細節：

  1. 從 {1, dots, n - 1} 中隨機選擇一個整數 d 作為私鑰（ n 是循環子羣的階數）
  2. 計算公鑰 H=dG （ G 是循環子羣的基點）我們注意到，如果我們已知 d （和橢圓曲線的領域參數），計算 H （標量乘）是很容易的。但是在已知 H=dG 的情況下，計算 d 是「困難」的，因為這要求我們解一個離散對數問題。

現在我們來介紹兩種基於此的公鑰演算法：ECDH（Elliptic curve Diffie-Hellman，一種加密演算法）和ECDSA（Elliptic Curve Digital Signature Algorithm，一種簽名演算法）。

ECDH加密（Encryption with ECDH）

ECDH是DH演算法的一個變體。本質上它是一個密鑰協商協議，而不是一個加密演算法。換句話說，對於通信的雙方，ECDH定義了密鑰生成和交換的規則，至於怎麼用密鑰對數據進行加密，取決於其他的演算法。

譯者註：實際上ECDH值完成了數據加密的第一步，生成一個用於加密的密鑰，這一步是用橢圓曲線完成的，後續利於密鑰加密的演算法實際上是由其他現有的對稱加密演算法完成的。

演算法試圖解決如下問題：

通信的雙方（例如Alice和Bob）希望安全地交換信息，使得第三方（中間人）即使可以截取通信的報文，但是無法解碼得到原文。

演算法的流程如下：

  1. 首先，Alice和Bob生成自己的公鑰和私鑰。我們記Alice的私鑰為 d_A ，公鑰為 H_A=d_A G 。Bob的私鑰為 d_B ，私鑰為 H_B=d_B G 。這裡Alice和Bob用的是同一條橢圓曲線的領域參數。
  2. Alice和Bob通過一個不安全的信道交換公鑰。中間人將會截取到 H_A,H_B ，但是他無法得到 d_A,d_B ，除非他可以求解這條橢圓曲線上的離散對數問題。
  3. Alice計算 S=d_AH_B ，Bob計算 S=d_BH_A 。注意這兩個人計算出來的 S 是一樣的，事實上，我們有： S = d_A H_B = d_A (d_B G) = d_B (d_A G) = d_B H_A

中間人只知道 H_A,H_B （可能他還知道這條橢圓曲線的領域參數），但是他幾乎不可能知道Alice和Bob之間共享的祕密 S 。這被稱為Diffie-Hellman問題，可以表述如下:

已知三個點 P 、 aP 和 bP ， abP 的結果是什麼？

或者等價地：

給定三個整數 k 、 k^x 和 k^y ， k^{xy} 的結果是什麼？

(後一種表述用於原本的DH演算法，基於模運算)

Diffie-Hellman密鑰交換: Alice和Bob可以「輕鬆」計算共享祕密，而中間人必須解決一個「難題」（Diffie-Hellman問題）。

這裡有一段視頻解釋了DH演算法的原理（基於模運算的）

既然Alice和Bob已經得到了一個共享的密鑰 S ，他們就可以用對稱加密演算法來進行數據加密和通信了。

例如，他們可以使用 S 的 x 坐標作為密鑰，使用AES或3DES等加密演算法來加密消息。這與TLS所做的或多或少有點相似，不同之處在於TLS將 x 坐標與其他與通信連接相關的信息結合起來，然後計算得到的位元組串的哈希值。

譯者註：事實上，橢圓曲線在ECDH中解決了對稱加密時，密鑰可能會泄露的問題。ECDH的解決方式是：不通過信道直接傳輸對稱密鑰，而是傳輸橢圓曲線生成的公鑰，然後通過收到的公鑰再結合自己的私鑰各自計算共享的密鑰，橢圓曲線保證了雙方計算出的密鑰一定是相同的，並且第三方在不知道通信雙方私鑰的前提下，無法通過從信道中截取到的信息反推出共享密鑰。

ECDH實踐（Playing with ECDH）

作者提供了一個Python腳本用來生成一條特定橢圓曲線的公私鑰和共享密鑰。這個腳本中使用的橢圓曲線是標準的（能夠支撐實際的加密演算法），而不是那種簡單的曲線。這條曲線被稱為secp256k1，取自SECG（Standards for Efficient Cryptography Group）。這條曲線也是比特幣用來做數字簽名的橢圓曲線。具體的參數如下：

  • p = 0xffffffff ffffffff ffffffff ffffffff ffffffff ffffffff fffffffe fffffc2f
  • a =0
  • b = 7
  • x_G = 0x79be667e f9dcbbac 55a06295 ce870b07 029bfcdb 2dce28d9 59f2815b 16f81798
  • y_G = 0x483ada77 26a3c465 5da4fbfc 0e1108a8 fd17b448 a6855419 9c47d08f fb10d4b8
  • n = 0xffffffff ffffffff ffffffff fffffffe baaedce6 af48a03b bfd25e8c d0364141
  • h = 1

(這些參數摘自 OpenSSL source code.)

當然，你也可以修改這個腳本來使用其他參數的曲線，只要保證曲線定義在一個質數階的有限域內，並且符合Weierstrass範式即可。

這個腳本非常的簡單，它實現了一些我們之前提到的演算法：點加法、標量乘法、ECDH。演算法產生的輸出如下：

Curve: secp256k1
Alices private key: 0xe32868331fa8ef0138de0de85478346aec5e3912b6029ae71691c384237a3eeb
Alices public key: (0x86b1aa5120f079594348c67647679e7ac4c365b2c01330db782b0ba611c1d677, 0x5f4376a23eed633657a90f385ba21068ed7e29859a7fab09e953cc5b3e89beba)
Bobs private key: 0xcef147652aa90162e1fff9cf07f2605ea05529ca215a04350a98ecc24aa34342
Bobs public key: (0x4034127647bb7fdab7f1526c7d10be8b28174e2bba35b06ffd8a26fc2c20134a, 0x9e773199edc1ea792b150270ea3317689286c9fe239dd5b9c5cfd9e81b4b632)
Shared secret: (0x3e2ffbc3aa8a2836c1689e55cd169ba638b58a3a18803fcf7de153525b28c3cd, 0x43ca148c92af58ebdb525542488a4fe6397809200fe8c61b41a105449507083)

Ephemeral ECDH

有的讀者可能聽說過ECDHE，ECDHE中的E（Ephemeral）代表演算法的密鑰交換過程是臨時的，而不是靜態的。

ECDHE在TLS協議中被使用，當建立連接的時候，客戶端和服務端都會動態的生成各自的公鑰-私鑰對。公鑰隨後用TLS證書籤名(用於認證)，並在雙方之間交換。

ECDSA簽名（Signing with ECDSA）

想像如下的場景：Alice想用她的私鑰( d_A )對一條消息進行簽名，Bob想用Alice的公鑰( H_A )驗證簽名。除了Alice，沒有人能生成有效的簽名，每個擁有Alice公鑰的人都應該能夠驗證這個簽名的有效性。

同樣的，Alice和Bob使用的是同一條橢圓曲線。我們接下來要介紹的演算法是ECDSA，它是數字簽名演算法(DSA)使用橢圓曲線作為離散對數問題的一個變體。

ESCDA處理的實際上是消息的哈希值，而不是消息本身。哈希函數是可選擇的，但這個哈希函數必須是一個密碼學安全的哈希函數。消息的哈希值需要截取一個固定的長度 L_n ，這個長度是 n （子羣的階）的二進位位數。截取後的哈希值是一個整數，我們記為 z 。

Alice對消息簽名的演算法執行流程如下：

  1. 在 {1, dots, n - 1} 隨機選擇一個整數 k （ n 是子羣的階）
  2. 計算點 P=kG (其中 G 是子羣的基點)
  3. 計算 r = x_P mod{n} （其中 x_P 是 P 點的橫坐標）
  4. 如果 r=0 ，就重新選擇一個 k 然後再嘗試一次同樣的流程
  5. 計算 s = k^{-1} (z + rd_A) mod{n} （其中 d_A 是Alice的私鑰， k^{-1} 是 k 在模n下的乘法逆元）
  6. 如果 s=0 ，就重新選擇一個 k 然後再嘗試一次同樣的流程

二元組 (r,s) 就是消息的簽名。

簡單地說，這個演算法首先生成一個祕密的整數k 。這個祕密隨後被隱藏在 r 中，這要歸功於標量乘法(我們知道，標量乘法計算很「容易」，但是從結果反推卻很「困難」)。隨後， r 通過s = k^{-1} (z + rd_A) mod{n}和消息的哈希值綁定在一起。

注意，為了計算 s ，我們要先計算 k 的乘法逆元k^{-1} 。我們已經在前一篇文章中說過，只有當 n 是質數時，我們才能定義一個有限域，從而計算 k 的乘法逆元。如果子羣的階 n 不是質數，那麼ECDSA的數學基礎就是不成立的。幾乎所有標準曲線都有質數階，而那些非質數階的曲線不適合ECDSA，這並非一個偶然。

驗證簽名（Verifying signatures）

為了驗證簽名，我們需要的參數有：Alice的公鑰 H_A ，截取後的哈希值 z ，簽名 (r,s) ，驗證的流程如下：

  1. 計算整數 u_1 = s^{-1} z mod{n}
  2. 計算整數 u_2 = s^{-1} r mod{n}
  3. 計算點 P = u_1 G + u_2 H_A

只有當 r = x_P mod{n} 時，簽名纔有效

演算法的正確性（Correctness of the algorithm）

乍一看，ECDSA演算法背後的邏輯可能並不明顯，但是如果我們把所有等式放在一起看，就會發現一些清晰的脈絡。

讓我們從 P = u_1 G + u_2 H_A 開始。從公鑰的定義中，我們知道 H_A = d_A G (其中 d_A 是私鑰)。我們可以寫:

egin{array}{rl} P & = u_1 G + u_2 H_A \ & = u_1 G + u_2 d_A G \ & = (u_1 + u_2 d_A) G end{array}

譯者註：上面的等式變換中提取了公因子，讀者若是想了解為什麼這樣做是成立的，可以參考第二篇文章中標量乘法的定義。

代入 u_1,u_2 的定義，我們有：

egin{array}{rl} P & = (u_1 + u_2 d_A) G \ & = (s^{-1} z + s^{-1} r d_A) G \ & = s^{-1} (z + r d_A) G end{array}

譯者註：這裡的提取公因子之所以成立，原因和上一個是不同的。這裡是因為上式除了點 G 以外的參數都是定義在 mathbb{F}_n （模質數n的有限域）上的，有限域首先是一個環，因此滿足分配律

這裡為了簡潔起見，我們省略了「 ext{mod} n 」，因為基點G 生成的循環子羣具有階 n ，因此「 ext{mod} n」是多餘的。

我們回到之前的定義 s = k^{-1} (z + rd_A) mod{n} 。在等式兩邊同乘以 kcdot s^{-1} ，得到 k = s^{-1} (z + rd_A) mod{n} ，將這個結果代入我們的 P 方程，我們得到：

egin{array}{rl} P & = s^{-1} (z + r d_A) G \ & = k G end{array}

這與我們在簽名生成演算法的步驟2中得到的等式相同！在生成簽名和驗證簽名時，我們用不同的方程組可以計算得到相同的點 P 。這就證明ECDSA的正確性。

ECDSA實踐（Playing with ECDSA）

作者提供了Python腳本可以實現簽名的生成和驗證。腳本的輸出如下：

Curve: secp256k1
Private key: 0x9f4c9eb899bd86e0e83ecca659602a15b2edb648e2ae4ee4a256b17bb29a1a1e
Public key: (0xabd9791437093d377ca25ea974ddc099eafa3d97c7250d2ea32af6a1556f92a, 0x3fe60f6150b6d87ae8d64b78199b13f26977407c801f233288c97ddc4acca326)

Message: bHello!
Signature: (0xddcb8b5abfe46902f2ac54ab9cd5cf205e359c03fdf66ead1130826f79d45478, 0x551a5b2cd8465db43254df998ba577cb28e1ee73c5530430395e4fba96610151)
Verification: signature matches

Message: bHi there!
Verification: invalid signature

Message: bHello!
Public key: (0xc40572bb38dec72b82b3efb1efc8552588b8774149a32e546fb703021cf3b78a, 0x8c6e5c5a9c1ea4cad778072fe955ed1c6a2a92f516f02cab57e0ba7d0765f8bb)
Verification: invalid signature

該腳本首先簽名一條消息(位元組字元串「Hello！」)，然後驗證簽名。之後，它試圖對照另一條消息(「Hi there!」)驗證相同的簽名並且驗證失敗。最後，它試圖根據正確的消息驗證簽名，但是使用另一個隨機公鑰，驗證再次失敗。

k 的重要性（The importance of k）

當生成ECDSA簽名時，需要保證 k 是保密且唯一的。 k 值重複（弱偽隨機）可能導致私鑰泄露。

這是索尼公司幾年前犯的錯誤。PlayStation 3主機只能運行索尼使用ECDSA簽名的遊戲。如果我想為PlayStation 3創建一款新遊戲，沒有索尼的簽名，我就無法將它分發給公眾。問題是:索尼生成的所有簽名都是使用靜態的 k 生成的。

在這種情況下，我們可以很容易地反推出索尼的私鑰 d_S ，只需購買兩個簽好名的遊戲，提取它們的哈希值( z_1,z_2 )和它們的簽名 (r_1, s_1) 和 (r_2, s_2) 以及橢圓曲線的領域參數。

  • 首先我們注意到 r_1=r_2 ，因為 r 由 k 唯一確定，而 k 是固定的。
  • 然後我們有 (s_1 - s_2) mod{n} = k^{-1} (z_1 - z_2) mod{n}
  • 在等式兩邊同乘以 k ，得到 k (s_1 - s_2) mod{n} = (z_1 - z_2) mod{n}
  • 兩邊同乘以 (s_1-s_2)^{-1} ，得到 k = (z_1 - z_2)(s_1 - s_2)^{-1} mod{n}

最後一個等式讓我們可以只使用兩個哈希值及其對應的簽名來計算 k 。現在，我們可以使用 s 的等式來提取私鑰:

s = k^{-1}(z + rd_S) mod{n} Rightarrow d_S = r^{-1} (sk - z) mod{n}

如果 k 不是靜態的，但在某種程度上是可預測的，那麼我們也可以用類似的方法計算出私鑰。

k值必須是保密且唯一的，並不一定必須隨機！以太坊k值的生成參考RFC6979實現。

譯者註：我們可以將RFC6979的簡化版理解為：k = SHA256(d + HASH(m))

其中，d是私鑰，m是消息，我們一般會對消息的HASH進行簽名，因此這裡是HASH(m)。因為參數裏有私鑰d，就保證了「保密」，再加上消息m，保證了「唯一」，這也是「確定性」的演算法，只要SHA256是安全的，此演算法就是安全的，很完美。

下篇文章是本系列的第四篇也是最後一篇文章。文章將會涉及離散對數問題的解法，橢圓曲線密碼的一些重要問題，以及ECC與RSA的比較。

推薦閱讀：

相關文章