ECC橢圓曲線加密演算法：介紹

05-21

ECC橢圓曲線加密演算法：介紹

來自專欄橢圓曲線加密演算法和國密演算法

此篇是翻譯，因為寫的太好了！！！已經拿到作者授權，就翻譯了一下，供大家參考。如有不同見解，歡迎提出，我們一起討論，學習就是一個成長的過程啊。

http://andrea.corbellini.name/2015/05/17/elliptic-curve-cryptography-a-gentle-introduction/?

andrea.corbellini.name

現在我們聽說過的公鑰加密有ECC，ECDH 或者 ECDSA。第一個是橢圓曲線加密（Elliptic Curve Cryptography）的縮寫，後兩個演算法是基於它的演算法。

今時今日，我們可以在TLS（Transport Layer Security安全傳輸層協議）,PGP（Pretty Good Privacy基於RSA的郵件加密系統）和SSH（Secure Shell安全外殼協議）中找到橢圓曲線加密系統，這是三項構建了現代Web和IT世界的重要技術，更不用提比特幣和其他數字貨幣加密技術了。

在ECC盛行之前，基本上所有的公鑰加密演算法都是基於RSA,DSA和DH的，其他的加密系統也都是基於模運算的。RSA和他的小夥伴們在今天仍然很重要，而且經常和ECC一起伴隨使用。但是RSA和他的小夥伴們很容易被解釋，也被廣泛的理解了，況且看上去很難實現的東西寫起來還是很容易的，但是ECC對大多數人來說仍舊是個謎。

在這篇文章中，我的目的並不是提供關於ECC完整且細節的指導，我是想提供一個簡單的概略：為什麼ECC被認為是安全的？這裡也不涉及冗長的數學證明或者實現細節。

接下來我會涉及到的文章有：

實數域上的橢圓曲線和群論（本文）。
有限域上的橢圓曲線和離散對數問題。
密鑰對的生成和兩種ECC演算法：ECDH和ECDSA。
破解ECC安全性的演算法，以及和RSA的對比。

為了理解上述文章，你需要先了解一下基礎的集合論，幾何和模運算，而且要熟悉對稱和非對稱加密演算法。最後，你需要很清楚，什麼是「簡單」的問題，什麼是「困難」的問題，以及他們在加密中所扮演的角色。

開始了!

橢圓曲線

首先，什麼是橢圓曲線？Wolfram MathWorld 給出了非常精準的定義：一條橢圓曲線就是一組被 $y^2 = x^3 + ax + b$ 定義的且滿足 $4a^3 + 27b^2 e 0$ 的點集。 $4a^3 + 27b^2 e 0$ 這個限定條件是為了保證曲線不包含奇點(singularities). $y^2 = x^3 + ax + b$ 這個方程稱為橢圓曲線的維爾斯特拉斯標準形式（Weierstrass normal form）。

不同的橢圓曲線對應不同的形狀（b=1，a從2到-3）

奇異點：左圖，帶銳點(式1)；右圖，曲線自交（式2）。他們都不是有效的橢圓曲線

式1： $y^{2} = x^{3}$
式2： $y^{2}=x^{3}-3x+2$

隨著a和b的不同，橢圓曲線也會在平面上呈現出不同的形狀，但他還是很容易辨認的，橢圓曲線始終是關於x軸對稱的。

另外，我們還需要一個無窮處的點（point at infinity/ideal point）作為曲線的一部分，從現在開始，我們將用 0 這個符號表示無窮處的點。如果我們將無窮處的點也考慮進來的話，那麼橢圓曲線的表達式精鍊為：

$left{ (x, y) in mathbb{R}^2 | y^2 = x^3 + ax + b, 4 a^3 + 27 b^2 e 0 ight} cup left{ 0 ight}$

群（Group）

我們在一個集合上定義一個二元運算，這就是數學中的群。比如，二元運算-->「加法」並用符號「+」表示，（可以任意符號任意名字，此處僅為舉例。也可以這麼理解：一個群，由自身的集合和二元運算符『+』組成），為了使集合 $mathbb{G}$ 成為一個群，必須滿足以下四個條件：

