新手上路：實數上的橢圓曲線和群論

03-14

本文節選自推文集《友好型入門：橢圓曲線密碼學（Elliptic Curve Cryptography: a gentle introduction）》，作為史上最賤的數學題的拓展閱讀。

原文出處：ANDREA CORBELLINI

翻譯：鏡子文明

【引子】

如果你聽說過公共密鑰密碼學，那你應該也聽說過ECC，ECDH或者ECDSA。其中，ECC就是橢圓曲線密碼學首字母縮略詞，後二者都是基於ECC的演算法。

如今，在構建現代網路和IT世界的主流技術中，比如TLS（Transport Layer Security，安全傳輸層協議），PGP（Pretty Good Privacy，基於RSA的郵件加密系統）和SSH（Secure Shell，安全外殼協議）裡面，我們都能夠找到橢圓曲線加密系統的蹤影。更不要說比特幣和其它加密電子貨幣了。

在ECC普及之前，幾乎所有公共密鑰演算法都用基於RSA、DSA和DH等使用模塊計算的加密系統替代。RSA及其衍生演算法在現在仍然十分重要，常常被用於輔助ECC演算法。然而，相對於易於解釋、易於一般性地理解並且易於粗要實現的RSA及其衍生演算法來說，ECC的理論基礎對多數人還是一個謎團（*註：RSA理論基礎簡單來說就是因式分解兩個大素數的乘積非常困難）。

通過一系列的博客推文（*註：我只翻譯了橢圓曲線入門介紹，後續見原文鏈接），我將用友好的方式向你介紹橢圓曲線密碼學的世界。我的目標不是提供一個完整詳細的ECC導論（網上這種文章俯拾皆是），而是把冗長數學證明和枯燥實現細節的功夫節省下來，直接帶你簡要總觀ECC，然後理解它為什麼能確保加密安全。我也會以可視交互工具和腳本的形式提供一些有意思的例子，幫助你把弄這個玩意。

具體來說，我展開的主題如下

1.實數上的橢圓曲線和群論（本篇）

2.有限域上的橢圓曲線和離散對數問題

3.密鑰對生成和兩個ECC演算法：ECDH和ECDSA

4.破解ECC安全性的演算法以及與RSA的對比。

為了能夠理解本文內容，你需要了解一點集合論基礎、幾何學和模運算，並且熟悉對稱和不對稱加密。最後，你需要清晰地認識到，密碼學中什麼是簡單問題，什麼是困難問題，它們在密碼學中扮演什麼樣的角色。

準備好了嗎？正文開始！

【橢圓曲線】

首先，我們需要知道，到底什麼才是橢圓曲線呢？Woldram MathWorld給出了精彩而完整的定義。但考慮到我們的初衷，我們可以簡化理解，它就是由這個方程描述的曲線：

$y^2=x^3+ax+b$

其中， $4a^3+27b^2≠0$ （需要排除退化成奇異曲線的情況）。上述方程就是所謂的橢圓曲線魏爾斯特拉斯一般形式。

橢圓曲線的不同形狀（b=1，a從2開始遞減到-3）

退化的奇異曲線類型：左邊是一條帶尖點（cusp）的曲線（y^2=x^3）；右邊是一條自交的曲線（y^2=x^3-3x+2）。它們都不是有效的橢圓曲線。

隨著 $a$ 和 $b$ 取值的變化，橢圓曲線可能在平面上呈現不同的性狀。不論是直觀還是證明，我們都可以發現橢圓曲線是關於X軸對稱的。

想要講清橢圓曲線，我們還需要引入無窮遠點（也被稱為理想點）作為曲線的一部分。從現在開始我們將用符號 $0$ （零）表示無窮遠點。

如果我們想明確地理解無窮遠點，我們還需要進一步精鍊橢圓曲線的定義，如下所示：

{ ${(x,y)∈R2 | y^2=x^3+ax+b, 4a^3+27b^2≠0}$ } $∪$ { $0$ }

【群】

數學裡面的群是一類定義了二元運算（我們稱之為加法，用符號+表示）的集合。如果想讓集合 $G$ 變成一個群，我們必須定義滿足如下四條性質的加法：

1.封閉性：如果 $a$ 和 $b$ 屬於 $G$ ，那麼 $a+b$ 也屬於 $G$ ;

2.結合律： $(a+b)+c=a+(b+c)$ ;

