一場橢圓曲線的尋根問祖之旅

本文介紹密碼學中常見的橢圓曲線以及他們之間的關係，介紹不同標準體系的命名規則，嘗試描述橢圓曲線之間的家族演義關係。文章試圖講清橢圓曲線相關概念和功能，不涉及複雜的數學證明和推理，歡迎感興趣的同學閱讀。

筆者主要參考 Wikipedia 和相關組織網站的信息進行整理，不排除出現紕漏的可能，歡迎專家批評指正。

一個可能你沒關心過的問題

在《一個數字引發的探索——ECDSA 解析》中提到的橢圓曲線 secp256k1，它有一些特性，可以快速計算出 recoveryID。

這個 secp256k1 爲什麼如此命名？

不怕各位笑話，我在弄清楚它之前，經常拼寫錯，寫成 sec256pk1，seck256p1 等。

咬文嚼字 secp256k1

搞清楚 secp256k1 的命名含義其實很簡單，搜索引擎可以快速爲你定位到答案，它出自一個密碼協議標準，每一個字母和數字都代表着特定含義，我們來逐一解析。

1、密碼協議標準

第一部分是「sec」，sec 是 Standards for Efficient Cryptography 的簡稱，是 SECG 發佈的一種密碼學協議標準。

SECG 發佈的「SEC 1」和「SEC 2」兩個關於橢圓曲線的協議標準，在「SEC 2」中有詳細說明 secp256k1 以及其他曲線的參數定義。

除了「sec」，還有衆多其他關於橢圓曲線的協議標準，從「SafeCurve」中可以看到有下列不同類型的標準。

「SafeCurve」此處較久沒有更新，有些標準已經更新了多次，例如 NIST 關於數字簽名的標準 FIPS 186 目前在用的是第四版，第五版也在起草中了，從「NIST」官網中可見。

NIST 是美國的國家標準技術研究所（National Institute of Standards and Technology），因此，NIST 的標準也是美國標準。

「NIST FIPS 186-4」標準中定義了若干橢圓曲線標準，例如 NIST P-256、NIST P-384 等，其中開頭 NIST 也代表密碼協議標準的名字。後續描述都是圍繞這兩個標準來解析。

2、有限域

第二部分是「p」，p 表示該橢圓曲線是基於素數有限域 Fp。有限域是離散數學中的概念，此處不做展開，簡單來說，它是一個由有限數量元素組成的集合，元素之間可以進行加法和乘法計算，具備一些獨特的屬性。

密碼學中使用橢圓曲線都是基於有限域的，除了素數有限域 Fp 之外，還有另一種特徵爲 2 的有限域 F2m（因格式問題，2m 應爲 2 的 m 次方，下同），Fp 的大小（元素個數）爲 p，F2m 的大小爲 2m。

基於 Fp 的橢圓曲線爲：

基於 F2m 的橢圓曲線爲：

在「SEC 2」中還定義了 sect163k1、sect163r1 等曲線，其中，t 表示的是該曲線基於 F2m。在「NIST FIPS 186-4」中定了 P-256、B-163 等曲線，P- 表示基於 Fp，B- 表示基於 F2m。

3、有限域大小

每個橢圓曲線 E 都有若干關鍵參數，包括階爲 n 的基點 G 和係數 h 等，其中，n 爲一個大素數，n*h 爲橢圓曲線上點的數量。爲了計算效率考慮，h 通常設置爲 1、2 或 4。

通俗地講，如果橢圓曲線上的點數量越多，那麼這條橢圓曲線的安全度就越高，因此 n 的取值是影響曲線安全的關鍵。

橢圓曲線又都是基於有限域的，曲線上的點都是有限域中的元素，因此，有限域大小決定了曲線安全度。

第三部分「256」就是有限域大小的表現形式，還有更多其他如 192、224、384 等，在「NIST FIPS 186-4」中有個表格展現了 Fp 和 F2m 兩個域的各種不同大小配置。

SEC 標準在這塊的設置和 NIST 標準類似，我們會看到 p 系列的曲線有 p192、p224、p256（secp256k1 就是其中一種）、p384 和 p521，t/B 系列有 t163/B-163、t233/B-233 等。

4、Koblitz Curve

第四部分「k」表示該曲線是 Koblitz Curve，從「SEC 2」中可以看到還有此處標記爲 r 的曲線（如 secp256r1），r 表示該曲線是僞隨機曲線 Pesudo-Random Curve。

