sign the ca7s

这题跟sign in the ca7s是一模一样的，但是多一个level3，所以只贴这一道题。

题目

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
from Crypto.Util.number import bytes_to_long
from hashlib import md5
import os

FLAG = os.environ.get("FLAG", "flag{**redacted**}")

E = EllipticCurve(GF(0x1337_ca7_eae368ff5d702e6067aaaa77ca_ca7_1337), [0, 3])
G, n = E(1, 2), E.order()

def sign(priv, ctx, msg):
    k = bytes_to_long(ctx + md5(str(priv).encode() + msg).digest())
    z = bytes_to_long(md5(ctx + msg).digest())
    r = int((k * G).x()) % n
    s = (pow(k, -1, n) * (z + r * priv)) % n
    return r, s

def verify(pub, ctx, msg, sig):
    z = bytes_to_long(md5(ctx + msg).digest())
    r, s = sig
    if 0 < r < n and 0 < s < n:
        return r == int((pow(s, -1, n) * (z * G + r * pub)).x()) % n

def chall(level, flag):
    priv = randint(1, n - 1)
    pub = priv * G
    msg = os.urandom(64)
    
    print(f"=== level {level} ===")
    for _ in range(catalan_number(level)):
        ctx = bytes.fromhex(input('context: '))
        r, s = sign(priv, ctx, msg)
        assert verify(pub, ctx, msg, (r, s))
        if level <= 1: print('message:', msg.hex())
        if level <= 2: print('sign:', r)
        if level <= 3: print('ature:', s)
    
    r, s = map(int, input('signature: ').split())
    assert verify(pub, b'n1junior_2025', f'cat /flag{level}'.encode(), (r, s))
    print(f'flag{level}:', flag)

if __name__ == "__main__":
    chall(1, "💧")
    chall(2, "🐱")
    chall(3, FLAG)

分析

看的出来这是一个ECDSA的题目，过程简单说说就是一次签名流程先生成一个私钥privpriv，在每次签名过程中随机生成一个整数kk，明文通过MD5转换得到整数zz，最后生成公钥组{r,s}\{r,s\}。公式如下

r≡(k⋅G)x(modn)s≡k−1⋅(z+r⋅priv)(modn)r\equiv (k \cdot G)_x \pmod{n}\\ s\equiv k^{-1} \cdot (z+r \cdot priv) \pmod{n}

理解上述过程之后检验参数其实是比较好推的

(s−1⋅(z⋅G+r⋅pub))x=(s−1⋅(z+r⋅priv)⋅G)x=(s−1⋅(s⋅k)⋅G)x=(k⋅G)x≡r(modn)(s^{-1}\cdot (z \cdot G+r \cdot pub))_x=(s^{-1} \cdot (z +r \cdot priv)\cdot G)_x=(s^{-1} \cdot (s\cdot k) \cdot G)_x=(k \cdot G)_x \equiv r \pmod{n}

再来看看构造的曲线E：y2=x3+3E：y^2=x^3+3，曲线EE的阶刚好等于有限域pp的值，求解ECDLP的时候可以考虑smart attack，不过这里可能是GG和EE比较简单的缘故，直接使用log()函数也能求解kk。不过这里求得的kk是模nn意义下的，如果ctxctx过长，无法恢复出最原始的kk。另外由于我们恢复点RR的时候，只知道RR的横坐标，此时会得到两个点RR，因此得到两个kk。这个时候可以利用kk的构造方法，kk的高位是ctxctx所以kk会满足

ctx⋅2128<k<(ctx+1)cdot2128ctx \cdot 2^{128}<k<(ctx+1) cdot 2^{128}

level1

level1阶段给出了{msg,r,s}\{msg,r,s\}，通过msgmsg我们可以得到zz的值，然后通过rr我们可以得到kk的值。根据s≡k−1⋅(z+r⋅priv)(modn)s\equiv k^{-1} \cdot (z+r \cdot priv) \pmod{n}其中只有一个未知数privpriv，于是求得privpriv。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
from Crypto.Util.number import *
from hashlib import md5
E = EllipticCurve(GF(0x1337_ca7_eae368ff5d702e6067aaaa77ca_ca7_1337), [0, 3])
G, n = E(1, 2), E.order()
msg=bytes.fromhex("..")
r=..
s=..
ctx=bytes.fromhex("..")#输入尽量短
g=bytes_to_long(ctx)
R=E.lift_x(r)
k=0
for _ in range(2):
    k=R.log(G)
    if k>g*2^128%n and k<(g+1)*2^128%n:
        break
    R=-R
