春勃

这个世界，还会变好吗？

这次 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 ...

这次 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 ...

这次 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$ 的验证，以及根据已有猜测对 ...

这次 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 他丫是真的牛逼，这种东西靠自己想是完全他妈的想不出来的，只能说人与人之间智商的差距是最令人绝望的…… 所以就直接抄就行了，至于要 ...

这次 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 ...

这次 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) < ...

这次 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 ...

这次 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$ 构成的集合，就得到 ...

一九九七年 我学会了开汽车 上坡 下坡 轧死了一千多 警察来抓我 我跑到女厕所 女厕所的灯 没 有 开 一脚掉到茅屎坑 和粑粑交朋友 点此欣赏芜湖童谣 这周末，一年一度的 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 ...