封閉性（closure）：如果a和b被包含於 $mathbb{G}$ ，那麼a+b 也一定是 $mathbb{G}$ 的元素。
結合律(associativity)。
存在一個單位元（identity element）0，使得 a+0 = 0+a = a;[單位元：與任意元素運算不改變其值的元素]
每個數都存在一個相反數(inverse)。

如果我們再加上第五個條件：

5. 交換律(commutativity):a+b = b+a.

這個群就叫做阿貝爾群(abelian group)。

從我們通常的加法概念來看，整數集 $mathbb{Z}$ 是一個群（而且是一個阿貝爾群）。自然數集 $mathbb{N}$ 不是一個群，因為它不滿足第4條。

群是非常好的，因為如果我們可以證明這四條屬性，那麼我們可以直接拿來用其他的屬性了。比如，有且只有一個單位元，對應的相反數也是獨一無二的，那麼不論直接還是間接，關於群的所有屬性和結論我們都可以隨意使用。

橢圓曲線上的群論

我們可以在橢圓曲線上定義一個群：

群中的元素就是橢圓曲線上的點。
單位元就是無窮處的點0.
相反數P，是關於X軸對稱的另一邊的點。
加法規則定義如下：取一條直線上的三點（這條直線和橢圓曲線相交的三點），P, Q, R（皆非零），他們的總和等於0，P+Q+R=0。

三個對齊的點的和是0

請注意最後一條規則，我們僅僅說了需要三個在一條直線上的點，並沒有規定他們的順序。這就意味著，如果P, Q, R在一條直線上的話，他們滿足

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的結果。

這個幾何方法非常有用但是還需要再精鍊一下。讓我們來回答一下以下幾個問題：

如果 P = 0或者 Q = 0 呢？很明顯，這樣我們是畫不出線的，無窮遠點0 不在xy平面上。但是我們已經定義了0作為單位元。 P + 0 = P 和 Q + 0 = Q，對於任意的P和Q都適用，單位元的作用就是與任意元素運算不改變其值的元素。
如果P = -Q呢？在這種情況下，穿過兩點的直線是垂直的，沒有相交的第三個點。但是呢，如果P是Q的相反數，然後我們將會從相反數的定義中得到 P+Q=P+(?P)=0。
如果P = Q呢？在這種情況下，有無數條線會經過這個點。我們假設一個點 $Q e P$ . 當Q』越來越接近P的時候會發生什麼？

當兩點越來越接近，穿過兩點的直線將會和曲線相切

【針對這一條我要補充一下：從上文我們知道，P，Q，R三點在一條線上而且沒有先後順序，這是一般情況。當兩個點越來越接近的時候，這條線會成為曲線的一條切線，這條切線與曲線相交的另一點就是R。這樣的線由於橢圓曲線的有山丘山谷的形狀，所以會存在很多條。】

當出現切線這種情況，鑒於此我們可以寫成P+P=?R，R是曲線和切線的交點，P是切點。

如果當P!=Q，但是沒有第三點R呢？這種情況與上一條非常相似。事實上，這種情況就是一條直線穿過P和Q與曲線相切。

如果直線和曲線僅相交於兩點，這意味著直線是曲線的切線。P+Q的結果顯而易見是其中一個點關於X軸的對稱點。

我們可以假設P是切點，在上一個情況下，我們已經說明了P+P=?Q，這個方程現在可以寫成：P+Q=?P。換句話說，Q是切點，標準的寫法是：P+Q=?Q。

幾何方法已經全部講完了並且涵蓋了所有的情況。原創作者Corbellini, Andrea還做了一些小動畫幫助大家理解，鏈接我以前能打開的，今天試了一下打不開了。。。我放在這裡

HTML5/JavaScript visual tool

代數加法

如果我們想要一台計算機能夠運行點的加法 $P = (x_P, y_P)$ ，那我們就需要把幾何方法轉換成代數方法。將一些規則轉換成一系列的方程式看上去是非常直觀的，但是實際上是很枯燥的，因為要算三次方程。出於這個原因，這裡我只放結果。

首先，我們先去掉一些特殊情況，已知：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$ )：

$egin{array}{rcl} x_R & = & m^2 - x_P - x_Q \ y_R & = & y_P + m(x_R - x_P) end{array}$

也可以寫成： $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是否屬於這條曲線就很麻煩了，因為解決一個三次方程，一點樂趣都沒有。

我們來看一個例子：

