python椭圆曲线加密算法_区块链的基石--椭圆曲线密码学

椭圆曲线密码学

椭圆曲线密码学(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 \neq 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$轴对称的。因为 $16\equiv-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 \neq 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\{\begin{matrix}

\frac{y_1-y_2}{x_1-x_2} \pmod p ; \quad P \neq Q \\

\frac{3x_{1}^{2} + a}{2y_{1}} \pmod p ; \quad P = Q

\end{matrix}\right.

$$

还有几个公式，对于$ 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是以太坊中使用的椭圆曲线，其参数可以点击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

2. 计算 $R = k_EA$

3. 令 $r \equiv x_R \pmod p $ ,即 $r$ 为 $R$ 的 $x$ 坐标对 $p$ 求模

4. 计算 $s \equiv (h(x) + d \cdot r)k_E^{-1} \pmod q $

则生成的 $(r,s)$ 就是数字签名。之后发送方将 $(s,(r,s))$ 发送给接收方

####接收方验证

1. 计算 $u_1 \equiv s^{-1} \cdot h(x) \pmod q $ ^`注1`

2. 计算 $u_2 \equiv s^{-1} \cdot r \pmod q $

3. 计算 $P = u_1A + u_2B $

4. 进行验证 $$ x_P = \left\{

\begin{array}{lr}

\equiv r \pmod q \rightarrow 签名有效 \\

\not\equiv r \pmod q \rightarrow 签名无效

\end{array}

\right.

$$

注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$都能满足条件。

例子

注意以下椭圆曲线上的点的计算过程中

加法运算代入$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...