3.存在單位元（*註：在二元運算中，單位元指與任意元素運算不改變其值的元素，以實數為例，乘法單位元為1，加法單位元為0） $heta$ 使得 $a+ heta= heta+a=a$ ;

4.每個元素都存在逆元素，也即對於任意元素a存在b使得 $a+b= heta$ 。

如果我們添加第五條要求：

5.交換律： $a+b=b+a$

那麼這個群就是阿貝爾群。

根據加法的一般定義，整數集Z是一個群（更確切地說，它是個阿貝爾群）。然而，自然數集N卻並不是一個群，因為它不滿足第四條性質。

群是一個好東西，如果我們能夠證明那四條性質一直保持，那我們就可以無條件地得到其它一些性質。例如：單位元唯一，元素的逆唯一，也即：對於任意元素 $a$ ，有且僅有唯一元素 $b$ 使得 $a+b= heta$ （而且可以用 $-a$ 表示 $b$ ）。在接下來的文章中，有關群的這些或其它事實將會向我們直接或間接地展現出它們的重要性。

【橢圓曲線的群律】

我們可以在橢圓曲線上定義一個群。具體地說，

群的元素是橢圓曲線上的點；

單位元 $heta$ 是無窮遠點 $0$ ；

點P的逆是它關於 $x$ 軸的對稱點。

加法通過如下法則定義：給定三個共線非零的點 $P，Q$ 和 $R$ ，它們的和為 $P+Q+R=0$ 。

共線三點的和為0

既然根據最後一條法則，加法只需要三個共線的點，對順序沒有要求，也就是

$P+(Q+R)=Q+(P+R)=R+(P+Q)=……=0$

通過這種方式，我們已經直觀地證明了我們的+算符同時滿足結合律和交換律：我們得到了一個阿貝爾群。到此為止，還算完美。但現在問題來了，我們該怎麼計算任意兩個點的加法？

【幾何加法】

萬幸我們處理的是一個阿貝爾群，這樣我們可以順手地將 $P+Q+R=0$ 變形為 $P+Q=-R$ 。通過這種形式的等式，我們可以導出計算兩點P和Q之和的幾何方法：如果我們過 $P，Q$ 做一條直線，這條直線將與曲線交於第三個點 $R$ （ $P，Q，R$ 三點共線的定義已經暗示了該曲線的這條性質）。如果我們取這個點的逆 $-R$ ，那我們就得到了結果 $P+Q$ 。

過P，Q作直線交曲線於第三個點R。R關於X軸的對稱點-R就是P+Q的結果

這個幾何方法很有效，但它還需要一點完善。具體地，我們需要回答幾個問題：

1. $P=0$ 或者 $Q=0$ 怎麼辦？顯然，我們不能作任何直線（無窮遠點 $0$ 不在 $xy$ 平面上）。但既然我們已經把 $0$ 定義為標準元，那對於任何點 $P$ 或者 $Q$ 來說，它們與 $0$ 的和就是它們自身。

2. $P=-Q$ 怎麼辦？在這種情況下，過兩點的直線垂直於X軸不與曲線相交。但根據逆的定義，如果P是Q的逆，那麼 $P+Q=P+(-P)=0$ 。

*註：不嚴謹的理解，這條直線與橢圓曲線在無窮遠點相交。

3.如果 $P=Q$ 怎麼辦？在這種情況下，有無數條直線過這個點。這裡事情就變得有點複雜了。但我們可以先構想一個 $Q』$ 點 $（Q』≠P）$ 。如果 $Q』$ 逐漸接近 $P$ 點， $PQ』$ 會變成什麼樣？

隨著兩點越來越靠近，過兩點的直線逐漸趨近於曲線的切線。

隨著 $Q』$ 點逐漸趨近 $P$ 點，過 $P，Q』$ 兩點的直線也逐漸趨近曲線的切線。根據這個事實，我們能這樣斷言：過 $P$ 點作曲線的切線與曲線交於另一點 $R$ ， $P+P=-R$ 。

4.如果 $P≠Q$ ，但找不到第三點 $R$ 怎麼辦？這種情況很像上一種。事實上，這種情況就是過 $P，Q$ 的直線是曲線的切線（*這裡的 $Q$ 就是上一種情況裡面的 $R$ ）。

如果直線僅有兩個交點，那意味著它與曲線相切。

