摘要：如果公式解析有問(wèn)題，請(qǐng)移步備份鏈接橢圓曲線(xiàn)密碼學(xué)橢圓曲線(xiàn)密碼學(xué)是基于橢圓曲線(xiàn)數(shù)學(xué)的一種公鑰加密方法。橢圓曲線(xiàn)數(shù)字簽名什么是數(shù)字簽名現(xiàn)實(shí)生活中的簽名作用是簽署者對(duì)文件進(jìn)行授權(quán)防止交易中的抵賴(lài)發(fā)生。

橢圓曲線(xiàn)密碼學(xué)(ECC, Elliptic Curve Cryptography)是基于橢圓曲線(xiàn)數(shù)學(xué)的一種公鑰加密方法。

在諸如 DES、AES 這類(lèi)對(duì)稱(chēng)密碼系統(tǒng)中，信息的發(fā)送方使用一把密鑰進(jìn)行加密，接收方使用相同的密鑰進(jìn)行解密。
而在公鑰加密方法中，信息的加密和解密使用的密鑰是不同的，稱(chēng)之為公鑰和私鑰（注：既可以公鑰加密私鑰解密，也可以私鑰加密公鑰解密），常用的公鑰加密方法有

RSA - 基于大因數(shù)分解

ECC - 基于橢圓曲線(xiàn)和離散對(duì)數(shù)

兩者的理論基礎(chǔ)都是數(shù)論理論中的單向運(yùn)算函數(shù),這種函數(shù)有一個(gè)特點(diǎn)：正方向計(jì)算容易，反方向計(jì)算卻十分困難。以RSA背后的因數(shù)大數(shù)分解理論為例：
請(qǐng)完成下面的等式：

$$ 373 * 751 = ？ $$

如果你有草稿紙和筆 ，會(huì)發(fā)現(xiàn)這并不是很困難，那么如果是下面因數(shù)分解呢？

$$ 280123 = ？ * ？ $$

太困難了 ! 即使是使用計(jì)算器，我覺(jué)得也沒(méi)有誰(shuí)一時(shí)半會(huì)兒也算不出來(lái)。

答案是 $373 * 751 = 280123$ ，這就是RSA的理論基礎(chǔ)，兩個(gè)質(zhì)數(shù)(素?cái)?shù))的乘積很容易計(jì)算，但要將一個(gè)這樣的乘積分解回去就困難了。ECC采用的與之類(lèi)似,不同的是它采用的是離散對(duì)數(shù)問(wèn)題(DLP，Discrete Logarithm Problem)制造單向計(jì)算的困難(稍后有例子)。

我們?cè)谥袑W(xué)課本里一定都學(xué)過(guò)橢圓的定義。如下圖所示，

橢圓上的點(diǎn)都滿(mǎn)足

$$ ax^2 + by^2= c quad over , mathbb R $$

而密碼學(xué)中的橢圓曲線(xiàn)是滿(mǎn)足以下等式的點(diǎn)組成的集合，

$$ y^2 equiv x^3 + ax + b pmod p quad x,y in Bbb Z_p $$

加上一個(gè)想象中的無(wú)窮遠(yuǎn)點(diǎn) $mathscr O$ ，其中$x,y$的取值范圍是 $Bbb Z_p = { 1,2,3...p-1}$
注：上面的等式需要滿(mǎn)足 $ 4a^3 + 27b^2 eq 0 pmod p$

舉個(gè)栗子

橢圓曲線(xiàn)

$$ E :quad y^2 ≡ x^3+2x+2 pmod {17} quad x,y in Bbb Z_{17} $$

包含這些點(diǎn)： $(5,1)$ , $(6,3)$ , $(10,6)$ , $(3,1)$ , $(9,16)$ , $(16,13)$ , $(0,6)$ , $(13,7)$ , $(7,6)$ , $(7,11)$ , $(13,10)$ , $(0,11)$ , $(16,4)$ , $(9,1)$ , $(3,16)$ , $(10,11)$ , $(6,14)$ , $(5,16)$ 以及 $mathscr O$。上面的點(diǎn)除了 $mathscr O$以外，它們是下面曲線(xiàn)上的一些離散的點(diǎn)：

