CryptoCTF 2024 medium 分类团队解题 writeup 之四

这次 medium 分类题量还是最多的，结果一开始里面很多题都不可解，甚至比赛结束了还 TMD 有一道零解。

~~我去年买了个表~~

RM2

题目描述

题目需要我们和远程服务器交互：

我们需要提供 1024bit 的两个素数 $p, q$，而且 $p \ne q$
服务器提供 $e = 65537$，计算 $n = pq$
服务器生成一个随机的 256byte 可打印字符串 $s$，bytes_to_long 之后就是 $m$，且保证 $m < 4n$
将 $s$ 从中间劈两半成 $s_1, s_2$，分别 bytes_to_long 之后就是 $m1, m2$
计算 $c_1 = m_1^e \bmod (p-1)(q-1)$
计算 $c_2 = m_2^e \bmod (2p+1)(2q+1)$
已知 $c_1, c_2$，求 $s$；$s$ 的两部分必须同时求出来，不能一次只求一边。

我的解答

首先可打印字符串是我们需要利用的一个判别条件。

然后因为有两个 $n_1 = (p-1)(q-1)$ 和 $n_2 = (2p+1)(2q+1)$，我们希望这两个玩意儿都能分解。所以我们为了方便构造：

$\left\{\begin{aligned}p &= 2p_1 + 1 \\ p_2 &= 2 p + 1\end{aligned}\right.$

看看有没有机会使得 $p, p_1, p_2$ 均为素数。然后这个拼人品过程还是比较折磨的，所以接下来会给出纯 python 和 sagemath 版本的拼人品代码：

import multiprocessing as mp
from Crypto.Util.number import *

def foo():
    while True:
        p1 = getPrime(1023)
        p = 2 * p1 + 1
        p2 = 2 * p + 1
        if isPrime(p) and isPrime(p2):
            print(f'AOLIGEI!!!')
            print(f'{p = }')


if __name__ =="__main__":
    cores=200
    threads=[]
    for i in range(0,cores):
        threads.append(mp.Process(target=foo,args=()))
    for i in range(0,cores):
        threads[i].start()
    for i in range(0,cores):
       threads[i].join()

import multiprocessing as mp

def foo(i):
    set_random_seed(i)
    while True:
        p1 = random_prime(2^1023-1, False, 2^1022)
        p = 2 * p1 + 1
        p2 = 2 * p + 1
        if is_prime(p) and is_prime(p2):
            print(f'AOLIGEI!!!')
            print(f'{p = }')


if __name__ =="__main__":
    cores=16
    threads=[]
    for i in range(0,cores):
        threads.append(mp.Process(target=foo,args=(i,)))
    for i in range(0,cores):
        threads[i].start()
    for i in range(0,cores):
       threads[i].join()

需要注意 sagemath 是需要在每个进程单独设置随机种子的，不然的话大家的随机种子都一样，随机的过程也完全一样，就没有利用到多进程的优势了。这里为了避免大家受折磨，我也给出一些可用的结果：

p = 110598963128206029146765005567976400551252821326820761634842705844231553162227632664548054666497796622794062169070761269846059674983300718897806207809316445501660744576082811632826051521981392774109347485625137377414804884956968844657911576950879481134837170517406967712375212664629606155737787366417228920479
p = 125834462937515514677952736351086477723189729376609237064972472894555759877882476569437044272175628959389274769857516194048130275708221472338605048821258868578062704405546439911796474901862378213766360589621269578212699588653799137952968362066454793101495940157317172250788360259833809994814260032964280454279
p = 100901414083041935147565989244623721954379094110518159236755177583163984200889793113587729459559520404983625806167856159967860770505185684577116986060782555274476108602462759564999450628547960715880426418276206531296054104831649681935990743078827088355146864761100183036677309515622196184065072999258123805239
p = 146496675022473012211857165143712747843246040874368584905858010585448843220035648485403137716275826156399518871757281036627660955362913708683959326736269351823871633144933008767581852850465282804501453322937241886850655418311690001221505594362048575315000371530770930693400115574470709373629360789754857606423
p = 153444654371502759312369957861806438560869346201934408107090630860121077971217342534491164144300657682724587336411469313073980007519090429493425313057960273105930550206028662533909546955123308145793269974880422767558196767811472521559229803064323084233643777404514878684631500363639829028720434718377936413723
p = 151938210068739317119037902475523471283351855826895709268281779606178616041813782684483513203011655045886298899315081189952485123708781999276530762477397662483246705057837976284722750121815117376779839692622348687715083607434723618196689363562394123094927732413453290261021832723310278894402025717298262583199

然后就是朴实无华的互动与解密了，代码如下：

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


class Gao:
    def __init__(self):
        # self.conn = process(['python3', 'another.py'])
        self.conn = remote('00.cr.yp.toc.tf', '13371')
        self.p = 
        self.q = 
    
    def send_primes(self):
        self.conn.sendlineafter('p, q:', f'{self.p},{self.q}')
    
    def recv_num(self, num_name):
        self.conn.recvuntil(f'{num_name} = ')
        return int(self.conn.recvline())
    
    def solve_prob_one(self, c, p):
        e = 65537
        d = inverse_mod(e, euler_phi(p))
        m = pow(c, d, p)
        return ZZ(m)
    
    def solve_prob(self, c, p, q):
        mp = self.solve_prob_one(c, p)
        mq = self.solve_prob_one(c, q)
        m = crt([mp, mq], [p, q])
        return long_to_bytes(int(m))
    
    def gao(self):
        self.send_primes()
        c1 = self.recv_num('c1')
        c2 = self.recv_num('c2')
        m1 = self.solve_prob(c1, self.p - 1, self.q - 1)
        m2 = self.solve_prob(c2, 2 * self.p + 1, 2 * self.q + 1)
        m = m1 + m2
        self.conn.sendline(m)
        self.conn.interactive()

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

得到 flag 为：

1	CCTF{i_l0v3_5UpeR_S4fE_Pr1m3s!!}

Soufia

题目描述

解函数方程 $f: \mathbb{Z} \to \mathbb{Z}$ 满足：对一个常整数 $t$，有 $\forall x, y \in \mathbb{Z}$，我们有

$f(tx) + tf(x) = f(f(x+y))$

并且知道 $f(x_1) = y_1$，$f(x_2) = y_2$，求 $f(x)$。

我的解答

没活儿了，已经偷题偷到 IMO 上了，脸都不要了。

对解题过程有兴趣的话可以参考这里

不是你偷题目都能偷歪来？几把玩意儿你看看你自己写的是什么东西？原题不是

$f(2a) + 2f(b) = f(f(a+b))$

太闹弹了，推导又没法考，只能整出这种烂活儿，对着抄都抄不明白，建议以后在开始出题之前先去检查一下自己智商有没有问题。

所以 $f(x)$ 只能是线性函数，这下就不用说了，剩下的就是把 $f(x)$ 的系数求出来，再挨个算一下就完事儿。

from pwn import *
import re

context.log_level = 'debug'

class Gao:
    def __init__(self):
        self.conn = remote('00.cr.yp.toc.tf', 13377)
    
    def gao_1(self):
        self.conn.recvuntil('send the ')
        s = self.conn.recvline().decode()
        mat = re.search(r'f\((.+?)\)', s)
        x = int(mat.group(1))
        y = self.k * x + self.b
        self.conn.sendline(str(y))
    
    def gao_xy(self, begin, end):
        self.conn.recvuntil(begin)
        s = self.conn.recvline().decode()
        mat = re.search(r'f\((.+?)\) = (.+?)' + end, s)
        x, y = map(int, [mat.group(i+1) for i in range(2)])
        return x, y

    def gao(self):
        x0, y0 = self.gao_xy('Also,', ',')
        x1, y1 = self.gao_xy('and ', ' ')
        self.k = (y1 - y0) // (x1 - x0)
        self.b = y0 - self.k * x0
        for i in range(20):
            self.gao_1()
        self.conn.interactive()

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

得到 flag 为：

1	CCTF{A_funCti0nal_3qu4tiOn_iZ_4_7yPe_oF_EquAtioN_tHaT_inv0lVe5_an_unKnOwn_funCt!on_r4tH3r_thAn_juS7_vArIabl3s!!}

Vantuk

题目描述

先定义两个函数 $u(a, x, y)$ 和 $v(a, x, y)$：

$u(a, x, y) = x + \frac{ax - y}{x^2 + y^2}$ $v(a, x, y) = y - \frac{x + ay}{x^2 + y^2}$

然后有 $m_1, m_2, a \in \mathbb{Z}$ 且

$\left\{\begin{aligned}A &= u(5, a, 4a) \\ U &= u(a, m_1, m_2) \\ V &= v(a, m_1, m_2)\end{aligned}\right.$

已知 $A, U, V$，求 $m_1, m_2$。

我的解答

AUV，巴黎倍儿甜！

朴实无华的解方程题目。需要注意 $m_1, m_2, a \in \mathbb{Z}$。所以先解 $a$：

A = 

PR.<t> = PolynomialRing(QQ)
a, x, y = 5, t, 4*t

f = (x - A) * ((x ** 2 + y ** 2)) + (a * x - y)
print(f.roots())

会得到几个解，但是只有那个非零整数才是真正的 $a$。然后就是已知 $a$ 求 $u, v$，单走一个 variety：

a = 

U = 
V = 

PR.<x, y> = PolynomialRing(QQ)

f = x * (x^2+y^2) + (a * x - y) - U * (x^2+y^2)
g = y * (x^2+y^2) - (x + a * y) - V * (x^2+y^2)

print(Ideal([f, g]).variety())

还是找到那一组唯一的非零整数解即可，然后打印出结果：

from Crypto.Util.number import *

m1 = 
m2 = 

print(long_to_bytes(m1)+long_to_bytes(m2))

看到 flag 为：

1	CCTF{d!D_y0U_5oLv3_7HiS_eQu4T!On_wItH_uSing_c0mPlEx_Num8erS!!?}

赛后反思

flag 中所谓的复数视角，就是：

$\begin{aligned}U + V i &= x + y i + \frac{(a-i)x - (1 + ai) y}{x^2 + y^2} \\ &= x + yi + \frac{(a-i)(x - y i)}{x^2 + y^2} \\ &= x + yi + \frac{(a-i)}{x + y i}\end{aligned}$

令 $z = x + y i$，$W = U + V i$ 就可以解得关于 $z$ 的二次方程：

$z^2 - wz + a - i = 0$

直接套求根公式就可以求出 $z$ 来。

然而 sagemath 的复数域和实数域都只支持双精度和任意精度的，如果想嗯出可以用任意精度的大力出奇迹：

a = 

U = 
V = 

CC = ComplexField(1234)

W = U + V * i

b = -W
c = a - i
delta_sqrt = (b^2 - 4 * c).sqrt()
x1 = (- b + delta_sqrt) / 2
x2 = (b + delta_sqrt) / 2

from Crypto.Util.number import *
x = x1
m1 = long_to_bytes(int(x.real()))
m2 = long_to_bytes(int(x.imag()))
print(m1 + m2)

这样也能解得 flag。