要想找到和的結果其實很簡單，它就是其中一個點關於X軸的對稱點。不妨設 $P$ 點就是切點，在上一種情況，我們已經說明 $P+P=-Q$ ，這個等式可以變成 $P+Q=-P$ 。如果切點是 $Q$ 點，正確的等式就變成了 $P+Q=-Q$ 。

幾何方法現在已經完備地覆蓋了所有情形。用一支鉛筆一塊橡皮我們就能對任意橢圓曲線上的所有點作加法。如果你躍躍欲試，儘管參考HTML5/JavaScript visual tool ，我已經搭建了橢圓曲線和值計算的環境。

【代數加法】

如果我們想用計算機作加法，我們需要把幾何方法改造成代數方法。將上述規則轉化為一組方程看上去簡單直接，但做起來就冗長乏味了，因為它需要解三次方程。基於這個理由，我直接把答案貼出來。

首先，讓我避開那些惱人的極端情況。我們已經知道 $P+(-P)=0$ ，並且 $P+0=0+P=P$ 。因此，在我們的方程中，不考慮這兩種情況，僅僅考慮兩個非零、非對稱的點 $P$ $(x_{P},y_{P})$ 和 $Q$ $(x_{Q},y_{Q})$ 。如果 $P$ 和 $Q$ 不重合 $(x_{P} e x_{Q})$ ，那麼過兩點直線的斜率就是：

$m=frac{y_{P}-y_{Q}}{x_{P}-x_{Q}}$

與橢圓曲線的交點為第三點 $R=$ $(x_{R},y_{R})$

$x_{R}=m^2-x_{P}-y_{P}$

$y_{R}=y_{P}+m(x_{R}-x_{P})$

或者等於

$y_{R}=y_{Q}+m(x_{R}-x_{Q})$

因此 $(x_P,y_P)+(x_Q,y_Q)=(x_R,?y_R)$ （注意這些符號並且別忘了 $P+Q=-R$ ）

如果我們想要檢查這個結果是否正確，我們必須得檢查R是否屬於曲線而且 $P，Q，R$ 三點共線。檢查三點共線不足為慮，但檢查 $R$ 屬於曲線就很煩躁了，因為我們要解一個三次方程，那真的一點都不好玩。

扔掉上面的問題，我們直接從例子入手：根據我們的可視化工具，給定曲線上的 $P（1,2）$ 和 $Q（3,4）$ ，它們的和 $P+Q=-R=(-3,2)$ 。讓我們看看代入方程是否一致。 $m=frac{y_P-y_Q}{x_P-x_Q}=frac{2-4}{1-3}=1$

$x_R=m^2-x_P-x_Q=1^2-1-3=-3$

$y_R=y_P+m(x_R-x_P)=2+1cdot(-3-1)=-2$

或者 $y_R=y_Q+m(x_R-x_Q)=4+1cdot(-3-3)=-2$

耶，對的！

既然這些方程即使在 $P$ 或者 $Q$ 是切點的時候都有效，那我們就試試 $P（-1,4）$ 和 $Q（1,2）$ ：

$m=frac{y_P-y_Q}{x_P-x_Q}=frac{4-2}{-1-1}=-1$

$x_R=m^2-x_P-x_Q=(-1)^2-(-1)-1=1$

$y_R=y_P+m(x_R-x_P)=4+(-1)cdot[1-(-1)]=-2$

我們得到了結果 $P+Q=(1,-2)$ ，與可視化工具給出的一模一樣。

$P=Q$ 的情況需要一點特別對待：計算 $x_R$ 和 $y_R$ 的方程是一樣的，但奈何 $x_P=x_Q$ ，我們必須使用一個不一樣的方程處理斜率問題。

$m=frac{3x_P^2+a}{2y_P}$

正如我們期望的那樣，可以看到， $m$ 的表達式就是下式的一階導數

$y_P=±sqrt{x_P^3+ax_P+b}$

證明這個結果的正確性就足以說明 $R$ 屬於前並且過 $P$ 和 $R$ 的直線與曲線僅僅交於兩點。但同樣的（它的證明還是太難了），我們不直接證明這個事實，取而代之的是用實例檢驗： $P=Q=(1,2)$ 。

$m=frac{3x_P^2+a}{2y_P}=frac{3cdot1^2-7}{2cdot2}=-1$

$x_R=m^2-x_P-x_Q=(-1)^2-1-1=-1$

$y_R=y_P+m(x_R-x_P)=2+(-1)cdot[-1-1]=4$

計算結果 $P+P=-R=(-1，-4)$ 。正確！

