上一篇文章(《曲線上的“加密貨幣”(一)》)介紹了Bitcoin網(wǎng)絡(luò)中對(duì)ECC的使用，說(shuō)明了支付時(shí)解鎖腳本與鎖定腳本的執(zhí)行過(guò)程，結(jié)尾處留了幾個(gè)問(wèn)題，這些問(wèn)題的答案就在橢圓曲線加密的機(jī)制中。

公鑰加密體系中，最重要的就是通過(guò)一個(gè)數(shù)學(xué)難題生成密鑰對(duì)，這個(gè)數(shù)學(xué)難題使得從私鑰生成公鑰很容易，而從公鑰反推出私鑰很難。傳統(tǒng)的公鑰加密體系(如RSA)中，使用的數(shù)學(xué)難題是整數(shù)的因式分解，即兩個(gè)素?cái)?shù)求其乘積很容易，而從其乘積通過(guò)因式分解找到對(duì)應(yīng)的兩個(gè)素?cái)?shù)因子很難。橢圓曲線加密中使用的數(shù)學(xué)難題則是橢圓曲線在有限域上的離散對(duì)數(shù)問(wèn)題。

(......前方高能預(yù)警，一大波數(shù)學(xué)概念和公式來(lái)襲......)

迪卡爾建立解析幾何后，我們都知道直線、曲線等幾何對(duì)象可以用代數(shù)方程表式，如直線可以由一次方程表示，圓錐曲線可以由二次方程表示：
直線:

橢圓:

那橢圓曲線的方程式是什么樣的呢？它可以由三次方程表示:

它對(duì)應(yīng)的圖形大致是(a、b的值不同時(shí)，形狀將不一樣):

從圖中看，橢圓曲線與橢圓相差很遠(yuǎn)，為什么叫它橢圓曲線呢？實(shí)際上是因?yàn)闄E圓曲線的方程式正好是橢圓周長(zhǎng)公式中積分表達(dá)式分母的平方：

為了進(jìn)一步理解橢圓曲線上點(diǎn)與點(diǎn)之間的關(guān)系，數(shù)學(xué)上抽象了橢圓曲線的群(Group)，規(guī)定:

1. 群里的元素均是橢圓曲線上的點(diǎn)；
2. 群的零元是無(wú)窮遠(yuǎn)點(diǎn)；
3. 群中元素的逆元是該點(diǎn)在曲線上關(guān)于x軸的對(duì)稱(chēng)點(diǎn)；
4. 群中元素P、Q和R如果在一條直線上，則 P + Q + R = 0。

由于 4 中P、Q和R在一條直線上與其順序無(wú)關(guān)，故很容易證明群中的加法運(yùn)算滿足交換律和結(jié)合律，因而橢圓曲線上的群是一個(gè)加群，或者Abel群，即它的加法運(yùn)算與我們實(shí)數(shù)的加法形式完全一樣。那么橢圓曲線群中的加法是什么樣的呢？根據(jù)上述第 4 條:

即點(diǎn) P 與點(diǎn) Q 相加的結(jié)果是點(diǎn) R 在群中的逆元，我們?cè)?3 中定義群中的逆元是點(diǎn)關(guān)于 x 軸的對(duì)稱(chēng)點(diǎn)，所以 P + Q 就是指連接 P 和 Q 的直線與曲線的交點(diǎn)R關(guān)于 x 軸的對(duì)稱(chēng)點(diǎn)R'，如圖所示：

特別地，當(dāng) P = Q 時(shí)，P 與 Q 的連線即為曲線在 P 點(diǎn)的切線；當(dāng) P = -Q 時(shí)，P、Q的連線與x軸垂直，其與曲線的交點(diǎn)在無(wú)窮遠(yuǎn)點(diǎn)， P + Q = 0；當(dāng) P = 0 或者 Q = 0 時(shí)，P 與 Q 的連線為 Q 或者 P 與無(wú)窮遠(yuǎn)點(diǎn)的連線，其與x軸垂直，故與曲線的交點(diǎn)位于 -Q 或者 -P，所以 P + Q = Q (P = 0) 或者 P (Q = 0)。

