Crypto CTF 2021 Writeup

August 02, 2021

medium Triplet Elegant Curve Improved Ferman Salt and Pepper Tiny ECC Onlude Tuti Maid medium-hard Double Miff Frozen Wolf LINDA RSAphantine hard Rohald Trunc

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

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

medium

Triplet

50 solves

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

$\phi_2 = k_1 \phi_1 = k_1 k_0 \phi_0 (k_0, k_1 \in \N)$ となるような $\phi_i$ を見つけられれば、 $ed \equiv 1 \mod \phi_2, ed > \phi_2$ のときに $ed \equiv 1 \mod \phi_i (0 \le i < 2)$ も同時に満たされます。なので $\phi_i$ がそのようになっている素数を求めていきます。適当に素数 $p_0$ を生成し、 $p_1 = k_0 (p_0 - 1) + 1$ が素数となるような $k_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]

次に $ed \equiv 1 \mod \phi_2$ かつ $d < \phi_0$ となる $e, 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, 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種類の楕円曲線のパラメータ $y^2 = x^3 + ax + b \mod p$ , $y^2 = x^3 + cx + d \mod q$ を指定します。 nbit は160です。その楕円曲線上で離散対数問題が解ければフラグが得られます。

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

これで離散対数問題を十分高速に解くことができるようになるのですが、 $P = xG$ の $G$ の位数によっては偽の解が生じ得ます (解を位数で割った余りしか得られないため。 $p - 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

で $m$ のハッシュが計算されます。このハッシュが衝突する $m_1, m_2$ を送ればフラグが得られます。

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

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

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, q$ に対し、 $(p-a)^2 + (q-b)^2 = c$ が成立するという条件が与えられます。

ガウス整数の素因数分解を考えることで、 $(x + iy)(x - iy) = x^2 + y^2$ となる $x, 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

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
    )

salt や pepper のハッシュがわかっているときに、ある特定の文字列を含んでいる 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, q$ を指定したあと、楕円曲線 $\bar{F_p}$ 上と $\bar{F_q}$ 上の楕円曲線 $y^2 = x^3 + ax + b$ で離散対数問題が解ければフラグが得られます。

$a, b$ の条件がゆるく、 $a = b = pq$ とすれば楕円曲線は $y^2 = x^3$ となります。このような singular curve 上では $(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の行列 $A$ に対し、 $E = L^{-1}S(A+R)$ という計算で暗号化されています。ここで $L, U$ は $S$ をLU分解したもので、 $S = LU$ が成立します。与えられている値は $E, LUL, L^{-1}S^2L, R^{-1}S^8$ です。

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

$S^2 = (LUL) (L^{-1}S^2L)$ (LUL)^{-1}
$S^8 = (S^2)^4$
$R = S^8 (R^{-1}S^8)^{-1}$
$L^{-1}S = (L^{-1}S^2L)(SL)^{-1} = (L^{-1}S^2L)(LUL)^{-1}$
$A = (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, y$ (整数表示) として、ある与えられた $k$ に対し

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, y$ が正であることから、

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

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

992752253935874779143952218845275961347009322164731344882417010624071055636710540798045985678351986133612

で割り切れる必要があります。この整数を素因数分解し、それぞれの素因数が $x, 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

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

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

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(y^2-1) - by(x^2-1) \mod p$ ) を考えます。フラグの前半部分、後半部分を $x$ 座標に持つこの曲線上の点を $P, Q$ として、 $P + 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 + Q$ の3点が与えられているので、この曲線のパラメータ $a, b, p$ が求められないかを考えます。がちゃがちゃ式変形をすると、ある2点 $A_0, A_1$ の $x, y$ 座標について、

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

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

次に $P$ や $Q$ の座標を求めるため、 $P = (x, y)$ としたときに $P + P$ を計算することで $x, 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, r$ ( $p$ は素数) が与えられ、 $c = 0, 1, \cdots, 4$ の5種類について $r^{c+1}s \mod p$ ( $s$ はランダムな整数) の前半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

ある固定の素数 $p$ (given) でパラメータ $u, 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

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

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, s$ がわかればフラグを復号できそうです。

$p - 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, z$ が求まれば $p, q$ が求まり、フラグを復号できそうです。

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

3133713317731333 * 28413320364759425177418147555143516002041291710972733253944530195017276664069717887927099709630886727522090965378073004342203980057853092114878433424202989

となっていました。 $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, y$ が求まり、式1-3から $z$ も求まります。

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, t$ としたとき、 Edwards curve 上の $P, Q$ について、 $sP, tQ$ が与えられています。

Double Miff と同様に、 $P, Q, sP, tQ$ の4点から Edwards curve のパラメータを求めます。煩雑な計算なので省略しますが、 $p, 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, l$ を乱数で生成して $u = (kG).x, v = (lG).y$ 、さらに $s = k^{-1}(hu - vx)$ を計算します。ここで $h$ はメッセージのハッシュ、 $x$ は秘密鍵です。 $u, v, s$ が署名です。 ElGamal や DSA の署名は2変数であるのに対しこの問題では3変数なため、署名をいい感じに改変できそうな予感がします。

ある既知メッセージ $m_0$ の署名を $u_0, v_0, s_0$ とし、署名をつくりたいメッセージを $m$ とします。

\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 = u_0$ , $v = H(m)/H(m_0) v_0$ , $s = H(m)/H(m_0) s_0$ とすれば $m$ の署名として有効なものになります。

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!!!}

medium Triplet Elegant Curve Improved Ferman Salt and Pepper Tiny ECC Onlude Tuti Maid medium-hard Double Miff Frozen Wolf LINDA RSAphantine hard Rohald Trunc