椭圆曲线同源与weil对

AiY0u2025-09-182025-10-07

同源（isogeny）

椭圆曲线同源（isogeny）是椭圆曲线曲线理论中的核心概念

它描述两条椭圆曲线之间的特殊映射关系
我们在这里研究它的定义、核心性质，然后讨论它和weil对之间的关系，并在最后附上一道CTF真题

一、定义

$设E_1和E_2是定义在同一域k上的两条椭圆曲线（标准形式为y^2 = x^3 + ax+b,其中a,b\in k ）$

同源（isogeny） 是一个从 $E_1$ 到$ E_2$ 的映射

$\phi:E_1\to E_2$ ，满足：

代数性： $\phi$ 由域 k 上的有理函数（分式多项式）定义；
群同态：保持椭圆曲线的加法群结构，即对任意点 $P,Q\in E1，有 \phi(P+Q)=\phi(P)+\phi(Q)$ ；
非平凡性：不将所有点映射到 $E_2$ 的无穷远点（单位元）。

我们用通俗的语言来描述一下这三条性质

– 代数性使得我们可以用代数的形式，将 $E_1$ 中的元素通过分式多项式的运算，得到其到 $E_2$ 的映射

这就使得两个椭圆曲线之间是有明确的公式连接的；

– 群同态则是保持了两个曲线的运算结构不发生变化，这是当然要保证的；

– 在理解非平凡性之前我们先想想，平凡代表了什么

如果一个曲线是平凡的，那么 $E_1$ 中的所有点全部会映射成 $E_2$ 上的无穷远点,

在实际的密码学应用中，平凡的映射会导致 $E_2$ 无法体现任何 $E_1$ 的信息，也就是说，对我们没有任何意义
所以说非平凡性保证了我们至少能在 $E_2$ 中获知一些 $E_1$ 的信息

二、核心性质

度数（Degree）

同源 $\phi$ 的度数（记为 $deg\phi$ ）是一个正整数，描述了映射的 “覆盖次数”：
- 对于有限域上的椭圆曲线，度数等于原曲线上每个点在映射下的原像个数（计数重数）。
- 度数为 1 的同源称为同构（isomorphism），此时 $\phi$ 可逆（存在逆映射 $\phi−1$ ），即 $E_1$ 与 $E_2$ 结构完全相同。
核（Kernel）

同源的核是 E1 中被映射到 E2 无穷远点（单位元）的点集： $ker\phi = {P\in E_1|\phi(P) \in \mathcal{O}_{E_2}}$

核是 E1 的有限子群（因同源是有限到一的映射），且同源由其核唯一确定（在同构意义下）。这是同源的核心特征 —— 知道核即可构造同源。
双有理性质

同源是双有理映射的推广：若 ϕ 是度数为 d 的同源，则存在 “对偶同源” $\hat{\phi}$ :E2→E1，使得 $\hat{\phi}∘ϕ=[d]$ （即 “乘以 d” 的映射）。
基域扩张下的性质

若域 k 扩张为更大的域 K（如有限域的扩域），同源在 K 上仍保持群同态性质，这对研究有限域上的椭圆曲线至关重要。

这里不做解释可能会很难懂，我们先来看“核”这一概念
首先我们看到，核是一个由E1中的某些点组成的点集，这些点都有一个特点，就是它们经过映射之后，都映射在了E2的无穷远点。

这里我们把这些点记作 $K_i$ , 假设我们随便从E1中拎出来一个不同于 $K_i$ 的点，记为P

那么我们可以运算得到其他点：

$P+K_i \\ P+2K_i \\ P+3K_i\\ ……$

根据群同态的性质 $(如果Q = P + K,那么\phi(Q) = \phi(P) + \phi(K))$

由此我们容易得到，上面由P和 $K_i$ 经过运算得到的点，全部映射在 $\phi(P)$ 上

这就是为什么我们说，一旦知道了核，我们就唯一确定了同源

我们可以把“核”理解为一个压缩机，其他点通过这个压缩机之后，就会出现E1中的若干点映射到E2上的同一个点的现象