這樣，橢圓曲線代數(shù)加法運(yùn)算與實(shí)數(shù)的加法運(yùn)算完全一致，而且與其幾何意義完全對(duì)應(yīng)起來(lái)。很自然地，我們得到群的點(diǎn)乘(或者標(biāo)量乘法，Scalar multiplication):

其中n為自然數(shù)。它的幾何意義如下:

即以點(diǎn)P作曲線的切線，切線與曲線相交于R(-2P)，R 關(guān)于 x 軸的對(duì)稱(chēng)點(diǎn)即是點(diǎn)2P，在點(diǎn)2P處作切線，按相同方法可以找到點(diǎn)4P、8P等。如果連接點(diǎn)2P與P，直線與曲線相交于點(diǎn)-3P，其x軸的對(duì)稱(chēng)點(diǎn)是3P，如此循環(huán)下去可以得到點(diǎn) nP。代數(shù)求解點(diǎn)R的坐標(biāo)，就是求解直線方程與橢圓曲線的方程組，這在中學(xué)數(shù)學(xué)中反復(fù)練習(xí)過(guò)，這里不再贅述。定義完點(diǎn)乘運(yùn)算后，我們就可以定義橢圓曲線的對(duì)數(shù)問(wèn)題了:

已知曲線、點(diǎn)P 和 Q，如何求n。這是一個(gè)難題。當(dāng)已經(jīng)知道n和P的時(shí)候，我們通過(guò)上面的點(diǎn)乘運(yùn)算，容易求得點(diǎn)Q。但知道P和Q，求n很難。就是說(shuō): 給了你一條曲線和起始點(diǎn)P，規(guī)定了每一次加P后點(diǎn)的位置，當(dāng)告訴你最后點(diǎn)的位置時(shí)，你無(wú)法知道作了多少次加法，除非你遍歷所有i*P(0<i<n)，找到正好對(duì)應(yīng)最后點(diǎn)位置的i值。

然而，當(dāng)橢圓曲線應(yīng)用到計(jì)算機(jī)加密領(lǐng)域時(shí)，不能在整個(gè)實(shí)數(shù)域來(lái)取點(diǎn)或者運(yùn)算，而需將其“映射”到一個(gè)元素個(gè)數(shù)或者點(diǎn)的個(gè)數(shù)有限的集合中(離散化)。當(dāng)我們對(duì)橢圓曲線方程兩邊對(duì)素?cái)?shù)p取模時(shí)(模運(yùn)算不展開(kāi)說(shuō)明了)，就定義了一個(gè)有限域F(p)：

這樣，在F(p)中的曲線的點(diǎn)的個(gè)數(shù)就不再是無(wú)限多個(gè)了，而是有限個(gè)數(shù)N，它是有限域中曲線群的階。在有限域上的曲線不再是連續(xù)的，而是分散的點(diǎn)，如圖(可以通過(guò)鏈接演示橢圓曲線在實(shí)數(shù)域和有限域的加法和乘法):

一個(gè)有限域F(p)類(lèi)似于一個(gè)有理數(shù)集合，有自己的加法、乘法、除法、單位元(1)，零元(0)，并滿足交換率和分配率。值得注意的是，這里的p必須是素?cái)?shù)，否則不能滿足有限域內(nèi)的所有元素均有乘法逆元素(multiplicative inverse)，即不能實(shí)現(xiàn)除法。

顯然，F(xiàn)(p)中的曲線仍然是一個(gè)加群，即上述連續(xù)實(shí)數(shù)域上的加法和點(diǎn)乘運(yùn)算仍然適用，但不再有直觀的幾何意義了。特別地，在有限域F(p)中的曲線上點(diǎn)的點(diǎn)乘將呈現(xiàn)周期循環(huán)特性，即存在最小整數(shù)n，使得：

