很多人都聽說過加密算法，包括ECC、ECDH或者ECDSA。ECC是Elliptic Curve Cryptography的縮寫，就是橢圓加密算法，ECDH和ECDSA是ECC的不同實現(xiàn)。

橢圓加密算法的應(yīng)用范圍很廣，主要的三個技術(shù) TLS、PGP以及SSH 都在使用它，更別提比特幣以及其他加密數(shù)字貨幣了。

在橢圓加密算法流行之前，絕大多數(shù)的公鑰加密算法都是基于RSA、DSA以及DH這些基于模運算的替代加密系統(tǒng)。這些加密算法在今天依然占據(jù)非常重要的位置。然而，盡管ECC背后的這些算法很容易理解而且廣泛使用，但是對于絕大多數(shù)人來說，這些算法是一個謎團。

接下來的一系列文章：橢圓加密算法（從入門到放棄），我將對該算法做一個詳細介紹。我的目標并不是要徹底解釋清楚以及證明背后的數(shù)學原理，而是做一個介紹，講清楚：簡要解釋ECC，以及為什么ECC被認為是安全的。同時，也會給出模擬操作的例子以及腳本幫助你更加理解。

接下來的幾篇文章會涉及到：

• 實數(shù)下的橢圓曲線以及群公理（就是這篇文章啦）
• 有限域下的橢圓曲線以及離散數(shù)學
• 密鑰對加解密以及兩種橢圓加密算法：ECDH和ECDSA
• 破解ECC的安全性算法，以及同RSA的比較

筆者假設(shè)閱讀這篇文章的讀者已經(jīng)對以下幾個概念并不陌生：集合論、幾何學、模運算，并且對對稱加密和非對稱加密有了一些了解。最后，在加密學里面，對于什么是“簡單”的問題，什么是“困難”的問題有個清晰的認知。

橢圓曲線

首先：什么是橢圓曲線？Wolfram MathWorld給出了個準確非凡的定義橢圓曲線。但對于目前的我們來說，橢圓曲線可以暫時簡單的理解為描述了特定點的集合的公式：

該公式在橢圓曲線里面稱為*Weierstrass normal form*

以下是a和b參數(shù)的變化對應(yīng)的圖形的示例：

b=1，a取值范圍從2到-3

特殊曲線：左邊參數(shù)是a=b=0，右邊參數(shù)是a=-3，b=2.這兩條都不是符合標準的曲線

a和b的取值變化決定了曲線在坐標系上的不同形狀。從圖中可以看到，橢圓曲線是相對X軸對稱。

為了達到我們的目的，我們還要定義一個無窮大的點（也可以成為理想點），從現(xiàn)在開始，我們以符號0，也就是零表示該點。

把上面幾個點結(jié)合起來，我們的橢圓曲線公式就變成了

群(Groups)

數(shù)學上，群(Groups)指的是我們定義了二元操作“運算”并且用符號+表示的一個集合。假定我們要操作的群用 ??表示，那么我們在這個群上面要定義的“運算”必須符合以下幾個屬性：

• 閉包。如果a和b都是??的成員，那么a+b也是??的成員。
• 組合性。(a+b)+c=a+(b+c)
• 單位元。存在確切的一個值，稱之為單位元，0可以保證該等式成立 a+0=0+a=a
• 逆元。每個成員都有一個相反數(shù)：對于任意值a必定存在b使得a+b=0

如果加上第五條這要求：

• 交換性a+b=b+a

這樣的群我們稱之為 阿貝爾群。

根據(jù)以上的定義，我們很容易得知，整數(shù)集合 ? 是一個群，也可以稱之為 阿貝爾群。自然數(shù)集合 ? 卻不是一個群，因為不符合第四個屬性（自然數(shù)都是整數(shù)，不存在a+b=0）。

根據(jù)組的這四個屬性，我們很容易可以推導出其他屬性。比如：第三個屬性的確切的值0是唯一的；相反數(shù)也是唯一的，也就意味著a+b=0，a的相反數(shù)b也是唯一的。這些屬性有助于我們接下去的數(shù)學邏輯推理。