儘管獲得答案的流程過於冗長，但我們的方程還是相當緊湊的。這得感謝魏爾斯特拉斯標準形式：沒有它，這些方程就會真的又長又繁。

【標量乘法（數乘）】

除了加法，我們還可以定義另一種算符：數乘，也即

$nP=P+P+......P（n個P相加）$

其中n是自然數。如果你想把玩它的話，我也寫了一個數乘的可視化工具。

寫成如上形式的話， $nP$ 的計算看上去需要 $n$ 次加法。如果 $n$ 有 $k$ 位二進位位的話，那我們的演算法複雜度就是O（ $2^k$ ），簡直鬧心。

然而，我們能找到更快的演算法：其中一個就是倍乘相加的演算法，它操作的原則用實例解釋更直白。取 $n=151$ ，用二進位表示就是 $10010111_2$ 。這個二進位表示可以轉化為 $2$ 的冪次依次加和。

$151=1?2^7+0?2^6+0?2^5+1?2^4+0?2^3+1?2^2+1?2^1+1?2^0$

$=2^7+2^4+2^2+2^1+2^0$

通過這種方法，我們可以這樣書寫原式：

$151?P=2^7P+2^4P+2^2P+2^1P+2^0P$

倍乘相加演算法需要這樣操作：

$ullet$ 取 $P$ 點

$ullet$ 倍乘，得到 $2P$

$ullet$ 計算 $2P+P$ （為了得到 $2^1P+2^0P$ ）

$ullet$ 倍乘 $2P$ ，從而得到 $2^2P$

$ullet$ 與上面得到的序列和相加得到 $2^2P+2^1P+2^0P$

$ullet$ 倍乘，得到 $2^3P$

$ullet$ 不作任何操作

$ullet$ 倍乘，得到 $2^4P$

$ullet$ 與序列和相加，得到 $2^4P+2^2P+2^1P+2^0P$

$ullet$ ……

最後，我們可以僅僅通過七次倍乘和四次加和得到 $151P$ 的值。

如果上述描繪還不夠明晰，這裡還有個實現該演算法的Python腳本。

def bits(n): """ Generates the binary digits of n, starting from the least significant bit. bits(151) -> 1, 1, 1, 0, 1, 0, 0, 1 """ while n: yield n & 1 n >>= 1def double_and_add(n, x): """ Returns the result of n * x, computed using the double and add algorithm. """ result = 0 addend = x for bit in bits(n): if bit == 1: result += addend addend *= 2 return result

如果倍乘和加和都是複雜度為 $O(1)$ 的操作，那這個演算法的複雜度就是 $O(log n)$ （考慮比特長度的話就是 $O(k)$ ），這就相當優秀了，比最開始的 $O(n)$ 演算法不知道高到哪裡去了。

【演算法】

給定 $n$ 和 $P$ ，我們至少有一種多項式時間的演算法（*就是文中給的那種）可以計算 $Q=nP$ 。但是反過來呢？我們知道 $Q$ 和 $P$ 需要求解 $n$ 呢？這個問題就是大名鼎鼎的對數問題。我們稱它為「對數」而不是除法是因為需要與其它加密系統保持一致（這些系統中我們使用乘方而不是乘法）。

我不知曉對數問題的任何「簡單」演算法，但是玩轉乘法可以呈現某些端倪。例如，對於曲線和點 $P(0,1)$ ，我們可以立即驗證，如果 $n$ 是奇數， $nP$ 就在曲線的左半平面；如果 $n$ 是偶數， $nP$ 在曲線的右半平面。如果我們試驗更多的點，我們可能可以找到某種模式，最終引導我們寫出曲線上對數計算的有效演算法。

對數問題還有個變體：離散對數問題。下篇推文中我們可以看到，如果我們減小橢圓曲線的定義域，數乘還是很「簡單」，但離散對數問題就變得艱難起來。這種二元對立（對偶，duality）正是橢圓曲線加密的關鍵鑰匙。

預告：

專欄關於數學的內容到此就告一段落了，對於一個非數學系的學生，看這些東西真是難為我了，儘管是科普性質的東西，但還是常常超出我的智商範圍(；′д｀)ゞ

接下來我會回到我擅長的科普方向，某21世紀學科。

下一篇文章的標題我已經想好了：震驚！毛毛蟲的起源竟然是祖先亂交。(￣▽￣)／

感謝閱讀！

歡迎關注我們的微信公眾號：