Categories
程式開發

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


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

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

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

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

這個secp256k1為什麼如此命名?

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

咬文嚼字secp256k1

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

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

1、密碼協議標準

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

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

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

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

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

NIST是美國的國家標準技術研究所(National Institute of Standards and Technology),因此,NIST的標準也是美國標準。

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

「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的橢圓曲線為:

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

基於F2m的橢圓曲線為:
一場橢圓曲線的尋根問祖之旅 5

在「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 兩個域的各種不同大小配置。

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

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分別簡化為:
一場橢圓曲線的尋根問祖之旅 7一場橢圓曲線的尋根問祖之旅 8

例如,secp256k1對應的曲線b=7,即曲線表示為

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

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

5、末位標記

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

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

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

上述表格中,同一行中 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」定義如下:

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

「Montgomery Curve」定義如下:

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

「Twisted Edward Curve」定義如下:

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

「Curve25519」定義如下:

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

「Ed25519」的定義如下:

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

根據 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。

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

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

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

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

後話

古有拆文解字,參透漢字玄機,道破人生天機;
而今咬文嚼字,摸清橢圓原理,揭開曲線家譜。

始於名字,解碼 secp256k1,釐清標準;
終於名字,問祖 weierstrass,致敬大神。

通過了解橢圓曲線之間的內在關係,對其設計有了更多一點的理解。知道的更多了,不知道的也更多了,那些特殊曲線的數學原理是什麼?為什麼具有更高的計算效率?性能能提升多少? …

又是一個深夜,擁抱最新的收穫,夾雜更多的困惑。電腦中正好在播放“把太細的神經割掉,會不會比較睡得著…”

作者簡介

李輝忠,微眾銀行FISCO BCOS 高級架構師。

參考資料

SEC1 :
https://www.secg.org/sec1-v2.pdf

SEC2:
https://www.secg.org/sec2-v2.pdf

NIST:
https://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.186-4.pdf

STD:
https://neuromancer.sk/std/

SafeCurves:
https://safecurves.cr.yp.to

Koblitz Curves:
https://link.springer.com/content/pdf/10.1007%2F3-540-46766-1_22.pdf

Weierstrass Equation:
https://www.lmfdb.org/knowledge/show/ec.weierstrass_coeffs

Montgomery Curve wiki:
https://en.wikipedia.org/wiki/Montgomery_curve

Twisted Edward Curve wiki:
https://en.wikipedia.org/wiki/Twisted_Edwards_curve

Edward Curve wiki:
https://en.wikipedia.org/wiki/Twisted_Edwards_curve

ECDSA wiki:
https://en.wikipedia.org/wiki/EdDSA#Ed25519

Curve25519 wiki:
https://en.wikipedia.org/wiki/Curve25519

Curve25519 paper:
http://cr.yp.to/ecdh/curve25519-20060209.pdf

Ed25519 paper:
http://ed25519.cr.yp.to/ed25519-20110926.pdf