z=bytes_to_long(md5(ctx + msg).digest())
priv=(s*k-z)*inverse(r,n)%n
kk=bytes_to_long(ctx + md5(str(priv).encode() + msg).digest())
assert kk==k
print(k)
def sign(priv, ctx, msg):
    k = bytes_to_long(ctx + md5(str(priv).encode() + msg).digest())
    z = bytes_to_long(md5(ctx + msg).digest())
    r = int((k * G).x()) % n
    s = (pow(k, -1, n) * (z + r * priv)) % n
    return r, s
rr,ss=sign(priv,b'n1junior_2025',f'cat /flag{0}'.encode())
print(rr)
print(ss)

level2

对比level1我们少了msgmsg的内容也就是无法得到zz，但是我们多了一组输入。
整理一下我们的已知条件

s1k1≡z1+r1⋅priv(modn)s2k2≡z2+r2⋅priv(modn)s_1k_1 \equiv z_1+r_1 \cdot priv \pmod{n}\\ s_2k_2 \equiv z_2+r_2 \cdot priv \pmod{n}

到这里容易想到HNP问题，这也就是为什么卡了两天一点进展都没有(怒)。后面想想其实也能知道为什么，两个模式解三个未知数，并且z1,z2,privz_1,z_2,priv没有很强的范围要求。本身维度较小的情况解决n.bit=157n.bit=157的情况是完全不可能的。所以漏洞似乎转移到了MD5上，可惜到比赛结束也没想出什么漏洞。后面看了大佬的WP才知道MD5的利用方式。
简单来说就是可以通过hashclash得到两个不同的s1,s2s1,s2实现MD5(s1)=MD5(s2)并且这样的s1,s2s1,s2还有非常优秀的性质即对于任意字符串suf都有MD5(s1+suf)=MD5(s2+suf)，再会看题目中对zz的构造方式，z = bytes_to_long(md5(ctx + msg).digest())，签名过程中msgmsg是固定的，因此我们可以构造出两个ctxctx实现zz相同，这样问题就变成二元一次的模式方程组求解，显然可以求出privpriv。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
E = EllipticCurve(GF(0x1337_ca7_eae368ff5d702e6067aaaa77ca_ca7_1337), [0, 3])
G, n = E(1, 2), E.order()
ctx=[..,..]
ctx=[bytes.fromhex(ct) for ct in ctx]
r= [..,..]
s= [..,..]
k=[]
for i in range(2):
    R=E.lift_x(r[i])
    g=bytes_to_long(ctx[i])
    print(g*2^128%n)
    print((g+1)*2^128%n)
    for _ in range(2):
        kk=R.log(G)
        if kk>g*2^128%n and kk<(g+1)*2^128%n:
            k.append(kk)
            break
        R=-R
print(k)
priv=(s[0]*k[0]-s[1]*k[1])*inverse(r[0]-r[1],n)%n
print('priv=',priv)
def sign(priv, ctx, msg):
    k = bytes_to_long(ctx + md5(str(priv).encode() + msg).digest())
    z = bytes_to_long(md5(ctx + msg).digest())
    r = int((k * G).x()) % n
    s = (pow(k, -1, n) * (z + r * priv)) % n
    return r, s
rr,ss=sign(priv,b'n1junior_2025',f'cat /flag{2}'.encode())
print(rr)
print(ss)

level3

首先回顾一下Weierstrass曲线的点加公式椭圆曲线一般写成：E:  y2=x3+ax+bE: \; y^2 = x^3 + ax + b
对于两点P=(x1,y1),Q=(x2,y2),P = (x_1, y_1), \quad Q = (x_2, y_2),它们的和R=P+Q=(x3,y3)R = P + Q = (x_3, y_3)的计算公式是：
斜率

λ=y2−y1x2−x1,(P≠Q)\lambda = \frac{y_2 - y_1}{x_2 - x_1}, \quad (P \neq Q)

横坐标

x3=λ2−x1−x2x_3 = \lambda^2 - x_1 - x_2

纵坐标

