Introduction to Elliptic Curve over Complex Fields

之前参加了 imaginaryCTF 的练习赛，解了 Complex Curve Crypto 这道在复数域上的椭圆曲线题，很好玩。做这道题的时候也学习了一下复数域上的椭圆曲线，所以会顺带介绍一下。

椭圆曲线与模形式#

Theorem. 对所有椭圆曲线 $E$ ，都有 $E\cong\mathbb{C}/\Lambda$ ，其中 $\Lambda=\mathbb{Z}\omega_1+\mathbb{Z}\omega_2$ 是一个复数域上的格。

这个定理证明很复杂，我自己也搞不太懂。大概是 Weierstrass 函数同时满足了 $\wp(x+z_1)=\wp(x+z_2)=\wp(x)$ 和 $\wp'(z)^2=4\wp(z)^3-g_2\wp(z)-g_3$ ，所以可以构造一个映射。

这个定理说明我们可以把椭圆曲线上的离散对数问题变成一个格上的离散对数问题。而格上的离散对数就是一个有理逼近问题，所以可以用 LLL 解决。

接下来是 $j$ -invariant 的定义。这个东西最初是用来分类格的同构类的。首先一个格在旋转下是同构的，所以我们可以把一个格简化为 $\Lambda=\mathbb{Z}+\mathbb{Z}\tau, \tau=\frac{\omega_2}{\omega_1}$ 。但即便是这样， $\tau$ 也不能唯一确定格的同构类，例如 $\omega_1=2+\tau,\omega_2=1+\tau$ 也表示了同样的格。实际上，一个格的全部同构类为 $\tau\sim\frac{a\tau+b}{c\tau+d}, |ad-bc|=1$ ，其中 $a,b,c,d\in\mathbb{Z}$ 。

Prop. $j$ -invariant 是唯一一个满足 $j(\tau)=j(\frac{a\tau+b}{c\tau+d}), ad-bc=1$ 且 $j(i)=1728, j(e^{2\pi i/3})=0$ ，定义在复数域上半平面的全纯函数。

同样，这个的证明也很难，而且也牵扯到了模形式的一些东西。所以只做密码学的话可以跳过了，总之先相信（x

对于所有的格， $j$ -invariant 都唯一地确定了它的同构类。基于前面的定理，我们可以把椭圆曲线的同构类和格的同构类联系起来，这自然给出了椭圆曲线的 $j$ -invariant。¹

通过各种变换，我们可以把所有 $\tau$ 变换到 $|\tau|\geq 1,|\text{Re}(\tau)|<\frac{1}{2}$ 的区域上（图自己去 wikipedia 看）。

然后，我们来看一下椭圆曲线在复数域上的 isogeny。首先，我们可以仿照有限域，利用 torsion point 来构造 isogeny。而 torsion point 在格上就变成了类似 $n$ 等分点的东西。因此从格的角度来看，isogeny 是两个共享很多 $n$ 等分点的格之间的部分同态（或者说嵌入？）。

Prop. classical modular polynomial 的一组解是一个 isogeny 的对应格的 $j$ -invariant，即 $j(n\tau),j(\tau)$ 是 classical modular polynomial 的一组解。

在椭圆曲线 isogeny 的 mitm 攻击中，我们也会用到 classical modular polynomial 来加速遍历。这就是用到了它的解集恰好是 isogeny 的两个椭圆曲线的 $j$ -invariant 这个性质。对于一个 $\tau$ ，它的 $n$ 次 isogeny 有 $n+1$ 个，分别是 $n\tau$ 和 $\frac{\tau+k}{n}, k=0,1,\cdots,n-1$ ，恰好是格的所有不同构的 $n$ 等分点。

所以说，isogeny 在复数域上的性质是非常好的，后面这道题就是一个例子。

Complex Curve Crypto#

1
from sage.all import *
2
phi = classical_modular_polynomial(l:=3)
3
flag = ZZ.from_bytes(os.environ.get('FLAG', 'jctf{fakeflag}').encode())
4
j = jp = ComplexField(1337)(1337)
5
for d in flag.digits(l):
6
    roots = phi(X=j).univariate_polynomial().roots(multiplicities=False)