橢圓曲線里的群公理

如上文所說，我們可以基于橢圓曲線定義一個群。特別要指出的是：

• 群里的元素都在橢圓曲線上
• 橢圓上的單位元指的是無限遠點
• 橢圓上的點P的逆元與P關(guān)于X軸軸對稱
• 定義+運算：給定三個非零的點 P，Q和R，則P+Q+R=0（無限遠點）成立

P+Q+R=0（無限遠點）

注意：最后一條公理里，給出了三個點，但是沒有限定順序，也就意味著P+(Q+R)=Q+(P+R)=R+(P+Q)=?=0。這就充分表明了，這里定義的+運算符符合群公理的組合性和交換性，也就意味著橢圓曲線符合阿貝爾群。

到目前為止，一切都推理挺順利的，對吧。那么問題來了，我們要如何計算兩個任意點之和呢？

幾何學上的加法

因為橢圓曲線是阿貝爾群，所以公式P+Q+R=0 以及 P+Q=?R成立。根據(jù)這些公式，我們可以從幾何學的角度去計算點P+點Q的值：在橢圓曲線上畫出點P和點Q，連直線穿過P和Q，該直線會與橢圓曲線相較于第三個點，稱之為R。根據(jù)R取得R的逆元-R，P+Q=-R。

運用幾何學的方法很容易得到我們要的結(jié)果，但是我們需要再對一些更精確的解釋。特別是有一些問題需要考慮：

• 如果P=0或者Q=0(0是無窮遠點)呢？我們當然無法畫出該直線，因為無窮遠點無法體現(xiàn)在直角坐標系里。但是既然已經(jīng)定義了無窮遠點0，那么對于任意給定的P或者Q，P+0=P以及0+Q=Q都是成立的。
• 如果P=-Q呢？這種情況下該直線是與X軸是垂直的，并且不會與橢圓曲線相交于第三個點。 根據(jù)公理，P就是Q的逆元，P+Q=P+(-P)=0。
• 如果P=Q呢？這種情況下，存在無數(shù)條線穿過這個點。這里要用到極限的思維。假設(shè)線上有另外一個點Q1，讓Q1不斷靠近P，會怎么樣？

隨著兩個點的不斷靠近，最終產(chǎn)生的線跟橢圓曲線是切線關(guān)系

隨著Q1不斷靠近P，最終Q1無限靠近P，產(chǎn)生了一條直線與橢圓曲線相切。那么可以得到 P+P=-R, 在這里R就是該直線與橢圓曲線的另外一個交點。

• 如果P≠Q(mào)，但是不存在第三個交點R呢？這種情況和上一個情況很類似。實際上，這種情況下該直線跟橢圓曲線是相切的關(guān)系。

假設(shè)P就是相切的點。在上一個情況里，有該等式P+P=-Q。而在這里變成了P+Q=-P。另一方面，如果Q是相切的點，那么P+Q=-Q。

我們需要了解的幾何學只是已經(jīng)差不多涵蓋了所有情況了。只要給我們筆和尺子，我們就能在橢圓曲線上執(zhí)行加法。如果有興趣，可以到HTML5/JavaScript visual tool計算橢圓曲線上的加法

代數(shù)上的加法

要計算點的加法的話，我們必須把前面的幾何學的討論轉(zhuǎn)到代數(shù)上的討論。最直接的方法是把上面的公理用代數(shù)上的公式表示出來，但是這件事情會很乏味而且需要解決一些三次方程。所以在這里我就只給出結(jié)果吧。

首先，聲明下我們暫時不討論一些特殊情況。比如我們已經(jīng)知道了P+(-P)=0，P+0=0+P=P，所以，接下去我們不考慮這兩種情況。我們考慮的是 非0，非對稱的點 P和Q，如下圖

如果xP≠xQ(P和Q是下標)，那么該直線的斜率是：

該直線與橢圓曲線相交的第三個點R(xR,yR)(R是下標)：

或者也可以寫成：

