区块链的基石--椭圆曲线密码学

摘要：如果公式解析有问题，请移步备份链接椭圆曲线密码学椭圆曲线密码学是基于椭圆曲线数学的一种公钥加密方法。椭圆曲线数字签名什么是数字签名现实生活中的签名作用是签署者对文件进行授权防止交易中的抵赖发生。

椭圆曲线密码学(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...