y3=λ(x1−x3)−y1y_3 = \lambda (x_1 - x_3) - y_1

对比前面的level可见我们现在只有ss的信息，缺失rr意味着我们缺失了kk的内容。不过由于kk的特殊构造，我们可以知道kk高位的信息也就是ctxctx，于是我们可以写成ki=ctx⋅2128+hk_i=ctx \cdot 2^{128} +h，这里的hh也就是MD5产生的值不超过128位。顺着这个思路我们得到Ri=(ctx⋅2128+h)GR_i=(ctx \cdot 2^{128} +h) G。为了消去hh的影响不妨差分得到

R2−R1=(ctx2−ctx1)⋅2128GR3−R1=(ctx3−ctx1)⋅2128GR4−R1=(ctx4−ctx1)⋅2128GR5−R1=(ctx5−ctx1)⋅2128GR_2-R_1=(ctx_2-ctx_1)\cdot 2^{128} G\\ R_3-R_1=(ctx_3-ctx_1)\cdot 2^{128} G\\ R_4-R_1=(ctx_4-ctx_1)\cdot 2^{128} G\\ R_5-R_1=(ctx_5-ctx_1)\cdot 2^{128} G

可以发现等式右边全是已知量，我们只需要知道其中任意一个RiR_i就可以得到全部的RR，于是我们不妨记R1=(r1,y)R_1=(r_1,y)，对于RiR_i,我们记对应得常数点为Di=(dx,dy)D_i=(d_x,d_y)，根据点加法我们知道

λ=dy−ydx−r1\lambda = \frac{d_y - y}{d_x - r_1}

则

ri=λ2−dx−r1r_i=\lambda^2 - d_x - r_1

带入siki=z+ri⋅privs_ik_i=z+r_i \cdot priv得到

siki=z+(λ2−dx−r1)⋅privs_ik_i=z+(\lambda^2 - d_x - r_1)\cdot priv

为了在多项式环中表示（不能出现分式），我们将等式两边乘以分母 (dxi−r1)2(dx_i - r_1)^2：

(siki−z)⋅(dxi−r1)2=[(dyi−y1)2−(r1+dxi)(dxi−r1)2]⋅priv(s_i k_i - z) \cdot (dx_i - r_1)^2 = \Big[ (dy_i - y_1)^2 - (r_1 + dx_i)(dx_i - r_1)^2 \Big] \cdot priv

如法炮制可以得到四个类似得等式，再又因为我们设出了R1=(r1,y)R_1=(r_1,y)，于是我们还能得到两个等式

y2=r13+3s1k1=z+r1⋅privy^2=r_1^3+3 \\ s_1k_1=z+r_1\cdot priv

