椭圆曲线上点的运算

对定义在有限域上的椭圆曲线 $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

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

curve = EllipticCurve(
name='Secp256k1',
p=0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f,
a=0,
b=7,
g=(0x79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798, 0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8),
n=0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141,
h=1,
)


def on_curve(point: tuple) -> bool:
"""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 negative(point: tuple) -> tuple or None:
"""Returns -point."""
assert on_curve(point)
if point is None:
# -0 = 0
return None
x, y = point
result = (x, -y % curve.p)
assert on_curve(result)
return result

点的(代数)加法

当 $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:
"""Returns the result of p + q according to the group law."""
assert on_curve(p)
assert on_curve(q)
if p is None:
# 0 + q = q
return q
if q is None:
# p + 0 = p
return p
#
# p == -q
#
if p == negative(q):
return None
#
# p != -q
#
x1, y1 = p
x2, y2 = q
if p == q:
m = (3 * x1 * x1 + curve.a) * modular_multiplicative_inverse(2 * y1, curve.p)
else:
m = (y1 - y2) * modular_multiplicative_inverse(x1 - x2, curve.p)
x = m * m - x1 - x2
y = y1 + m * (x - x1)
result = (x % curve.p, -y % curve.p)
assert on_curve(result)
return result

标量积(数乘运算)

标量积(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:
"""Returns k * point computed using the double and add algorithm."""
assert on_curve(point)
if k % curve.n == 0 or point is None:
return None
if k < 0:
# k * point = -k * (-point)
return scalar_multiply(-k, negative(point))
# Double and add
result = None
while k:
if k & 1:
result = add(result, point)
point = add(point, point)
k >>= 1
assert on_curve(result)
return result

验证

我们使用之前文章中的例子,来验证一下代码的正确性。

if __name__ == '__main__':
a = 0xf97c89aaacf0cd2e47ddbacc97dae1f88bec49106ac37716c451dcdd008a4b62
print('a =', hex(a))
ag = scalar_multiply(a, curve.g)
print('x =', hex(ag[0]))
print('y =', hex(ag[1]))

运行结果为

a = 0xf97c89aaacf0cd2e47ddbacc97dae1f88bec49106ac37716c451dcdd008a4b62
x = 0xe46dcd7991e5a4bd642739249b0158312e1aee56a60fd1bf622172ffe65bd789
y = 0x97693d32c540ac253de7a3dc73f7e4ba7b38d2dc1ecc8e07920b496fb107d6b2

完整代码

ec_point_operation.py

参考