那么之后我们就很好理解“度数”了

**度数(degree)**就是上面所说的“压缩”程度的量化标准，具体来说就是，我们把多少个点压缩在了一起

倘若 $deg\phi = 1$ ,那么我们将同源 $\phi$ 称为同构， $E_1$ 和 $E_2$ 是一一对应的，因为没有"压缩"操作，我们也容易得到 $E_2\rightarrow E_1$ 的逆过程

Weil对

weil对，这里我们只把它当一个封装好的匣子来用，先不讨论匣子内部的数学运算.

将它的形式记为 $e(P,Q)$

weil对的输入和输出

输入是椭圆曲线中的两个n阶点

输出是域（比如复数域、有限域）中的一个 n 次单位根

weil对输出结果的意义

weil对在应用层面，能够帮助我们观察输入的两个点是否线性相关

如果 $e(P,Q)=1$ ,说明P和Q两个点，要么P=Q，要么Q是P的倍数，它们是线性相关的，也就是说它们之间的联系很平凡

如果 $e(P,Q)\not=1$ ,说明P和Q两个点，是线性无关的(无法通过倍数关系表示），关联能反映群的深层结构，传递更多信息。

weil对的双线性性

我们先了解一下**双线性性（Bilinearity）**的概念

双线性性简单来说是一个映射对两个输入变量分别满足 “线性关系”

先举一个两个变量的函数 $f(x,y)$ ，如果它满足以下两条规则，就说它具有双线性性：

对第一个变量线性

$对任意常数 a,b 和变量 x_1,x_2,y,有：f(a\cdot x_1+b\cdot x_2,y)=a\cdot f(x_1,y)+b\cdot f(x_2,y)$
对第二个变量线性

$对任意常数 a,b 和变量 x,y_1,y_2，有：f(x,a\cdot y_1+b\cdot y_2)=a⋅f(x,y_1)+b⋅f(x,y_2)$

而weil对的双线性性关系写为：

对第一个变量线性

$对任意常数 a,b 和变量 P_1,P_2,Q,有：e(a\cdot P_1+b\cdot P_2,Q)=e(P_1,Q)^a\cdot e(P_2,Q)^b$
对第二个变量线性

$对任意常数 a,b 和变量 P,Q_1,Q_2，有：e(P,a\cdot Q_1+b\cdot Q_2)=e(P,Q_1)^a\cdot e(P,Q_2)^b$

尤为突出的特点是，它把加法全部翻译为了乘法，把乘法全部翻译为了幂运算，这个性质是重点！

这也说明了weil对的一个重要能力：加法域问题转化到乘法域来解决！

椭圆曲线同源与Weil对的联系

$设椭圆曲线E_1，同源曲线E_2，同源映射度数为deg\phi，有关系式\\e_2(φ(P),φ(Q)) = e_1(P,Q)^{degφ}$

真的要讨论为什么有这个关系式，很复杂，我还没学会

但我们可以用很不专业的语言来方便记忆

因为我们对椭圆曲线进行了压缩 $deg\phi$ 倍，所以Weil对的翻译也要进行 $deg\phi$ 重（雾）

前面的东西越写越水，我们先看这么一道题

from Crypto.Util.number import *
from secret import flag

f = open("output.txt", "w")

def get_Prime(bits):
    from random import choices
    bytes = [long_to_bytes(x) for x in range(1, 256)]
    while True:
        num = b''.join(choices(bytes, k=bits//8))
        if is_prime(bytes_to_long(num)):
            return bytes_to_long(num)

def gen_para():
    while True:
        a = randint(50, 70)
        r = getPrime(10)
        if is_prime(2**a * r * lcm(range(1, 256)) - 1):
            return a, r

a, r = gen_para()
f.write(f'{a = }\n')
f.write(f'{r = }\n')

p = 2**a * r * lcm(range(1, 256)) - 1
F.<i> = GF(p^2, modulus=[1, 0, 1])
E = EllipticCurve(F, [0, 1])
E.set_order((p+1)**2)

P, Q = E.gens()[0], E.gens()[1]

f.write(f'P = {(P.x(), P.y())}\n')
f.write(f'Q = {(Q.x(), Q.y())}\n')

pp = get_Prime(1024)
qq = get_Prime(1024)
n = pp * qq
e = 65537

gift = []

while pp:
    x = pp & 0xff
    assert x != 0
    pp = pp >> 8
    k = randint(1, 2**a * x)
    R = P + k * Q
    K = (p + 1) // (2**a * x) * R
    phi = E.isogeny(K, algorithm="factored")
    tmp1 = phi(P)
    tmp2 = phi(Q)
    gift.append([(tmp1.x(), tmp1.y()), (tmp2.x(), tmp2.y())])

f.write(f'gift = {gift}\n')

m = bytes_to_long(flag)
c = pow(m, e, n)

f.write(f'n = {n}\n')
f.write(f'c = {c}\n')

附件太长不放了

大概翻译一下题目：

生成了一个素数p，并且p+1的因数很多

搞了一个 $(p+1)^2$ 阶的椭圆曲线E，并获取生成元P、Q

随机生成大质数pp和qq，进入RSA环节

pp的每八位摘出来经过一系列过程生成一个同源映射，并记录 $\phi(P)和\phi(Q)$ 到gift

加密flag用的是标准的RSA

那么我们应当是从gift入手，尝试恢复pp

解题脚本如下：

load("output.sage")

L = lcm(range(1,256))
p = (1<<a)*r*L - 1
F.<i> = GF(p^2, modulus=[1,0,1])
E = EllipticCurve(F,[0,1])
nE = p+1

def toF(z):
    return F(Integer(z.real())) + F(Integer(z.imag()))*i

P = E(toF(P[0]), toF(P[1]))
Q = E(toF(Q[0]), toF(Q[1]))
gift2 = [((toF(Xp), toF(Yp)), (toF(Xq), toF(Yq))) for (Xp,Yp),(Xq,Yq) in gift]

g = P.weil_pairing(Q, nE)

pp_bytes = []
for (Xp,Yp),(Xq,Yq) in gift2:
    A = ((Yp^2 - Xp^3) - (Yq^2 - Xq^3))/(Xp-Xq)
    B = (Yp^2 - Xp^3) - A*Xp
    E2 = EllipticCurve(F,[A,B])
    P2 = E2(Xp,Yp); Q2 = E2(Xq,Yq)
    h = P2.weil_pairing(Q2, nE)
    d = discrete_log(h, g, ord=nE)
    x = d >> a
    pp_bytes.append(x)

pp = sum(b<<(8*i) for i,b in enumerate(pp_bytes))
qq = n//pp
phi = (pp-1)*(qq-1)
d = inverse_mod(65537, phi)
m = pow(c,d,n)
print(int(m).to_bytes((m.bit_length()+7)//8,'big'))

前面就是数据的正常处理

重点在于恢复pp

我们重建同源得到的曲线E2，并构建出 $h=e(\phi(P),\phi(Q))$

直接根据上面所说的关系
$e_2(φ(P),φ(Q)) = e_1(P,Q)^{degφ}$

因为Weil对的值域是P,Q点对应的所有n次单位根，这个离散对数问题其实相当简单

能很容易求出 $deg\phi$

1	K = [(p+1)/(2^a · x)] · R

其中R = P + k·Q（P, Q是生成元，k是随机数）。

由于椭圆曲线E的阶是(p+1)^2，且P, Q的阶都是p+1，因此R的阶也是p+1（生成元的线性组合仍为p+1阶）。

进一步，(p+1)/(2^a · x)是整数，因此：

(2^a · x) · K = (p+1) · R = 𝒪（无穷远点，群的单位元）

这意味着 K 的阶是2^a · x

也就是说，度数 $deg\phi=2^a \cdot x$

我们求出 $deg\phi$ 之后，就很容易恢复x。

也就很容易恢复pp，并进行常规RSA解密。

先这样子，后续会在本文进行补充修缮。