摘要：如果公式解析有問題，請移步備份鏈接橢圓曲線密碼學橢圓曲線密碼學是基于橢圓曲線數學的一種公鑰加密方法。橢圓曲線數字簽名什么是數字簽名現實生活中的簽名作用是簽署者對文件進行授權防止交易中的抵賴發生。

橢圓曲線密碼學(ECC, Elliptic Curve Cryptography)是基于橢圓曲線數學的一種公鑰加密方法。

在諸如 DES、AES 這類對稱密碼系統中，信息的發送方使用一把密鑰進行加密，接收方使用相同的密鑰進行解密。
而在公鑰加密方法中，信息的加密和解密使用的密鑰是不同的，稱之為公鑰和私鑰（注：既可以公鑰加密私鑰解密，也可以私鑰加密公鑰解密），常用的公鑰加密方法有

RSA - 基于大因數分解

ECC - 基于橢圓曲線和離散對數

兩者的理論基礎都是數論理論中的單向運算函數,這種函數有一個特點：正方向計算容易，反方向計算卻十分困難。以RSA背后的因數大數分解理論為例：
請完成下面的等式：

$$ 373 * 751 = ？ $$

如果你有草稿紙和筆 ，會發現這并不是很困難，那么如果是下面因數分解呢？

$$ 280123 = ？ * ？ $$

太困難了 ! 即使是使用計算器，我覺得也沒有誰一時半會兒也算不出來。

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

我們在中學課本里一定都學過橢圓的定義。如下圖所示，

橢圓上的點都滿足

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

而密碼學中的橢圓曲線是滿足以下等式的點組成的集合，

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

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

舉個栗子

橢圓曲線

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

包含這些點： $(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$。上面的點除了 $mathscr O$以外，它們是下面曲線上的一些離散的點：

注意：顯然從圖像中可以看出這條曲線是關于 $x$ 軸對稱的，但上面的點的 $y$ 坐標都大于0，這是由于$x,y in Bbb Z_{17}$ 。舉例來說點 $(5,1)$ 和 $(5,16)$實際上就是關于$x$軸對稱的。因為 $16equiv-1 pmod {17} $，而$(5,-1)$也滿足 $ y^2 ≡ x^3+2x+2 pmod {17} quad x,y in Bbb R $。
.

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

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

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

兩個不同的點相加 $P+Q$ 且 $P eq Q$

將 $P$ 和 $Q$ 相連的線段延伸，與橢圓曲線有一個交點，該交點關于$x$軸的對稱點就是所求的$P+Q$

一個點自加 $P+P$

作$P$在橢圓曲線上的切線，這條切線與橢圓曲線有一個交點，該交點關于$x$軸的對稱點就是所求的$2P$

經過一些數學推導，可以得到計算$R(x_3,y_3)$坐標的公式

$$ 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. $$

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

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

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

再以剛才的例子舉例，

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

曲線上的所有點就可以表示為 $P$ 的倍數
$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$

之前提到過，橢圓曲線密碼系統使用離散對數問題(DLP)構建公鑰密碼方法，這體現為以下一個事實：

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

計算一個點由是由哪個數與生成元相乘得到的很困難 $ B = ？P $

類比與我們熟悉的實數域上，指數運算比對數運算容易得多

而這里 $ d $ 就是橢圓曲線密碼系統中的 私鑰，$ B $ 就是公鑰，這也就是為什么可以用私鑰推導出公鑰，反之不行的原因。

secp256k1是以太坊中使用的橢圓曲線，其參數可以點擊Secp256k1 wiki查看，包括橢圓曲線的系數、生成元等。

現實生活中的簽名作用是簽署者對文件進行授權、防止交易中的抵賴發生。

而數字簽名也有這個效果。

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

橢圓曲線數字簽名算法(ECDSA)就是利用橢圓曲線加密方法進行數字簽名的方法。

設我們使用的曲線

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

^注1：這里的$^{-1}$表示在模運算中求逆，在$ Bbb Z_p$中，一個數 $a$ 與它的逆 $a^{-1}$ 滿足 $a cdot a^{-1} equiv 1 pmod p $

由

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

兩邊同時乘以 $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 $$

同時計算對 生成元$A$的數乘,由 $B = dA$ 有

$$ k_EA = u_1A + u_2B $$

即

$$ R = u_1A + u_2B $$

所以只要接收方計算的 $P$ 的 $x$ 坐標等于 $R$ 的 $x$ 坐標 $r$ ，則可說明驗證通過 (之所以看 $x$ 坐標是因為橢圓曲線中，只憑一個點的 $x$ 坐標并不能唯一確定它的 $y$ 坐標)

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

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

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

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

兩邊同時 $A$ 數乘 得到 $R = s^{-1}h(x)A + s^{-1}B $
表示出$B$ 可得 $B= r^{-1}(sR - h(x)A) $
觀察上式可知，只要知道了 $R$ 點坐標，我們就可以算出 $B$ ，但我們沒有 $R$ 點坐標， 不過我們有它的 $x$ 軸坐標 $r$ ^注2 ，我們可以將其代入曲線方程，反解出$R$ 點$y$ 坐標，但由于橢圓曲線是關于 $x$ 軸對稱的，所以我們可以解出兩個符合條件的 $B$

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

注意以下橢圓曲線上的點的計算過程中

數乘運算使用Double-and-Add算法

加法運算代入$P +Q$ 的坐標公式計算

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

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

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

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

當 $R=(7,6)$ 時

$$ 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) $

當 $R=(7,11)$ 時

$$ 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) $

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

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