一共六个式子。然后我们梳理一下未知量的个数发现我们只缺少{h,z,priv,r1,y}\{h,z,priv,r_1,y\}这五个，此时差不多已经胜券在握了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
from Crypto.Util.number import *
from hashlib import md5
E = EllipticCurve(GF(0x1337_ca7_eae368ff5d702e6067aaaa77ca_ca7_1337), [0, 3])
G, n = E(1, 2), E.order()
ctx=['ca44bdf16ebf41337b32e92b53da7da9d9f5a5c6a96a4d3cf90942822e2a25b40ffbeacdfe134e1c8bea761a888f587db154c96aa04c7539e0e4475396dda070a73dcff0477b54b15d34d07cd9571e30886e833a01463eeac95af6bbec47fee32025a695f4d007fdc88b50f7b17072ec5948ffc708f6eee6b0d2f71bafab9fbdc3062b2f701959dff2df72e3051dfe82112da950008f9dd02e8a82dd08ba1b2e0f04fddf38722b41c74bbca39e4b0e629d17ad9d9313a6d22f07dc5c396912ba318bd0079baccacac255808167fb06c7d4ef8dc7c4a5fa0c1ccd3576cd4bbdbc4d38b2dfa9369ca8b271c58188945e9dca885c3976d6a3e4c7d759dedb175c86a35d6390db80955d6c05b17150945327daaac4f0c689c116437243f2ed9516058ebc0eee3cad76de6b4650422a125a75347024551169566fdc3e5e8a6ee79f96b2eedaf2c92dfe5a29c1dac5168b45bec176fcb63156cefd128961064c37f58e350fbb7f20904e07de5b099a9dcc99bd0e9de8fcabd2a396c32458dedc97d938',
'ca44bdf16ebf41337b32e92b53da7da9d9f5a5c6a96a4d3cf90942822e2a25b40ffbeacdfe134e1c8bea761a888f587db154c96aa04c7539e0e4475396dda070a73dcff0477b54b15d34d07cd9571e30886e833a01463eeac95af6bbec47fee32025a695f4d007fdc88b50f7b17072ec5948ffc708f6eee6b0d2f71bafab9fbdc3062b2f701959dff2df72e3051dfe82112da950008f9dd02e8a82dd08ba1b2e0f04fddf38722b41c74bbca39e4b0e629d17ad9d9313a6d22f07dc5c396912ba318bd0079baccacac255808167fb06c7d4ef8dc7c4a5fa0c1ccd3576cd4bbdbc4d38b2dfa9369ca8b271c58188945e9dca885c3976d6a3e4c7d759dedb175c86a35d6390db80955d6c05b17150945327daaac470c689c116437243f2ed9516058ebc0eee3cad76de6b4650422a925a75347024551169566fdc3e5e0a6ee79f96b2eedaf2c92dfe5a29c1dac5168b45bec176fc363156cefd128961064c37f58e350fbb7f20904e07de5b099a9d4c99bd0e9de8fcabd2a396c324585edc97d938',
'ca44bdf16ebf41337b32e92b53da7da9d9f5a5c6a96a4d3cf90942822e2a25b40ffbeacdfe134e1c8bea761a888f587db154c96aa04c7539e0e4475396dda070a73dcff0477b54b15d34d07cd9571e30886e833a01463eeac95af6bbec47fee32025a695f4d007fdc88b50f7b17072ec5948ffc708f6eee6b0d2f71bafab9fbdc3062b2f701959dff2df72e3051dfe82112da9d0008f9dd02e8a82dd08ba1b2e0f04fddf38722b41c74bbca39ecb0e629d17ad9d9313a6d22f07dcdc396912ba318bd0079baccacac255808167fb06c7d4ef8d47c4a5fa0c1ccd3576cd4bbdbc4d38b2dfa9369ca8b271c58188145e9dca885c3976d6a3e4c7d7595edb175c86a35d6390db80955d6c05b17150945327daaac4f0c689c116437243f2ed9516058ebc0eee3cad76de6b4650422a125a75347024551169566fdc3e5e8a6ee79f96b2eedaf2c92dfe5a29c1dac5168b45bec176fcb63156cefd128961064c37f58e350fbb7f20904e07de5b099a9dcc99bd0e9de8fcabd2a396c32458dedc97d938',
'ca44bdf16ebf41337b32e92b53da7da9d9f5a5c6a96a4d3cf90942822e2a25b40ffbeacdfe134e1c8bea761a888f587db154c96aa04c7539e0e4475396dda070a73dcff0477b54b15d34d07cd9571e30886e833a01463eeac95af6bbec47fee32025a695f4d007fdc88b50f7b17072ec5948ffc708f6eee6b0d2f71bafab9fbdc3062b2f701959dff2df72e3051dfe82112da9d0008f9dd02e8a82dd08ba1b2e0f04fddf38722b41c74bbca39ecb0e629d17ad9d9313a6d22f07dcdc396912ba318bd0079baccacac255808167fb06c7d4ef8d47c4a5fa0c1ccd3576cd4bbdbc4d38b2dfa9369ca8b271c58188145e9dca885c3976d6a3e4c7d7595edb175c86a35d6390db80955d6c05b17150945327daaac470c689c116437243f2ed9516058ebc0eee3cad76de6b4650422a925a75347024551169566fdc3e5e0a6ee79f96b2eedaf2c92dfe5a29c1dac5168b45bec176fc363156cefd128961064c37f58e350fbb7f20904e07de5b099a9d4c99bd0e9de8fcabd2a396c324585edc97d938',
'ca44bdf16ebf41337b32e92b53da7da9d9f5a546a96a4d3cf90942822e2a25b40ffbeacdfe134e1c8bea761a880f597db154c96aa04c7539e0e447d396dda070a73dcff0477b54b15d34d07cd9571e30886e83ba01463eeac95af6bbec47fee32025a695f4d007fdc88b50f7b1f071ec5948ffc708f6eee6b0d2f79bafab9fbdc3062b2f701959dff2df72e3051dfe82112da950008f9dd02e8a82dd08ba1b2e0f04fddf38722b41c74bbca39e4b0e629d17ad9d9313a6d22f07dc5c396912ba318bd0079baccacac255808167fb06c7d4ef8dc7c4a5fa0c1ccd3576cd4bbdbc4d38b2dfa9369ca8b271c58188945e9dca885c3976d6a3e4c7d759dedb175c86a35d6390db80955d6c05b17150945327daaac4f0c689c116437243f2ed9516058ebc0eee3cad76de6b4650422a125a75347024551169566fdc3e5e8a6ee79f96b2eedaf2c92dfe5a29c1dac5168b45bec176fcb63156cefd128961064c37f58e350fbb7f20904e07de5b099a9dcc99bd0e9de8fcabd2a396c32458dedc97d938']
s=[11154694896732447905689374736338618815276091537, 74933960157450757671256061540484810446107345123, 51873568513748381018351602926997229967297958417, 31581818612454837771407319666185013378637291428, 43899203296223282768371041553603410773341644426]
ctx=[(bytes_to_long(bytes.fromhex(ct))) for ct in ctx]
P.<r_1,y,h,z,priv>=PolynomialRing(GF(n))
TG=2^128*G
D_points=[]
for i in range(1,len(ctx)):
    D_points.append((ctx[i]-ctx[0])*TG)
