Crypto CTF 2021 Writeup

Mon Aug 02 2021

    7/31-8/1 で開催していた Crypto CTF 2021 にソロで参加しました。結果は 7th/444 (得点のあるチームのみカウント) でした。 image

    自分の好きな Crypto のみが出題される CTF だったので結構力を入れて挑みました (早寝早起きした)。Crypto というよりは算数パズルみたいな問題が多かったですが楽しめました。 問題数多いので難易度 medium 以上の問題について writeup を書きます。

    medium

    Triplet

    50 solves

    RSA の問題。 ある1つの e,de, ded1modϕi,ϕi=(pi1)(qi1)ed \equiv 1 \mod \phi_i, \phi_i = (p_i-1)(q_i-1) (0i<3)(0 \le i < 3) が満たされるような3種類の素数ペア (p0,q0),(p1,q1),(p2,q2)(p_0, q_0), (p_1, q_1), (p_2, q_2) を指定します。1<e<ϕi,1<d<ϕi1 < e < \phi_i, 1 < d < \phi_i を満たす必要があります。

    ϕ2=k1ϕ1=k1k0ϕ0(k0,k1N)\phi_2 = k_1 \phi_1 = k_1 k_0 \phi_0 (k_0, k_1 \in \N) となるような ϕi\phi_i を見つけられれば、ed1modϕ2,ed>ϕ2ed \equiv 1 \mod \phi_2, ed > \phi_2 のときに ed1modϕi(0i<2)ed \equiv 1 \mod \phi_i (0 \le i < 2) も同時に満たされます。なので ϕi\phi_i がそのようになっている素数を求めていきます。 適当に素数 p0p_0 を生成し、 p1=k0(p01)+1p_1 = k_0 (p_0 - 1) + 1 が素数となるような k0k_0 を探すことで雑に見つかります。

    find_pq.py
    from Crypto.Util.number import isPrime
    
    p_list = [978192613682615126805602952972767216490903041377]
    for i in range(2, 100):
        tmp = (p_list[-1] - 1) * i + 1
        if isPrime(tmp):
            p_list.append(tmp)
            break
    for i in range(2, 1000):
        tmp = (p_list[-1] - 1) * i + 1
        if isPrime(tmp):
            p_list.append(tmp)
            break
    q = 792815675392945389923804143268131204888157010473
    phi_list = [(p - 1) * (q - 1) for p in p_list]

    次に ed1modϕ2ed \equiv 1 \mod \phi_2 かつ d<ϕ0d < \phi_0 となる e,de, d を雑に探します。

    find_ed.py
    for e in range(2, 10**6):
        try:
            d = int(pow(e, -1, phi_list[-1]))
        except ZeroDivisionError:
            continue
        if d < phi_list[0]:
            print(e, d)
            break

    これで求まったe,d,pi,qie, d, p_i, q_i を送ることでフラグを得ることができました。

    solve.py
    from pwn import remote
    
    e, d = (
        10391,
        288835272238104090924086199222396301800937844500536833016516522864596327429508604217436920083751,
    )
    
    _r = remote("07.cr.yp.toc.tf", 18010)
    
    _r.sendlineafter("[Q]uit\n", "s")
    
    for i in range(3):
        _ = _r.recvline()
        _r.sendline(f"{p_list[i]},{q}")
    
    _ = _r.recvline()
    _r.sendline(f"{e},{d}")
    _r.interactive()

    CCTF{7HrE3_b4Bie5_c4rRi3d_dUr1nG_0Ne_pr39naNcY_Ar3_triplets}

    Elegant Curve

    16 solves

    楕円曲線の問題。

    if isPrime(p) and 0 < a < p and 0 < b < p and p.bit_length() == nbit:
    if isPrime(q) and 0 < c < q and 0 < d < q and 0 < q - p <= 2022 and q.bit_length() == nbit:

    これらを満たす2種類の楕円曲線のパラメータ y2=x3+ax+bmodpy^2 = x^3 + ax + b \mod p, y2=x3+cx+dmodqy^2 = x^3 + cx + d \mod q を指定します。 nbit は160です。その楕円曲線上で離散対数問題が解ければフラグが得られます。

    まともな楕円曲線だと160bit での離散対数問題を解くのは難しいため、2種類の工夫をしました。 1つ目は y2=(x+1)2(x2)=x33x2y^2 = (x + 1)^2(x-2) = x^3 - 3x - 2 の形にしたことです。このような楕円曲線では ψ:(x,y)y+α(x+1)yα(x+1)\psi: (x, y) \to \frac{y + \alpha(x+1)}{y - \alpha(x+1)} (ただし α2=a\alpha^2 = a) の写像によって体 FpF_p 上の multiplicative group に移せることが知られています。 2つ目は p1p - 1 を小さい整数の積にすることです。これは Pohlig-Hellman algorithm を使えるようにするためです。

    これで離散対数問題を十分高速に解くことができるようになるのですが、P=xGP = xGGG の位数によっては偽の解が生じ得ます (解を位数で割った余りしか得られないため。p1p - 1 の素因数に小さい値があればあるほど偽の解が出やすい)。これはいい回避方法がぱっと思いつかなかったので何回か try することでフラグを得ました。

    solve.sage
    import re
    from pwn import remote, context
    
    
    def fast_dlp_modn(H, G, n):
        return int(pari(f"znlog({H}, Mod({G}, {n}))"))
    
    
    while True:
        _r = remote("07.cr.yp.toc.tf", 10010)
    
        p = 2^2 * 3 * 5 * 149 * 397 * 89431 * 429733 * 4754429087 * 21431031803 * 54082242377 + 1
        q = 2^2 * 3 * 47^2 * 341676649 * 21030287449 * 105537162827 * 37391085931811 + 1
    
        a = p - 3
        b = p - 2
        c = q - 3
        d = q - 2
    
        _r.sendlineafter("[Q]uit\n", "s")
        _r.sendlineafter(": a, b, p \n", f"{a},{b},{p}")
        _r.sendlineafter("<= 2022\n", f"{c},{d},{q}")
        ret = _r.recvline().strip().decode()
        G = list(map(int, re.findall(r"\| G is on first  ECC and G = {\(([0-9]+), ([0-9]+)\)}", ret)[0]))
        ret = _r.recvline().strip().decode()
        H = list(map(int, re.findall(r"\| H is on second ECC and H = {\(([0-9]+), ([0-9]+)\)}", ret)[0]))
        ret = _r.recvline().strip().decode()
        U = list(map(int, re.findall(r"\| r \* G = {\(([0-9]+), ([0-9]+)\)}", ret)[0]))
        ret = _r.recvline().strip().decode()
        V = list(map(int, re.findall(r"\| s \* H = {\(([0-9]+), ([0-9]+)\)}", ret)[0]))
    
        alpha = 691543214394924384546321648306135152969653983571
        G_psi = (G[1] + alpha * (G[0] + 1)) * pow(G[1] - alpha * (G[0] + 1), -1, p) % p
        U_psi = (U[1] + alpha * (U[0] + 1)) * pow(U[1] - alpha * (U[0] + 1), -1, p) % p
    
        r = fast_dlp_modn(U_psi, G_psi, p)
        assert pow(G_psi, r, p) == U_psi
    
        alpha = 522942771760774594392535493944005348637064325562
        H_psi = (H[1] + alpha * (H[0] + 1)) * pow(H[1] - alpha * (H[0] + 1), -1, q) % q
        V_psi = (V[1] + alpha * (V[0] + 1)) * pow(V[1] - alpha * (V[0] + 1), -1, q) % q
    
        s = fast_dlp_modn(V_psi, H_psi, q)
        assert pow(H_psi, s, q) == V_psi
    
        _r.sendlineafter("get the flag: \n", f"{r},{s}")
        ret = _r.recvline().strip().decode()
        _r.close()
        if "flag" in ret:
            print(ret)
            break

    Improved

    37 solves

    def gen_params(nbit):
        p, q = [getPrime(nbit) for _ in range(2)]
        n, f, g = p * q, lcm(p - 1, q - 1), p + q
        e = pow(g, f, n ** 2)
        u = divmod(e - 1, n)[0]
        v = inverse(u, n)
        params = int(n), int(f), int(v)
        return params

    このように生成された params に対し、

    def improved(m, params):
        n, f, v = params
        if 1 < m < n ** 2 - 1:
            e = pow(m, f, n ** 2)
            u = divmod(e - 1, n)[0]
            L = divmod(u * v, n)[1]
        H = hashlib.sha1(str(L).encode("utf-8")).hexdigest()
        return H

    mm のハッシュが計算されます。このハッシュが衝突する m1,m2m_1, m_2 を送ればフラグが得られます。

    実は nn % f + 1 = g なので g=p+qg = p + q が求まるため2次方程式を解くことで p,qp, q が求まったり、eun=1e - u * n = 1 から ee が求まったりします。

    しかし f=lcm(p1,q1)f = \mathrm{lcm}(p-1,q-1) なので2の倍数であることが確実なため、 m1=2m_1 = 2m2=n222modn2m_2 = n^2 - 2 \equiv -2 \mod n^2 を指定するだけで ee が同じになり、ハッシュを衝突させることができます。何を問われた問題だったのだろう🤔

    solve.py
    import re
    
    from Crypto.Util.number import getPrime, inverse
    from pwn import remote
    
    
    _r = remote("05.cr.yp.toc.tf", 14010)
    
    _r.sendlineafter("[Q]uit\n", "g")
    ret = _r.recvline().strip().decode()
    n, f, v = map(int, re.findall(r"\| Parameters = \(([0-9]+), ([0-9]+), ([0-9]+)\)", ret)[0])
    
    _r.sendlineafter("[Q]uit\n", "r")
    _r.sendlineafter("| please send the messages split by comma: \n", f"{2},{n**2-2}")
    _r.interactive()

    CCTF{Phillip_N0W_4_pr0b4b1liStiC__aSymM3Tr1C__AlGOrithM!!}

    Ferman

    31 solves

    e = 65537
    isPrime(p) = True
    isPrime(q) = True
    n = p * q
    (p - 437)**2 + (q - 784)**2 = 10361260280629817716615376756017077930645839952216327941760067320726021213209057344786508377349803583538968917852066194184384961070812319588143033971547102366229627802808807925134421089388501061177731372428832404144683890221704206802913372432409131676725210901535098751418251872866013280844158228683928132748670905650514575544930537361662019547998142569015889799098700356406386839808082802819221420083338846406259588746394272324929265325919199250529991846741612256230795883813515625
    m = bytes_to_long(flag)
    c = pow(m, e, n)

    RSA の秘密鍵 p,qp, q に対し、 (pa)2+(qb)2=c(p-a)^2 + (q-b)^2 = c が成立するという条件が与えられます。

    ガウス整数の素因数分解を考えることで、 (x+iy)(xiy)=x2+y2(x + iy)(x - iy) = x^2 + y^2 となる x,yx, y を求めることができたため、これを利用します。

    k = 10361260280629817716615376756017077930645839952216327941760067320726021213209057344786508377349803583538968917852066194184384961070812319588143033971547102366229627802808807925134421089388501061177731372428832404144683890221704206802913372432409131676725210901535098751418251872866013280844158228683928132748670905650514575544930537361662019547998142569015889799098700356406386839808082802819221420083338846406259588746394272324929265325919199250529991846741612256230795883813515625
    
    GI = GaussianIntegers()
    GI(k).factor()
    (I) * (-110935748565706808545452731038884*I - 1673809851384879136750725022885175)^7 * (110935748565706808545452731038884*I - 1673809851384879136750725022885175)^7 * (I - 6)^7 * (-I - 2)^7 * (2*I + 1)^7 * (I + 6)^7
    
    (-110935748565706808545452731038884*I - 1673809851384879136750725022885175)^7 * (I - 6)^7 * (2*I +1)^7
    2250191360275908942759836805214916387730617773023826091034265686964815046012130214759405715974002077792077919656432366401968366052803784066989682480353264274699925759660197732461666118233606279297721205467765814980690185654667097229297968283*I + 2301716560041542621183488933524077475239162882878719181927983642214147903067475044730115988538550222999449838267481218690409785448038694891086920968207750944411381429555732054836934832649287381942584929838820786450610981028633759669457251244
    
    a = 2250191360275908942759836805214916387730617773023826091034265686964815046012130214759405715974002077792077919656432366401968366052803784066989682480353264274699925759660197732461666118233606279297721205467765814980690185654667097229297968283
    b = 2301716560041542621183488933524077475239162882878719181927983642214147903067475044730115988538550222999449838267481218690409785448038694891086920968207750944411381429555732054836934832649287381942584929838820786450610981028633759669457251244
    assert a ** 2 + b ** 2 == k

    あとは RSA の復号を行うだけです。

    solve.py
    enc_flag = 275368327318108903295175979235078859662726052499685937295398091157377276372757798047586402720819472986388661996446380988082266671821826476798218433162440327531549083297724499051700420109280345499960900696603611709412955636174302937617820524571024304344901792165038939427510954561450506468719265498723674829197024796448390659474630664539875687968121994396242843446045450727872511862272187355405758196007422012606406934513453435705131334147064102151401784980611761888867009132682337
    
    p = b + 437
    q = a + 784
    phi = (p - 1) * (q - 1)
    d = int(pow(65537, -1, phi))
    flag = pow(enc_flag, d, p * q)
    print(long_to_bytes(flag))

    CCTF{Congrats_Y0u_5OLv3d_x**2+y**2=z**7}

    Salt and Pepper

    69 solves

    :salt_pepper.py
    assert len(salt) == len(pepper) == 19
    assert md5(salt).hexdigest() == "5f72c4360a2287bc269e0ccba6fc24ba"
    assert sha1(pepper).hexdigest() == "3e0d000a4b0bd712999d730bc331f400221008e0"
    
    
    def auth_check(salt, pepper, username, password, h):
        return (
            sha1(
                pepper + password + md5(salt + username).hexdigest().encode("utf-8")
            ).hexdigest()
            == h
        )

    saltpepper のハッシュがわかっているときに、ある特定の文字列を含んでいる username password を指定したときに auth_check が通るようなハッシュを求める問題です。 length extension attack が使えます。 length extension attack には hashpump を使用しました。

    hashpump -s 5f72c4360a2287bc269e0ccba6fc24ba -k 19 -a n3T4Dm1n
    95623660d3d04c7680a52679e35f041c
    \x80\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x98\x00\x00\x00\x00\x00\x00\x00n3T4Dm1n
    
    hashpump -s 3e0d000a4b0bd712999d730bc331f400221008e0 -k 19 -a P4s5W0rd95623660d3d04c7680a52679e35f041c
    83875efbe020ced3e2c5ecc908edc98481eba47f
    \x80\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x98P4s5W0rd95623660d3d04c7680a52679e35f041c

    これらをサーバーに送ることでフラグが得られました。

    solve.py
    from hashlib import md5, sha1
    
    from Crypto.Util.number import long_to_bytes, bytes_to_long
    from pwn import remote
    
    inp_username = b"\x80\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x98\x00\x00\x00\x00\x00\x00\x00n3T4Dm1n"
    inp_password = b"\x80\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x98P4s5W0rd"
    sha1_hash = "83875efbe020ced3e2c5ecc908edc98481eba47f".encode()
    
    _r = remote("02.cr.yp.toc.tf", 28010)
    
    _r.sendlineafter("[Q]uit\n", "l")
    _r.sendlineafter(
        "| send your username, password as hex string separated with comma: \n",
        inp_username.hex() + "," + inp_password.hex(),
    )
    _r.sendlineafter("| send your authentication hash: \n", sha1_hash)
    _r.interactive()

    CCTF{Hunters_Killed_82%_More_Wolves_Than_Quota_Allowed_in_Wisconsin}

    Tiny ECC

    16 solves

    Elegant Curve と似た問題。

    if a*b != 0:
    if isPrime(p) and p.bit_length() == nbit and isPrime(2*p + 1):

    これらを満たす a,b,p,qa, b, p, q を指定したあと、楕円曲線 Fpˉ\bar{F_p} 上と Fqˉ\bar{F_q} 上の楕円曲線 y2=x3+ax+by^2 = x^3 + ax + b で離散対数問題が解ければフラグが得られます。

    a,ba, b の条件がゆるく、 a=b=pqa = b = pq とすれば楕円曲線は y2=x3y^2 = x^3 となります。このような singular curve 上では (x,y)xy(x, y) \to \frac{x}{y} の写像によって additive group に移せることが知られています。

    solve.py
    import re
    
    from Crypto.Util.number import inverse
    from pwn import remote, context
    
    # 適当に決めた
    p = 210954976541768303162895189242638938551
    q = 421909953083536606325790378485277877103
    
    _r = remote("01.cr.yp.toc.tf", 29010)
    
    _r.sendlineafter("[Q]uit\n", "c")
    _r.sendlineafter("send your prime: \n", str(p))
    
    _r.sendlineafter("[Q]uit\n", "a")
    _r.sendlineafter("a and b separated by comma: \n", f"{p*q},{p*q}")
    
    _r.sendlineafter("[Q]uit\n", "s")
    _ = _r.recvuntil("| We know that: \n")
    ret = _r.recvline().strip().decode()
    Px, Py = map(int, re.findall(r"\| P = \(([0-9]+),([0-9]+)\)", ret)[0])
    ret = _r.recvline().strip().decode()
    kPx, kPy = map(int, re.findall(r"\| k\*P = \(([0-9]+),([0-9]+)\)", ret)[0])
    ret = _r.recvline().strip().decode()
    Qx, Qy = map(int, re.findall(r"\| Q = \(([0-9]+),([0-9]+)\)", ret)[0])
    ret = _r.recvline().strip().decode()
    lQx, lQy = map(int, re.findall(r"\| l\*Q = \(([0-9]+),([0-9]+)\)", ret)[0])
    k = inverse(Px * inverse(Py, p) % p, p) * kPx * inverse(kPy, p) % p
    l = inverse(Qx * inverse(Qy, q) % q, q) * lQx * inverse(lQy, q) % q
    _r.sendlineafter("send the k and l separated by comma: \n", f"{k},{l}")
    
    _r.interactive()

    CCTF{ECC_With_Special_Prime5}

    Onlude

    48 solves

    フラグの値を陽に含んでいる11x11の行列AAに対し、 E=L1S(A+R)E = L^{-1}S(A+R) という計算で暗号化されています。ここでL,UL, USS をLU分解したもので、S=LUS = LU が成立します。与えられている値はE,LUL,L1S2L,R1S8E, LUL, L^{-1}S^2L, R^{-1}S^8です。

    がちゃがちゃ式変形をすることで AA が求まります。

    • S2=(LUL)(L1S2L)S^2 = (LUL) (L^{-1}S^2L) (LUL)^{-1}
    • S8=(S2)4S^8 = (S^2)^4
    • R=S8(R1S8)1R = S^8 (R^{-1}S^8)^{-1}
    • L1S=(L1S2L)(SL)1=(L1S2L)(LUL)1L^{-1}S = (L^{-1}S^2L)(SL)^{-1} = (L^{-1}S^2L)(LUL)^{-1}
    • A=(L1S)1ERA = (L^{-1}S)^{-1} E - R
    solve.py
    p = 71
    alphabet = "=0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ$!?_{}<>"
    
    
    def load_matrix(s):
        s_mod = s.replace("[ ", "[").replace("  ", ",").replace(" ", ",")
        return matrix(GF(p), list(map(eval, s_mod.split("\n"))))
    
    
    E = load_matrix(
        """[25 55 61 28 11 46 19 50 37  5 21]
    [20 57 39  9 25 37 63 31 70 15 47]
    [56 31  1  1 50 67 38 14 42 46 14]
    [42 54 38 22 19 55  7 18 45 53 39]
    [55 26 42 15 48  6 24  4 17 60 64]
    [ 1 38 50 10 19 57 26 48  6  4 14]
    [13  4 38 54 23 34 54 42 15 56 29]
    [26 66  8 48  6 70 44  8 67 68 65]
    [56 67 49 61 18 34 53 21  7 48 32]
    [15 70 10 34  1 57 70 27 12 33 46]
    [25 29 20 21 30 55 63 49 11 36  7]"""
    )
    LUL = load_matrix(
        """[50  8 21 16 13 33  2 12 35 20 14]
    [36 55 36 34 27 28 23 21 62 17  8]
    [56 26 49 39 43 30 35 46  0 58 43]
    [11 25 25 35 29  0 22 38 53 51 58]
    [34 14 69 68  5 32 27  4 27 62 15]
    [46 49 36 42 26 12 28 60 54 66 23]
    [69 55 30 65 56 13 14 36 26 46 48]
    [25 48 16 20 34 57 64 62 61 25 62]
    [68 39 11 40 25 11  7 40 24 43 65]
    [54 20 40 59 52 60 37 14 32 44  4]
    [45 20  7 26 45 45 50 17 41 59 50]"""
    )
    L1S2L = load_matrix(
        """[34 12 70 21 36  2  2 43  7 14  2]
    [ 1 54 59 12 64 35  9  7 49 11 49]
    [69 14 10 19 16 27 11  9 26 10 45]
    [70 17 41 13 35 58 19 29 70  5 30]
    [68 69 67 37 63 69 15 64 66 28 26]
    [18 29 64 38 63 67 15 27 64  6 26]
    [ 0 12 40 41 48 30 46 52 39 48 58]
    [22  3 28 35 55 30 15 17 22 49 55]
    [50 55 55 61 45 23 24 32 10 59 69]
    [27 21 68 56 67 49 64 53 42 46 14]
    [42 66 16 29 42 42 23 49 43  3 23]"""
    )
    R1S8 = load_matrix(
        """[51  9 22 61 63 14  2  4 18 18 23]
    [33 53 31 31 62 21 66  7 66 68  7]
    [59 19 32 21 13 34 16 43 49 25  7]
    [44 37  4 29 70 50 46 39 55  4 65]
    [29 63 29 43 47 28 40 33  0 62  8]
    [45 62 36 68 10 66 26 48 10  6 61]
    [43 30 25 18 23 38 61  0 52 46 35]
    [ 3 40  6 45 20 55 35 67 25 14 63]
    [15 30 61 66 25 33 14 20 60 50 50]
    [29 15 53 22 55 64 69 56 44 40  8]
    [28 40 69 60 28 41  9 14 29  4 29]"""
    )
    
    S2 = LUL * L1S2L * LUL.inverse()
    S8 = S2 ** 4
    R = S8 * R1S8.inverse()
    L1S = L1S2L * LUL.inverse()
    A = L1S.inverse() * E - R
    
    A_list = A.list()
    flag = ""
    for a in A_list[:120:5]:
        flag += alphabet[a]

    CCTF{LU__D3c0mpO517Ion__4L90?}

    Tuti

    71 solves

    フラグの前半部分、後半部分をそれぞれ x,yx, y (整数表示) として、ある与えられた kk に対し

    assert((x**2 + 1)*(y**2 + 1) - 2*(x - y)*(x*y - 1) == 4*(int(k, 16) + x*y))

    が成立することがわかっています。

    雑に sagemath の solve に投げてみます。

    k = int(
        """
    000bfdc32162934ad6a054b4b3db8578674e27a165113f8ed018cbe9112
    4fbd63144ab6923d107eee2bc0712fcbdb50d96fdf04dd1ba1b69cb1efe
    71af7ca08ddc7cc2d3dfb9080ae56861d952e8d5ec0ba0d3dfdf2d12764
    """.replace(
            "\n", ""
        ),
        16,
    )
    
    x, y = var("x, y")
    f = (x^2 + 1) * (y^2 + 1) - 2 * (x - y) * (x * y - 1) - 4 * (k + x * y)
    roots = solve(f == 0, [x, y])

    x,yx, y が正であることから、

    x == -(r2 - 992752253935874779143952218845275961347009322164731344882417010624071055636710540798045985678351986133613)/(r2 - 1), y == r2

    と表されることがわかります。 s=r21s = r2 - 1 と変数を変えると、 ss

    992752253935874779143952218845275961347009322164731344882417010624071055636710540798045985678351986133612

    で割り切れる必要があります。 この整数を素因数分解し、それぞれの素因数がx,yx, yのどちらのものかを全探索させるコードを書き、フラグを復元しました。

    solve.sage
    primes = [2, 2, 3, 11, 11, 19, 47, 71, 3449, 11953, 5485619, 2035395403834744453, 17258104558019725087, 1357459302115148222329561139218955500171643099]
    
    for i in range(2**len(primes)):
        n = i
        tmp_primes = []
        for j in range(len(primes)):
            if n % 2 == 1:
                tmp_primes.append(primes[j])
            n //= 2
        s = prod(tmp_primes)
        flag_suf = long_to_bytes(s + 1)
        flag_pre = long_to_bytes(992752253935874779143952218845275961347009322164731344882417010624071055636710540798045985678351986133612 // s - 1)
        if b"CCTF" in flag_pre:
            print(flag_pre + flag_suf)
    
    

    CCTF{S1mPL3_4Nd_N!cE_Diophantine_EqUa7I0nS!}

    Maid

    36 solves

    ある公開鍵 p2qp^2q に対して、 m2modp2qm^2 \mod p^2q の暗号化が何回でもできます。またソースコードには計算方法が書かれていないのですが復号もできます。フラグを m65537modpqm^{65537} \mod pq で暗号化したものが与えられるのでこれを復号する問題です。

    復号の処理を探るためいろいろ実験を行ったところ、 enc(dec(c))c\mathrm{enc}(\mathrm{dec}(c)) \ne c となっていることがわかりました (なんで)。怪しいので gcd(p2q,dec(2)22)\gcd(p^2q, \mathrm{dec}(2)^2 - 2) を計算してみると pp が求まりました (なんで)。何もわからない。

    solve.sage
    import re
    
    from Crypto.Util.number import long_to_bytes
    from pwn import remote
    
    _r = remote("04.cr.yp.toc.tf", 38010)
    
    # leak pubkey
    _r.sendlineafter("|	[Q]uit\n", "e")
    _r.sendlineafter("| Send the message to encrypt: \n", str(2**1536))
    ret = _r.recvline().strip().decode()
    ret_int = int(re.findall(r"\| encrypt\(msg, pubkey\) = (.*)", ret)[0])
    pubkey = 2 ** 3072 - ret_int
    
    # leak p
    _r.sendlineafter("|	[Q]uit\n", "d")
    _r.sendlineafter("| Send the ciphertext to decrypt: \n", str(2))
    ret = _r.recvline().strip().decode()
    ret_int = int(re.findall(r"\| decrypt\(enc, privkey\) = (.*)", ret)[0])
    p = int(sqrt(gcd(ret_int ** 2 - 2, pubkey)))
    q = pubkey // p ** 2
    assert p ** 2 * q == pubkey
    phi = (p - 1) * (q - 1)
    d = int(pow(65537, -1, phi))
    
    # decode enc flag
    _r.sendlineafter("|	[Q]uit\n", "s")
    ret = _r.recvline().strip().decode()
    ret_int = int(re.findall(r"\| enc = (.*)", ret)[0])
    flag = int(pow(ret_int, d, p * q))
    print(long_to_bytes(flag))

    CCTF{___Ra8!N_H_Cryp70_5YsT3M___}

    medium-hard

    Double Miff

    16 solves

    def onmiff(a, b, p, G):
        x, y = G
        return (a * x * (y ** 2 - 1) - b * y * (x ** 2 - 1)) % p == 0

    このような曲線 (ax(y21)by(x21)modpax(y^2-1) - by(x^2-1) \mod p) を考えます。フラグの前半部分、後半部分を xx 座標に持つこの曲線上の点を P,QP, Q として、 P+P,P+Q,Q+QP + P, P + Q, Q + Q の座標が与えられています。ここでこの曲線上の足し算は

    def addmiff(X, Y):
        x_1, y_1 = X
        x_2, y_2 = Y
        x_3 = (
            (x_1 + x_2)
            * (1 + y_1 * y_2)
            * inverse((1 + x_1 * x_2) * (1 - y_1 * y_2), p)
            % p
        )
        y_3 = (
            (y_1 + y_2)
            * (1 + x_1 * x_2)
            * inverse((1 + y_1 * y_2) * (1 - x_1 * x_2), p)
            % p
        )
        return (x_3, y_3)

    で定義されます。

    P+P,P+Q,Q+QP + P, P + Q, Q + Q の3点が与えられているので、この曲線のパラメータ a,b,pa, b, p が求められないかを考えます。 がちゃがちゃ式変形をすると、ある2点 A0,A1A_0, A_1x,yx, y 座標について、

    x0 * (y0 ^ 2 - 1) * y1 * (x1 ^ 2 - 1) - x1 * (y1 ^ 2 - 1) * y0 * (x0 ^ 2 - 1)

    pp の倍数となることがわかります。これを3点から3通り求め gcd を取り、さらに素因数分解を行うことで pp が求まります。 pp が求まれば連立方程式から a,ba, b も求まりますが、この方程式の解は不定となり、 b=kamodpb = ka \mod p となる kk が求まります。簡単のため a=1,b=ka = 1, b = k とします。

    次に PPQQ の座標を求めるため、 P=(x,y)P = (x, y) としたときに P+PP + P を計算することで x,yx, y についての方程式を立てます。煩雑なので省略しますが、

    (x21)2a1bc=x2c=41(P+P).x(P+P).y(x^2 - 1)^2 a^{-1} b c = x^2 \\ c = 4^{-1} (P + P).x (P + P).y

    が成り立ちます。

    あとはこの4次方程式を解けばフラグが得られます。

    solve.sage
    PQ = (
        540660810777215925744546848899656347269220877882,
        102385886258464739091823423239617164469644309399,
    )
    QQ = (
        814107817937473043563607662608397956822280643025,
        961531436304505096581595159128436662629537620355,
    )
    PP = (
        5565164868721370436896101492497307801898270333,
        496921328106062528508026412328171886461223562143,
    )
    
    p = 1141623079614587900848768080393294899678477852887
    c = int(x0 * (y0 ^ 2 - 1) * pow(y0 * (x0 ^ 2 - 1), -1, p) % p)
    assert c == x1 * (y1 ^ 2 - 1) * pow(y1 * (x1 ^ 2 - 1), -1, p) % p
    a = 1
    b = c
    
    PR.<x> = PolynomialRing(Zmod(p))
    
    cpp = int((PP[0] * PP[1]) * pow(4, -1, p))
    f = (x^2 - 1)^2 * pow(a, -1, p) * b * cpp - x^2
    roots = f.roots()
    for root, _ in roots:
        print(long_to_bytes(root))
    
    cqq = int((QQ[0] * QQ[1]) * pow(4, -1, p))
    f = (x^2 - 1)^2 * pow(a, -1, p) * b * cqq - x^2
    roots = f.roots()
    for root, _ in roots:
        print(long_to_bytes(root))

    CCTF{D39enEr47E_ECC_4TtaCk!_iN_Huffs?}

    Frozen

    29 solves

    あるパラメータ p,rp, r (pp は素数) が与えられ、 c=0,1,,4c = 0, 1, \cdots, 4 の5種類について rc+1smodpr^{c+1}s \mod p (ssはランダムな整数) の前半96bitが与えられています。後半32bitは秘密鍵になっており sign に使われます。 指定された文字列について sign を求められればフラグが得られます。 sign

    def sign(msg, privkey, d):
        msg = msg.encode("utf-8")
        l = len(msg) // 4
        M = [bytes_to_long(msg[4 * i : 4 * (i + 1)]) for i in range(l)]
        q = int(next_prime(max(M)))
        sign = [M[i] * privkey[i] % q for i in range(l)]
        return sign

    となっており、実質的に秘密鍵を求めればよさそうです。

    問題の性質上 LLL が使えそうです。https://github.com/rkm0959/Inequality_Solving_with_CVP を使わせていただきました。

    solve.sage
    import copy
    import re
    from sage.modules.free_module_integer import IntegerLattice
    
    from Crypto.Util.number import bytes_to_long
    from pwn import remote
    
    # Directly taken from rbtree's LLL repository
    # From https://oddcoder.com/LOL-34c3/, https://hackmd.io/@hakatashi/B1OM7HFVI
    def Babai_CVP(mat, target):
        M = IntegerLattice(mat, lll_reduce=True).reduced_basis
        G = M.gram_schmidt()[0]
        diff = target
        for i in reversed(range(G.nrows())):
            diff -= M[i] * ((diff * G[i]) / (G[i] * G[i])).round()
        return target - diff
    
    
    def solve(mat, lb, ub, weight=None):
        num_var = mat.nrows()
        num_ineq = mat.ncols()
    
        max_element = 0
        for i in range(num_var):
            for j in range(num_ineq):
                max_element = max(max_element, abs(mat[i, j]))
    
        if weight == None:
            weight = num_ineq * max_element
    
            # sanity checker
        if len(lb) != num_ineq:
            print("Fail: len(lb) != num_ineq")
            return
    
        if len(ub) != num_ineq:
            print("Fail: len(ub) != num_ineq")
            return
    
        for i in range(num_ineq):
            if lb[i] > ub[i]:
                print("Fail: lb[i] > ub[i] at index", i)
                return
    
                # heuristic for number of solutions
        DET = 0
    
        if num_var == num_ineq:
            DET = abs(mat.det())
            num_sol = 1
            for i in range(num_ineq):
                num_sol *= ub[i] - lb[i]
            if DET == 0:
                print("Zero Determinant")
            else:
                num_sol //= DET
                # + 1 added in for the sake of not making it zero...
                print("Expected Number of Solutions : ", num_sol + 1)
    
        # scaling process begins
        max_diff = max([ub[i] - lb[i] for i in range(num_ineq)])
        applied_weights = []
    
        for i in range(num_ineq):
            ineq_weight = weight if lb[i] == ub[i] else max_diff // (ub[i] - lb[i])
            applied_weights.append(ineq_weight)
            for j in range(num_var):
                mat[j, i] *= ineq_weight
            lb[i] *= ineq_weight
            ub[i] *= ineq_weight
    
        # Solve CVP
        target = vector([(lb[i] + ub[i]) // 2 for i in range(num_ineq)])
        result = Babai_CVP(mat, target)
    
        for i in range(num_ineq):
            if (lb[i] <= result[i] <= ub[i]) == False:
                print("Fail : inequality does not hold after solving")
                break
    
                # recover x
        fin = None
    
        if DET != 0:
            mat = mat.transpose()
            fin = mat.solve_right(result)
    
        ## recover your result
        return result, applied_weights, fin
    
    
    def sign(msg, privkey, d):
        msg = msg.encode("utf-8")
        l = len(msg) // 4
        M = [bytes_to_long(msg[4 * i : 4 * (i + 1)]) for i in range(l)]
        q = int(next_prime(max(M)))
        sign = [M[i] * privkey[i] % q for i in range(l)]
        return sign
    
    
    _r = remote("03.cr.yp.toc.tf", 25010)
    
    _r.sendlineafter("[Q]uit\n", "s")
    _ = _r.recvuntil("p = ")
    p = int(_r.recvline())
    _ = _r.recvuntil("r = ")
    r = int(_r.recvline())
    
    _r.sendlineafter("[Q]uit\n", "p")
    ret = _r.recvline().strip().decode()
    pubkey = list(
        map(
            int,
            re.findall(
                r"pubkey = \[([0-9]+), ([0-9]+), ([0-9]+), ([0-9]+), ([0-9]+)\]", ret
            )[0],
        )
    )
    
    _r.sendlineafter("[Q]uit\n", "e")
    ret = _r.recvline().strip().decode()
    rand_msg = re.findall(r"\| the signature for \"(.*)\" is :", ret)[0]
    ret = _r.recvline().strip().decode()
    rand_sign = list(
        map(
            int,
            re.findall(
                r"\| signature = \[([0-9]+), ([0-9]+), ([0-9]+), ([0-9]+), ([0-9]+)\]", ret
            )[0],
        )
    )
    
    # [pub0, ..., pub4, priv0, ..., priv4, s]
    mat = matrix(ZZ, 11, 10)
    for i in range(5):
        mat[i, i] = -1
        mat[5 + i, i] = -p
        mat[10, i] = r ** (i + 1)
        mat[i, 5 + i] = 1
    lb = pubkey + [0] * 5
    ub = pubkey + [2 ** 32] * 5
    ret = solve(copy.deepcopy(mat), copy.deepcopy(lb), copy.deepcopy(ub))
    privkey = list(ret[0][5:10])
    
    
    # check
    dbit = 32
    assert sign(rand_msg, privkey, dbit) == rand_sign
    
    _r.sendlineafter("[Q]uit\n", "f")
    ret = _r.recvline().strip().decode()
    rand_msg = re.findall(r"\| send the signature of the following message like example: (.*)", ret)[0]
    sign = sign(rand_msg, privkey, dbit)
    _r.sendline(",".join(map(str, sign)))
    _r.interactive()

    CCTF{Lattice_bA5eD_T3cHn1QuE_70_Br34K_LCG!!}

    Wolf

    33 solves

    AES の問題。AES の key が与えられており、 GCM モードでフラグが暗号化されます。 nonce

    niv = os.urandom(random.randint(1, 11))

    で生成されます。

    niv の文字列長が2以下であれば十分高速に niv を全探索できます。さらに文字列長が2以下である確率は2/11であり、十分に高いです。下のスクリプトを何度か回してフラグを得ました。

    solve.py
    import re
    from itertools import product
    
    from binascii import unhexlify
    from Crypto.Cipher import AES
    from Crypto.Util.number import long_to_bytes
    from pwn import remote
    
    passphrase = b'HungryTimberWolf'
    
    _r = remote("01.cr.yp.toc.tf", 27010)
    
    _r.sendlineafter("[Q]uit\n", "g")
    ret = _r.recvline().strip().decode()
    enc_flag = unhexlify(re.findall(r"\| encrypt\(flag\) = (.*)", ret)[0])
    
    for n in range(1, 3):
        for i_list in product(range(256), repeat=n):
            tmp_niv = b"".join(map(long_to_bytes, i_list))
            tmp_aes = AES.new(passphrase, AES.MODE_GCM, nonce=tmp_niv)
            tmp_flag = tmp_aes.decrypt(enc_flag)
            if b"CCTF{" in tmp_flag:
                print(tmp_flag)

    CCTF{____w0lveS____c4n____be____dan9er0uS____t0____p3oplE____!!!!!!}

    LINDA

    23 solves

    ある固定の素数 pp (given) でパラメータ u,v,wu, v, w が以下のように生成されます (これらも given)。

    def keygen(p):
        while True:
            u = getRandomRange(1, p)
            if pow(u, (p - 1) // 2, p) != 1:
                break
        x = getRandomRange(1, p)
        w = pow(u, x, p)
        while True:
            r = getRandomRange(1, p - 1)
            if gcd(r, p - 1) == 1:
                y = x * inverse(r, p - 1) % (p - 1)
                v = pow(u, r, p)
                return u, v, w

    これらを使ってフラグ (mm) が以下のように暗号化されます。

    def encrypt(m, pubkey):
        p, u, v, w = pubkey
        assert m < p
        r, s = [getRandomRange(1, p) for _ in "01"]
        ca = pow(u, r, p)
        cb = pow(v, s, p)
        cc = m * pow(w, r + s, p) % p
        enc = (ca, cb, cc)
        return enc

    encrypt 内で生成されている r,sr, s がわかればフラグを復号できそうです。

    p1p - 1 を試しに素因数分解してみると小さい素数の積になっていることがわかりました。つまり Pohlig-Hellman algorithm が使えます。

    solve.sage
    from Crypto.Util.number import long_to_bytes
    
    # 一度接続して p, u, v, w を入手
    p = 80040674322486200183331704165146058688355128781788651227350875871674742319920911360783561260194150493874495739587048685899899944078938543685265460797023
    u = 14108147438067096264181521725638271783716062505015085501011997363539105529220134686668833616162025711494007957907693959413538566683505186659769015857877
    v = 16000409593087500438791179247115777574915938869122915417574163962787315162920602492446105732367216596908836487469326834168577373919395024737878728742484
    w = 36011874435065497442299962693196160030321693654149785514569095639364173271601769821987901048673065443159944404388580038382010555730000137869326611006262
    enc = (51546876314099158815771406875395450944729146278198246293217184833201398085891945591409346537984132235322811468863166962330212626988458892438754396495963, 56446131178709957909815173502301466085398638405195449492108949845556028028436338736444947623899626798956388201052886950557276582688956351454340069032396, 10555296210928660270792188233294969486948538480518952008230817142909325378503829670147773076742266881530756838661770694462905599485290318088924705105178)
    
    Z = Zmod(p)
    r = int(discrete_log(Z(enc[0]), Z(u)))
    s = int(discrete_log(Z(enc[1]), Z(v)))
    print(long_to_bytes(pow(Z(w) ** (r + s), -1, p) * enc[2]))

    CCTF{1mPr0v3D_CrYp7O_5yST3m_8Y_Boneh_Boyen_Shacham!}

    RSAphantine

    29 solves

    2*z**5 - x**3 + y*z = 47769864706750161581152919266942014884728504309791272300873440765010405681123224050402253883248571746202060439521835359010439155922618613520747411963822349374260144229698759495359592287331083229572369186844312169397998958687629858407857496154424105344376591742814310010312178029414792153520127354594349356721
    x**4 + y**5 + x*y*z = 89701863794494741579279495149280970802005356650985500935516314994149482802770873012891936617235883383779949043375656934782512958529863426837860653654512392603575042842591799236152988759047643602681210429449595866940656449163014827637584123867198437888098961323599436457342203222948370386342070941174587735051
    y**6 + 2*z**5 + z*y = 47769864706750161581152919266942014884728504309791272300873440765010405681123224050402253883248571746202060439521835359010439155922618613609786612391835856376321085593999733543104760294208916442207908167085574197779179315081994735796390000652436258333943257231020011932605906567086908226693333446521506911058
    p = nextPrime(x**2 + z**2 + y**2 << 76)
    q = nextPrime(z**2 + y**3 - y*x*z ^ 67)
    n, e = p * q, 31337
    m = bytes_to_long(FLAG)
    c = pow(m, e, n)
    c = 486675922771716096231737399040548486325658137529857293201278143425470143429646265649376948017991651364539656238516890519597468182912015548139675971112490154510727743335620826075143903361868438931223801236515950567326769413127995861265368340866053590373839051019268657129382281794222269715218496547178894867320406378387056032984394810093686367691759705672

    以上の情報だけが与えられます… 最初の3式から x,y,zx, y, z が求まれば p,qp, q が求まり、フラグを復号できそうです。

    3式を上から順に式1, 2, 3と呼ぶことにし、右辺の数値をそれぞれ s,t,us, t, u とします。 式3 - 式1 を考えると、 x3+y6=usx^3 + y^6 = u - s となります。 usu-s を素因数分解してみると

    3133713317731333 * 28413320364759425177418147555143516002041291710972733253944530195017276664069717887927099709630886727522090965378073004342203980057853092114878433424202989

    となっていました。 x3+y6=(x+y2)(x2xy2+y4)x^3 + y^6 = (x + y^2)(x^2 - xy^2 + y^4) であることから

    x + y^2 == 3133713317731333
    x^2 - xy^2 + y^4 == 28413320364759425177418147555143516002041291710972733253944530195017276664069717887927099709630886727522090965378073004342203980057853092114878433424202989
    

    がわかります。これらを連立して解くことで x,yx, y が求まり、式1-3からzzも求まります。

    solve.sage
    a = 3133713317731333
    """
    # y を以下の式で求めた
    y = var("y")
    solve(y^4 - 2 * a * y^2 + a^2 + y^4 - a * y^2 + y^4 - 28413320364759425177418147555143516002041291710972733253944530195017276664069717887927099709630886727522090965378073004342203980057853092114878433424202989, y)
    """
    y = 311960913464334198969500852124413736815
    x = a - y^2
    z = (89701863794494741579279495149280970802005356650985500935516314994149482802770873012891936617235883383779949043375656934782512958529863426837860653654512392603575042842591799236152988759047643602681210429449595866940656449163014827637584123867198437888098961323599436457342203222948370386342070941174587735051 - x^4 - y^5) // x // y
    
    p = next_prime(x**2 + z**2 + y**2 << 76)
    q = next_prime(z**2 + y**3 - y*x*z ^^ 67)
    n = p * q
    phi = (p - 1) * (q - 1)
    d = int(pow(e, -1, phi))
    pow(c, d, n)

    CCTF{y0Ur_jO8_C4l13D_Diophantine_An4LySI5!}

    hard

    Rohald

    21 solves

    ison, teal, peam の実装を見るに、 Edwards curve のようです。Edwards curve のパラメータは不明です。フラグの前半部分、後半部分を s,ts, t としたとき、 Edwards curve 上の P,QP, Q について、 sP,tQsP, tQ が与えられています。

    Double Miff と同様に、P,Q,sP,tQP, Q, sP, tQ の4点から Edwards curve のパラメータを求めます。煩雑な計算なので省略しますが、 p,c2,dp, c^2, d が求まります。

    求まったパラメータを元に Edwards curve の位数の素因数分解を計算すると、小さい素数の積であり、 Pohlig-Hellman algorithm を使って離散対数問題を解くことができることがわかります。

    solve.sage
    from Crypto.Util.number import long_to_bytes
    
    
    P = (398011447251267732058427934569710020713094, 548950454294712661054528329798266699762662)
    Px, Py = P
    Q = (139255151342889674616838168412769112246165, 649791718379009629228240558980851356197207)
    Qx, Qy = Q
    S = (730393937659426993430595540476247076383331, 461597565155009635099537158476419433012710)
    Sx, Sy = S
    T = (500532897653416664117493978883484252869079, 620853965501593867437705135137758828401933)
    Tx, Ty = T
    
    p = 903968861315877429495243431349919213155709
    c2 = Zmod(p)(int(((x0^2+y0^2)*x1^2*y1^2 - (x1^2+y1^2)*x0^2*y0^2) * pow(x1^2*y1^2 - x0^2*y0^2, -1, p)))
    d = int((x0^2 + y0^2 - c2) * pow(c2*x0^2*y0^2, -1, p))
    
    for c in sqrt(c2, all=True):
        Pw = (c^2 * d * P[0]^2 - 1) * P[1] % p
        Px = -2 * c * (Pw - c) * pow(P[0], -2, p) % p
        Py = (4 * c^2 * (Pw - c) + 2 * c * (c^4 * d + 1) * P[0]^2) * pow(P[0], -3, p)
        Sw = (c^2 * d * S[0]^2 - 1) * S[1] % p
        Sx = -2 * c * (Sw - c) * pow(S[0], -2, p) % p
        Sy = (4 * c^2 * (Sw - c) + 2 * c * (c^4 * d + 1) * S[0]^2) * pow(S[0], -3, p)
    
        Qw = (c^2 * d * Q[0]^2 - 1) * Q[1] % p
        Qx = -2 * c * (Qw - c) * pow(Q[0], -2, p) % p
        Qy = (4 * c^2 * (Qw - c) + 2 * c * (c^4 * d + 1) * Q[0]^2) * pow(Q[0], -3, p)
        Tw = (c^2 * d * T[0]^2 - 1) * T[1] % p
        Tx = -2 * c * (Tw - c) * pow(T[0], -2, p) % p
        Ty = (4 * c^2 * (Tw - c) + 2 * c * (c^4 * d + 1) * T[0]^2) * pow(T[0], -3, p)
    
    
        PR.<x, y> = PolynomialRing(GF(p))
        f = y^2 - (x - c^4*d - 1) * (x^2 - 4*c^4*d)
        EC = EllipticCurve(f)
        P_EC = EC(Px, Py)
        S_EC = EC(Sx, Sy)
        Q_EC = EC(Qx, Qy)
        T_EC = EC(Tx, Ty)
        s = P_EC.discrete_log(S_EC)
        t = Q_EC.discrete_log(T_EC)
        print(long_to_bytes(s) + long_to_bytes(t))

    CCTF{nOt_50_3a5Y_Edw4rDs_3LlipT!c_CURv3}

    Trunc

    7 solves

    ある指定されたメッセージの署名をつくる問題 (そのメッセージで署名はできません)。署名と検証は以下のように行われます。

    def sign(msg, keypair):
        nbit, dbit = 256, 25
        pubkey, privkey = keypair
        privkey_bytes = long_to_bytes(privkey)
        x = int(sha256(privkey_bytes).hexdigest(), 16) % 2 ** dbit
        while True:
            k, l = [(getRandomNBitInteger(nbit) << dbit) + x for _ in "01"]
            u, v = (k * G).x(), (l * G).y()
            if u + v > 0:
                break
        h = int(sha256(msg).hexdigest(), 16)
        s = inverse(k, n) * (h * u - v * privkey) % n
        return (int(u), int(v), int(s))
    
    
    def verify(msg, pubkey, sig):
        if any(x < 1 or x >= n for x in sig):
            return False
        u, v, s = sig
        h = int(sha256(msg).hexdigest(), 16)
        k, l = h * u * inverse(s, n), v * inverse(s, n)
        X = (k * G + (n - l) * pubkey).x()
        return (X - u) % n == 0

    署名は ElGamal に似ています。 k,lk, l を乱数で生成して u=(kG).x,v=(lG).yu = (kG).x, v = (lG).y、さらに s=k1(huvx)s = k^{-1}(hu - vx) を計算します。ここで hh はメッセージのハッシュ、 xx は秘密鍵です。u,v,su, v, s が署名です。 ElGamal や DSA の署名は2変数であるのに対しこの問題では3変数なため、署名をいい感じに改変できそうな予感がします。

    ある既知メッセージ m0m_0 の署名を u0,v0,s0u_0, v_0, s_0 とし、署名をつくりたいメッセージを mm とします。

    k0=H(m0)s01u0s01v0x=H(m)H(m0)H(m)s01u0s01v0x=H(m)(H(m)H(m0)s0)1u0(H(m)H(m0)s0)1(H(m)H(m0)v0)x\begin{align*} k_0 &= H(m_0) s_0^{-1}u_0 - s_0^{-1} v_0 x \\ &= H(m) \frac{H(m_0)}{H(m)} s_0^{-1}u_0 - s_0^{-1} v_0 x \\ &= H(m) \left( \frac{H(m)}{H(m_0)}s_0 \right)^{-1} u_0 - \left( \frac{H(m)}{H(m_0)} s_0 \right)^{-1} \left( \frac{H(m)}{H(m_0)} v_0 \right) x \end{align*}

    と変形できるため、 u=u0u = u_0, v=H(m)/H(m0)v0v = H(m)/H(m_0) v_0, s=H(m)/H(m0)s0s = H(m)/H(m_0) s_0 とすれば mm の署名として有効なものになります。

    solve.py
    import re
    from hashlib import sha256
    
    import ecdsa
    from Crypto.Util.number import bytes_to_long
    from pwn import remote
    
    E = ecdsa.SECP256k1
    G, n = E.generator, E.order
    p = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F
    
    cryptonym = b'Persian Gulf'
    
    _r = remote("07.cr.yp.toc.tf", 23010)
    
    _r.sendlineafter("[Q]uit\n", "p")
    ret = _r.recvline().strip().decode()
    Hx, Hy = map(int, re.findall(r"\| pubkey = ([0-9]+) ([0-9]+)", ret)[0])
    
    _r.sendlineafter("[Q]uit\n", "s")
    _r.sendlineafter("to sign: \n", "00")
    ret = _r.recvline().strip().decode()
    u0, v0, s0 = map(int, re.findall(r"\| sign = \(([0-9]+), ([0-9]+), ([0-9]+)\)", ret)[0])
    
    h_0 = bytes_to_long(sha256(b"\x00").digest())
    h = bytes_to_long(sha256(cryptonym).digest())
    s = int(s0 * h * pow(h_0, -1, n) % n)
    v = int(v0 * h * pow(h_0, -1, n) % n)
    u = u0
    
    _r.sendlineafter("[Q]uit\n", "v")
    _r.sendlineafter("to verify: \n", cryptonym.hex())
    _r.sendlineafter("with comma: \n", f"{u},{v},{s}")
    _r.interactive()

    CCTF{__ECC_Bi4seD_N0nCE_53ns3_LLL!!!}