Goodbye World
这个世界,还会变好吗?
CryptoCTF 2023 tough分类 团队解题writeup
这次 tough 分类真的也就还好,没有那种很长的算法需要审计,思维上也没有到那种难到抓狂的,也没有涉及太高级的数学工具,对算力也没有啥很苛刻的要求。
所以综合下来,跟去年以及前年的最高难度相比,真的也就还好。
Slowsum题目描述题目里面所给出的系统巨复杂,感觉就是用来把人绕晕的。
首先 $q = 113$,整套系统基于 $\mathbb{F}_q$ 中的多项式。
一开始我们可以输入变量的个数 $n$ 以及多项式 $f$ 的次数 $d$,需要满足 $n \ge 5, d \ge 3, n d/q < 0.1$
我们可用的变量为 $x_0, x_1, \ldots, x_{n-1}$
然后我们需要输入这个 $d$ 次多项式 $f(x_0, x_1, \ldots, x_{n-1})$。记
g = \sum_{x_0 = 0}^{1}\sum_{x_1 = 0}^{1} \ldots \sum_{x_{n-1} = 0}^{1} f(x_0, x_1, \ldots, x_{n-1})然后我们需要输入一个数 $g’ \ne g$。
然后我们需要输入 $n$ 个一元多项式 $p_0 ...
CryptoCTF 2023 hard分类 团队解题writeup 之二
这次 hard 分类也有 5 题,虽然思维方面肯定比 medium 要难些,但也还中规中矩。
Vinefruit题目描述题目定义了一个函数 $f$:输入一个消息 $m$,记该消息的每个字节的内容分别为 $m_1, m_2, \ldots, m_l$。$v_0$ 已知,然后满足一个递推关系:
v_i = (p \cdot (v_{i-1} + m_i)) \bmod 2^{128}其中 $p$ 已知。根据这个迭代式一直计算,返回 $f(m) = v_l$。
给定 $l$,需要给出 $m, m’$ 使得 $f(m) = f(m’)$,且 $f(m)$ 在之后的关卡中不能和之前已经用过的 $f(m)$ 相等。
我的解答可以把那个迭代式展开,得:
v_l \equiv p^l v_0 + \sum_{i=1}^{l}p^{l-i+1}m_i \pmod{2^{128}}把 $m’$ 的各项也代入到上式,两式相减,并记 $d_i = m_i - m_i’$,我们便有:
\sum_{i=1}^{l}p^{l-i}d_i \equiv 0 \pmod{2^{128}}且有 $d_i \in \{-2 ...
CryptoCTF 2023 hard分类 团队解题writeup 之一
这次 hard 分类也有 5 题,虽然思维方面肯定比 medium 要难些,但也还中规中矩。
Big题目描述$p$ 是一个 512 位的 $4k+3$ 型素数,$q$ 是把 $p$ 的十进制表示进行逆序之后的数,也是素数。$N=pq$。
然后 $a$ 是一个模 $N$ 的二次剩余。
首先得到 flag 的二进制为 $\{m_1, m_2, \ldots, m_l\}$,其中 $m_i \in \{0, 1\}$ 对于 $i = 1, 2, \ldots, l$。
然后生成一个随机的 $t_i$,使得 $t_i$ 在 $m_i = 0$ 时不为模 $N$ 的二次剩余,在 $m_i$ 为 1 时为模 $N$ 的二次剩余。
然后记 $c_i = (t_i - a t_i^{-1}) \bmod N$。
已知 $N, a, c_1, c_2, \ldots, c_l$,求 flag。
我的解答首先是找到 $N=pq$ 的分解。
由于 $q$ 是把 $p$ 的十进制表示进行逆序之后的数,所以可以用估界的手法:逐步猜测 $p$ 和 $q$ 的高位值,通过模 $10^k$ 的验证,以及根据已有猜测对 ...
CryptoCTF 2023 medium分类 团队解题writeup 之四
这次 medium 分类题量是最多的,内容方面是最丰富的,两极分化比较严重。
有脑筋急转弯的,有考察 SageMath API 使用的,有 MISC 题目混进来的……
总之 medium 分类最难的比 tough 还要更难……
TPSD题目描述题目基于一个不定方程:
p^3 + q^3 + r^3 = 1其中解 $p, q, r$ 至少要有一个素数。每次提交结果,都要求最小值的比特数在限定范围内。
我的解答自己瞎几把想+乱试了好久没想出个所以然来,所以直接抄答案:
https://www.ams.org/journals/mcom/2007-76-259/S0025-5718-07-01947-3/S0025-5718-07-01947-3.pdf
In 1936, Mahler discovered a parametric solution for $k = 1$:
(9t^4)^3 + (3t - 9t^4)^3 + (1 - 9t^3)^3 = 1
他丫是真的牛逼,这种东西靠自己想是完全他妈的想不出来的,只能说人与人之间智商的差距是最令人绝望的……
所以就直接抄就行了,至于要 ...
CryptoCTF 2023 medium分类 团队解题writeup 之三
这次 medium 分类题量是最多的,内容方面是最丰富的,两极分化比较严重。
有脑筋急转弯的,有考察 SageMath API 使用的,有 MISC 题目混进来的……
总之 medium 分类最难的比 tough 还要更难……
Resuction题目描述和 easy 分类 里面的 Suction 类似,不过有加强。
RSA 中,$N=pq$,$p, q$ 有 1024 位。
题目给出的 $(N, e, c)$ 的后 8 位均未知,且 $d$ 为 64 位素数。
求明文 $m$。
我的解答因为 $d$ 较小,所以可以采用 Wiener 攻击得出 $d$ 的值。
所以就是枚举 $N$ 和 $e$ 的低 8 位,然后如果能够通过 Wiener 攻击成功得到 64 位的 $d$ 来。
然后再枚举 $c$ 的低 8 位去解密就行。
这样好像要挂个 40 分钟的样子,因为 Wiener 攻击需要求在每次都要求连分数,以及判断是否为解。
12345678910for Nl in trange(2^7): for el in range(2^8): N = Nh + 2 * Nl ...
CryptoCTF 2023 medium分类 团队解题writeup 之二
这次 medium 分类题量是最多的,内容方面是最丰富的,两极分化比较严重。
有脑筋急转弯的,有考察 SageMath API 使用的,有 MISC 题目混进来的……
总之 medium 分类最难的比 tough 还要更难……
Roldy题目描述题目的加密基于 ECB 模式的分组加密,以及基于 pyope 包中的 OPE 加密算法。
与远程终端交互,可以知道 flag 的密文,也能进行任意次输入明文,得到加密结果的操作。
试求 flag。
我的解答首先搜一波 OPE 是什么:
https://crypto.stackexchange.com/questions/37375/order-preserving-encryption-ope-and-leakage
简单来说,OPE 就是 Order-Preserving Encryption(保序加密)的缩写。
接着具体看到 pyope 包的页面:
https://pypi.org/project/pyope/
其中有:
1assert cipher.encrypt(1000) < cipher.encrypt(2000) < ...
CryptoCTF 2023 medium分类 团队解题writeup 之一
这次 medium 分类题量是最多的,内容方面是最丰富的,两极分化比较严重。
有脑筋急转弯的,有考察 SageMath API 使用的,有 MISC 题目混进来的……
总之 medium 分类最难的比 tough 还要更难……
Derik题目描述已知 $O_0, O_1, O_2, O_3$ 的值,以及 $C_0, C_1, C_2, C_3, C_4, C_5, C_6, C_7$ 的值,未知 $e, d, p, q, r$ 的值。
有如下条件:
$e, d, p, q, r$ 均为素数
$C_0 p - C_1 q \ge 0$
$C_2 p - C_3 r \ge 0$
$C_4 r - C_5 p \ge 0$
$(C_0 p - C_1 q) ^ e + (C_2 q - C_3 r) ^ e + (C_4 r - C_5 p) ^ e = d (C_0 p - C_1 q) (C_2 q - C_3 r) (C_4 r - C_5 p)$
$C_6 e - C_7 d = O_3$
RSA 中,$N = edpqr$,加密指数为 65537,对 flag 加密得到 $c ...
CryptoCTF 2023 easy分类 团队解题writeup
这次 easy 分类偏简单,
不过由于配合得不是很好,所以在实战中会有部分题目卡壳的情况
不过还好能有其他人也帮忙看一看,所以马上就能够解围
Did it!题目描述记 $n = 127$,$N=\{0, 1, 2, \ldots, n-1\}$,有随机的未知 $K \subseteq N$,且 $|K| \le 20$。
有至多 12 次的机会,输入一个集合 $A \subseteq N$,且 $|A| \le 20$,返回结果
\{x_0^2 \bmod n + r_0, x_1^2 \bmod n + r_1, \ldots\}对于所有 ${x_i \in A - K}$
其中 $r_i \in \{0, 1\}$ 为一个关于 $x_i$ 的随机数。
如果输入的 $A = K$,则得到 flag。
我的解答也就是说,有至多 11 次的机会去得到结果,然后就要猜出 $K$ 来。
因为 $n$ 是素数,所以对于结果中的每一组 $x_i^2 \bmod n + r_i$,都可以枚举 $r_i$,通过开平方求得可能的 $x_i$。然后再用 $A$ 减去这些 $x_i$ 构成的集合,就得到 ...
CryptoCTF 2023 战果速报
一九九七年
我学会了开汽车
上坡 下坡
轧死了一千多
警察来抓我
我跑到女厕所
女厕所的灯
没 有 开
一脚掉到茅屎坑
和粑粑交朋友
点此欣赏芜湖童谣
这周末,一年一度的 Crypto CTF 如期举行。在炎炎夏季,穿上发病棉袄,和队友们一起参加周五晚 22: 00 开始的 Crypto CTF,并 AK 了此次比赛。老规矩,先鸣谢下队友:
沛公 @peigong
石卡库 @sh1kaku
苏氨酸 @苏氨酸
To1in @To1in
V @Vanish
等风 @等风
Xenny @Xenny
Tover @Tover.
这波配合得不错
然后放个总榜
这次的题目总体来说都偏简(luan)单(gao),最难搞的反而是偏 misc 的几道题。所以说手速,或者是出 idea 的速度是最关键的。因为我们队伍还是贯彻一个养生 CTF,所以说基本上没搞得很晚就先歇逼了一阵,痛失前五。
之后更 writeup,下方为 writeup 传送门:
easy 分类
medium 分类之一
medium 分类之二
medium 分类之三
medium 分类之四
hard 分类之一
har ...