polynomials=[]
polynomials.append(y^2-r_1^3-3)
for i in range(len(ctx)):
    k_i=ctx[i]*2^128+h
    if i==0:
        polynomials.append(s[i]*k_i-z-r_1*priv)
    else:
        D_i=D_points[i-1]
        dx_i, dy_i = D_i.xy()
        num = (dy_i - y)^2 - (r_1 + dx_i) * (dx_i - r_1)^2
        den = (dx_i - r_1)^2
        poly_sig = (s[i] * k_i - z) * den - num * priv
        polynomials.append(poly_sig)

现在polynomials里面存的就是我们刚刚推导的六个式子，再通过格罗布纳基方法化简多项式。

1
2
3
4
5
6
7
8
I=P.ideal(polynomials)
B=I.groebner_basis()
poly_h = None
for poly in B:
    vars_in_poly = poly.variables()
    if len(vars_in_poly) == 1 and vars_in_poly[0] == h:
        poly_h = poly
        break

得到的poly_h就是只含有hh的多项式h+109715005092730082481014013427730311863191312900h+109715005092730082481014013427730311863191312900，不过这里不能用roots方法求解hh因为这个多项式虽然只有一个元hh，但是他的类型依旧是多元多项式，无法调用。
下面提供两种方法求解hh。

1
2
3
4
const_term=poly_h.coefficient({h:0})#返回h^0的系数，也就是常系数
#或者调用const_term=poly_h.constant_coefficient()
h_val=n-const_term
print(h_val)
1
2
3
4
R.<h>=PolynomialRing(GF(n))
poly_h_univar=R(poly_h)    # 转成一元多项式
roots=poly_h_univar.roots(multiplicities=False)
print(roots)

最后由于得到了hh于是我们可以算出kik_i的值，这样就变成和level2一样的问题了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
k1=int(ctx[1]*2^128+h_val)
k2=int(ctx[2]*2^128+h_val)
r1=int((k1*G).x())%n
r2=int((k2*G).x())%n
priv_val=(s[1]*k1-s[2]*k2)*inverse(r1-r2,n)%n
def sign(priv, ctx, msg):
    k = bytes_to_long(ctx + md5(str(priv).encode() + msg).digest())
    z = bytes_to_long(md5(ctx + msg).digest())
    r = int((k * G).x()) % n
    s = (pow(k, -1, n) * (z + r * priv)) % n
    return r, s
rr,ss=sign(priv_val,b'n1junior_2025',f'cat /flag{3}'.encode())
print(rr)
print(ss)

