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

本文介紹密碼學中常見的橢圓曲線以及他們之間的關系，介紹不同標準體系的命名規(guī)則榄檬，嘗試描述橢圓曲線之間的家族演義關系础浮。文章試圖講清橢圓曲線相關概念和功能嘀粱，不涉及復雜的數(shù)學證明和推理，歡迎感興趣的同學閱讀爬迟。筆者主要參考Wikipedia和相關組織網站的信息進行整理橘蜜，不排除出現(xiàn)紕漏的可能，歡迎專家批評指正付呕。

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

在《一個數(shù)字引發(fā)的探索——ECDSA解析》（加鏈接）中提到一個橢圓曲線secp256k1计福，它有一些特性，可以快速計算出recoveryID徽职。

這個secp256k1為什么如此命名象颖？

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

咬文嚼字secp256k1

搞清楚secp256k1的命名含義其實很簡單潮瓶，搜索引擎可以快速為你定位到答案陶冷，它出自一個密碼協(xié)議標準，每一個字母和數(shù)字都代表著特定含義毯辅，我們來逐一解析埂伦。

image.png

（1）密碼協(xié)議標準

第一部分是「sec」，sec是Standards for Efficient Cryptography 的簡稱思恐，是SECG發(fā)布的一種密碼學協(xié)議標準沾谜。

SECG發(fā)布的「SEC 1」和「SEC 2」兩個關于橢圓曲線的協(xié)議標準，在「SEC 2」中有詳細說明secp256k1以及其他曲線的參數(shù)定義壁袄。

除了「sec」类早，還有眾多其他關于橢圓曲線的協(xié)議標準，從「SafeCurve」中可以看到有下列不同類型的標準嗜逻。

image.png

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

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

image.png

「NIST FIPS 186-4」標準中定義了若干橢圓曲線標準，例如NIST P-256坪圾、NIST P-384等晓折，其中開頭NIST也代表密碼協(xié)議標準的名字。后續(xù)描述都是圍繞這兩個標準來解析兽泄。

（2）有限域

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

密碼學中使用橢圓曲線都是基于有限域的钮热，除了素數(shù)有限域Fp之外填抬，還有另一種特征為2的有限域F2m （因輸入格式問題，全文2m應為2的m次方霉旗，下同）痴奏，F(xiàn)p的大小（元素個數(shù)）為p厌秒，F(xiàn)2m的大小為2m读拆。

基于Fp的橢圓曲線為：

image.png

基于F2m的橢圓曲線為：

image.png

在「SEC 2」中還定義了sect163k1、sect163r1等曲線鸵闪，其中檐晕，t表示的是該曲線基于F2m。在「NIST FIPS 186-4」中定了P-256蚌讼、B-163等曲線辟灰，P-表示基于Fp，B-表示基于F2m篡石。

（3）有限域大小

每個橢圓曲線E都有若干關鍵參數(shù)芥喇，包括階為n的基點G和系數(shù)h等，其中凰萨，n為一個大素數(shù)继控，n*h為橢圓曲線上點的數(shù)量械馆。為了計算效率考慮，h通常設置為1武通、2或4霹崎。

通俗地講，如果橢圓曲線上的點數(shù)量越多冶忱，那么這條橢圓曲線的安全度就越高尾菇，因此n的取值是影響曲線安全的關鍵。

橢圓曲線又都是基于有限域的囚枪，曲線上的點都是有限域中的元素派诬，因此，有限域大小決定了曲線安全度链沼。

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

image.png

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命名源自數(shù)學家「Neal Koblitz」，它是一種特殊的曲線孵奶，它的一些參數(shù)是精心挑選設置的疲酌。Koblitz Curve具有自同態(tài)的性質，可以通過優(yōu)化大幅提升計算效率了袁。

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

對應「（2）有限域」中的兩個橢圓曲線粥诫，Koblitz Curve分別簡化為

image.png

image.jpeg

例如，secp256k1對應的曲線b=7崭庸，即曲線表示為

