第十二個知識點：橢圓曲線上的群理論是什麼

這是系列中的第12篇,我們繼續數學背景的部分,通過介紹橢圓曲線的群理論...

橢圓曲線群定律是一種在一組橢圓曲線有理點中定義的二進制操作來形成一個群的方法.現在,讓我們看看到底什麼意思,和這個東西怎麼用.感謝Dr Dan Page提供的群定律圖.

橢圓曲線和它的有理點

橢圓曲線就是數學領域中的二進制三次等式.它們能被寫成各種各樣的形式\(^1\),但是大多數領域中能被形成short Weierstrass form:

\(E:y^2=x^3+ax+b\)

從現在開始我們假設我們工作在實數域忽略有限域中的複雜性.上面這個公式需要\(a,b\)滿足\(27b^2 \ne -4a^3\)(這個就是判别式,如果相等了就會有二重根或者三重根),那麼就是橢圓曲線.

這組元素的集合就是橢圓曲線的有理點.這是簡單的滿足橢圓曲線的點\((x,y)\)滿足\(x,y\)都是有理數.是以,就是一組\((x,y) \in Q\)當\(y^2=x^3+x+b\).我們還應該包含一個無窮遠的點,包含的原因是清晰的\(^2\).

在橢圓曲線中加入群理論

描述我們要添加到有理點集合中的關系的最簡單的方法是用圖表:

是以為了将\(P\)和\(Q\),我們畫出一條通過\(P\)和\(Q\)的直線,然後做出 \(T = (T_x,T_y)\)第三個和這條直線相交的點.然後,\(P+Q=(T_x,-T_y)\).為了能讓點自己加自己我們取點的切線.現在這個令人吃驚的事實就是群在這種操作下,有一個無窮遠的自然元素.

成為一個群的大多數需求都很容易在幾何學中觀察到.例如,很容易找到一個元素的逆元.在這個圖中\((P+Q)+T=0\).因為從\(T\)到\(P+Q\)的線是在無窮遠處有一個交點,是以\((P+Q)=-T\).事實上,對任何在short Weierstrass形式的橢圓曲線,要消去一個點,隻需改變它的y坐标符号.

這就是全部了嗎

同樣的方法也适用于有限域,盡管這種情況下,把群的運算看作代數結構而不是幾何結構會更簡單,因為有限域的橢圓曲線沒有一個直覺的結構.同樣，我們也不需要用簡單的維爾斯特拉斯形式來觀察曲線，因為有許多不同的坐标格式和方程表示同一條曲線。事實上，一些曲線和坐标系的選擇有助于我們進行某些類型的計算。

這和密碼學有什麼關系

結果表明，在一定的有限域上，橢圓曲線群對密碼學家有幾個很好的性質。令人驚訝的是，在大量的曲線和字段對中，進行分組計算的成本并不高，但是對于這些曲線和字段對，各種離散對數或DH問題(請參閱上周的部落格)是很難解決的。此外，與使用大型乘法組(如RSA組)相比，計算變量要小得多。把所有這些放在一起，橢圓曲線使密碼學家能夠有效地計算比其他多邊環境協定建立的密文小得多的密文.

1.特别的,數字域不等于2,3.那就是說,\(2 \ne 0\)和\(3 \ne 0\).不幸的是，顯然意味着我們讨論的結果在二進制字段中并不适用，但這已經超出了本文的讨論範圍。

2.證明這一點的理由來自于把橢圓曲線看作射影空間中的一條曲線，但現在它滿足于這樣一個點的存在.

3.結合律是迄今為止最複雜的。維基百科上的這張圖表解釋了證明背後的概念，盡管細節相當複雜.

4.即使在我寫這篇文章的時候，我肯定有人會質疑這種說法的正确性，但确實，與我們可以構造的許多組相比，橢圓曲線上的點算術相對容易處理.