CryptoCTF 2025 getting there 分类 团队解题 writeup 之一

这次 getting there 分类比赛的时候我看了两题，幸亏队友给力，帮我解决了其他的题目。此处要感谢队友，同时也要 继续批判临场背刺的叛徒

ASIS Primes

题目描述

记消息为 $m$。服务器先生成一对 $n=512$ 位的素数 $p, q$，$e=65536$，然后有两个选项：

1. RSA 加密 服务器根据当前素数 $p, q$，计算 $N=pq$，$c=m^e \bmod N$
2. 参数修改 服务器接收我们的输入 $p’, q’$，并执行检验：
   a) $p’, q’$ 为素数
   b) 满足关于 $p, q$ 转化为字符串之后均为可见字符串，并且满足某个 随机长度 的消息格式检验

   def is_valid(msg):
       msg, charset = msg.decode(), string.printable[:63] + '_{-}'
       return all(_ in charset for _ in msg)
   
   pinit = f'CCTF{{7H!S_iZ_th3_f1RSt_pRim3__P_f0R_oUr_{nbit}-bit_m0DulU5_{rand_str(randint(5, 40))}'.encode()
   qinit = f'CCTF{{7H!S_iZ_th3_s3c0Nd_pRim3_Q_f0R_oUr_{nbit}-bit_m0DulU5_{rand_str(randint(5, 40))}'.encode()
   ok = (
       isPrime(_p) and isPrime(_q) 
       and _pbytes.startswith(pinit) and _qbytes.startswith(qinit) 
       and _pbytes.endswith(b'}') and _qbytes.endswith(b'}') 
       and is_valid(_pbytes) and is_valid(_qbytes)
   )

   c) $9 p’ q’$ 为 $2n$ 位数
   若上述条件均满足，则执行参数修改 $p=p’$，$q=q’$，并且给 $n$ 加上一（这里 会影响到后续的参数修改

最终我们需要求得 $m$

听队友说这道题最开始的附件在 is_valid 函数里面是没有包括 } 这个字符的，所以没法过这个测试，还好后面 re-upload 了。re-download CTF √

不过我刚才又看了下那个比赛网页，都变成 re-re-download 了，那是真的牛批

我的解答

直接按照他的要求生成随机数就好。

注意到他那个判断里面有个 randint 函数是控制那个模板后缀的实际长度，并且输入过不了检查的话整个程序不会退出，所以可以通过赌博的方式去刷那个 randint 出来的数字，也就是刷模板的实际长度。

然后，如果我们一开始在 $n=512$ 的时候就去提交结果的话，最坏情况下（叛徒最坏了），模板字符串长这样：

CCTF{7H!S_iZ_th3_f1RSt_pRim3__P_f0R_oUr_512-bit_m0DulU5_AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA

此时算上末尾的 }，$p’$ 转成字符串的长度至少是 97，$p’$ 的位数至少是 776，怎么过也过不了。

但是同样地，这个时候我们可以一开始就乱填，让 $n$ 不断增大，等增大后，也就是我们的操作空间比较大的时候，我们再去随机尝试素数。

先看看要将 $n$ 增大到多少才比较有希望：

from Crypto.Util.number import *

a = b'CCTF{7H!S_iZ_th3_f1RSt_pRim3__P_f0R_oUr_512-bit_m0DulU5_' + b'A' * 40
b = b'CCTF{7H!S_iZ_th3_s3c0Nd_pRim3_Q_f0R_oUr_512-bit_m0DulU5_' + b'A' * 40

a1 = bytes_to_long(a)
b1 = bytes_to_long(b)
n = 9 * a1 * b1
print(f'{n.bit_length() = }')

输出 1536，也就是得猛猛增大才行。

代码如下：

from pwn import *
from Crypto.Util.number import *
import random
import string
from tqdm import trange


