很多人都聽(tīng)說(shuō)過(guò)加密算法街佑，包括ECC茅信、ECDH或者ECDSA似踱。ECC是Elliptic Curve Cryptography的縮寫(xiě)隅熙，就是橢圓加密算法，ECDH和ECDSA是ECC的不同實(shí)現(xiàn)核芽。
橢圓加密算法的應(yīng)用范圍很廣囚戚，主要的三個(gè)技術(shù) TLS、PGP以及SSH 都在使用它轧简，更別提比特幣以及其他加密數(shù)字貨幣了驰坊。
在橢圓加密算法流行之前，絕大多數(shù)的公鑰加密算法都是基于RSA哮独、DSA以及DH這些基于模運(yùn)算的替代加密系統(tǒng)拳芙。這些加密算法在今天依然占據(jù)非常重要的位置察藐。然而，盡管ECC背后的這些算法很容易理解而且廣泛使用舟扎，但是對(duì)于絕大多數(shù)人來(lái)說(shuō)分飞，這些算法是一個(gè)謎團(tuán)。
接下來(lái)的一系列文章：橢圓加密算法（從入門(mén)到放棄）睹限，我將對(duì)該算法做一個(gè)詳細(xì)介紹譬猫。我的目標(biāo)并不是要徹底解釋清楚以及證明背后的數(shù)學(xué)原理，而是做一個(gè)介紹羡疗，講清楚：簡(jiǎn)要解釋ECC删窒，以及為什么ECC被認(rèn)為是安全的。同時(shí)顺囊，也會(huì)給出模擬操作的例子以及腳本幫助你更加理解。
接下來(lái)的幾篇文章會(huì)涉及到：
- 實(shí)數(shù)下的橢圓曲線(xiàn)以及群公理（就是這篇文章啦）
- 有限域下的橢圓曲線(xiàn)以及離散數(shù)學(xué)
- 密鑰對(duì)加解密以及兩種橢圓加密算法：ECDH和ECDSA
- 破解ECC的安全性算法蕉拢，以及同RSA的比較
筆者假設(shè)閱讀這篇文章的讀者已經(jīng)對(duì)以下幾個(gè)概念并不陌生：集合論特碳、幾何學(xué)、模運(yùn)算晕换，并且對(duì)對(duì)稱(chēng)加密和非對(duì)稱(chēng)加密有了一些了解午乓。最后，在加密學(xué)里面闸准，對(duì)于什么是“簡(jiǎn)單”的問(wèn)題益愈，什么是“困難”的問(wèn)題有個(gè)清晰的認(rèn)知。
橢圓曲線(xiàn)
首先：什么是橢圓曲線(xiàn)夷家？Wolfram MathWorld給出了個(gè)準(zhǔn)確非凡的定義橢圓曲線(xiàn)蒸其。但對(duì)于目前的我們來(lái)說(shuō)，橢圓曲線(xiàn)可以暫時(shí)簡(jiǎn)單的理解為描述了特定點(diǎn)的集合的公式：
其中库快，
[圖片上傳失敗...(image-d0bb69-1524474030026)])](http://upload-images.jianshu.io/upload_images/785822-6c9ac5e2d832271e.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/1240)
以下是a和b參數(shù)的變化對(duì)應(yīng)的圖形的示例：
a和b的取值變化決定了曲線(xiàn)在坐標(biāo)系上的不同形狀靠汁。從圖中可以看到，橢圓曲線(xiàn)是相對(duì)X軸對(duì)稱(chēng)闽铐。
為了達(dá)到我們的目的蝶怔，我們還要定義一個(gè)無(wú)窮大的點(diǎn)（也可以成為理想點(diǎn)），從現(xiàn)在開(kāi)始兄墅，我們以符號(hào)0踢星，也就是零表示該點(diǎn)。
把上面幾個(gè)點(diǎn)結(jié)合起來(lái)隙咸，我們的橢圓曲線(xiàn)公式就變成了
群(Groups)
數(shù)學(xué)上斩狱，群(Groups)指的是我們定義了二元操作“運(yùn)算”并且用符號(hào)+表示的一個(gè)集合耳高。假定我們要操作的群用 ??表示，那么我們?cè)谶@個(gè)群上面要定義的“運(yùn)算”必須符合以下幾個(gè)屬性：
- 閉包所踊。如果a和b都是??的成員泌枪，那么a+b也是??的成員。
- 組合性秕岛。(a+b)+c=a+(b+c)
- 單位元碌燕。存在確切的一個(gè)值，稱(chēng)之為單位元继薛，0可以保證該等式成立 a+0=0+a=a
- 逆元修壕。每個(gè)成員都有一個(gè)相反數(shù)：對(duì)于任意值a必定存在b使得a+b=0
如果加上第五條這要求：
- 交換性a+b=b+a
這樣的群我們稱(chēng)之為 阿貝爾群。
根據(jù)以上的定義遏考，我們很容易得知慈鸠，整數(shù)集合 ? 是一個(gè)群，也可以稱(chēng)之為 阿貝爾群灌具。自然數(shù)集合 ? 卻不是一個(gè)群青团，因?yàn)椴环系谒膫€(gè)屬性（自然數(shù)都是整數(shù)，不存在a+b=0）咖楣。
根據(jù)組的這四個(gè)屬性督笆，我們很容易可以推導(dǎo)出其他屬性。比如：第三個(gè)屬性的確切的值0是唯一的诱贿；相反數(shù)也是唯一的娃肿，也就意味著a+b=0，a的相反數(shù)b也是唯一的珠十。這些屬性有助于我們接下去的數(shù)學(xué)邏輯推理料扰。
橢圓曲線(xiàn)里的群公理
如上文所說(shuō)，我們可以基于橢圓曲線(xiàn)定義一個(gè)群焙蹭。特別要指出的是：
- 群里的元素都在橢圓曲線(xiàn)上
- 橢圓上的單位元指的是無(wú)限遠(yuǎn)點(diǎn)
- 橢圓上的點(diǎn)P的逆元與P關(guān)于X軸軸對(duì)稱(chēng)
- 定義+運(yùn)算：給定三個(gè)非零的點(diǎn) P记罚，Q和R，則P+Q+R=0（無(wú)限遠(yuǎn)點(diǎn)）成立
注意：最后一條公理里壳嚎，給出了三個(gè)點(diǎn)桐智，但是沒(méi)有限定順序，也就意味著P+(Q+R)=Q+(P+R)=R+(P+Q)=?=0烟馅。這就充分表明了说庭，這里定義的+運(yùn)算符符合群公理的組合性和交換性，也就意味著橢圓曲線(xiàn)符合阿貝爾群郑趁。
到目前為止刊驴，一切都推理挺順利的，對(duì)吧。那么問(wèn)題來(lái)了捆憎，我們要如何計(jì)算兩個(gè)任意點(diǎn)之和呢舅柜？
幾何學(xué)上的加法
因?yàn)闄E圓曲線(xiàn)是阿貝爾群，所以公式P+Q+R=0 以及 P+Q=?R成立躲惰。根據(jù)這些公式致份，我們可以從幾何學(xué)的角度去計(jì)算點(diǎn)P+點(diǎn)Q的值：在橢圓曲線(xiàn)上畫(huà)出點(diǎn)P和點(diǎn)Q，連直線(xiàn)穿過(guò)P和Q础拨，該直線(xiàn)會(huì)與橢圓曲線(xiàn)相較于第三個(gè)點(diǎn)氮块，稱(chēng)之為R。根據(jù)R取得R的逆元-R诡宗，P+Q=-R滔蝉。
運(yùn)用幾何學(xué)的方法很容易得到我們要的結(jié)果，但是我們需要再對(duì)一些更精確的解釋塔沃。特別是有一些問(wèn)題需要考慮：
- 如果P=0或者Q=0(0是無(wú)窮遠(yuǎn)點(diǎn))呢蝠引？我們當(dāng)然無(wú)法畫(huà)出該直線(xiàn)，因?yàn)闊o(wú)窮遠(yuǎn)點(diǎn)無(wú)法體現(xiàn)在直角坐標(biāo)系里蛀柴。但是既然已經(jīng)定義了無(wú)窮遠(yuǎn)點(diǎn)0螃概，那么對(duì)于任意給定的P或者Q，P+0=P以及0+Q=Q都是成立的名扛。
- 如果P=-Q呢？這種情況下該直線(xiàn)是與X軸是垂直的茧痒，并且不會(huì)與橢圓曲線(xiàn)相交于第三個(gè)點(diǎn)肮韧。 根據(jù)公理，P就是Q的逆元旺订，P+Q=P+(-P)=0弄企。
- 如果P=Q呢？這種情況下区拳，存在無(wú)數(shù)條線(xiàn)穿過(guò)這個(gè)點(diǎn)拘领。這里要用到極限的思維。假設(shè)線(xiàn)上有另外一個(gè)點(diǎn)Q1樱调，讓Q1不斷靠近P约素，會(huì)怎么樣？
隨著Q1不斷靠近P圣猎，最終Q1無(wú)限靠近P，產(chǎn)生了一條直線(xiàn)與橢圓曲線(xiàn)相切乞而。那么可以得到 P+P=-R, 在這里R就是該直線(xiàn)與橢圓曲線(xiàn)的另外一個(gè)交點(diǎn)送悔。
- 如果P≠Q(mào)，但是不存在第三個(gè)交點(diǎn)R呢？這種情況和上一個(gè)情況很類(lèi)似欠啤。實(shí)際上荚藻，這種情況下該直線(xiàn)跟橢圓曲線(xiàn)是相切的關(guān)系。
假設(shè)P就是相切的點(diǎn)洁段。在上一個(gè)情況里应狱，有該等式P+P=-Q。而在這里變成了P+Q=-P眉撵。另一方面侦香，如果Q是相切的點(diǎn)，那么P+Q=-Q纽疟。
我們需要了解的幾何學(xué)只是已經(jīng)差不多涵蓋了所有情況了罐韩。只要給我們筆和尺子，我們就能在橢圓曲線(xiàn)上執(zhí)行加法污朽。如果有興趣散吵，可以到HTML5/JavaScript visual tool計(jì)算橢圓曲線(xiàn)上的加法
代數(shù)上的加法
要計(jì)算點(diǎn)的加法的話(huà)，我們必須把前面的幾何學(xué)的討論轉(zhuǎn)到代數(shù)上的討論蟆肆。最直接的方法是把上面的公理用代數(shù)上的公式表示出來(lái)矾睦，但是這件事情會(huì)很乏味而且需要解決一些三次方程。所以在這里我就只給出結(jié)果吧炎功。
首先枚冗，聲明下我們暫時(shí)不討論一些特殊情況。比如我們已經(jīng)知道了P+(-P)=0蛇损，P+0=0+P=P赁温，所以，接下去我們不考慮這兩種情況淤齐。我們考慮的是 非0股囊，非對(duì)稱(chēng)的點(diǎn) P和Q，如下圖
[聲明下更啄，因?yàn)榫庉嬈鞯膯?wèn)題稚疹，下文中將用P=(xP,yP)(P是下標(biāo))來(lái)表示這種等式，否則一直貼圖排版很累]
如果xP≠xQ(P和Q是下標(biāo))祭务，那么該直線(xiàn)的斜率是：
該直線(xiàn)與橢圓曲線(xiàn)相交的第三個(gè)點(diǎn)R(xR,yR)(R是下標(biāo))：
或者也可以寫(xiě)成：
特別強(qiáng)調(diào)一下 (xP,yP)+(xQ,yQ)=(xR,?yR)（P内狗，Q，R都是下標(biāo)）义锥。
如果要檢查結(jié)果是否正確其屏，我們需要檢查R是否在橢圓曲線(xiàn)上，以及P缨该，Q和R是否都在直線(xiàn)上偎行。檢查這些點(diǎn)是否在直線(xiàn)上是顯而易見(jiàn)的，然而檢查R是否屬于橢圓曲線(xiàn)并不是，因?yàn)槲覀儾坏貌唤鉀Q一個(gè)一點(diǎn)都不有趣的三次方程問(wèn)題蛤袒。
考慮這么一個(gè)例子：根據(jù)我們給出的visual tool熄云，給定的P=（1，2）和Q=（3妙真，4）都在曲線(xiàn)上y2=x3?7x+10（y的2次方缴允，x的3次方），那么P+Q=-R=（-3珍德，2）练般。反過(guò)來(lái)去根據(jù)我們前面的公式驗(yàn)證該結(jié)果是否正確：
驗(yàn)證正確！
注意锈候，即使P或者Q是切點(diǎn)薄料，該等式依然成立。拿P=(-1,4) Q=(1,2)嘗試下：
得到的結(jié)果是P+Q=(1,-2)泵琳，該結(jié)果與用該工具visual tool計(jì)算是一樣的摄职。
另一種情況P=Q則需要另外處理了：關(guān)于xR以及yR的公式是一樣的，但是針對(duì)直線(xiàn)的斜率必須用另外的方式處理：
注意获列，該公式是由一下公式推導(dǎo)出來(lái)的：
為了證明該公式的正確性谷市，有必要驗(yàn)證R是否屬于橢圓曲線(xiàn)上，以及P和R連成的直線(xiàn)與橢圓曲線(xiàn)有且僅有2個(gè)交點(diǎn)击孩。但是在這里迫悠，我們不作證明，先做個(gè)測(cè)試：P=Q=(1,2)
所以得出 P+P=-R=(-1, -4)巩梢。正確
標(biāo)量乘法
除了加法之外创泄，我們定義另外一個(gè)運(yùn)算：標(biāo)量乘法：
在這里n是一個(gè)自然數(shù)。嗯且改，我寫(xiě)了個(gè)visual tool用來(lái)玩標(biāo)量乘法验烧，有興趣點(diǎn)擊去試試吧板驳。
該公式看起來(lái)計(jì)算nP需要計(jì)算n次加法又跛。如果n是k個(gè)二進(jìn)制位，那么該算法復(fù)雜度是O(2k)（2的k次方）若治，計(jì)算量有點(diǎn)大慨蓝。但是其實(shí)存在更快速的方案。
其中一個(gè)就是先做倍數(shù)再做加法端幼。要了解基本原理還是直接看例子會(huì)比較快礼烈。假設(shè)n=151，其對(duì)應(yīng)的二進(jìn)制是10010111婆跑。而該二進(jìn)制數(shù)字可以轉(zhuǎn)化為：
所以我們可以這么寫(xiě)：
所以此熬，該運(yùn)算過(guò)程是這樣的：
- 獲取P
- 取P的2倍，得到2P
- 2P加上P
- 把2P再取2倍，得到4P
- 4P加上2P加上P
- 4P再取2倍犀忱，得到8P
- 不取8P做運(yùn)算
- 8P取2倍募谎，得到16P
- 16P加上4P加上2P加上P
- ……
最終，要得到151P我們只是做了一些簡(jiǎn)單的倍數(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ù)和加法都是復(fù)雜度為O(1)的運(yùn)算，那么該算法的復(fù)雜度就是O(log n)（或者O(k)）（考慮到k個(gè)bit的長(zhǎng)度）搀庶。依然比O(n)的復(fù)雜度要好拐纱。
對(duì)數(shù)
給定n和P，我們運(yùn)算Q=nP至少需要一個(gè)多項(xiàng)式時(shí)間哥倔。但是如果反過(guò)來(lái)呢秸架？如果我們知道Q和P，要反過(guò)來(lái)得到n呢未斑？該問(wèn)題被認(rèn)為是對(duì)數(shù)問(wèn)題咕宿。為了與其他加密算法保持一致性，我們稱(chēng)該問(wèn)題為“對(duì)數(shù)”問(wèn)題而非“除法”蜡秽。
我并不清楚什么是“簡(jiǎn)單”的問(wèn)題府阀，但是從該鏈接里的乘法，很容易看出一些規(guī)則芽突。舉個(gè)例子试浙，假設(shè)該曲線(xiàn)是 y2=x3?3x+1（y的2次方，x的3次方）寞蚌，P點(diǎn)是（0田巴，1）。我們很容易驗(yàn)證得到挟秤，如果n是奇數(shù)壹哺，nP是在左半邊坐標(biāo)軸里，如果n是偶數(shù)艘刚，nP在右半邊坐標(biāo)軸里管宵。如果做更多實(shí)驗(yàn)，甚至發(fā)現(xiàn)更多規(guī)則攀甚，最終可以寫(xiě)出算法讓我們計(jì)算曲線(xiàn)可以更高效箩朴。
但是還有個(gè)算法問(wèn)題：離散數(shù)學(xué)問(wèn)題。在下篇文章里秋度，我們會(huì)討論如果我們減少橢圓曲線(xiàn)的域炸庞，標(biāo)量乘法依然是個(gè)“簡(jiǎn)單”的數(shù)學(xué)問(wèn)題，然而離散數(shù)學(xué)變成一個(gè)“困難”的數(shù)學(xué)問(wèn)題荚斯。這種二元性就是橢圓加密算法的核心埠居。
下篇文章查牌，下周見(jiàn)。
注：該文章翻譯自這里滥壕，如果有翻譯不當(dāng)?shù)牡胤缴猓?qǐng)指正。
