对定义在有限域上的椭圆曲线 $E = (p, a, b, G, n, h)$
$$
y^2 \equiv x^3 + ax + b \pmod{p}
$$
本文将通过代码计算下面两个问题:
- 已知曲线上的点 $P = (x_P, y_P)$ 和 $Q = (x_Q, y_Q)$,求点 $R = P + Q$
- 已知整数 $k$,求点 $K = k \cdot G$
比特币使用的椭圆曲线由 Secp256k1 标准定义,我们可以事先声明好这些参数,并实现一些基础方法。
import collections |
点的(代数)加法
当 $P = -Q\ (x_Q, -y_Q \bmod{p})$ 时,根据定义,$P + Q = 0$,结果为理想点(无穷远点)。
当 $P \neq -Q$ 时,有
$$
x = (m^2 - x_P - x_Q) \bmod{p}
$$
$$
y = (y_P + m(x_R - x_P)) \bmod{p} = (y_Q + m(x_R - x_Q)) \bmod{p}
$$
对于 $m$,当 $P \neq Q$ 时,
$$
m = (y_P - y_Q)(x_P - x_Q)^{-1} \bmod{p}
$$
当 $P = Q$ 时,
$$
m = (3 x_P^2 + a)(2 y_P)^{-1} \bmod{p}
$$
综上,$R = (x \bmod{p}, -y \bmod{p})$。
注意,在计算 $m$ 时,用到了模 $p$ 的除法(模逆元),相关概念及代码请参考之前的文章。
def add(p: tuple, q: tuple) -> tuple or None: |
标量积(数乘运算)
标量积(scalar multiplication)的定义可以从加法扩展,其中 $k$ 为正整数。
$$k \cdot P = \underbrace{P + P + … + P}_{k\ 个}$$
通过调用已实现的加法并循环累加结果,可以直接求得点 $141P$ 的坐标,但这样要做 140 次加法运算。
因为椭圆曲线上点的加法,满足交换律和结合律,所以我们可以用“倍乘法”改进。将 141 用二进制表示
$$141_{10} = 10001101_{2}$$
也就是说
$$
141P = 2^7P + 2^3P + 2^2P + 2^0P
$$
改进后的计算过程为
- 计算 $2P = P + P$,即 $2^1P$
- 计算 $4P = 2P + 2P$,即 $2^2P$
- 计算 $8P = 4P + 4P$,即 $2^3P$
- ……
- 计算 $2^7P$
- 计算 $2^7P + 2^3P + 2^2P + 2^0P$ 得到 $141P$
只需要做 10 次加法运算。显而易见,随着 $k$ 的增大,“倍乘法”能显著提升 $k \cdot P$ 的计算效率。
def scalar_multiply(k: int, point: tuple) -> tuple or None: |
验证
我们使用之前文章中的例子,来验证一下代码的正确性。
if __name__ == '__main__': |
运行结果为
a = 0xf97c89aaacf0cd2e47ddbacc97dae1f88bec49106ac37716c451dcdd008a4b62 |
完整代码
参考
- Elliptic Curve Cryptography: a gentle introduction 原文 译文
- Elliptic Curve Cryptography: finite fields and discrete logarithms 原文 译文
- GitHub andreacorbellini/ecc