椭圆曲线密码学密钥验证失败：Python实现结果不符问题求助

问题描述 #

正在学习椭圆曲线密码学（ECC），编写了一段Python程序用于生成密钥材料，但计算得到的y_squared与Q.y^2结果不一致。程序采用《RFC 5903》第4页的256位随机ECP组参数，以及《NIST.SP.800-56Ar3》第30页的「使用额外随机位生成密钥对」步骤。代码如下：

# RFC 5903 256-Bit Random ECP Group page 4
# NIST.SP.800-56Ar3 Key Pair Generation Using Extra Random Bits page 30
import sympy
import os

s = 128
p = pow(2, 256) - pow(2, 224) + pow(2, 192) + pow(2, 96) - 1
group_prime = int.from_bytes(bytes.fromhex('FFFFFFFF00000001000000000000000000000000FFFFFFFFFFFFFFFFFFFFFFFF'), byteorder='big')
assert p == group_prime

x, b = sympy.symbols('x, b')
ecurve = x**3 - 3*x + b 

group_b = int.from_bytes(bytes.fromhex('5AC635D8AA3A93E7B3EBBD55769886BC651D06B0CC53B0F63BCE3C3E27D2604B'), byteorder='big')
group_order = int.from_bytes(bytes.fromhex('FFFFFFFF00000000FFFFFFFFFFFFFFFFBCE6FAADA7179E84F3B9CAC2FC632551'), byteorder='big')
gx = int.from_bytes(bytes.fromhex('6B17D1F2E12C4247F8BCE6E563A440F277037D812DEB33A0F4A13945D898C296'), byteorder='big')
gy = int.from_bytes(bytes.fromhex('4FE342E2FE1A7F9B8EE7EB4A7C0F9E162BCE33576B315ECECBB6406837BF51F5'), byteorder='big')

L = group_order.bit_length() + 64
c = int.from_bytes(os.urandom(max(s, L) // 8))

assert c > 0 and c < (pow(2, max(s, L)) - 1)

d = (c % (group_order - 1)) + 1
Q = (d*gx, d*gy)
y_squared = pow(Q[1], 2, group_prime)
print(f"y_squared: {y_squared}")
print(f"Q.y^2: {ecurve.subs([(x, Q[0]),(b, group_b)]) % group_prime}")

问题原因与修复 #

核心错误 #

• 错误的标量乘实现：椭圆曲线的标量乘d*G不是简单的将基点坐标与标量d做整数乘法，而是要遵循椭圆曲线的点加法规则：将基点G重复相加d次（实际工程中用快速幂优化的点加倍/加法算法）。直接用d*gx、d*gy得到的坐标根本不在椭圆曲线上，自然无法满足曲线方程y² = x³ -3x + b。

修复方案 #

实现椭圆曲线的点加法和标量乘函数，正确计算公钥Q。以下是修正后的代码：

# RFC 5903 256-Bit Random ECP Group page 4
# NIST.SP.800-56Ar3 Key Pair Generation Using Extra Random Bits page 30
import sympy
import os

s = 128
p = pow(2, 256) - pow(2, 224) + pow(2, 192) + pow(2, 96) - 1
group_prime = int.from_bytes(bytes.fromhex('FFFFFFFF00000001000000000000000000000000FFFFFFFFFFFFFFFFFFFFFFFF'), byteorder='big')
assert p == group_prime

x, b = sympy.symbols('x, b')
ecurve = x**3 - 3*x + b 

group_b = int.from_bytes(bytes.fromhex('5AC635D8AA3A93E7B3EBBD55769886BC651D06B0CC53B0F63BCE3C3E27D2604B'), byteorder='big')
group_order = int.from_bytes(bytes.fromhex('FFFFFFFF00000000FFFFFFFFFFFFFFFFBCE6FAADA7179E84F3B9CAC2FC632551'), byteorder='big')
gx = int.from_bytes(bytes.fromhex('6B17D1F2E12C4247F8BCE6E563A440F277037D812DEB33A0F4A13945D898C296'), byteorder='big')
gy = int.from_bytes(bytes.fromhex('4FE342E2FE1A7F9B8EE7EB4A7C0F9E162BCE33576B315ECECBB6406837BF51F5'), byteorder='big')

# 椭圆曲线点加法实现
def ec_add(p1, p2, p, b):
    if p1 is None:
        return p2
    if p2 is None:
        return p1
    x1, y1 = p1
    x2, y2 = p2
    if x1 == x2:
        if y1 != y2:
            return None  # 无穷远点
        # 点加倍
        lam = (3 * x1**2 - 3) * pow(2 * y1, -1, p) % p
    else:
        lam = (y2 - y1) * pow(x2 - x1, -1, p) % p
    x3 = (lam**2 - x1 - x2) % p
    y3 = (lam * (x1 - x3) - y1) % p
    return (x3, y3)

# 椭圆曲线标量乘实现（快速幂法）
def ec_scalar_mult(k, point, p, b):
    result = None
    current = point
    while k > 0:
        if k % 2 == 1:
            result = ec_add(result, current, p, b)
        current = ec_add(current, current, p, b)
        k = k // 2
    return result

L = group_order.bit_length() + 64
c = int.from_bytes(os.urandom(max(s, L) // 8))

assert c > 0 and c < (pow(2, max(s, L)) - 1)

d = (c % (group_order - 1)) + 1
Q = ec_scalar_mult(d, (gx, gy), group_prime, group_b)
y_squared = pow(Q[1], 2, group_prime)
curve_right = ecurve.subs([(x, Q[0]),(b, group_b)]) % group_prime
print(f"y_squared: {y_squared}")
print(f"曲线右侧值: {curve_right}")
print(f"是否相等: {y_squared == curve_right}")

验证说明 #

修正后的代码通过ec_scalar_mult函数正确计算标量乘，得到的公钥Q坐标会严格满足椭圆曲线方程，此时y_squared和曲线右侧计算结果会完全一致。

内容的提问来源于stack exchange，提问作者Mehkir