2024 SJTUCTF WriteUp

2024 SJTUCTF中部分Crypto题目的WriteUp

babyctr

使用内置加密库加密，再用某个seekctr库使用相同的参数解密，却解出来一串乱码。http.ServeContent会先调用ReadSeeker的Seek方法来获取到文件的大小。所以收到请求时会先Seek(0, 2)再Seek(0, 0)，然后这个seekctr的代码不知道哪里写错了，导致这样seek两次后iv没有恢复原样，好像iv[15]变成了41，导致解密出了问题。不过如果请求头里加上Range: bytes=16-154的话，收到请求时会先Seek(0, 2)再Seek(16, 0)，这样iv[15]会变成1，并从16字节处开始正常解密，于是获得flag。

easyctr

对一大段文本加密，感觉会用到古典密码学。请求头里加上Range: bytes=16-16,0-9191，收到请求时会先Seek(0, 2)再Seek(16, 0)再Seek(0, 0)，于是iv[15]变成33，并从头开始加密，可以表示为cip1[x] = msg[x] ^ key[x + 33 * 16]。同理请求头里加上Range: bytes=32-32,0-9191可以得到cip2[x] = msg[x] ^ key[x + 34 * 16]。于是cip1[x + 16] ^ cip2[x] == msg[x + 16] ^ msg[x]，可以由原文的前16个字节确定原文，依次枚举这16个字节使得结果中的a-z数量最多，得到原文，从而获得flag。

SpARse

先解析PEM格式, $d_q$ 的长度需要猜，可能要多试几次。给了私钥的完整的 $N$，以及 $p,q,d,d_p = d \mod (p-1),d_q = d\mod(q-1)$ 的一些bits，要还原私钥。网上找到一篇文章 https://eprint.iacr.org/2020/1506.pdf 里面含有所有这题要用到的东西。注意到 $e d_p\mod(p-1) = 1$，所以存在 $k_p < e$ 满足 $ed_p = k_p(p-1)+1$，同理 $ed_q = k_q(q-1)+1,ed = k(p-1)(q-1)+1$。这里三个未知数 $k_p,k_q,k$ 各只有65536种可能，可以枚举。再加上 $pq=N$，这四个式子都是模2的幂不变的，所以可以利用已知的bits，依次由低位向高位推断与枚举（和去年的Matryoshka有点像）

刚开始枚举时可能需要手动规划一下，大致步骤是

• 枚举 $p$ 和 $q$ 到第16位
• 枚举 $k_p$ 并枚举 $p,q,d_p$ 到第58位
• 枚举 $k$ 并枚举 $d$ 到第58位（感觉这一步耗时最长）
• 枚举 $k_q$ 并枚举 $p,q,d,d_p,d_q$ 到约800位

然后再用文章第14页的方法构造格就能解出完整的 $p,q$，于是复原私钥，获得flag。

babypairing

这题的加密方式是对一段文字的每个字符单独加密，感觉会用到古典密码学。这条椭圆曲线上的群结构是 $\mathbb Z_{p+1}\times \mathbb Z_{p+1}$，于是可以构造双线性对。再由双线性对的性质, $e(g, c_1) = e(g, P)$。又由于题目设计，相同的字符对应的 $P$ 点相同，计算发现 $e(g, P)$ 只有27个不同的值，于是题目转化成了个简单的替换密码，使用quipquip等工具可以解出原文，于是获得flag。