在曲線 $y^2 = x^3 - 7x + 10$ 上定義兩個點P=(1,2)和Q=(3,4).他們的和是P+Q = -R = (-3,2)。讓我們看一下這個方程是否滿足：

$egin{array}{rcl} 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 + 1 cdot (-3 - 1) = -2 \ & = & y_Q + m(x_R - x_Q) = 4 + 1 cdot (-3 - 3) = -2 end{array}$

是對的。

請注意，這個公式在P和Q其中一個是切點的時候也成立，我們再試一下P=(-1,4)和Q=(1,2)。

$egin{array}{rcl} 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 end{array}$

我們可以得到結果P+Q = (1,-2)。

但是當P=Q的時候有一點點不同，方程中的x_R和y_R是一樣的，但是 $x_P = x_Q$ ,這時我們要用不同的斜率公式：

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

因此，就像我們期望的那樣，m的表達式就是下式的一階導數：

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

證明這個結果的有效性已經足夠去說明R點是否屬於這個曲線，且P，Q所在的直線和這條曲線僅有兩個交點。但是，我們沒法正面突破去證明這個情況，從側面下手，我們用實例檢驗：

P = Q = (1,2)。

$egin{array}{rcl} m & = & frac{3x_P^2 + a}{2 y_P} = frac{3 cdot 1^2 - 7}{2 cdot 2} = -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 end{array}$

最後，P + P = -R = (-1,-4)，對的！

儘管，推導這個答案的過程是無趣的，我們的方程還是很緊湊的。這幸得Weierstrass標準形式：沒有它，這些方程會又複雜又長。

標量積（Scalar multiplication）

除了加法，我們還需定義另一個運算:標量積（數乘），如下：

$nP = underbrace{P + P + cdots + P}_{n ext{times}}$

在這裡，n是一個自然數。

寫成上述式子，可以看出計算nP需要做n次加法。如果n有k位二進位的話，我們的演算法時間複雜度是O( $2^k$ )，這不是一個好的結果。還好還有更好的演算法。

其中一個比較好的演算法是倍加演算法，它的原理用例子解釋如下：

n = 151, 二進位表示： $10010111_2$ ，這個二進位也可以表示成冪次加和：

$egin{array}{rcl} 151 & = & 1 cdot 2^7 + 0 cdot 2^6 + 0 cdot 2^5 + 1 cdot 2^4 + 0 cdot 2^3 + 1 cdot 2^2 + 1 cdot 2^1 + 1 cdot 2^0 \ & = & 2^7 + 2^4 + 2^2 + 2^1 + 2^0 end{array}$

簡化一下：

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

倍加演算法告訴我們的是：

取一個P
倍乘，我們得到2P
2P加P（為了得到 $2^1P + 2^0P$ ）
2*2P，我們得到 $2^2P$
$2^2P$ 加到結果上，（ $2^2P + 2^1P + 2^0P$ ）
2* $2^2P$ ,得到 $2^3P$
扔掉， $2^3P$ 不參加任何加法運算
2* $2^3P$ ,得到 $2^4P$
加到結果上， $(2^4P + 2^2P + 2^1P + 2^0P)$
…

最後，我們計算151P只用了7次倍乘和4次加法。

Python code如下：

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(logn)。（或者是O(k)，如果我們考慮到比特長度的話），這個結果還是非常好的。

對數

對於給定的n和p，我們現在至少有一個多項式最高次冪的演算法來計算Q=nP.那麼反過來呢？如果我們已知Q和P，需要找到n呢？這個問題就是出名的對數問題，我們稱它為「對數」而不是「除」是為了和其他密碼系統保持一致性（用冪來代替乘）。

我不清楚對於這個對數問題是否有「簡單」的演算法。比如，有了曲線 $y^2 = x^3 - 3x + 1$ 和點P=(0,1)，我們可以很快驗證。如果n是奇數，nP在左半平面上；如果n是偶數，nP在右半平面上。當我們測試了更多的點的時候，我們就能找到更多的樣本和經驗，可以帶領我們寫下更有效的解決對數問題的演算法。

還有很多對數問題的變體：離散對數問題。當我們減少橢圓曲線的域，數乘還算是「簡單」，而離散對數問題變成了「難題」。這是橢圓曲線加密演算法的二元性的核心。