class Gao:
    def __init__(self):
        # self.conn = process(['python3', 'another.py'])
        self.conn = remote('91.107.252.0', '13737')
        self.n = 512
        self.num_makes = 648
    
    def make_n_great_again(self):
        self.conn.sendlineafter('[Q]uit\n', 'S')
        self.conn.sendlineafter('p, q: \n', 'FUCK YOU TRAITOR')
        self.n += 1
    
    def make_p_great_again(self, num_chars: int, p_head: bytes):
        base_str = string.printable[:63] + '_'
        while True:
            part2 = ''.join(random.choices(base_str, k=num_chars - len(p_head) - 1)).encode()
            p_bytes = p_head + part2 + b'}'
            p = bytes_to_long(p_bytes)
            if isPrime(p):
                return p
    
    def gao_pq(self):
        assert self.n % 2 == 0
        num_chars = self.n // 8
        self.conn.sendlineafter('[Q]uit\n', 'S')
        self.conn.recvuntil('is: ')
        p_head = eval(self.conn.recvline())
        self.conn.recvuntil('is: ')
        q_head = eval(self.conn.recvline())
        while True:
            p = self.make_p_great_again(num_chars, p_head)
            print("p ok")
            q = self.make_p_great_again(num_chars, q_head)
            print("q ok")
            if (9 * p * q).bit_length() == 2 * self.n:
                print("nbits check ok")
                break
            else:
                print("nbits check GG")
        self.p = p
        self.q = q
        self.conn.sendlineafter('p, q: \n', f'{p},{q}')
    
    def gao_m(self):
        self.conn.sendlineafter('[Q]uit\n', 'E')
        self.conn.recvuntil('c = ')
        c = eval(self.conn.recvline())
        print(f'p = {self.p}')
        print(f'q = {self.q}')
        print(f'c = {c}')
    
    def gao(self):
        for i in trange(self.num_makes):
            self.make_n_great_again()
        self.gao_pq()
        self.gao_m()

if __name__ == '__main__':
    g = Gao()
    g.gao()

