作者：aaron67
时间：2020年10月11日 00:51:42
来源：https://blog.csdn.net/aaron67/article/details/109006982
对定义在有限域上的椭圆曲线 E = ( p , a , b , G , n , h )
y^2 ≡ x^3 + ax + b ( mod p )
本文将通过代码计算下面两个问题：
已知曲线上的点 P = (x_P, y_P) 和 Q = (x_Q, y_Q)，求点 R = P + Q
已知整数 k，求点 K = k ⋅ 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 mod p) 时，根据定义，P + Q = 0，结果为理想点（无穷远点）。
当 P ≠ -Q 时，有
x = (m^2 – x_P – x_Q) mod p
y = (y_P + m(x_R – x_P)) mod p = (y_Q + m(x_R – x_Q)) mod p
对于 m，当 P ≠ Q 时，
m = (y_P – y_Q)(x_P – x_Q)^(-1) mod p
当 P = Q 时，
m = (3x_P^2 + a)(2y_P)^(-1) mod p
综上，R = (x mod p, -y mod 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 ⋅ P = 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^0P2
得到 141P
只需要做 10 次加法运算。显而易见，随着 k 的增大，“倍乘法”能显著提升 k ⋅ 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
参考
Elliptic Curve Cryptography: a gentle introduction 原文 译文
Elliptic Curve Cryptography: finite fields and discrete logarithms 原文 译文
GitHub andreacorbellini/ecc