7
    roots.sort(key=jp.dist)
8
    del roots[0] # no turning back
9
    roots.sort(key=arg)
10
    j, jp = roots[d], j
11
print(j)

这道题通过 classical modular polynomial 实现了复数域上的 isogeny。我们的目标是找到通往最终 $j$ -invariant 的路径。

我们先调用 pari 的库算出起点和终点的 $\tau$ 。但 $j$ -invariant 的逆不唯一，我们实际获取的那个是 normalized 的那一个解。

根据前面的说明，我们知道起始值是 $j(\tau)=1337$ ，而每次 isogeny 都会将其变成 $j(\frac{\tau+k}{n}), k=0,1,\cdots,n-1$ 。² 因此在最终 $\tau$ 会变成 $\frac{\tau+k}{3^n}, k\in\mathbb{Z}$ 。可以看到，这个过程中 $\tau$ 的虚部会不断变小，所以最终的解一定无法轻易地 normalize 到 $|\tau|\geq 1,|\text{Re}(\tau)|<\frac{1}{2}$ 的区域上。

于是，问题转化为了给定 $\tau_1, \tau_2$ ，怎么找到 $k$ 使得 $j(\tau_2)=j(\frac{\tau_1+k}{3^n})$ 。我们可以把这个写成 $\text{PSL}(2,\mathbb{Z})$ 的变换，即 $\frac{a\tau_2+b}{c\tau_2+d}=\frac{\tau_1+k}{3^n}$ 。

这个式子的实部因为 $k$ 的存在，是非常难解的，但好消息是虚部是不变的，而 $a,b,c,d$ 的值大概是 $3^n$ 的量级，所以如果精度足够高的话，我们可以用 LLL 来找小整数解。我们先利用 $ad-bc=1$ 化简一下虚部。设 $\tau_2=x+yi$ ，

\begin{align*} &\text{Im}\left(\frac{a\tau_2+b}{c\tau_2+d}\right) \\ &=\text{Im}\left(\frac{ax+b+ayi}{cx+d+cyi}\right) \\ &=\text{Im}\left(\frac{(ax+b+ayi)(cx+d-cyi)}{(cx+d)^2+(cy)^2}\right) \\ &=\frac{(cx+d)ay-(ax+b)cy}{(cx+d)^2+(cy)^2} \\ &=\frac{y}{c^2(x^2+y^2)+2cdx+d^2} \\ \end{align*}

在一通消元后，我们只需要把 $c^2, cd, d^2$ 当做未知数，构造一个矩阵，然后用 LLL 求解。这个 LLL 还是有一些不稳定，所以需要用 $c^2, cd, d^2$ 的关系稍微调一下。

在解出 $k$ 之后，我们可以直接算出每一步对应的 $j$ -invariant，然后稍微验证一下就可以知道是第几个了。

1
from sage.all import *
2
from mpmath import mp
3

4
def babai_cvp(B, t, perform_reduction=True):
5
    if perform_reduction:
6
        B = B.LLL(delta=0.75)
7

8
    G = B.gram_schmidt()[0]
9
    b = t
10
    for i in reversed(range(B.nrows())):
11
        c = ((b * G[i]) / (G[i] * G[i])).round()
12
        b -= c * B[i]
13

14
    return b
15

16
l = 3
17
phi = classical_modular_polynomial(l)
18
flag = ZZ.from_bytes(os.environ.get('FLAG', 'jctf{ghrf65fakefd2lag}').encode())
19
# flag = ZZ.from_bytes(b'jctf{fakef212113lag}')
20
j = jp = ComplexField(1337)(1337)
21
print(len(flag.digits(l)), flag.digits(l))
22
ddd = [2, 1, 2, 2, 1, 2, 2, 0, 1, 1, 1, 2, 0, 0, 0, 1, 0, 2, 0, 2, 1, 0, 1, 0, 1, 2, 2, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 1, 2, 1, 0, 1, 0, 0, 2, 1, 0, 2, 1, 2, 0, 1, 0, 2, 1, 1, 1, 0, 1, 0, 2, 2, 1, 0, 2, 0, 0, 1, 2, 0, 2, 2, 2, 2, 0, 0, 1, 0, 1, 2, 1, 1, 2, 0, 0, 2, 2, 1, 2, 0, 1, 2, 1, 1, 1, 1, 1, 0, 1, 0, 0, 1, 1, 0, 1, 2, 1, 2, 2, 0, 0, 1, 0, 1, 2, 0, 0, 2, 0, 1, 1, 1, 2, 1, 2, 1, 1, 2, 0, 1, 2, 1, 2, 2, 0, 1]
23
for d in ddd:
24
    roots = phi(X=j).univariate_polynomial().roots(multiplicities=False)