特別強調(diào)一下 (xP,yP)+(xQ,yQ)=(xR,?yR)（P，Q，R都是下標）。
如果要檢查結(jié)果是否正確，我們需要檢查R是否在橢圓曲線上，以及P，Q和R是否都在直線上。檢查這些點是否在直線上是顯而易見的，然而檢查R是否屬于橢圓曲線并不是，因為我們不得不解決一個一點都不有趣的三次方程問題。

考慮這么一個例子：根據(jù)我們給出的visual tool，給定的P=（1，2）和Q=（3，4）都在曲線上y2=x3?7x+10（y的2次方，x的3次方），那么P+Q=-R=（-3，2）。反過來去根據(jù)我們前面的公式驗證該結(jié)果是否正確：

驗證正確！

注意，即使P或者Q是切點，該等式依然成立。拿P=(-1,4) Q=(1,2)嘗試下：

另一種情況P=Q則需要另外處理了：關(guān)于xR以及yR的公式是一樣的，但是針對直線的斜率必須用另外的方式處理：

注意，該公式是由一下公式推導出來的：

為了證明該公式的正確性，有必要驗證R是否屬于橢圓曲線上，以及P和R連成的直線與橢圓曲線有且僅有2個交點。但是在這里，我們不作證明，先做個測試：P=Q=(1,2)

所以得出 P+P=-R=(-1, -4)。正確

標量乘法

除了加法之外，我們定義另外一個運算：標量乘法：

在這里n是一個自然數(shù)。嗯，我寫了個visual tool用來玩標量乘法，有興趣點擊去試試吧。

該公式看起來計算nP需要計算n次加法。如果n是k個二進制位，那么該算法復雜度是O(2k)（2的k次方），計算量有點大。但是其實存在更快速的方案。

其中一個就是先做倍數(shù)再做加法。要了解基本原理還是直接看例子會比較快。假設(shè)n=151，其對應(yīng)的二進制是10010111。而該二進制數(shù)字可以轉(zhuǎn)化為：

所以我們可以這么寫：

所以，該運算過程是這樣的：

• 獲取P
• 取P的2倍，得到2P
• 2P加上P
• 把2P再取2倍，得到4P
• 4P加上2P加上P
• 4P再取2倍，得到8P
• 不取8P做運算
• 8P取2倍，得到16P
• 16P加上4P加上2P加上P
• ……
  最終，要得到151P我們只是做了一些簡單的倍數(shù)以及加法。

如果還是不清楚，可以看看下面的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 >>= 1

def 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

如果倍數(shù)和加法都是復雜度為O(1)的運算，那么該算法的復雜度就是O(log n)（或者O(k)）（考慮到k個bit的長度）。依然比O(n)的復雜度要好。

對數(shù)

給定n和P，我們運算Q=nP至少需要一個多項式時間。但是如果反過來呢？如果我們知道Q和P，要反過來得到n呢？該問題被認為是對數(shù)問題。為了與其他加密算法保持一致性，我們稱該問題為“對數(shù)”問題而非“除法”。

我并不清楚什么是“簡單”的問題，但是從該鏈接里的乘法，很容易看出一些規(guī)則。舉個例子，假設(shè)該曲線是 y2=x3?3x+1（y的2次方，x的3次方），P點是（0，1）。我們很容易驗證得到，如果n是奇數(shù)，nP是在左半邊坐標軸里，如果n是偶數(shù)，nP在右半邊坐標軸里。如果做更多實驗，甚至發(fā)現(xiàn)更多規(guī)則，最終可以寫出算法讓我們計算曲線可以更高效。

但是還有個算法問題：離散數(shù)學問題。在下篇文章里，我們會討論如果我們減少橢圓曲線的域，標量乘法依然是個“簡單”的數(shù)學問題，然而離散數(shù)學變成一個“困難”的數(shù)學問題。這種二元性就是橢圓加密算法的核心。

下篇文章，下周見。

注：該文章翻譯自這里，如果有翻譯不當?shù)牡胤?，請指正?/p>

其他鏈接

blockchain in js