注意：顯然從圖像中可以看出這條曲線(xiàn)是關(guān)于 $x$ 軸對(duì)稱(chēng)的，但上面的點(diǎn)的 $y$ 坐標(biāo)都大于0，這是由于$x,y in Bbb Z_{17}$ 。舉例來(lái)說(shuō)點(diǎn) $(5,1)$ 和 $(5,16)$實(shí)際上就是關(guān)于$x$軸對(duì)稱(chēng)的。因?yàn)?$16equiv-1 pmod {17} $，而$(5,-1)$也滿(mǎn)足 $ y^2 ≡ x^3+2x+2 pmod {17} quad x,y in Bbb R $。
.

橢圓曲線(xiàn)上的點(diǎn)構(gòu)成的集合中只有一種運(yùn)算，那就是加法(常數(shù)與點(diǎn)的乘法可以看做多個(gè)加法)，兩個(gè)點(diǎn)可以進(jìn)行加法運(yùn)算得到第三個(gè)點(diǎn)，注意，這里的加法不是簡(jiǎn)單的平面坐標(biāo)系橫縱坐標(biāo)的相加(這樣相加的結(jié)果得到的坐標(biāo)很有可能不在曲線(xiàn)上)。
假設(shè)$P=(x_1,y_1)$和$Q=(x_2,y_2)$ 都在曲線(xiàn)上，如何得到$R=(x_3,y_3)$ 使得

$$ P+Q=R (x_1,y_1)+(x_2,y_2)=(x_3,y_3) $$

我們從幾何學(xué)上定義這種加法，有兩種情況：

兩個(gè)不同的點(diǎn)相加 $P+Q$ 且 $P eq Q$

將 $P$ 和 $Q$ 相連的線(xiàn)段延伸，與橢圓曲線(xiàn)有一個(gè)交點(diǎn)，該交點(diǎn)關(guān)于$x$軸的對(duì)稱(chēng)點(diǎn)就是所求的$P+Q$

一個(gè)點(diǎn)自加 $P+P$

作$P$在橢圓曲線(xiàn)上的切線(xiàn)，這條切線(xiàn)與橢圓曲線(xiàn)有一個(gè)交點(diǎn)，該交點(diǎn)關(guān)于$x$軸的對(duì)稱(chēng)點(diǎn)就是所求的$2P$

經(jīng)過(guò)一些數(shù)學(xué)推導(dǎo)，可以得到計(jì)算$R(x_3,y_3)$坐標(biāo)的公式

$$ x_3 = s^2?x_1?x_2 pmod p y_3 = s(x_1?x_3)?y_1 pmod p $$

其中