完整代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
from Crypto.Util.number import *
from hashlib import md5
E = EllipticCurve(GF(0x1337_ca7_eae368ff5d702e6067aaaa77ca_ca7_1337), [0, 3])
G, n = E(1, 2), E.order()
ctx=['ca44bdf16ebf41337b32e92b53da7da9d9f5a5c6a96a4d3cf90942822e2a25b40ffbeacdfe134e1c8bea761a888f587db154c96aa04c7539e0e4475396dda070a73dcff0477b54b15d34d07cd9571e30886e833a01463eeac95af6bbec47fee32025a695f4d007fdc88b50f7b17072ec5948ffc708f6eee6b0d2f71bafab9fbdc3062b2f701959dff2df72e3051dfe82112da950008f9dd02e8a82dd08ba1b2e0f04fddf38722b41c74bbca39e4b0e629d17ad9d9313a6d22f07dc5c396912ba318bd0079baccacac255808167fb06c7d4ef8dc7c4a5fa0c1ccd3576cd4bbdbc4d38b2dfa9369ca8b271c58188945e9dca885c3976d6a3e4c7d759dedb175c86a35d6390db80955d6c05b17150945327daaac4f0c689c116437243f2ed9516058ebc0eee3cad76de6b4650422a125a75347024551169566fdc3e5e8a6ee79f96b2eedaf2c92dfe5a29c1dac5168b45bec176fcb63156cefd128961064c37f58e350fbb7f20904e07de5b099a9dcc99bd0e9de8fcabd2a396c32458dedc97d938',
'ca44bdf16ebf41337b32e92b53da7da9d9f5a5c6a96a4d3cf90942822e2a25b40ffbeacdfe134e1c8bea761a888f587db154c96aa04c7539e0e4475396dda070a73dcff0477b54b15d34d07cd9571e30886e833a01463eeac95af6bbec47fee32025a695f4d007fdc88b50f7b17072ec5948ffc708f6eee6b0d2f71bafab9fbdc3062b2f701959dff2df72e3051dfe82112da950008f9dd02e8a82dd08ba1b2e0f04fddf38722b41c74bbca39e4b0e629d17ad9d9313a6d22f07dc5c396912ba318bd0079baccacac255808167fb06c7d4ef8dc7c4a5fa0c1ccd3576cd4bbdbc4d38b2dfa9369ca8b271c58188945e9dca885c3976d6a3e4c7d759dedb175c86a35d6390db80955d6c05b17150945327daaac470c689c116437243f2ed9516058ebc0eee3cad76de6b4650422a925a75347024551169566fdc3e5e0a6ee79f96b2eedaf2c92dfe5a29c1dac5168b45bec176fc363156cefd128961064c37f58e350fbb7f20904e07de5b099a9d4c99bd0e9de8fcabd2a396c324585edc97d938',
'ca44bdf16ebf41337b32e92b53da7da9d9f5a5c6a96a4d3cf90942822e2a25b40ffbeacdfe134e1c8bea761a888f587db154c96aa04c7539e0e4475396dda070a73dcff0477b54b15d34d07cd9571e30886e833a01463eeac95af6bbec47fee32025a695f4d007fdc88b50f7b17072ec5948ffc708f6eee6b0d2f71bafab9fbdc3062b2f701959dff2df72e3051dfe82112da9d0008f9dd02e8a82dd08ba1b2e0f04fddf38722b41c74bbca39ecb0e629d17ad9d9313a6d22f07dcdc396912ba318bd0079baccacac255808167fb06c7d4ef8d47c4a5fa0c1ccd3576cd4bbdbc4d38b2dfa9369ca8b271c58188145e9dca885c3976d6a3e4c7d7595edb175c86a35d6390db80955d6c05b17150945327daaac4f0c689c116437243f2ed9516058ebc0eee3cad76de6b4650422a125a75347024551169566fdc3e5e8a6ee79f96b2eedaf2c92dfe5a29c1dac5168b45bec176fcb63156cefd128961064c37f58e350fbb7f20904e07de5b099a9dcc99bd0e9de8fcabd2a396c32458dedc97d938',
'ca44bdf16ebf41337b32e92b53da7da9d9f5a5c6a96a4d3cf90942822e2a25b40ffbeacdfe134e1c8bea761a888f587db154c96aa04c7539e0e4475396dda070a73dcff0477b54b15d34d07cd9571e30886e833a01463eeac95af6bbec47fee32025a695f4d007fdc88b50f7b17072ec5948ffc708f6eee6b0d2f71bafab9fbdc3062b2f701959dff2df72e3051dfe82112da9d0008f9dd02e8a82dd08ba1b2e0f04fddf38722b41c74bbca39ecb0e629d17ad9d9313a6d22f07dcdc396912ba318bd0079baccacac255808167fb06c7d4ef8d47c4a5fa0c1ccd3576cd4bbdbc4d38b2dfa9369ca8b271c58188145e9dca885c3976d6a3e4c7d7595edb175c86a35d6390db80955d6c05b17150945327daaac470c689c116437243f2ed9516058ebc0eee3cad76de6b4650422a925a75347024551169566fdc3e5e0a6ee79f96b2eedaf2c92dfe5a29c1dac5168b45bec176fc363156cefd128961064c37f58e350fbb7f20904e07de5b099a9d4c99bd0e9de8fcabd2a396c324585edc97d938',
'ca44bdf16ebf41337b32e92b53da7da9d9f5a546a96a4d3cf90942822e2a25b40ffbeacdfe134e1c8bea761a880f597db154c96aa04c7539e0e447d396dda070a73dcff0477b54b15d34d07cd9571e30886e83ba01463eeac95af6bbec47fee32025a695f4d007fdc88b50f7b1f071ec5948ffc708f6eee6b0d2f79bafab9fbdc3062b2f701959dff2df72e3051dfe82112da950008f9dd02e8a82dd08ba1b2e0f04fddf38722b41c74bbca39e4b0e629d17ad9d9313a6d22f07dc5c396912ba318bd0079baccacac255808167fb06c7d4ef8dc7c4a5fa0c1ccd3576cd4bbdbc4d38b2dfa9369ca8b271c58188945e9dca885c3976d6a3e4c7d759dedb175c86a35d6390db80955d6c05b17150945327daaac4f0c689c116437243f2ed9516058ebc0eee3cad76de6b4650422a125a75347024551169566fdc3e5e8a6ee79f96b2eedaf2c92dfe5a29c1dac5168b45bec176fcb63156cefd128961064c37f58e350fbb7f20904e07de5b099a9dcc99bd0e9de8fcabd2a396c32458dedc97d938']
s=[11154694896732447905689374736338618815276091537, 74933960157450757671256061540484810446107345123, 51873568513748381018351602926997229967297958417, 31581818612454837771407319666185013378637291428, 43899203296223282768371041553603410773341644426]
ctx=[(bytes_to_long(bytes.fromhex(ct))) for ct in ctx]
P.<r_1,y,h,z,priv>=PolynomialRing(GF(n))
TG=2^128*G
D_points=[]
for i in range(1,len(ctx)):
    D_points.append((ctx[i]-ctx[0])*TG)