25

26
    roots.sort(key=jp.dist)
27
    del roots[0] # no turning back
28
    roots.sort(key=arg)
29
    j, jp = roots[d], j
30
print(j)
31
target_j = j
32

33
mp.dps = 8000
34
pari("\p 8000")
35
def get_tau(j_val):
36
    """
37
    solve j(tau) = j_val
38
    """
39
    j_val = CC(j_val)
40
    output = pari(f"ellinit([{str(j_val)}]).omega")
41
    w1, w2 = output
42
    tau = w1 / w2
43
    return CC(tau)
44

45
CC = ComplexField(8000)
46
# target_j = CC(target_j)
47
target_j = CC(["-6380.29156755903034687704660000282270448709570700984709657263854520138341881550084848649839410922876936678108641559731906139407589458824525200739437427675429842545943862350406898342718600643307574207936681432539822432021043321858999100455988010088297166788530685045590301521392833041157761230553808660966639987227996254364651040683587985017755013287627806460764447918220597797227073500295101888328945378", "-40214.6672669145274363733990190234269396915010860735171342583778810557492152506583335099397606096949655915384682940536670398063862158837139959936293817852537495478495004482851179789975853315750442943613549504080182872285152393975211173312274904654221951964258004673123691758298620284682558712820558193891787303533093197420998108945366704043133890680849252774739771188873183182185315971489373696493547256"]) # i=136
48
t = get_tau(CC(1337))
49
t = (t - 4) / (t - 3)
50

51
R = PolynomialRing(RR, 'x')
52
xbar = R.gen()
53

54
def try_get_transform(t1, t2):
55
        """
56
        t2 = (a*t1 + b) / (c*t1 + d), a*d - b*c = 1
57
        """
58
        x0 = t1.real()
59
        x1 = t2.real()
60
        y0 = t1.imag()
61
        y1 = t2.imag()
62
        u = y0 / y1
63
        v1 = x0 ** 2 + y0 ** 2
64
        v2 = 2 * x0
65
        S1 = 2**3800
66
        S2 = 2**3000
67
        M = matrix(ZZ, [[S1, -S2, 0, 0], [(v1*S1).round(), 0, -S2, 0], [(v2*S1).round(), 0, 0, -S2]])
68
        target = vector(ZZ, [(u*S1).round(), 0, 0, 0])
69
        M = M.LLL()
70
        short_vectors = []
71
        v=M[0]