$$ s = left{egin{matrix} frac{y_1-y_2}{x_1-x_2} pmod p ; quad P eq Q frac{3x_{1}^{2} + a}{2y_{1}} pmod p ; quad P = Q end{matrix} ight. $$

還有幾個(gè)公式，對(duì)于$ P(x_p,y_p)$

$$ P+mathscr O = P P+(-P) = mathscr O -P = (x_p , p-y_p ) $$

橢圓曲線(xiàn)上所有點(diǎn)加上$ mathscr O$ 包含了很多循環(huán)子群(cyclic subgroups) ，其中一個(gè)循環(huán)子群就是自身，本文僅考慮這種情形。
循環(huán)子群中的 生成元(Generator)也被稱(chēng)作素元(primitive element)，通過(guò)不斷自加，它可以“生成”群眾其他所有元素。那么對(duì)本文來(lái)說(shuō)，就是橢圓曲線(xiàn)上的一個(gè)點(diǎn)$P$，通過(guò)不斷自加，它可以生成橢圓曲線(xiàn)上所有點(diǎn)。
即橢圓曲線(xiàn)上 = ${ P、2P、3P、....nP}$，其中$n$為循環(huán)子群的階。

再以剛才的例子舉例，

$$ E :quad y^2 ≡ x^3+2x+2 pmod {17} quad x,y in Bbb Z_{17} $$

曲線(xiàn)上的所有點(diǎn)就可以表示為 $P$ 的倍數(shù)
$P=(5,1)quad 2P=(6,3)quad3P=(10,6)quad4P=(3,1)quad5P=(9,16)quad6P=(16,13)quad 7P=(0,6) $
$8P=(13,7)quad9P=(7,6)quad10P=(7,11)quad11P=(13,10)quad12P=(0,11)quad13P=(16,4)$
$14P=(9,1)quad15P=(3,16)quad16P=(10,11)quad17P=(6,14)quad18P=(5,16)quad19P=mathscr O$

之前提到過(guò)，橢圓曲線(xiàn)密碼系統(tǒng)使用離散對(duì)數(shù)問(wèn)題(DLP)構(gòu)建公鑰密碼方法，這體現(xiàn)為以下一個(gè)事實(shí)：

計(jì)算生成元與一個(gè)數(shù)$ d $的乘積很容易 $ dP =？ $ 很容易 (Double-and-Add算法)

計(jì)算一個(gè)點(diǎn)由是由哪個(gè)數(shù)與生成元相乘得到的很困難 $ B = ？P $

類(lèi)比與我們熟悉的實(shí)數(shù)域上，指數(shù)運(yùn)算比對(duì)數(shù)運(yùn)算容易得多

而這里 $ d $ 就是橢圓曲線(xiàn)密碼系統(tǒng)中的 私鑰，$ B $ 就是公鑰，這也就是為什么可以用私鑰推導(dǎo)出公鑰，反之不行的原因。

secp256k1是以太坊中使用的橢圓曲線(xiàn)，其參數(shù)可以點(diǎn)擊Secp256k1 wiki查看，包括橢圓曲線(xiàn)的系數(shù)、生成元等。

現(xiàn)實(shí)生活中的簽名作用是簽署者對(duì)文件進(jìn)行授權(quán)、防止交易中的抵賴(lài)發(fā)生。

而數(shù)字簽名也有這個(gè)效果。

Bob將原文$x$用特定Hash函數(shù)生成摘要$h$， 用私鑰加密$h$生成簽名$s$，將原文$x$和摘要$s$一起傳送給Alice。Alice收到后$x"$和$s’$，然后用相同的Hash函數(shù)將收到消息$x"$生成摘要$h"$，用Bob的公鑰進(jìn)行解密得到簽名$s’$，如果$s = s’$ 則表示消息是完整的，在傳輸過(guò)程中沒(méi)有修改。

橢圓曲線(xiàn)數(shù)字簽名算法(ECDSA)就是利用橢圓曲線(xiàn)加密方法進(jìn)行數(shù)字簽名的方法。

設(shè)我們使用的曲線(xiàn)

$$ y^2 equiv x^3 + ax + b pmod p quad x,y in Bbb Z_p $$ , 其生成元$A$的階數(shù)為$q$，`私鑰`為$d$，則`公鑰`$B = dA$ ####發(fā)送方簽名 1. 選擇一個(gè)隨機(jī)的key $k_E$，滿(mǎn)足$0`注1` 2. 計(jì)算 $u_2 equiv s^{-1} cdot r pmod q $ 3. 計(jì)算 $P = u_1A + u_2B $ 4. 進(jìn)行驗(yàn)證 $$ x_P = left{ egin{array}{lr} equiv r pmod q ightarrow 簽名有效 otequiv r pmod q ightarrow 簽名無(wú)效 end{array} ight. $$

^注1：這里的$^{-1}$表示在模運(yùn)算中求逆，在$ Bbb Z_p$中，一個(gè)數(shù) $a$ 與它的逆 $a^{-1}$ 滿(mǎn)足 $a cdot a^{-1} equiv 1 pmod p $

由

$$ s equiv (h(x) + d cdot r)k_E^{-1} pmod q $$

兩邊同時(shí)乘以 $k_E cdot s^{-1}$ 可得

$$ k_E equiv s^{-1}(h(x) + d cdot r) pmod q $$

然后

$$ k_E equiv s^{-1}h(x) + d cdot s^{-1} cdot r pmod q $$

即

$$ k_E equiv u_1 + u_2d pmod q $$

同時(shí)計(jì)算對(duì) 生成元$A$的數(shù)乘,由 $B = dA$ 有

$$ k_EA = u_1A + u_2B $$

即

$$ R = u_1A + u_2B $$

所以只要接收方計(jì)算的 $P$ 的 $x$ 坐標(biāo)等于 $R$ 的 $x$ 坐標(biāo) $r$ ，則可說(shuō)明驗(yàn)證通過(guò) (之所以看 $x$ 坐標(biāo)是因?yàn)闄E圓曲線(xiàn)中，只憑一個(gè)點(diǎn)的 $x$ 坐標(biāo)并不能唯一確定它的 $y$ 坐標(biāo))