然后就是直接在 SageMath 10.X 版本里面开 65536 次方根并且筛选出 CCTF{ 头即可。我测试的 10.3 可以直接开根，9.X 版本应该不能直接开根。

from Crypto.Util.number import *

p = 
q = 
c = 

for mp in mps:
    mp_bytes = long_to_bytes(int(mp))
    if mp_bytes.startswith(b'CCTF{'):
        print('AOLIGEI!!!')
        print(f'{mp_bytes = }')

然后有个问题就是现在这道题目的远程已经 down 掉了，所以不能把 msg 给 pull 下来。这里只需要在模 $p$ 下解是因为他那个原本的（也就是没改过参数的）RSA 加密是在 1024 位下的，也就是 $m$ 至多 1024 位，我们之后改过的 $p$ 位数都大过 1024 了，所以肯定有 $m < p$。

Ikkyu San

题目描述

题目基于模 256 位素数 $p$ 下的椭圆曲线 $E_p$：先生成 $p, E_p$，然后生成 $E_p$ 上的两个点 $G, H$，并且保证

• $E_p$ 不存在 $x=1$ 的点
• $b-a-1$ 不为模 $p$ 的二次剩余

服务器有以下选项：

加密 flag $m$ 为 flag，则返回 $m x_G y_H$

获取曲线上的随机点 服务器输出椭圆曲线 $E_p$ 上的随机点

fongi 计算 服务器接受椭圆曲线上 $E_p$ 的点 $P$ 作为输入，返回 $f(G, H, P) = x_P G + y_P H + x_G P$ 的结果

试获取 flag

我的解答

首先想到的肯定是通过获取随机点的方式，求出椭圆曲线参数 $E_p$：

$$y_0^2 - x_0^3 - a x_0 - b \equiv 0 \pmod{p}$$ $$y_1^2 - x_1^3 - a x_1 - b \equiv 0 \pmod{p}$$

作差消去 $p$：

$$(y_0^2 - x_0^3) - (y_1^2 - x_1^3) - a (x_0 - x_1) \equiv 0 \pmod{p}$$

记

$$A_0 = -(x_0 - x_1), B_0 = (y_0^2 - x_0^3) - (y_1^2 - x_1^3)$$

则有 $A_0 a + B_0 \equiv 0 \pmod{p}$

再从服务器拿下来一组点：$A_1 a + B_1 \equiv 0 \pmod{p}$

继续消去未知的 $a$：$B_0 A_1 - B_1 A_0 \equiv 0 \pmod{p}$

然后就是多次拿数据，算到很多组左边的数，做一个最大公约数就是 $p$ 的值

然后回到最上面两个式子，就可以看成是关于 $a, b$ 的线性方程组，解得 $a, b$ 即可。

然后就涉及到如何利用题目的 $f$ 函数得到点 $G, H$ 的信息了。这里 未央 在比赛的时候一直在用 deepseek 生成卵用都没有的屎山 ，还好 石卡库 介入得快，通过构造就解决了。TNND 也就是说自己用手堆屎山还嫌不够，直接把 deepseek 这台自动喷屎机给搞过来了，把合作文档里面喷得到处都是屎，这辈子有了。

好了不吐槽了，我们回到题目。题目中对 $E_p$ 加的限制可以被细化为：

• $E_p$ 不存在 $x=1$ 的点 → $1 + a + b$ 不为模 $p$ 的二次剩余
• $b-a-1$ 不为模 $p$ 的二次剩余 → $E_p$ 不存在 $x=-1$ 的点

但是还是不知道上面这个限制有什么用

如果要构造点的话，首先想到利用椭圆曲线的加法逆元性质：如果 $P(x, y)$ 为椭圆曲线 $E$ 上的点，那么 $-P(x, -y)$ 亦为椭圆曲线 $E$ 上的点。所以我们看看同时输入正负的点对得到那个函数值，能够得到什么：

• 输入 $P$: $Q = x_P G + y_P H + x_G P$
• 输入 $-P$: $R = x_P G + (p - y_P) H - x_G P$

这里有个坑，这个第二个式子的第二项系数不是 $y_P$，而是 $p-y_P$，这个跟 $f$ 函数的代码实现有关，第一次做的时候被这个实现坑到了，我说咋算算不对

两式相加得 $Q + R = 2 x_P G + p H$，这里单看的话我们是求不出 $G$，不过没关系，因为第二项 $pH$ 是常数项（与我们的输入 $P$ 无关），所以我们可以再来一组：

$$Q_1 + R_1 = 2 x_{P1} + p H$$ $$Q_2 + R_2 = 2 x_{P2} + p H$$

联立计算就可以算得 $G$：

$$G = (2 (x_{P1} - x_{P2}))^{-1} (Q_1 + R_1 - Q_2 - R_2)$$

这里有个问题是这个逆有可能不存在，主要原因是椭圆曲线的阶很可能是偶数，有两种解决方法，一种就是仿照 RSA 里面 $gcd(e, \phi(N)) \ne 1$ 的情形一样求出所有的可能，然后对多组数据取个交集，另一种就是不停连接服务器去拼人品

然后将求得的 $G$ 代入到第一个式子里面，就可以发现未知的只有 $H$，也是直接通过变形就可以算出 $H$：

$$H = (y_p)^{-1} (Q - x_P G - x_G P)$$

点的坐标都知道了之后，就可以直接通过求逆得到 $m$。代码如下：

from pwn import *
from sage.all import *
from Crypto.Util.number import *

class Gao:
    def __init__(self):
        self.conn = process(['sage', 'another.sage'])

    def gao_curve(self):
        N = 5
        points = []
        for i in range(N):
            self.conn.sendlineafter('[Q]uit\n', 'R')
            s = self.conn.recvline().decode()
            x, y = map(int, re.findall(r'(\d+) : (\d+) : 1', s)[0])
            points.append((x, y))
        
        def get_AB(P, Q):
            x0, y0 = P
            x1, y1 = Q
            A = -(x0 - x1)
            B = (y0**2 - x0**3) - (y1**2 - x1**3)
            return A, B
        
        WTF = []
        for i in range(N-2):
            A0, B0 = get_AB(points[i], points[i+1])
            A1, B1 = get_AB(points[i+1], points[i+2])
            WTF.append(B0 * A1 - B1 * A0)
        
        p = gcd(WTF)
        # Make it prime
        p = factor(p)[-1][0]
        x0, y0 = points[0]
        x1, y1 = points[1]
        AA = matrix(Zmod(p), [[x0, 1],
                              [x1, 1]])
        bb = vector(Zmod(p), [y0**2-x0**3, y1**2-x1**3])
        a, b = AA.solve_right(bb)
        E = EllipticCurve(Zmod(p), [a, b])
        
        self.p = p
        self.E = E

    def generate(self, P):
        E = P.curve()
        self.conn.sendlineafter('[Q]uit\n', 'G')
        x, y = P.xy()
        self.conn.sendlineafter('x, y: \n', f'{x},{y}')
        s = self.conn.recvline().decode()
        u, v = map(int, re.findall(r'(\d+) : (\d+) : 1', s)[0])
        return E(u, v) 

    def gao_GH(self):
        p = self.p
        E = self.E
        n = E.order()
        
        # P1
        P1 = E.random_point()
        xP1, yP1 = map(ZZ, P1.xy())
        Q1 = self.generate(P1)
        R1 = self.generate(-P1)
        
        # P2
        P2 = E.random_point()
        xP2, yP2 = map(ZZ, P2.xy())
        Q2 = self.generate(P2)
        R2 = self.generate(-P2)
        # Might fail, try multiple times
        denom = 2 * (xP1 - xP2)
        if gcd(denom, n) != 1:
            print('Find G GG')
            return False
        G = inverse_mod(denom, n) * (Q1 + R1 - Q2 - R2)
        xG, yG = map(ZZ, G.xy())
        if gcd(yP1, n) != 1:
            print('Find H GG')
            return False
        H = inverse_mod(yP1, n) * (Q1 - xP1 * G - xG * P1)
        
        self.G, self.H = G, H
        return True

    def gao_flag(self):
        p, G, H = self.p, self.G, self.H
        xG, yG = map(ZZ, G.xy())
        xH, yH = map(ZZ, H.xy())
        self.conn.sendlineafter('[Q]uit\n', 'E')
        s = self.conn.recvline().decode()
        c = int(re.findall(r' = (\d+)', s)[0])
        m = c * inverse_mod(xG * yH, p) % p
        print(long_to_bytes(int(m)))

    def gao(self):
        self.gao_curve()
        if not self.gao_GH():
            return False
        self.gao_flag()
        return True
    
if __name__ == '__main__':
    while True:
        g = Gao()
        if g.gao():
            break
        g.conn.close()

因为远程服务器已经关了，所以脱不下来 flag，悲

赛后复盘

实际上 deepseek 牌自动喷屎机喷出来的屎也是忽略了 $f$ 的实现中会把 $-P$ 的纵坐标弄成 $p - y_P$ 这一点，拉屎随便拉，可劲拉，到最后 debug 的时候还不是得靠人来（所以他奶奶的未央懒到 de 个 bug 都不去做了是吧）

Mancity

题目描述

题目主要包含了一个 man 函数，记为 $m(x)$。该函数可以描述为，如果 $x$ 的二进制表示为

$$x = \sum_{i=0}^{\infty} a_i 2^i$$

那么有

$$m(x) = \sum_{i=0}^{\infty} (a_i 2^{2i+1} + 2^{2i})$$

$p$ 为一个 $k=256$ 素数，$q = 2^k p + 2^k - 1$，$r = m(p)$，保证 $q$ 和 $r$ 是素数。$e = 1234567891$，$N = qr$，$c = m_0^e \bmod N$。已知 $N, e, c$，求 $m_0$

我的解答

因为 $q$ 的低位为固定值，所以可以先把 $N$ 模一个 $2^k$ 把 $p$ 消掉，可以得到

$N \bmod 2^k = r \bmod 2^k$

也就是说 $p$ 的后半比特已知了。记 $k_1 = k / 2$，此时可以把 $p$ 写作 $p=2^{k_1} h_1 + l_1$，此时 $l_1$ 已知。回到 $q$ 的形式上，$q=2^k (2^{k_1} h_1 + l_1) + 2^k - 1$，再对 $N$ 模 $2^{k+k_1}$ 就可以消去未知的 $h_1$，得到

$$N \equiv (2^k l_1 + 2^k - 1)r \pmod{2^{k+k_1}}$$

此时又能把 $r \bmod 2^{k+k_1}$ 的值给求出来，回到形式相当于知道了 $p$ 的低 $(k+k_1)/2$ 位。记 $k_2 = k_1 / 2$，也就是知道了 $p$ 的低 $k_1+k_2$ 位。

推到这里，我们就可以一直迭代上述步骤，直到 $k_n = 1$，做到这里的时候就不用往下做了，因为此时仅剩下 $p$ 的最高位未知，就是 1.

代码如下：

from Crypto.Util.number import *

n = 147170819334030469053514652921356515888015711942553338463409772437981228515273287953989706666936875524451626901247038180594875568558137526484665015890594045767912340169965961750130156341999306808017498374501001042628249176543370525803456692022546235595791111819909503496986338431136130272043196908119165239297
c = 77151713996168344370880352082934801122524956107256445231326053049976568087412199358725058612262271922128984783428798480191211811217854076875727477848490840660333035334309193217618178091153472265093622822195960145852562781183839474868269109313543427082414220136748700364027714272845969723750108397300867408537

pl = 0
K = 256
k = K
ksum = K
while k > 1:
    ql = 2**K * pl + 2**K - 1
    rl = n * inverse(ql, 2**ksum) % 2**ksum
    rl_bits = f'{rl:0{ksum}b}'
    pl_bits = rl_bits[::2]
    pl = int(pl_bits, 2)
    k //= 2
    ksum += k

p = pl + 2**(K-1)
q = 2**K * p + 2**K - 1

assert n % q == 0
r = n // q

e = 1234567891
d = inverse(e, (q-1)*(r-1))
m = pow(c, d, n)
print(long_to_bytes(m))

得到 flag 为：

CCTF{M4nch3sReR_c0D!ng_wI7H_RSA}

彳亍，曼彻斯特编码说是，MISC 里面有些烂题会搞一些差分曼彻斯特编码来追求刺激

Matemith

题目描述

已知 313 位素数 $p$。将消息 $m$ 根据块长度 $l = 14$ 分块构成一个长度为 6 的列表 $M$（也就是 $M$ 中的元素 $M_i$ 满足 $M_i < 256^{14} = 2^{112}$）

然后生成系数 $c_0, c_1, \ldots, c_{20}$ 满足 $0 < c_i < p$

定义六个关于 $u, v, w, x, y, z$ 的六元 无常数项 多项式 $f_0, g_0, h_0, i_0, j_0, k_0$，并且计算

$$f(u, v, w, x, y, z) = f_0(u, v, w, x, y, z) + (p - f_0(M_0, M_1, M_2, M_3, M_4, M_5)) \bmod p$$ $$g(u, v, w, x, y, z) = g_0(u, v, w, x, y, z) + (p - g_0(M_0, M_1, M_2, M_3, M_4, M_5)) \bmod p$$ $$\ldots$$ $$k(u, v, w, x, y, z) = k_0(u, v, w, x, y, z) + (p - k_0(M_0, M_1, M_2, M_3, M_4, M_5)) \bmod p$$

已知 $f, g, h, i, j, k$，求 $m$

我的解答

也就是说，需要先求 $M$。

因为观察到多项式 $f_0, g_0, h_0, i_0, j_0, k_0$ 是 无常数项的，$f$ 相当于给 $f_0$ 加了个常数项，所以

1. 直接取出 $f$ 的常数项部分，就是 $-f_0(M_0, M_1, M_2, M_3, M_4, M_5)$
2. 取出 $f$ 的非常数项部分，就是 $f_0(u, v, w, x, y, z)$

然后对于每条式子，我们都可以得到一个关于 $f_0(u, v, w, x, y, z) - f_0(M_0, M_1, M_2, M_3, M_4, M_5) = 0$ 的方程。联立这样的 6 条式子，求 variety 即可求出 $M$。然后再算回 $m$ 即可。代码如下：

p = 9892984422801315119260311427714389408772405421306235794826917610128461644036928139298330716261

PR.<u, v, w, x, y, z> = Zmod(p)[]

f = 
g = 
h = 
i = 
j = 
k = 

M = Ideal([f, g, h, i, j, k]).variety()
print(M)

然后会发现报错

    raise NotImplementedError("Factorization of multivariate polynomials over prime fields with characteristic > 2^29 is not implemented.")
NotImplementedError: Factorization of multivariate polynomials over prime fields with characteristic > 2^29 is not implemented.

不过没关系，我们最开始分析了 $M_i$ 的取值范围是在 $p^{1/3}$ 的样子，而且那些多项式最多也就是把三个变量乘一乘，所以可能可以用 coppersmith 求解。这里比较无脑的方法是利用 cuso 直接求解：

import cuso
from Crypto.Util.number import *

p = 

u, v, w, x, y, z = var("u, v, w, x, y, z")

f = 
g = 
h = 
i = 
j = 
k = 

var_list = [u, v, w, x, y, z]
bounds = {x: (0, 2**112) for x in var_list}

relations = [f, g, h, i, j, k]

roots = cuso.find_small_roots(
    relations=relations,
    bounds=bounds,
    modulus=p
)

M = [int(roots[0][x]) for x in var_list]
m = b''.join(map(long_to_bytes, M))
print(m)

嘿！您猜怎么着？还真有解了，盖了帽儿了嘿！得到 flag 为

CCTF{50lv!n6_7H3_H1dD3n__num8Ers_Pr08l3m_f0r_C51dH_4nd_C5uRf_v14_4uT0m473d_C0pp3r5m17h!!?}

其实题目名字也在暗示要用 coppersmith 去解

传统派 coppersmith 能否去解？可能也能解，不过估计得去调参之类的

赛后复盘

这几个等式跟 CSIDH/CSURF 有何关联？

搜 flag 可以搜到这篇 paper：https://eprint.iacr.org/2023/1409.pdf

该 paper 的第 5.1 节提到可以通过联立同源前后椭圆曲线的 Montgomery 形式系数的关系式得到一组方程。