Writeup for Crypto problems in WMCTF 2020
piece_of_cake
两个函数大概都是一个类似 RSA 的操作,加上一个加密算法,之前的一篇博客有介绍:http://am473ur.com/?p=234,
An Introduction to Mathematical Cryptography 书里称这个算法是 “a toy model of a real public key cryptosystem”。(bitlength 凑的刚刚好可以保证解密,很巧妙)
make_cake()
这边的 cake
很小(256bits)符合正常解密的条件,可以直接用高斯格基规约算法(上面那篇博客有实现),然而 eat_cake()
这边的 cake
是比较大的(768bits)就会导致在取模的时候值容易发生改变,所以给它加上几个 g
,并使用给出的 pow
来验证是否是正确的 cake
。
规约得到的密钥对 $(F, G)$ 是不一定等于原来的密钥对 $(f, g)$,但它们在解密过程是等价的,我们得到的密钥对 (F, G) 长度都是 768bits。
exp 多跑几次就能得到 flag。
|
|
babySum
密度接近 0.8 的子集和问题(Subset sum problem),BKZ-24 跑得比较慢好在成功率高一点。
|
|
到 check.py 里面运行输入得到 flag:WMCTF{83077532752999414286785898029842440}
Game
对 AES 选择明文攻击,逐个字节爆破。
CBC 模式的 AES 加密,块长度为 b,C0 是初始向量 IV,IV 是和服务器端同步的最新的加密向量。爆破第一个字节时,需要进行下面的操作:

IV 始终和服务器端的 IV 同步,用来消除掉当前加密的一次异或,再用 C0 异或一下就构造出了 Step2 的加密结果的第一个 block。所以爆破一个 byte 最多会和服务器交互 256 次,不过平均下来约 128 次得到一个 byte。
以 16bytes 块长度为例,让服务器把已知的 15bytes 的 r 和未知部分的前 1byte 拼起来加密,然后本地去枚举最后一个 byte 和 15bytes 拼起来发送到服务器加密,如果加密后的第一个块和在服务器端拼起来的那段是相等的,就说明猜对了。就多知道了一个 secret 的 byte,把它当作已知,再进行下一个 byte 的枚举。
|
|