以曲線(xiàn) $E： y^2 equiv x^3 + 2x + 2 pmod {17} $ 為例，生成元 $A = (5,1)$

在上面的例子中，Bob 首先需要向 Alice 告知它的公鑰，但實(shí)際上，我們憑簽名 $(r,s)$ 就恢復(fù)出公鑰， 在以太坊中使用 /crypto/secp256k1/secp256.go 中的 RecoverPubkey()函數(shù)完成這一功能。

接收方收到的信息包括原文和簽名： $(x, (r, s))$ ，從 $x$ 可以計(jì)算出 $h(x)$ ，除此之外接收方就只知道橢圓曲線(xiàn)的參數(shù)了，如$(a, b, p, q, A)$ ,要注意它不知道 $(d, k_E)$，而我們的目標(biāo)是在不知道 $d$ 的情況下求出 $B$。

由之前推導(dǎo)出的下式開(kāi)始 $ k_E equiv s^{-1}h(x) + d cdot s^{-1} cdot r pmod q $

兩邊同時(shí) $A$ 數(shù)乘 得到 $R = s^{-1}h(x)A + s^{-1}B $
表示出$B$ 可得 $B= r^{-1}(sR - h(x)A) $
觀(guān)察上式可知，只要知道了 $R$ 點(diǎn)坐標(biāo)，我們就可以算出 $B$ ，但我們沒(méi)有 $R$ 點(diǎn)坐標(biāo)， 不過(guò)我們有它的 $x$ 軸坐標(biāo) $r$ ^注2 ，我們可以將其代入曲線(xiàn)方程，反解出$R$ 點(diǎn)$y$ 坐標(biāo)，但由于橢圓曲線(xiàn)是關(guān)于 $x$ 軸對(duì)稱(chēng)的，所以我們可以解出兩個(gè)符合條件的 $B$

^注2：我們這里忽略 $ r < p - q $ 的情景，這種情況很罕見(jiàn)(在Secp256k1曲線(xiàn)中，大約是 $2^{-128}$)，在這種情況下 ，有兩個(gè)$x_R$都能滿(mǎn)足條件。

注意以下橢圓曲線(xiàn)上的點(diǎn)的計(jì)算過(guò)程中

數(shù)乘運(yùn)算使用Double-and-Add算法

加法運(yùn)算代入$P +Q$ 的坐標(biāo)公式計(jì)算

以剛才的橢圓曲線(xiàn)數(shù)字簽名為例,Alice 收到Bob帶有簽名的消息時(shí)，她自己有以下信息 (沒(méi)有了Bob的公鑰 $B$ )

橢圓曲線(xiàn)參數(shù) $E :quad y^2 ≡ x^3+2x+2 pmod {17} quad x,y in Bbb Z_{17} $ 生成元 $A = (5, 1) $ 階數(shù) $q = 19$。

$(r, s) = (7, 17) quad h(x) = 26 $

計(jì)算 $h(x)A = 26*(5,1) = (0,6) $
由 $ r = 7 $ ， $ 7 *11 equiv 1 pmod {19}$ 得到 $r^{-1} equiv 11 pmod {19} $
再將 $ r = 7 $ ，代入曲線(xiàn)方程，得到 $R$ 點(diǎn)的坐標(biāo)為 $(7,6)$ 或 $(7,11)$

當(dāng) $R=(7,6)$ 時(shí)

$$ sR = 17*(7,6) = (5, 1) $$

所以 $B= r^{-1}(sR - h(x)A) = 11((5,1) - (0,6)) = 11((5,1) + (0,11)) = 11(16, 4) = (7,11) $

當(dāng) $R=(7,11)$ 時(shí)

$$ sR = 17*(7,11) = (5, 16) $$

所以 $B= r^{-1}(sR - h(x)A) = 11((5,16) - (0,6)) = 11((5,16) + (0,11)) = 11(13, 10) = (0,6) $

最終我們可以得到 兩個(gè)符合條件的公鑰 $B = (7,11)$ 和 $B = (0,6)$ , 而無(wú)論是哪一個(gè)都可以得出相同的簽名

[1] Understanding Cryptography, Christof Paar / Jan Pelzl
[2] https://en.bitcoin.it/wiki/Se...