image.png

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

（5）末位標記

到了第五部分「1」揉稚，這是代表在前4個條件下提供了多種推薦參數(shù)設置秒啦，在SEC標準中大部分該位都是1，即只提供一種推薦參數(shù)搀玖，sect163r2是一個例外余境。

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

image.png

上述表格中芳来，同一行中SEC和NIST都出現(xiàn)的，兩個曲線雖然名字不同猜拾，但參數(shù)完全相同即舌，也就是說其實一樣的。

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

說到這里盯仪，不得不提一個正經八卦紊搪。據(jù)說，NIST推薦的Pesudo-Random Curve全景，也就是P和B系列耀石，并沒有公布隨機數(shù)挑選規(guī)則，外界存在一種疑慮爸黄，可能NSA（美國國家安全局）掌握了后門滞伟，能夠輕易破解這些密碼協(xié)議。有興趣的同學可以搜索「Dual_EC_DRBG后門」炕贵，更大的八卦是據(jù)說中本聰選擇secp256k1作為比特幣簽名算法的曲線梆奈，而沒有選擇更常用的secp256r1，也是因為這個潛藏的風險鲁驶。

橢圓曲線族譜

調研發(fā)現(xiàn)鉴裹，「Standard curve database」記錄了比「SafeCurve」更為詳細的標準和曲線，感覺這可以算是橢圓曲線族譜了钥弯。翻閱該網站記錄的所有曲線径荔，發(fā)現(xiàn)絕大部分還是基于「（2）有限域」中的曲線，推薦的參數(shù)不同而已脆霎。

但是总处，在「other」中存在幾種例外，E-222采用Edward Curve睛蛛，Curve25519采用Montgomery Curve鹦马，Ed448采用Twisted Edward Curve胧谈。

Edward Curve是什么？Montgomery Curve又是怎樣的荸频？Edward與Twisted Edward Curve又有什么關系菱肖？

上述問題再一次觸碰到我的知識盲區(qū)，所以接下來只好以截圖為主旭从，內容源自Wikipedia稳强，如果覺得看著有點暈，可直接跳過看結論和悦。

「Edward Curve」定義如下：

image.png

「Montgomery Curve」定義如下：

image.png

「Twisted Edward Curve」定義如下：

image.png

「Curve25519」定義如下：

image.png

「Ed25519」的定義如下：

image.png

根據(jù)Wikipedia退疫，大概可以整理出這么幾個信息：

Edward Curve是Twisted Edward Curve中的一種
Twisted Edward Curve和Montgomery Curve可以互相轉換
Edward Curve和Montgomery Curve這兩種曲線都具有特殊屬性，例如能夠為計算加速
Curve25519是一種曲線鸽素，Ed25519是一種簽名算法
Curve25519又是精選的Montgomery Curve褒繁，具有更高的計算效率
Curve25519和Ed25519采用的曲線是一致的，一個是Montgomery表現(xiàn)形式馍忽，一個是Twisted Edward Curve表現(xiàn)形式
25519的取名來自于該曲線的有限域參數(shù)p=2255-19
在閱讀Wikipedia的過程中發(fā)現(xiàn)一個名字「Weierstrass equation」棒坏，原來它才是這些曲線的鼻祖，在一個域k上的任何一個平面曲線遭笋，都可以表示成Weierstrass equation俊抵。

image.png

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

到此刹帕，為橢圓曲線尋根問到祖吵血，并且從「STD」也獲知了橢圓曲線家族的族譜⊥的纾「STD」中羅列了多個其他標準蹋辅，例如Brainpool曲線系列、BN曲線系列挫掏、MNT曲線系列等侦另，這些系列的背后都代表了一種獨特的曲線生成哲學，或是為了提供可驗證的隨機數(shù)尉共，或是為了提供滿足Paring的特性褒傅，或是為了提高抗攻擊的能力等等，每一份精心選擇的參數(shù)都是一群數(shù)學家們巧奪天工的設計袄友。