在今年的一月份，一个 Github 的小伙伴提了一个 Issue: Request for a more detailed explanation of the mathematical principles behind the elliptic curve in the code（要求更详细地解释代码中椭圆曲线背后的数学原理，今天刚好把这个坑填一下）。
1. 椭圆曲线加密算法
椭圆曲线加密算法（Elliptic Curve Cryptography，简称 ECC）是一种基于椭圆曲线数学结构的公钥密码学方法。与 RSA 算法相比，ECC 在相同的安全强度下，能够使用更短的密钥长度，从而大幅提升加密效率和降低计算资源消耗。ECC 的核心思想是利用椭圆曲线上的点的代数结构，构造难以破解的数学问题——椭圆曲线离散对数问题（ECDLP）。
接下来，我想先通过 Secp256k1 加密算法的示例，从而引出 WinRAR Keygen 的生成算法。
2. Secp256k1 加密算法
Secp256k1 是一种广泛应用于区块链和加密货币领域的椭圆曲线密码学（ECC）标准曲线。它定义在素数域 \mathbb{F}_p 上，其中 p = 2^{256} - 2^{32} - 977 是一个大素数。Secp256k1 采用简化的 Weierstrass 曲线方程形式：
y^2 = x^3 + 7
该曲线的主要特点是具有高效的计算性能和良好的安全性，特别适用于数字签名算法（如 ECDSA）和密钥交换协议。Secp256k1 的生成点（基点）具有大阶，确保了足够的密码强度。由于其高效性和安全性，Secp256k1 成为比特币及其他众多加密货币系统中的核心密码学基础，支持公私钥生成、交易签名和验证等关键操作。
Secp256k1 的基点 G 是这条曲线上固定且公开的一个点，用作公私钥生成的起点。它的坐标在十六进制下如下：
# 基点 G 的坐标 (十进制)
Gx = int("79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798", 16)
Gy = int("483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8", 16)这是 Secp256k1 曲线的标准生成点（基点 G），所有密钥对的公钥都是通过私钥与这个点进行标量乘法得到的。
接下来就是验证基点 G 位于曲线方程，代码如下：
# Secp256k1 模域
p = 2**256 - 2**32 - 977 # Secp256k1 的模 p
print(f"椭圆曲线方程的模 p: {p}")
# 基点 G 的坐标 (十进制)
Gx = int("79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798", 16)
Gy = int("483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8", 16)
# 计算左侧：y^2 % p
lhs = (Gy**2) % p
# 计算右侧：x^3 + 7 % p
rhs = (Gx**3 + 7) % p
# 输出结果
print(f"左侧计算结果 (y^2) % p: {lhs}")
print(f"右侧计算结果 (x^3 + 7) % p: {rhs}")
# 验证是否相等
if lhs == rhs:
print("基点 G 在椭圆曲线方程上，验证通过")
else:
print("基点 G 不在椭圆曲线方程上，验证失败")3. WinRAR Keygen 加密算法
WinRAR Keygen 算法的曲线采用的是复合有限域 GF((2^{15})^{17}) —— 扩展二元域。它不是简单的模素数运算，而是基于二元域（也称特征二域）的扩展域运算：
首先定义了一个基域 GF(2^{15})，它是用一个15次不可约多项式来定义的。然后在这个基域的基础上，用一个17次不可约多项式构造了扩展域 GF((2^{15})^{17})。
每个域元素需要用多项式系数表示，这些系数是 15-bit 的小端块，数据结构是把每个域元素拆成17个 15-bit 部分，这也意味着实现曲线方程验证和点乘需要写专门的多项式域运算代码，而不是用普通大整数运算，任何一次加法/乘法都需要拆成一段段 15-bit 小块计算，再合成。
曲线方程为：
y^2+xy=x^3+161，161 \in \mathrm{GF}((2^{15})^{17})WinRAR Keygen 的基点 G 坐标为：
# 基点 G 的坐标 (十进制)
Gx_int = 0x56fdcbc6a27acee0cc2996e0096ae74feb1acf220a2341b898b549440297b8cc
Gy_int = 0x20da32e8afc90b7cf0e76bde44496b4d0794054e6ea60f388682463132f931a7这是一个基点 G 转换的示例代码：
def to_field_repr(val, bits=15, count=17):
"""
将一个整数转换为 GF((2^bits)^count) 中的小端表示。
每一项是 bits 位，结果总共 count 项。
"""
mask = (1 << bits) - 1
result = []
for _ in range(count):
result.append(val & mask)
val >>= bits
return result
def print_field(label, field_data):
print(f"{label} = to_field([")
for i in range(len(field_data)):
print(f" 0x{field_data[i]:04X},", end="\n" if (i + 1) % 4 == 0 else " ")
print("])")
# G 点坐标
Gx_int = 0x56fdcbc6a27acee0cc2996e0096ae74feb1acf220a2341b898b549440297b8cc
Gy_int = 0x20da32e8afc90b7cf0e76bde44496b4d0794054e6ea60f388682463132f931a7
# 转换为 GF((2^15)^17)
Gx_field = to_field_repr(Gx_int)
Gy_field = to_field_repr(Gy_int)
print_field("Gx", Gx_field)
print()
print_field("Gy", Gy_field)输出结果你可以看到正是 WinRarConfig.hpp 文件中 435~456 行的内容：
Gx = to_field([
0x38CC, 0x052F, 0x2510, 0x45AA,
0x1B89, 0x4468, 0x4882, 0x0D67,
0x4FEB, 0x55CE, 0x0025, 0x4CB7,
0x0CC2, 0x59DC, 0x289E, 0x65E3,
0x56FD
])
Gy = to_field([
0x31A7, 0x65F2, 0x18C4, 0x3412,
0x7388, 0x54C1, 0x539B, 0x4A02,
0x4D07, 0x12D6, 0x7911, 0x3B5E,
0x4F0E, 0x216F, 0x2BF2, 0x1974,
0x20DA
])验证基点 G 在复合有限域 GF((2^{15})^{17}) 需要写专门的多项式域运算代码，整个验证代码示例如下：
# GF(((2^15)^17))
def gf2_15_add(a, b):
return a ^ b
def gf2_15_mul(a, b):
# 模 x^15 + x + 1
res = 0
for i in range(15):
if (b >> i) & 1:
res ^= a << i
# 模多项式 x^15 + x + 1
for i in range(29, 14, -1):
if (res >> i) & 1:
res ^= 0b1000000000000011 << (i - 15)
return res & 0x7FFF # 15-bit mask
def gf2_15_poly_add(a, b):
return [gf2_15_add(x, y) for x, y in zip(a, b)]
def gf2_15_poly_mul(a, b):
res = [0] * 33
for i in range(17):
for j in range(17):
res[i + j] ^= gf2_15_mul(a[i], b[j])
return res
def gf2_15_17_mod(poly):
# 模 y^17 + y^3 + 1
for i in range(len(poly) - 1, 16, -1):
if poly[i]:
poly[i - 17] ^= poly[i]
poly[i - 14] ^= poly[i]
poly[i] = 0
return poly[:17]
def gf2_15_17_mul(a, b):
return gf2_15_17_mod(gf2_15_poly_mul(a, b))
def gf2_15_17_square(a):
return gf2_15_17_mul(a, a)
def gf2_15_17_add(a, b):
return gf2_15_poly_add(a, b)
def gf2_15_17_eq(a, b):
return all(x == y for x, y in zip(a, b))
def is_on_curve(x, y, b):
y2 = gf2_15_17_square(y)
xy = gf2_15_17_mul(x, y)
lhs = gf2_15_17_add(y2, xy)
x2 = gf2_15_17_square(x)
x3 = gf2_15_17_mul(x2, x)
rhs = gf2_15_17_add(x3, b)
return gf2_15_17_eq(lhs, rhs)
def to_field(arr):
assert len(arr) == 17
return arr[:]
# 参数定义
b = [0x00] * 17
b = [161] + [0]*16 # GF((2^15)^17) 中的常数元素，等价于 b[0] = 0xA1
Gx = to_field([0x38CC, 0x052F, 0x2510, 0x45AA, 0x1B89, 0x4468, 0x4882, 0x0D67,
0x4FEB, 0x55CE, 0x0025, 0x4CB7, 0x0CC2, 0x59DC, 0x289E, 0x65E3, 0x56FD])
Gy = to_field([0x31A7, 0x65F2, 0x18C4, 0x3412, 0x7388, 0x54C1, 0x539B, 0x4A02,
0x4D07, 0x12D6, 0x7911, 0x3B5E, 0x4F0E, 0x216F, 0x2BF2, 0x1974, 0x20DA])
PKx = to_field([0x3A1A, 0x1109, 0x268A, 0x12F7, 0x3734, 0x75F0, 0x576C, 0x2EA4,
0x4813, 0x3F62, 0x0567, 0x784D, 0x753D, 0x6D92, 0x366C, 0x1107, 0x3861])
PKy = to_field([0x6C20, 0x6027, 0x1B22, 0x7A87, 0x43C4, 0x1908, 0x2449, 0x4675,
0x7933, 0x2E66, 0x32F5, 0x2A58, 0x1145, 0x74AC, 0x36D0, 0x2731, 0x12B6])
# 验证
print("验证基点 G 是否在曲线上：", is_on_curve(Gx, Gy, b))
print("验证 PublicKey 是否在曲线上：", is_on_curve(PKx, PKy, b))“不可约多项式” 就是构造复合域的关键，不同于简单的大素数模，必须用它来 “裁剪” 多项式运算结果，保证域的封闭性。这也是为什么代码里有对 0x8000 （15bit 的最高位）的检查，以及特别的查表运算（对数表和指数表），都是为了高效实现这种多项式域运算。
