Elliptic Curve Cryptography

Table of Contents

1 实数域上的椭圆曲线

在实数域上,椭圆曲线(Elliptic curve)的定义(“Weierstrass normal”形式)如下:
\[y^2 = x^3 + ax + b \tag{Weierstrass normal form for elliptic curves}\]
其中, \(a,b\) 为实数,且需满足 \(4a^3 + 27b^2 \neq 0\) ,这个不等式约束是为了保证曲线上所有点都是非奇异的(或称为光滑的)。显然,“Weierstrass normal”形式的椭圆曲线是关于 \(x\) 轴对称的。

当 \(a,b\) 取不同值时,椭圆曲线的形状实例如图 1 所示。

ecc_over_read_number.gif

Figure 1: 当 \(a,b\) 取不同值时,椭圆曲线的形状变化(摘自:Wolfram MathWorld

1.1 椭圆曲线上的加法运算


前面我们已经展示过几个椭圆曲线的图像,但点与点之间好像没有什么联系。我们能不能建立一个类似于在实数轴上加法的运算法则呢?数学家们定义了一个这样的运算法则。

椭圆曲线上两个点“加法”算法的定义: 任意取椭圆曲线上两点 \(P\) 和 \(Q\) (若 \(P\) 和 \(Q\) 两点重合,则做 \(P\) 点的切线)做直线交于椭圆曲线的另一点 \(R'\) ,过 \(R'\) 做 \(y\) 轴的平行线交于 \(R\) 。我们定义点 \(R\) 就是点 \(P\) 和 \(Q\) 相加的结果,记为: \(P+Q=R\) 。

椭圆曲线上两个点加法运算的例子如图 23 所示。

ecc_add_example1.gif

Figure 2: 加法实例(不同点相加): \(R=P+Q\)

ecc_add_example2.gif

Figure 3: 加法实例(相同点相加): \(R=P+P=2P\)

注1:我们称 \(y\) 轴的平行线与椭圆曲线的两个交点互为“负元”,图 23 的例子中 \(-R=R'\) 。
注2: \(k\) 个相同的点 \(P\) 相加,我们记作 \(kP\) ,如图 3 例子中有 \(R=2P\) ,再如图 4 例子中有 \(P+P+P=2P+P=3P\) 。

ecc_add_example3.gif

Figure 4: \(P+P+P=2P+P=3P\)

1.2 加法运算公式

前面介绍了椭圆曲线上加法运算的定义,这节介绍它的计算公式。需要注意的是椭圆曲线上的加法不是实数中普通的加法,而是从普通加法中抽象出来的加法,他具备普通加法的一些性质,但其运算规则显然与普通加法不同。

设有椭圆曲线 \(y^2 = x^3 + ax + b\) ,点 \(P=(x_P,y_P)\) 和 \(Q=(x_Q,y_Q)\) 是椭圆曲线上的两点,求 \(P+Q\) 。

把点 \(P+Q\) 记为 \(R=(x_R,y_R)\) ,当点 \(P\) 和点 \(Q\) 是不同点时(不考虑 \(x_P = x_Q\) 的特殊情况),记斜率 \(m=\frac{y_P - y_Q}{x_P - x_Q}\) ,过这两点直线为:
\[y=m (x - x_Q) + y_Q\]
由椭圆曲线上加法运算的定义知, \(P=(x_P,y_P),Q=(x_Q,y_Q),-R=R'=(x_R, -y_R)\) 三点共线,从而这三点的坐标满足下面方程组:
\[\begin{cases} y^2 = x^3 + ax + b \\ y=m (x - x_Q) + y_Q \\ \end{cases}\]
求解方程组可得 \(R\) 的坐标为:
\[\begin{cases} x_R & = m^2 - x_P - x_Q \\ y_R & = - m (x_R - x_P) - y_P \\ \end{cases}\]
当点 \(P\) 和点 \(Q\) 是同一点时,按照定义,我们需要先求过 \(P\) 点的切线,再求切线与椭圆曲线联立方程组求得交点 \(-R=R'=(x_R, -y_R)\) ,详细过程省略,这里直接给出结论:很巧的是,它也可以化为上面的形式(即和点 \(P,Q\) 是不同点的形式相同),不过此时式中的 \(m = \frac{3 x^2_P + a}{2y_P}\) 。

总结,椭圆曲线 \(y^2 = x^3 + ax + b\) 上加法运算 \((x_R,y_R) = (x_P,y_P) + (x_Q,y_Q)\) 的计算公式:
\[\begin{cases} x_R & = m^2 - x_P - x_Q \\ y_R & = - m (x_R - x_P) - y_P \\ \end{cases}\]
上式中,当点 \(P\) 和点 \(Q\) 是不同点时 \(m=\frac{y_P - y_Q}{x_P - x_Q}\) ,当点 \(P\) 和点 \(Q\) 是同一点时 \(m = \frac{3 x^2_P + a}{2y_P}\) 。

1.2.1 加法运算实例

设有椭圆曲线 \(y^2 = x^3 -7x + 10\) ,椭圆上两点 \(P = (1,2), Q=(3,4)\) ,求 \(P + Q\) 和 \(2P\) 。
解:设 \(R = P + Q\) ,由于 \(P\) 和 \(Q\) 不同,利用上一节介绍的公式,可知:
\[\begin{aligned} m &= \frac{y_P - y_Q}{x_P - x_Q} = \frac{2 - 4}{1 - 3} = 1 \\ x_R &= m^2 - x_P - x_Q = 1^2 - 1 - 3 = -3\\ y_R &= - m (x_R - x_P) - y_P = - 1 (- 3 - 1) - 2 = 2 \\ \end{aligned}\]
从而 \(R=(-3, 2)\) 即为所求,如图 5 所示。

ecc_real_add_example1.png

Figure 5: \(R = P + Q\)

现在设 \(R = 2P = P + P\) ,是两个相同点相加,利用上一节介绍的公式,可知:
\[\begin{aligned} m &= \frac{3 x^2_P + a}{2y_P} = \frac{3 \cdot 1^2 - 7}{2 \cdot 2} = -1 \\ x_R &= m^2 - x_P - x_P = (-1)^2 - 1 - 1 = -1 \\ y_R &= - m (x_R - x_P) - y_P = 1 \cdot (-1 - 1) - 2 = -4 \\ \end{aligned}\]
从而 \(R=(-1, -4)\) 即为所求,如图 6 所示。

ecc_real_add_example2.png

Figure 6: \(R = 2P\)

注:图 5 和图 6 摘自:https://cdn.rawgit.com/andreacorbellini/ecc/920b29a/interactive/reals-add.html

2 密码学中的椭圆曲线

前面介绍的椭圆曲线是连续的(点的两个坐标均定义在 \(R\) 上),它可表示为:
\[\begin{array}{rcl} \left\{(x, y) \in \mathbb{R}^2 \right. & \left. | \right. & \left. y^2 = x^3 + ax + b, \right. \\ & & \left. 4a^3 + 27b^2 \ne 0\right\} \end{array}\]
这种连续的椭圆曲线并不适合用于加密。在密码学中,我们把椭圆曲线定义在有限域 \(\mathbb{F}_p\) (其中 \(p\) 为素数)上(有限域的概念请参考近世代数相关书籍),这里我们可以简单地认为点的两个坐标是集合 \(\{0, 1, 2, \cdots, p-1\}\) 中的值。

在密码学中,我们把椭圆曲线定义为:
\[\begin{array}{rcl} \left\{(x, y) \in (\mathbb{F}_p)^2 \right. & \left. | \right. & \left. y^2 \equiv x^3 + ax + b \pmod{p}, \right. \\ & & \left. 4a^3 + 27b^2 \not\equiv 0 \pmod{p}\right\} \cup\ \left\{ \mathcal{O} \right\} \end{array}\]
注1: \(\mathcal{O}\) 是什么?为什么还要单独增加这样一个点,这里请忽略,后文将说明。
注2: 上式定义的椭圆曲线是离散的点,一点都不像椭圆 ,下面给出几个具体的例子。

取 \(a=-1, b=0\) ,素数 \(p=61\) ,其椭圆曲线的图形如图 7 所示。

Sorry, your browser does not support SVG.

Figure 7: Elliptic curve \(y^2 = x^3 − x\) over finite field \(\mathbb{F}_{61}\)

7 中取两点 \((4, 11), (4, 50)\) ,验证如下:
\[\begin{aligned} x^3 − x = 4^3 - 4 = 60 \pmod {61} \\ y^2 = 11^2 = 121 \equiv 60 \pmod {61} \\ y^2 = 50^2 = 2500 \equiv 60 \pmod {61} \\ \end{aligned}\]

再看一个例子,取 \(a=-1, b=0\) ,素数 \(p=71\) ,其椭圆曲线的图形如图 8 所示。

Sorry, your browser does not support SVG.

Figure 8: Elliptic curve \(y^2 = x^3 − x\) over finite field \(\mathbb{F}_{71}\)

2.1 从椭圆曲线到“群”

在近世代数中,“群”是集合再加上集合上一个二元运算(比如加法)满足下面条件后组成的代数结构:
(1) 封闭性: \(\forall a_1, a_2 \in A, \; a_1 + a_2 \in A\)
(2) 结合律: \(\forall a_1, a_2, a_3 \in A, \; (a_1 + a_2) + a_3 = a_1 + ( a_2 + a_3)\)
(3) 具有单位元: \(\exists e \in A, \; s.t. \; \forall a \in A, \; e + a = a + e = a\)
(4) 都有逆元素: \(\forall a \in A, \; \exists a^{-1} \in A, \; s.t. \; a + a^{-1} = e\)

把上一节中椭圆曲线所对应的离散点作为群的集合,仿照实数域椭圆曲线加法运算的定义(参见节 1.1 ),我们把群上的二元运算记为 \(+\) ,设 \(P=(x_P, y_P), Q=(x_Q, y_Q)\) ,把 \(R = P + Q\) 定义为:
\[\begin{aligned} x_R &= m^2 - x_P - x_Q \pmod p \\ y_R &= -m (x_R - x_P ) - y_P \pmod p \\ \end{aligned}\]
当 \(P \neq Q\) 时, \(m = \frac{y_P - y_Q}{x_P - x_Q} \pmod p\) ;当 \(P=Q\) 时, \(m = \frac{3 x_P^2 + a}{2 x_P} \pmod p\) 。

设 \(P,Q\) 在椭圆曲线上,按上面定义计算的点 \(P+Q\) 一定也在椭圆曲线上(即“封闭性”) ,为什么会这样呢?这里不证明,有兴趣的话可参考 An Elementary Proof Of The Group Law For Elliptic Curves(文章中也有关于“结合律”的证明)。我们通过一个具体的例子来验证一下“封闭性”。设椭圆曲线 \(y^2 \equiv x^3 − x \pmod {61}\) (参考图 7 ),易知点 \(P=(4,11), Q=(8,4)\) 都在椭圆曲线,通过上面的加法定义公式可求得 \(P+Q=(33, 55)\) ,容易验证点 \((33, 55)\) 确实也在椭圆曲线上。不仅如此,椭圆曲线上任意两点相加的结果都会在椭圆曲线上。

现在考察椭圆曲线上是否具有“单位元”,即是否存在点 \(\mathcal{O}\) (单位元)使所有点都满足:
\[P + \mathcal{O} = P\]
事实上,椭圆曲线满足上面条件的点 \(\mathcal{O}\) 是不存在的。为了满足群定义,我们将一个抽象的无穷点 \((x, \infty)\) 定义为单位元,这个无穷点可以看作是位于 \(y\) 轴正半轴的无穷远处,或 \(y\) 轴负半轴的无穷远处。

现在考察椭圆曲线上每个点是否都有“逆元素”,即对每一个点 \(P\) ,是否可以找到 \(-P\) 满足:
\[P + (-P) = \mathcal{O}\]
答案是肯定的, \(-P\) 可以这样定义(可以证明它一定存在于椭圆曲线上):
\[-P = (x_P, - y_P \bmod p)\]
比如,按上面公式可求椭圆曲线 \(y^2 \equiv x^3 − x \pmod {61}\) 上的点 \((4, 11)\) 的逆元素为 \((4, 50)\) ,容易验证它确实也在椭圆曲线上。

2.1.1 椭圆曲线上有多少个点(群的阶)

椭圆曲线,如 \(y^2 \equiv x^3 − x \pmod {61}\) 上(包含 \(\mathcal{O}\) )有多少个点呢(注:群中元素个数又称为群的阶)?这里素数 \(p\) 比较小,我们把 \(x\) 从 \(0\) 到 \(p-1\) 遍历一次,每个 \(x\) 看是否可以求出合法的 \(y\) 也满足 \(y \in \{0, 1, \cdots, p-1\}\) ,即可统计出所有满足要求的点。这种方法当素数 \(p\) 很大时效率很慢,可以用 Schoof's algorithm 快速计算椭圆曲线上点的个数。

2.2 循环子群

我们定义下面记号:
\[nP = \underbrace{P + P + \cdots + P}_{n \text{ times}}\]
定义 \(0P = \mathcal{O}\) 。以 \(y^2 \equiv x^3 + 2x + 3 \pmod {97}\) 为例,我们计算一下 \(P, 2P, 3P, 4P, 5P, 6P \cdots\) ,由群的“封闭性”可知,它们都属于椭圆曲线所在“群”。
\[\begin{aligned} 0P &= \mathcal{O} \\ 1P &= (3, 6) \\ 2P &= (80, 10) \\ 3P &= (80, 87) \\ 4P &= (3, 91) \\ 5P &= \mathcal{O} \\ 6P &= (3, 6) \\ 7P &= (80, 10) \\ 8P &= (80, 87) \\ 8P &= (3, 91) \\ 10P &= \mathcal{O} \\ \cdots \\ \end{aligned}\]
可以证明 \(\mathcal{O}, (3, 6), (80, 10), (80, 87), (3, 91)\) 在椭圆曲线群所定义的加法运算下也构成群,它称为椭圆曲线群的“子群”,由于这个子群的每个元素可通过对 \(P=(3, 6)\) 重复进行群运算而生成,所以这个子群又称为“循环子群”,其中 \(P\) 称为循环子群的Base Point (或者Generator)。

2.2.1 循环子群的元素个数(子群的阶)

拉格朗日定理(Lagrange's theorem):设 \(G\) 为有限群, \(A\) 是 \(G\) 的子群,则 \(A\) 的元素个数(子群的阶)是 \(G\) 的元素个数的因数。

上面定理阐述了子群的阶和群的阶的关系。

实例1:椭圆曲线群 \(y^2 \equiv x^3 - x + 3 \pmod {37}\) (包含点 \(\mathcal{O}\) )的阶经过计算可知为 \(N=42\) ,则其子群的阶只可能是 \(42\) 的因数,即 \(n=1,2,3,6,7,14,21,42\) 。在椭圆曲线取一点 \(P=(2,3)\) ,计算可知 \(P \neq \mathcal{O}, 2P \neq \mathcal{O}, \cdots, 6P \neq \mathcal{O}, 7P = \mathcal{O}, 8P = P, \cdots\) ,显然由点 \(P\) 生成的循环子群的阶为 \(7\) ,它确实是 \(42\) 的因数,这从侧面印证了拉格朗日定理。

实例2:椭圆曲线群 \(y^2 \equiv x^3 - x + 1 \pmod {29}\) (包含点 \(\mathcal{O}\) )的阶经过计算可知为 \(N=37\) 。由于 \(37\) 是素数,它只有两个因数,即 \(n=1, 37\) 。由拉格朗日定理知,子群的阶要么是 \(1\) ,要么是 \(37\) 。当 \(n=1\) 时,子群仅包含 \(\mathcal{O}\) ,当 \(n=37\) 时,子群就是椭圆曲线群本身。

注: 设 \(N\) 为椭圆曲线群的阶, \(n\) 为由 \(P\) (Base Point)生成的循环子群的阶,我们称 \(h=N/n\) 为相应循环子群的“cofactor”。

2.3 离散对数问题

在椭圆曲线的循环子群中(设循环子群的阶为 \(n\) ),考虑式子 \(Q=kP\) ,对于给定的 \(k\) 和 \(P\) 计算 \(Q\) 相对容易(可以使用 Double-and-add 算法);而如果已知点 \(P\) 和 \(Q\) ,求 \(k\) 则比较困难(当然我们并不能证明它很“难”,只是说目前没有找到有效的算法来上式中的 \(k\) ),这个问题称为离散对数问题(Elliptic-Curve Discrete-Logarithm Problem, ECDLP)。

如果要暴力求解 \(k\) 的话,你需要设 \(k=1,2,\cdots,n\) ,对于每一个 \(k\) 直接使用加法计算公式验证其是否满足 \(Q = \underbrace{P + P + \cdots + P}_{k \text{ times}}\) ,当 \(n\) 非常大时,暴力求解没有应用价值。

注:在Digital Signature Algorithm (DSA)或者Diffie-Hellman key exchange算法中,我们也会说到“离散对数问题”,它指的是另一个问题:已知 \(a\) 和 \(b\) 满足 \(b \equiv a^k \pmod p\) ,那么 \(k\) 是多少?这个问题也很“难”(目前没有找到有效算法),这里不介绍。

3 Elliptic Curve Cryptography

3.1 Domain parameters

密码学中,椭圆曲线的参数有:

  • The prime \(p\) that specifies the size of the finite field.(注: \(p\) 一般取很大的素数)
  • The coefficients \(a\) and \(b\) of the elliptic curve equation.
  • The base point \(G=(x_G, y_G)\) that generates our subgroup.
  • The order \(n\) of the subgrouop.(注: \(n\) 越大,越难暴力破解)
  • The cofactor \(h=N/n\) of the subgroup.(注: \(h\) 一般为较小的正整数。它为 \(h=1\) 时,循环子群就是椭圆曲线群本身)

上面这些参数称为“domain parameters”。

3.1.1 Random curves (seed \(S\))

前面说,椭圆曲线离散对数问题的困难的。这不完全正确,如当满足条件 \(p=hn\) 时的所有椭圆曲线都比较容易破解。

为了减少潜在的风险,我们可以增加一个随机种子 \(S\) ,用它来产生参数 \(a,b\) ,或者 \(G\) ,或者这两者。这样,椭圆曲线变得不可预测。

3.1.2 选择合适的椭圆曲线

关于选择椭圆曲线有很多不同的“标准”,如:

  • ANSI X9.62 (1999).
  • IEEE P1363 (2000).
  • SEC 2 (2000).
  • NIST FIPS 186-2 (2000).
  • ANSI X9.63 (2001).
  • Brainpool (2005).
  • NSA Suite B (2005).
  • ANSSI FRP256V1 (2011).

如何选择一个“安全的”?可参考:SafeCurves: choosing safe curves for elliptic-curve cryptography (注:Bitcoin使用的 secp256k1 ,在该网页中被标记为Unsafe。)

3.2 Elliptic Curve Diffie-Hellman (ECDH)

下面介绍使用椭圆曲线进行密钥交换(Key Exchange)的过程,它是 Diffie-Hellman algorithm 算法的变种,一般称为Elliptic curve Diffie-Hellman (ECDH)。

Alice和Bob想进行通信,为了加密(基于效率考虑往往会采用对称密钥算法,如 AES 等)通信的数据,他们需要约定同一个密钥(称为“Shared Secret”)。

使用ECDH算法约定“Shared Secret”的过程(和Diffie-Hellman密钥交换算法基本类似)如下。

第一步,选择一个椭圆曲线(即确定Domain parameters),你可以从 Standards for Efficient Cryptography, SEC 2: Recommended Elliptic Curve Domain Parameters 中选择一个推荐的参数,比如Bitcoin使用的 secp256k1 (注:Bitcoin中不是用它进行密钥交换,而是它用进行数字签名,参见 ECDSA ),它的参数如下:
\[\begin{aligned} p &= \texttt{0xffffffff ffffffff ffffffff ffffffff ffffffff ffffffff fffffffe fffffc2f} \\ a &= \texttt{0} \\ b &= \texttt{7} \\ x_G &= \texttt{0x79be667e f9dcbbac 55a06295 ce870b07 029bfcdb 2dce28d9 59f2815b 16f81798} \\ y_G &= \texttt{0x483ada77 26a3c465 5da4fbfc 0e1108a8 fd17b448 a6855419 9c47d08f fb10d4b8} \\ n &= \texttt{0xffffffff ffffffff ffffffff fffffffe baaedce6 af48a03b bfd25e8c d0364141} \\ h &= \texttt{1} \\ \end{aligned}\]

第二步,为Alice和Bob分别生成private key/public key。比如,Alice生成private key/public key的过程如下:
1、从 \(\{1, 2, \cdots, n - 1\}\) ( \(n\) 在Domain parameters中指定的循环子群的阶)中随机选择一个数 \(d_A\) 作为private key。
2、计算 \(Q_A=d_A G\) ( \(G\) 是Domain parameters中的Base Point), \(Q_A\) 就是public key。(注:这就是由私钥生成公钥的过程,直接按多次加法求解比较慢,可采用 Double-and-add 算法进行优化。这里有一个使用 Double-and-add 算法计算公钥的例子:https://bitcoin.stackexchange.com/questions/25024/how-do-you-get-a-bitcoin-public-key-from-a-private-key
类似的过程,Bob生成一个private key/public key,分别记为 \(d_B, Q_B\) ,有 \(Q_B=d_B G\) 。

第三步,Alice和Bob分别把自己的公钥传送给对方,传递过程被别人偷看也没关系,由公钥无法容易地计算出私钥。

第四步, Alice用自己的私钥和Bob的公钥计算 \(Secret_1=d_A Q_B\) ,同样地,Bob用自己的私钥和Alice的公钥计算 \(Secret_2=d_B Q_A\) ,由于 \(Secret_1 = Secret_2\) (因为 \(d_A Q_B = d_A (d_B G) = d_B (d_A G) = d_B Q_A\) ),所以它可作为“Shared Secret”。

3.2.1 Ephemeral ECDH (ECDHE)

如果通信双方不使用固定的private key/public key,而是在建立连接时才动态生成各自的private key/public key(注:这次通信结束,下次连接时重新生成各自的private key/public key),这称为Ephemeral ECDH (ECDHE)。

3.3 公钥表达形式(uncompressed and compressed)

在椭圆曲线中,私钥 \(d \in \{1, 2, \cdots, n - 1\}\) 是整数;而公钥 \(Q =d G\) 则是椭圆曲线上的一个“点”,它有 \(x_G, y_G\) 两个坐标,每个坐标都是整数。

一般地,我们往往用“一个数”来表达椭圆曲线中的公钥,如何用一个数来表达两个坐标呢?有两种方案:“Uncompressed format”和“Compressed format”(Compressed format有ansiX962_compressed_prime和ansiX962_compressed_char2标准,这里不介绍它们)。

下面介绍一下“Uncompressed format”,它的规则很简单,把 \(x_G\) 和 \(y_G\) 直接连接在一起,再在前面加个 0x04 前缀即可。例如有:
\[\begin{aligned} x_G &= \texttt{0x50863AD64A87AE8A2FE83C1AF1A8403CB53F53E486D8511DAD8A04887E5B2352} \\ y_G &= \texttt{0x2CD470243453A299FA9E77237716103ABC11A1DF38855ED6F2EE187E9C582BA6} \\ \end{aligned}\]
则公钥(十六进制)可表示为:

Q = 0450863AD64A87AE8A2FE83C1AF1A8403CB53F53E486D8511DAD8A04887E5B23522CD470243453A299FA9E77237716103ABC11A1DF38855ED6F2EE187E9C582BA6

参考:https://stackoverflow.com/questions/6665353/is-there-a-standardized-fixed-length-encoding-for-ec-public-keys

3.4 Elliptic Curve Digital Signature Algorithm (ECDSA)

前面介绍了使用椭圆曲线进行密钥交换(Key Exchange)的过程,这里将介绍如何使用椭圆曲线进行数字签名,简称 ECDSA

数字签名的场景为:Alice用他的私钥 \(d_A\) 对消息进行签名,而其它人(如Bob)可以使用Alice的公钥 \(Q_A\) 来验证这个消息确实是Alice发送的。

3.4.1 ECDSA签名及验证过程

本节介绍ECDSA签名及验证的具体过程(下一节将证明其正确性)。

假设Alice的私钥为 \(d_A\) ,公钥为 \(Q_A\) 。需要签名的消息为 \(m\) ,首先对消息 \(m\) 进行下面处理:

  1. 对原始消息计算哈希(需要使用 Cryptographic hash function),得到 \(e=HASH(m)\) ,把 \(e\) 当做一个大整数。
  2. 如果 \(e\) 的比特长度大于 \(n\) ( \(n\) 在Domain parameters中指定的循环子群的阶)的比特长度,则把截断 \(e\) ,只留下左边和 \(n\) 同样比特长的部分,记为 \(z\) ,后面把它当做大整数进行运算。

Alice签名过程:

  1. 从 \(\{1, 2, \cdots, n - 1\}\) 中随机选择一个数,记为 \(k\) ;
  2. 计算 \(P = k G\) (其中 \(G\) 是Domain parameters);
  3. 计算整数 \(r = x_P \pmod n\) (其中 \(x_P\) 是上一步计算的点 \(P\) 的横坐标);
  4. 如果 \(r=0\) ,则随机选择另外一个 \(k\) ,重新计算前面两步;
  5. 计算整数 \(s= k^{-1}(z + rd_A) \pmod n\) (其中 \(d_A\) 是Alice的私钥, \(k^{-1}\) 是满足 \(k k^{-1} = 1 \pmod n\) 的整数,整数 \(z\) 是摘要消息);
  6. 如果 \(s=0\) ,则随机选择另外一个 \(k\) ,重新计算前面步骤。

经常上面步骤得到的 整数对 \((r, s)\) 就是摘要消息 \(z\) 的数字签名。 特别说明:随机数 \(k\) 用完就丢弃,不能使用相同的 \(k\) 来对其它消息进行签名,如果每次签名都使用相同的 \(k\) 则签名是不安全的。

Bob验证签名的过程:

  1. 计算整数 \(u_1 = s^{-1} z \pmod n\) (其中 \(s^{-1}\) 是满足 \(s s^{-1} = 1 \pmod n\) 的整数);
  2. 计算整数 \(u_2 = s^{-1} r \pmod n\) ;
  3. 计算点 \(P = u_1 G + u_2 Q_A\) (其中 \(Q_A\) 是Alice的公钥)。
  4. 如果 \(r = x_P \pmod n\) (这里 \(x_P\) 是上一步计算的点 \(P\) 的横坐标)成立,则验证签名通过,否则验证失败。
3.4.1.1 ECDSA正确性证明

前面介绍的签名过程和验证签名过程为什么正确呢?下面来证明它的正确性。

首先,在验证签名时,有(后面推导将省写了 \(\text{mod } n\) ):
\[\begin{aligned} P &= u_1 G + u_2 Q_A \\ & = u_1 G + u_2 d_A G \\ & = (u_1 + u_2 d_A) G \\ & = (s^{-1} z + s^{-1} r d_A) G \\ & = s^{-1} (z + r d_A) G \\ \end{aligned}\]
在生成签名时,有:
\[\begin{aligned} P & = k G \\ & = s^{-1} (z + r d_A) G \\ \end{aligned}\]
所以,通过两种方法得到了 \(P\) 的相同表达形式,而我们在生成签名时定义了 \(r = x_P \pmod n\) ,所以如果这个式子在验证签名过程中也成立,则说明验证通过。

3.4.2 ECDSA的Python实现

下面是ECDSA的Python实现:

#!/usr/bin/env python3
# -*- coding: utf-8 -*-
# 代码摘自:https://github.com/andreacorbellini/ecc/blob/master/scripts/ecdsa.py

import collections
import hashlib
import random

EllipticCurve = collections.namedtuple('EllipticCurve', 'name p a b g n h')

curve = EllipticCurve(
    'secp256k1',
    # Field characteristic.
    p=0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f,
    # Curve coefficients.
    a=0,
    b=7,
    # Base point.
    g=(0x79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798,
       0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8),
    # Subgroup order.
    n=0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141,
    # Subgroup cofactor.
    h=1,
)


# Modular arithmetic ##########################################################

def inverse_mod(k, p):
    """Returns the inverse of k modulo p.
    This function returns the only integer x such that (x * k) % p == 1.
    k must be non-zero and p must be a prime.
    """
    if k == 0:
        raise ZeroDivisionError('division by zero')

    if k < 0:
        # k ** -1 = p - (-k) ** -1  (mod p)
        return p - inverse_mod(-k, p)

    # Extended Euclidean algorithm.
    s, old_s = 0, 1
    t, old_t = 1, 0
    r, old_r = p, k

    while r != 0:
        quotient = old_r // r
        old_r, r = r, old_r - quotient * r
        old_s, s = s, old_s - quotient * s
        old_t, t = t, old_t - quotient * t

    gcd, x, y = old_r, old_s, old_t

    assert gcd == 1
    assert (k * x) % p == 1

    return x % p


# Functions that work on curve points #########################################

def is_on_curve(point):
    """Returns True if the given point lies on the elliptic curve."""
    if point is None:
        # None represents the point at infinity.
        return True

    x, y = point

    return (y * y - x * x * x - curve.a * x - curve.b) % curve.p == 0


def point_neg(point):
    """Returns -point."""
    assert is_on_curve(point)

    if point is None:
        # -0 = 0
        return None

    x, y = point
    result = (x, -y % curve.p)

    assert is_on_curve(result)

    return result


def point_add(point1, point2):
    """Returns the result of point1 + point2 according to the group law."""
    assert is_on_curve(point1)
    assert is_on_curve(point2)

    if point1 is None:
        # 0 + point2 = point2
        return point2
    if point2 is None:
        # point1 + 0 = point1
        return point1

    x1, y1 = point1
    x2, y2 = point2

    if x1 == x2 and y1 != y2:
        # point1 + (-point1) = 0
        return None

    if x1 == x2:
        # This is the case point1 == point2.
        m = (3 * x1 * x1 + curve.a) * inverse_mod(2 * y1, curve.p)
    else:
        # This is the case point1 != point2.
        m = (y1 - y2) * inverse_mod(x1 - x2, curve.p)

    x3 = m * m - x1 - x2
    y3 = y1 + m * (x3 - x1)
    result = (x3 % curve.p,
              -y3 % curve.p)

    assert is_on_curve(result)

    return result


def scalar_mult(k, point):
    """Returns k * point computed using the double and point_add algorithm."""
    assert is_on_curve(point)

    if k % curve.n == 0 or point is None:
        return None

    if k < 0:
        # k * point = -k * (-point)
        return scalar_mult(-k, point_neg(point))

    result = None
    addend = point

    while k:
        if k & 1:
            # Add.
            result = point_add(result, addend)

        # Double.
        addend = point_add(addend, addend)

        k >>= 1

    assert is_on_curve(result)

    return result


# Keypair generation and ECDSA ################################################

def make_keypair():
    """Generates a random private-public key pair."""
    private_key = random.randrange(1, curve.n)
    public_key = scalar_mult(private_key, curve.g)

    return private_key, public_key


def hash_message(message):
    """Returns the truncated SHA521 hash of the message."""
    message_hash = hashlib.sha512(message).digest()
    e = int.from_bytes(message_hash, 'big')

    # FIPS 180 says that when a hash needs to be truncated, the rightmost bits
    # should be discarded.
    z = e >> (e.bit_length() - curve.n.bit_length())

    assert z.bit_length() <= curve.n.bit_length()

    return z


def sign_message(private_key, message):
    z = hash_message(message)

    r = 0
    s = 0

    while not r or not s:
        k = random.randrange(1, curve.n)
        x, y = scalar_mult(k, curve.g)

        r = x % curve.n
        s = ((z + r * private_key) * inverse_mod(k, curve.n)) % curve.n

    return (r, s)


def verify_signature(public_key, message, signature):
    z = hash_message(message)

    r, s = signature

    w = inverse_mod(s, curve.n)
    u1 = (z * w) % curve.n
    u2 = (r * w) % curve.n

    x, y = point_add(scalar_mult(u1, curve.g),
                     scalar_mult(u2, public_key))

    if (r % curve.n) == (x % curve.n):
        return 'signature matches'
    else:
        return 'invalid signature'


print('Curve:', curve.name)

private, public = make_keypair()
print("Private key:", hex(private))
print("Public key: (0x{:x}, 0x{:x})".format(*public))

msg = b'Hello!'
signature = sign_message(private, msg)

print()
print('Message:', msg)
print('Signature: (0x{:x}, 0x{:x})'.format(*signature))
print('Verification:', verify_signature(public, msg, signature)) # 验证通过

msg = b'Hi there!'                # 使用不同的消息,会验证失败
print()
print('Message:', msg)
print('Verification:', verify_signature(public, msg, signature))

private, public = make_keypair()  # 使用不同的公钥,会验证失败

msg = b'Hello!'
print()
print('Message:', msg)
print("Public key: (0x{:x}, 0x{:x})".format(*public))
print('Verification:', verify_signature(public, msg, signature))

4 参考


Author: cig01

Created: <2018-05-01 Tue 00:00>

Last updated: <2018-06-16 Sat 00:08>

Creator: Emacs 25.3.1 (Org mode 9.1.4)