回想第 11 章：在古典 Diffie–Hellman 中，雙方藉由交換非秘密值來建立共享秘密。

橢圓曲線版本的 DH 與古典 DH 完全相同，只是記法不同：

古典 DHECDH
固定參數數 g點 G
Alice 私鑰隨機數 a隨機數 dA
Alice 公鑰A = g^aPA = dA·G
Bob 私鑰隨機數 b隨機數 dB
Bob 公鑰B = g^bPB = dB·G
共享秘密A^b = B^a = g^abdA·PB = dB·PA = dA·dB·G

這個方法稱為 ECDH（elliptic curve Diffie–Hellman）。

因此依賴 DLP 的 DH 協定都能被改編成在橢圓曲線上運作、以 ECDLP 為困難性假設。例如鑑別式 DH 與 MQV 在搭配橢圓曲線時同樣安全。（事實上，MQV 最初就是定義在橢圓曲線上的。）

用橢圓曲線簽章：ECDSA#

用 ECC 簽章的標準演算法是 ECDSA（elliptic curve digital signature algorithm）。它在許多應用中取代了 RSA 簽章與古典 DSA 簽章——例如它是比特幣唯一使用的簽章演算法，也被許多 TLS 與 SSH 實作支援。

前提：簽署者持有數 d 作為私鑰，驗證者持有公鑰 P = dG。雙方事先都知道要用哪條橢圓曲線、它的階 n（曲線上的點數），以及基點 G 的座標。

簽章產生#

  1. 用 SHA-256 或 BLAKE2 這類密碼學雜湊函式雜湊訊息，產生雜湊值 h，解讀為 0 到 n − 1 之間的數。
  2. 挑一個 1 到 n − 1 之間的隨機數 k，計算點 kG，其座標為 (x, y)。
  3. 設 r = x mod n。
  4. 計算 s = (h + rd) / k mod n。
  5. 簽章就是 (r, s)。

簽章長度取決於所用的座標長度。例如在座標為 256 位元數的曲線上，r 與 s 各為 256 位元，產生 512 位元的簽章。

簽章驗證#

給定簽章 (r, s) 與訊息雜湊 h：

  1. 計算 w = 1/s（s 的反元素），它等於 k / (h + rd) mod n。
  2. 計算 u = w·h = hk / (h + rd)。
  3. 計算 v = w·r = rk / (h + rd)。
  4. 計算點 Q = uG + vP，其中 P 是簽署者的公鑰。
  5. 只有在 Q 的 x 座標等於簽章中的 r 時才接受該簽章。
延伸：為什麼驗證會成功

最後一步把公鑰 P 代換成它的實際值 dG：

Q = uG + vdG = (u + vd)G

把 u 與 v 換成它們的實際值：

u + vd = hk/(h + rd) + drk/(h + rd)
       = (hk + drk)/(h + rd)
       = k(h + dr)/(h + rd)
       = k

這告訴我們 (u + vd) 等於簽章產生時所選的 k，因此 uG + vdG 等於點 kG。

換句話說：驗證演算法成功算出了簽章產生時所算的同一個點 kG。 驗證者確認 kG 的 x 座標等於收到的 r 就完成驗證；否則簽章被判為無效。

ECDSA vs. RSA 簽章#

橢圓曲線密碼學常被視為 RSA 在公鑰密碼學上的替代品，但 ECC 與 RSA 其實沒什麼共通點：

  • RSA 只用於加密與簽章。
  • ECC 是一族演算法，可以用來加密、產生簽章、執行金鑰協商，並提供進階功能（如基於身分的加密——一種使用從個人識別碼〔例如電子郵件地址〕導出加密金鑰的加密）。

速度比較#

RSA 簽章中，簽署者用私鑰 d 算出 y = x^d mod n，驗證則用公鑰 e 確認 y^e mod n = x——流程明顯比 ECDSA 簡單。

但 ECC 相對 RSA 有兩大優勢：

  • 更短的簽章：ECC 處理較短的數，產生的簽章只有數百位元而非數千位元——若你得儲存或傳輸大量簽章，這是明顯的好處。
  • 更快的簽章速度：ECDSA 簽章遠快於 RSA 簽章（驗證則差不多快），因為在相近的安全等級下，ECDSA 處理的數字比 RSA 小得多。

實測：

$ openssl speed ecdsap256 rsa4096
                              sign     verify     sign/s     verify/s
rsa 4096 bits            0.007267s  0.000116s      137.6       8648.0
256 bit ecdsa (nistp256)   0.0000s    0.0001s    21074.6       9675.7

拿這兩種不同大小的簽章比較是公平的，因為它們提供相近的安全等級。然而實務上許多系統使用 2048 位元的 RSA 簽章——那比 256 位元 ECDSA 弱上數個數量級：

$ openssl speed rsa2048
                          sign         verify     sign/s     verify/s
rsa 2048 bits            0.000696s  0.000032s     1436.1      30967.1

由於模數較小，2048 位元 RSA 在驗證上比 256 位元 ECDSA 快，但在簽章上仍然較慢。

用橢圓曲線加密：ECIES#

儘管橢圓曲線更常用於簽章，你仍然可以用它們加密。

但實務上你很少看到有人這麼做，原因是可加密明文的大小受限：橢圓曲線只塞得下約 100 位元的明文，而相同安全等級的 RSA 幾乎能塞 4000 位元。

用橢圓曲線加密的一個簡單方法是整合加密方案（IES，integrated encryption scheme）——一個基於 Diffie–Hellman 金鑰交換的混合式非對稱／對稱加密演算法。搭配橢圓曲線使用時稱為 ECIES。

給定接收者的公鑰 P，ECIES 加密訊息 M 的流程：

  1. 挑一個隨機數 d，計算點 Q = dG（基點 G 是固定參數）。(d, Q) 是只用於加密 M 的短暫金鑰對。
  2. 計算 ECDH 共享秘密 S = dP。
  3. 用金鑰衍生方案（KDF）從 S 導出對稱金鑰 K。
  4. 用 K 與對稱鑑別式密碼加密 M，得到密文 C 與鑑別標籤 T。

ECIES 密文由短暫公鑰 Q、C 與 T 組成。

解密很直接：接收者用自己的私有指數乘上 Q 得到 S，導出金鑰 K，解密 C 並驗證 T。

Backward ECDLP 問題 選擇曲線 Forward