polynomials=[]
polynomials.append(y^2-r_1^3-3)
for i in range(len(ctx)):
    k_i=ctx[i]*2^128+h
    if i==0:
        polynomials.append(s[i]*k_i-z-r_1*priv)
    else:
        D_i=D_points[i-1]
        dx_i, dy_i = D_i.xy()
        num = (dy_i - y)^2 - (r_1 + dx_i) * (dx_i - r_1)^2
        den = (dx_i - r_1)^2
        poly_sig = (s[i] * k_i - z) * den - num * priv
        polynomials.append(poly_sig)
I=P.ideal(polynomials)
B=I.groebner_basis()
poly_h = None
for poly in B:
    vars_in_poly = poly.variables()
    if len(vars_in_poly) == 1 and vars_in_poly[0] == h:
        poly_h = poly
        break
const_term=poly_h.coefficient({h:0})#返回h^0的系数，也就是常系数
h_val=n-const_term
k1=int(ctx[1]*2^128+h_val)
k2=int(ctx[2]*2^128+h_val)
r1=int((k1*G).x())%n
r2=int((k2*G).x())%n
priv_val=(s[1]*k1-s[2]*k2)*inverse(r1-r2,n)%n
def sign(priv, ctx, msg):
    k = bytes_to_long(ctx + md5(str(priv).encode() + msg).digest())
    z = bytes_to_long(md5(ctx + msg).digest())
    r = int((k * G).x()) % n
    s = (pow(k, -1, n) * (z + r * priv)) % n
    return r, s
rr,ss=sign(priv_val,b'n1junior_2025',f'cat /flag{3}'.encode())
print(rr)
print(ss)

至此三个level已经全部解决。
对于构造hashclash的更多细节可以看这里。