點(diǎn)集{0, G, ..., (n-1)G}，構(gòu)成了一個(gè)循環(huán)子群(Subgroup)，n為該 子群的階(Order)，它是曲線在F(p)中的點(diǎn)的個(gè)數(shù)N的因子，點(diǎn)G即為該循環(huán)子群的生成點(diǎn)(Base Point)。需要注意的是，實(shí)際中確定一個(gè)子群的生成點(diǎn)時(shí)，是通過(guò)找到N的一個(gè)素?cái)?shù)因子n(必須是素?cái)?shù)，否則不能用于ECDSA，因?yàn)闊o(wú)法求乘法逆元素)，即確定了子群的階，然后計(jì)算子群的余子式(Cofactor)h=N/n，再?gòu)那€上任選一點(diǎn)P，計(jì)算當(dāng)滿足h*P != 0時(shí)，G=hP，從而確定生成點(diǎn)。(想想為什么呢？提示: NP=0)

好了，到這里我們就可以確定一條ECC上用到的曲線了，它通過(guò)六個(gè)參量描述:

其中，p為定義有限域F(p)大小的素?cái)?shù)，a、b為橢圓曲線方程的系數(shù)，n、h、G定義了曲線的一個(gè)循環(huán)子群，它的階為n(即元素個(gè)數(shù))，余子式為h(即曲線的點(diǎn)個(gè)數(shù)與子群的點(diǎn)的個(gè)數(shù)的比值)，生成點(diǎn)為G(即子群中的點(diǎn)為kG, 0<= k < n)。

那么在有限域上的數(shù)學(xué)難題與連續(xù)實(shí)數(shù)域上的數(shù)學(xué)難題有變化嗎？基本上沒(méi)有，只是引入了模運(yùn)算，就是我們文章開(kāi)始提到的離散對(duì)數(shù)問(wèn)題，即已知T和子群中一點(diǎn)：

如何求得k的問(wèn)題。這是一個(gè)難題，也是橢圓曲線能用于現(xiàn)代加密的原因。

到此，我們介紹了用于ECC的有限域F(p)中的橢圓曲線及其離散對(duì)數(shù)問(wèn)題，自然地，可以根據(jù)離散對(duì)數(shù)問(wèn)題來(lái)生成密鑰對(duì)。

1. 首先，從{0,1,...... ,n-1}中隨機(jī)選擇一個(gè)數(shù) d 作為私鑰；
2. 然后，通過(guò) Q=dG 計(jì)算出公鑰Q。

生成完畢后的密鑰對(duì)可以與DH密鑰交換算法結(jié)合形成ECDH算法，密鑰交換后可以用AES或者DES等加密，類(lèi)似于TLS加密過(guò)程。由于“加密貨幣”中主要使用ECDSA，接下來(lái)主要介紹使用橢圓曲線生成的密鑰對(duì)進(jìn)行數(shù)字簽名及驗(yàn)證簽名的機(jī)制。

到此，我們已經(jīng)回答了前文中提到如何從私鑰生成公鑰的問(wèn)題?，F(xiàn)在沒(méi)有確切數(shù)學(xué)證明解上述離散對(duì)數(shù)問(wèn)題是一個(gè)“難題”，但現(xiàn)有條件及算法均不可能在有效時(shí)間內(nèi)求解，所以我們可以說(shuō)從公鑰破解私鑰是很難的。在介紹完ECDSA后，我們就可以回答為什么前述的Android漏洞會(huì)導(dǎo)致私鑰泄露了。

介紹ECDSA時(shí)，我們要請(qǐng)出Alice和Bob了。假如Alice根據(jù)上述橢圓曲線生成了私鑰d(A)和公鑰Q(A)，她將向Bob發(fā)送消息m，并對(duì)該消息簽名；Bob知道Alice的公鑰Q(A)，他收到Alice的簽名消息后，要對(duì)該消息進(jìn)行驗(yàn)證，看是否是Alice發(fā)送的和有沒(méi)有被篡改。Alice和Bob均采用相同的橢圓曲線參數(shù)(p, a, b, n, h, G)。Alice發(fā)送簽名消息時(shí)，將:

1. 對(duì)消息m進(jìn)行安全Hash(如SHA-2)，然后截取Hash后的數(shù)據(jù)的左邊n bit，得到一個(gè)整數(shù)z;
2. 從 {0,1,...... ,n-1} 中安全隨機(jī)地選擇整數(shù)k;
3. 計(jì)算點(diǎn)

4. 計(jì)算

，如果 r=0，則回到步驟 2 重新計(jì)算;

5. 計(jì)算

，k^-1便是 k mod n 的乘法逆元素;

6. 如果s=0，再回到步驟 2 重新計(jì)算.

經(jīng)過(guò)上述計(jì)算后，Alice得到了對(duì)消息m的簽名(r, s)，將該簽名與消息m一并發(fā)送給Bob，Bob收到后將作如下驗(yàn)證:

1. 驗(yàn)證收到的r和s是否在{0,1, ...... ,n-1}范圍內(nèi);
2. 按照和Alice相同的安全Hash函數(shù)對(duì)m進(jìn)行Hash，并截取左邊n位得到整數(shù)z;
3. 計(jì)算

4. 計(jì)算

5. 計(jì)算點(diǎn)

，Q(A)為Alice的公鑰;

6. 如果r = x(p) mod n，則說(shuō)明簽名是真實(shí)的，否則簽名或者消息被篡改。

通過(guò)幾步代數(shù)替換，很容易證明上述驗(yàn)證過(guò)程:

可以看出，Bob計(jì)算出的P(x(p), y(p))與Alice計(jì)算出來(lái)的完全一樣，如果傳輸過(guò)程中，r,s,m中有被篡改的或者s不是由Alice的私鑰計(jì)算出來(lái)的，那上述等式不可能成立，Bob對(duì)簽名的驗(yàn)證將失敗。值得注意的是，簽名中的r與選擇的隨機(jī)數(shù)是強(qiáng)相關(guān)的，它必須是密碼學(xué)安全隨機(jī)的，我們來(lái)看看如果這個(gè)k不變會(huì)發(fā)生什么:

1. Alice對(duì)消息m1(對(duì)應(yīng)的Hash摘要為z1)，生成一個(gè)簽名(r1, s1);
2. Alice對(duì)消息m2(對(duì)應(yīng)的Hash摘要為z2)，生成一個(gè)簽名(r2, s2);

Bob收到兩次消息及簽名后，可以這樣做:

1. 因?yàn)?k 是不變的，所以Alice在簽名過(guò)程中計(jì)算的點(diǎn) P(x(p), y(p))也是一樣的，Blob收到的 r 也是一樣的，即 r1 = r2;
2. Bob計(jì)算:

容易得到:

將k代入:

可以得到:

這樣，接收方Bob便竊取了Alice的私鑰。所以在簽名時(shí)保證k在密碼學(xué)安全上的隨機(jī)性是十分關(guān)鍵的。前述的Android漏洞就是其4.2版本之前的安全隨機(jī)數(shù)生成器SecureRandom未初始化，ECDSA中選取隨機(jī)數(shù)時(shí)不能保證其隨機(jī)性，使得每次簽名時(shí)用的k值一樣，很容易被接收方反推出發(fā)送方的私鑰。這種攻擊方式就是旁路攻擊(side attack)的一種。

Bitcoin網(wǎng)絡(luò)中選擇的曲線是secp256k1，即曲線子群階 n 的長(zhǎng)度為256 bit，在現(xiàn)有算法和計(jì)算能力下，采取正面碰撞破解，大致需要2^71(2的71次方)年。隨著量子計(jì)算機(jī)的發(fā)展，通過(guò)量子計(jì)算有可能將計(jì)算時(shí)間縮短到可接受范圍，但目前還沒(méi)有實(shí)用的量子計(jì)算機(jī)，也許隨著量子計(jì)算的發(fā)展，人們會(huì)找到新的加密方法。了解了ECC加密和簽名的機(jī)制后，大家應(yīng)該對(duì)Bitcoin網(wǎng)絡(luò)的安全性有了合理的信心，那你會(huì)選擇使用它嗎？