Koblitz Curve 命名源自數學家「Neal Koblitz」，它是一種特殊的曲線，它的一些參數是精心挑選設置的。Koblitz Curve 具有自同態的性質，可以通過優化大幅提升計算效率。

相比之下，Pesudo-Random Curve 的對應參數是通過隨機種子計算出來的，有標準的檢驗算法可以檢測所有參數是隨機種子產生而來。

對應「2、有限域」中的兩個橢圓曲線，Koblitz Curve 分別簡化爲：

例如，secp256k1 對應的曲線 b=7，即曲線表示爲

在「NIST FIPS 186-4」中 Koblitz Curve 曲線以「K-」標記開頭，分別有 K-163、K-233 等。

5、末位標記

到了第五部分「1」，這是代表在前 4 個條件下提供了多種推薦參數設置，在 SEC 標準中大部分該位都是 1，即只提供一種推薦參數，sect163r2 是一個例外。

下面把 SEC 和 NIST 兩個標準推薦的曲線分別列一下，二者有較大部分是相同的參數設置。

上述表格中，同一行中 SEC 和 NIST 都出現的，兩個曲線雖然名字不同，但參數完全相同，也就是說其實一樣的。

橙色底紋的幾個 SEC 曲線沒有對應的 NIST 曲線，因此 SEC 標準包含的曲線比 NIST 多一些，本文開頭提到的 secp256k1 就是 SEC 單獨存在的。

說到這裏，不得不提一個正經八卦。據說，NIST 推薦的 Pesudo-Random Curve，也就是 P 和 B 系列，並沒有公佈隨機數挑選規則，外界存在一種疑慮，可能 NSA（美國國家安全局）掌握了後門，能夠輕易破解這些密碼協議。

有興趣的同學可以搜索「Dual_EC_DRBG 後門」，更大的八卦是據說中本聰選擇 secp256k1 作爲比特幣簽名算法的曲線，而沒有選擇更常用的 secp256r1，也是因爲這個潛藏的風險。

橢圓曲線族譜

調研發現，「STD」記錄了比「SafeCurve」更爲詳細的標準和曲線，感覺這可以算是橢圓曲線族譜了。翻閱該網站記錄的所有曲線，發現絕大部分還是基於「（2）有限域」中的曲線，推薦的參數不同而已。

但是，在「other」中存在幾種例外，E-222 採用 Edward Curve，Curve25519 採用 Montgomery Curve，Ed448 採用 Twisted Edward Curve。

Edward Curve 是什麼？Montgomery Curve 又是怎樣的？Edward 與 Twisted Edward Curve 又有什麼關係？

上述問題再一次觸碰到我的知識盲區，所以接下來只好以截圖爲主，內容源自 Wikipedia，如果覺得看着有點暈，可直接跳過看結論。

「Edward Curve」定義如下：

「Montgomery Curve」定義如下：

「Twisted Edward Curve」定義如下：

「Curve25519」定義如下：

「Ed25519」的定義如下：

根據 Wikipedia，大概可以整理出這麼幾個信息：

Edward Curve 是 Twisted Edward Curve 中的一種；
Twisted Edward Curve 和 Montgomery Curve 可以互相轉換；
Edward Curve 和 Montgomery Curve 這兩種曲線都具有特殊屬性，例如能夠爲計算加速；
Curve25519 是一種曲線，Ed25519 是一種簽名算法；
Curve25519 又是精選的 Montgomery Curve，具有更高的計算效率；
Curve25519 和 Ed25519 採用的曲線是一致的，一個是 Montgomery 表現形式，一個是 Twisted Edward Curve 表現形式；
25519 的取名來自於該曲線的有限域參數 p=2 的 225 次方 -19；

在閱讀 Wikipedia 的過程中發現一個名字「Weierstrass equation」，原來它纔是這些曲線的鼻祖，在一個域 k 上的任何一個平面曲線，都可以表示成 Weierstrass equation。

不難發現，前面提到過的各個公式都是 Weierstrass equation 的一種演化版本（Twisted Edward Curve 看起來不是，但是它可以轉換到 Montgomery Curve，本質上也一樣）

到此，爲橢圓曲線尋根問到祖，並且從「STD」也獲知了橢圓曲線家族的族譜。

「STD」中羅列了多個其他標準，例如 Brainpool 曲線系列、BN 曲線系列、MNT 曲線系列等，這些系列的背後都代表了一種獨特的曲線生成哲學，或是爲了提供可驗證的隨機數，或是爲了提供滿足 Paring 的特性，或是爲了提高抗攻擊的能力等等，每一份精心選擇的參數都是一羣數學家們巧奪天工的設計。