72
        v = [v[1] // S2, v[2] // S2, v[3] // S2]
73
        sol = babai_cvp(M, target, perform_reduction=False)
74

75
        dd = sol[1] // S2
76
        cc = sol[2] // S2
77
        cd = sol[3] // S2
78
        print(M[0][0].bit_length(), abs(sol[0]).bit_length(), sol[1].bit_length(), sol[2].bit_length(), sol[3].bit_length())
79
        print(cc, cd, dd)
80
        print(v)
81

82
        f = (dd+v[0]*xbar)*(cc+v[1]*xbar) - (cd+v[2]*xbar)**2
83
        rrr = f.roots(multiplicities=False)
84
        find = False
85
        print("rrr", rrr)
86
        for r in rrr[1:]:
87
            rr = r.round()
88
            cc2 = cc + rr * v[1]
89
            dd2 = dd + rr * v[0]
90
            cd2 = cd + rr * v[2]
91
            if cc2.is_square() and dd2.is_square() and gcd(cc2, dd2) == 1:
92
                print("Found a solution:", cc2, cd2, dd2)
93
                find = True
94
                cc, cd, dd = cc2, cd2, dd2
95
                break
96
        if not find:
97
            return None
98

99
        # print(cc * v1 + cd * v2 + dd - u)
100
        if not (cc.is_square() and dd.is_square()):
101
            return None
102
        c = sqrt(cc)
103
        d = sqrt(dd)
104
        if cd < 0:
105
            d = -d
106
        assert c * d == cd
107
        print(f"c = {c}, d = {d}")
108
        print(d**2+c**2 * v1 + cd * v2 - u)
109
        # c**2 * (x0**2+y0**2) + 2cd * x0 + d**2 = u
110
        return c, d
111

112
tau1 = t
113
tau2 = get_tau(target_j)
114

115
print()
116
print(target_j)
117
print(elliptic_j((t+1)/3))
118

119
for i in range(10, 180):
120
    print("checking i =", i)
121
    k = 3**i
122
    ret = try_get_transform(tau2, tau1/k)
123
    if ret is None:
124
        continue
125
    c, d = ret
126
    print(gcd(c, d))
127

128
    _, a, b = xgcd(d, c)
129
    b = -b
130

131
    assert a * d - b * c == 1
132

133
    tau2_transformed = (a * tau2 + b) / (c * tau2 + d)
134
    u = tau2_transformed.real_part().floor()
135
    a -= u * c
136
    b -= u * d
137
    tau2_transformed = (a * tau2 + b) / (c * tau2 + d)
138
    print(tau2_transformed)
139

140
    u = (tau2_transformed*k).real()
141
    v = tau1.real()
142
    if abs(u.frac() - v.frac()) > abs(u.frac() - (1 - v.frac())):
143
        raise
144
        tau2_transformed = 1-tau2_transformed.conjugate()
145

146
    print((tau2_transformed*k - tau1))
147
    print((tau2_transformed*k - tau1).real().round(), k)
148
    u0 = (tau2_transformed*k - tau1).real().round()
149
    break
150

151
def get_j(tau):
152
    while True:
153
        tau -= tau.real_part().round()
154
        if tau.norm() <= 1:
155
            tau = -1 / tau
156
        else:
157
            break
158
    return elliptic_j(tau)
159

160
print(get_j((tau1+u0) / k))
161
digits = []
162
test_j = test_jp = ComplexField(1337)(1337)
163

164
def walk(j, jp, d):
165
    roots = phi(X=j).univariate_polynomial().roots(multiplicities=False)
166
    roots.sort(key=jp.dist)
167
    del roots[0] # no turning back
168
    roots.sort(key=arg)
169
    return roots[d], j
170

171
for i in range(400):
172
    if k <= 3**i:
173
        break
174

175
    jp = get_j((tau1+u0) / 3**(i-1))
176
    j0 = get_j((tau1+u0) / 3**i)
177
    j1 = get_j((tau1+u0) / 3**(i+1))
178

179
    roots = phi(X=ComplexField(1337)(j0)).univariate_polynomial().roots(multiplicities=False)
180
    roots.sort(key=jp.dist)
181
    del roots[0]  # no turning back
182
    roots.sort(key=j1.dist)
183
    target = roots[0]
184
    # print(j1.dist(target))
185
    assert j1.dist(target) < 1e-10, j1.dist(target)
186
    roots.sort(key=arg)
187
    d = roots.index(target)
188
    digits.append(d)
189

190
    assert test_j.dist(get_j((tau1+u0) / 3**(i))) < 1e-10, i
191
    test_j, test_jp = walk(test_j, test_jp, d)
192

193
print(test_j)
194
print("Digits:", digits)
195

196
flag = sum(d * l**i for i, d in enumerate(digits))
197
print(bytes.fromhex(hex(flag)[2:]))

这也是那个 1728 的由来。 ↩
这里有个小trick，我们需要先通过 $\text{PSL}(2,\mathbb{Z})$ 将 $\tau$ 变一下，使得 $j(3\tau)$ 是被删掉的那一个。这样就可以通过不走回头路的方式躲掉 $\tau\to3\tau$ 的情况。 ↩

椭圆曲线与模形式#

Complex Curve Crypto#

Footnotes#