2022秋见到的一些Crypto题
0x00 前言
开篇博客写一点 Crypto 题解。这些题目有些是亲身参赛做过的，有些是从网上看到，觉得比较有价值。与读者诸君共同学习。附件可以从文章中下载。
0x01 网鼎杯2022初赛
网鼎杯作为简中赛博安全「奥运会」，第一、二届的初赛密码题风格都比较一致：不知所谓。做过「simple@2020」「boom@2020」「not_only_base@2018」的读者当明白笔者在说什么。
2022 年的第三届网鼎杯初赛，笔者参加了青龙组，又从互联网搜集到其他组的几道题目。今年网鼎杯的命题水平比往年有所进步，考察范围也从往年的几乎全部是模板题，变得更加需要一些思维能力。是一个好的现象。
T1 grasshopper
题目附件：
from Crypto.Util.number import *
from random import randrange
from grassfield import flag
p = getPrime(16)
k = [randrange(1,p) for i in range(5)]
for i in range(len(flag)):
grasshopper = flag[i]
for j in range(5):
k[j] = grasshopper = grasshopper * k[j] % p
print('Grasshopper#'+str(i).zfill(2)+':'+hex(grasshopper)[2:].zfill(4))
简单来说，维护一个长度为 $5$ 的状态向量，初始为随机值。总共进行了 len(flag) 即 $42$ 轮变换，每次变换是：
- $g \leftarrow flag _ i$
- 对 $k = 1 \to 5$ 执行 $g \leftarrow g \cdot k _ j; ~~ k _ j \leftarrow g$
我们记初始状态的 $k$ 向量为 $(x _ 0, x_ 1, x _ 2, x_ 3, x_4)$，那么在草稿纸上推演一下：
- 第一轮变换后，状态向量为：$$(f_0,\quad f_ 0 x _ 0, \quad f _ 0 x _ 0 x _ 1 ,\quad f _ 0 x _ 0 x _ 1 x _ 2 ,\quad f _ 0 x _ 0 x _ 1 x_ 2 x _ 3 ,\quad f _ 0 x _ 0 x _ 1 x _ 2 x_ 3 x _ 4 )$$
- 第二轮变换后，状态向量为：$$(f _ 0 f _ 1 x _ 0, \quad f _ 0 ^ 2 f _ 1 x _ 0 ^ 2 x _ 1,\quad f _ 0 ^ 3 f _ 1 x _ 0 ^ 3 x _ 1 ^ 2 x _ 2,\quad f _ 0 ^ 4 f _ 1 x _ 0 ^ 4 x _ 1 ^ 3 x _ 2 ^ 2 x _ 3, \quad f _ 0 ^ 5 f _ 1 x _ 0 ^ 5 x _ 1 ^ 4 x _ 2 ^ 3 x _ 3 ^ 2 x _ 4)$$
再往下很难再人工计算了。不过我们观察到一个性质：状态向量的每一个分量，始终是 $f _i$ 和 $x _ i$ 的幂相乘得到。想要表述状态向量中的一个分量，只需提供一个 $42 + 5 = 47$ 维数组，表示各个元素（$f_0 \sim f_{41}, x_0 \sim x_4$）的幂次。因此本题可以透过符号计算，直接求得每轮的状态向量（以 $f_i, x_i$ 之幂积来表示）。用 SageMath 做一个简单的演示：
如上图，我们手上有了 42 组方程，每个方程形如：$$f _ 0 ^ {\lambda _ 0} \cdot f _ 1 ^ {\lambda _ 1} \cdots f _ {41} ^ {\lambda _ {41}} \cdot x _ 0 ^ {\lambda _ {42}} \cdots x _ 4 ^ {\lambda _ {46}} \equiv out_{k} \pmod p$$
这显然可以通过高斯消元解决，但有一个很重要的问题：方程组不满秩。一共有 $47$ 个未知量，但只有 $42$ 组方程。这时候我们注意到，flag 的前缀一定是 flag{ ，于是 $f _ 0 \sim f_ 4$ 我们已知了。所以恰好可以补充到 $47$ 个方程，于是可以得到唯一解。
我们面临的最后一个问题：题目中的模数 $p$ 未知。但由于它只有 $16$ 位，而 $[2 ^ {15}, 2 ^ {16}]$ 范围内的质数仅有 $3030$ 个，故可以直接枚举 $p$，查看输出结果是否为可见字符。
代码细节有点多。首先生成增广矩阵：
class Symbol():
def __init__(self, s=None):
self.r = zero_vector(47)
if s:
if s[0] == 'f':
self.r[int(s[1:])] = 1
elif s[0] == 'x':
self.r[42 + int(s[1:])] = 1
def __str__(self):
return ' '.join([f'u{i}^{self.r[i]}' for i in range(47)])
def __mul__(self, a):
res = Symbol()
res.r = self.r + a.r
return res
k = [Symbol(f'x{i}') for i in range(5)]
flag = [Symbol(f'f{i}') for i in range(42)]
out = [0x2066,0xa222,0xcbb1,0xdbb4,0xdeb4,0xb1c5,0x33a4,0xc051,0x3b79,0x6bf8,0x2131,0x2c40,0x91ba,0x7b44,0x5f25,0x0208,0x7edb,0x62b5,0xcec5,0x5ab3,0x3c46,0xc272,0x714b,0x9e0b,0x48ee,0x44cc,0x05a0,0x3da3,0x11b1,0x259f,0x899d,0xa130,0xe58f,0x23f3,0x5829,0x6beb,0x3681,0x0054,0xa189,0x2765,0xc63d,0xbc68]
A = zero_matrix(47, 48)
for i in range(42):
grasshopper = flag[i]
for j in range(5):
k[j] = grasshopper = grasshopper * k[j]
A[i, :-1] = grasshopper.r
A[i, -1] = out[i]
for i in range(5):
A[42+i, i] = 1
A[42+i, -1] = list(b'flag{')[i]
print(A)
'''
[ 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 8294]
[ 5 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 5 4 3 2 1 41506]
[ 15 5 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 15 10 6 3 1 52145]
[ 35 15 5 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 35 20 10 4 1 56244]
[ 70 35 15 5 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 70 35 15 5 1 57012]
[ 126 70 35 15 5 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 126 56 21 6 1 45509]
[ 210 126 70 35 15 5 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 210 84 28 7 1 13220]
[ 330 210 126 70 35 15 5 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 330 120 36 8 1 49233]
[ 495 330 210 126 70 35 15 5 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 495 165 45 9 1 15225]
[ 715 495 330 210 126 70 35 15 5 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 715 220 55 10 1 27640]
[ 1001 715 495 330 210 126 70 35 15 5 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1001 286 66 11 1 8497]
[ 1365 1001 715 495 330 210 126 70 35 15 5 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1365 364 78 12 1 11328]
[ 1820 1365 1001 715 495 330 210 126 70 35 15 5 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1820 455 91 13 1 37306]
[ 2380 1820 1365 1001 715 495 330 210 126 70 35 15 5 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2380 560 105 14 1 31556]
[ 3060 2380 1820 1365 1001 715 495 330 210 126 70 35 15 5 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 3060 680 120 15 1 24357]
[ 3876 3060 2380 1820 1365 1001 715 495 330 210 126 70 35 15 5 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 3876 816 136 16 1 520]
[ 4845 3876 3060 2380 1820 1365 1001 715 495 330 210 126 70 35 15 5 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 4845 969 153 17 1 32475]
[ 5985 4845 3876 3060 2380 1820 1365 1001 715 495 330 210 126 70 35 15 5 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 5985 1140 171 18 1 25269]
[ 7315 5985 4845 3876 3060 2380 1820 1365 1001 715 495 330 210 126 70 35 15 5 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 7315 1330 190 19 1 52933]
[ 8855 7315 5985 4845 3876 3060 2380 1820 1365 1001 715 495 330 210 126 70 35 15 5 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 8855 1540 210 20 1 23219]
[ 10626 8855 7315 5985 4845 3876 3060 2380 1820 1365 1001 715 495 330 210 126 70 35 15 5 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 10626 1771 231 21 1 15430]
[ 12650 10626 8855 7315 5985 4845 3876 3060 2380 1820 1365 1001 715 495 330 210 126 70 35 15 5 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 12650 2024 253 22 1 49778]
[ 14950 12650 10626 8855 7315 5985 4845 3876 3060 2380 1820 1365 1001 715 495 330 210 126 70 35 15 5 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 14950 2300 276 23 1 29003]
[ 17550 14950 12650 10626 8855 7315 5985 4845 3876 3060 2380 1820 1365 1001 715 495 330 210 126 70 35 15 5 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 17550 2600 300 24 1 40459]
[ 20475 17550 14950 12650 10626 8855 7315 5985 4845 3876 3060 2380 1820 1365 1001 715 495 330 210 126 70 35 15 5 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 20475 2925 325 25 1 18670]
[ 23751 20475 17550 14950 12650 10626 8855 7315 5985 4845 3876 3060 2380 1820 1365 1001 715 495 330 210 126 70 35 15 5 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 23751 3276 351 26 1 17612]
[ 27405 23751 20475 17550 14950 12650 10626 8855 7315 5985 4845 3876 3060 2380 1820 1365 1001 715 495 330 210 126 70 35 15 5 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 27405 3654 378 27 1 1440]
[ 31465 27405 23751 20475 17550 14950 12650 10626 8855 7315 5985 4845 3876 3060 2380 1820 1365 1001 715 495 330 210 126 70 35 15 5 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 31465 4060 406 28 1 15779]
[ 35960 31465 27405 23751 20475 17550 14950 12650 10626 8855 7315 5985 4845 3876 3060 2380 1820 1365 1001 715 495 330 210 126 70 35 15 5 1 0 0 0 0 0 0 0 0 0 0 0 0 0 35960 4495 435 29 1 4529]
[ 40920 35960 31465 27405 23751 20475 17550 14950 12650 10626 8855 7315 5985 4845 3876 3060 2380 1820 1365 1001 715 495 330 210 126 70 35 15 5 1 0 0 0 0 0 0 0 0 0 0 0 0 40920 4960 465 30 1 9631]
[ 46376 40920 35960 31465 27405 23751 20475 17550 14950 12650 10626 8855 7315 5985 4845 3876 3060 2380 1820 1365 1001 715 495 330 210 126 70 35 15 5 1 0 0 0 0 0 0 0 0 0 0 0 46376 5456 496 31 1 35229]
[ 52360 46376 40920 35960 31465 27405 23751 20475 17550 14950 12650 10626 8855 7315 5985 4845 3876 3060 2380 1820 1365 1001 715 495 330 210 126 70 35 15 5 1 0 0 0 0 0 0 0 0 0 0 52360 5984 528 32 1 41264]
[ 58905 52360 46376 40920 35960 31465 27405 23751 20475 17550 14950 12650 10626 8855 7315 5985 4845 3876 3060 2380 1820 1365 1001 715 495 330 210 126 70 35 15 5 1 0 0 0 0 0 0 0 0 0 58905 6545 561 33 1 58767]
[ 66045 58905 52360 46376 40920 35960 31465 27405 23751 20475 17550 14950 12650 10626 8855 7315 5985 4845 3876 3060 2380 1820 1365 1001 715 495 330 210 126 70 35 15 5 1 0 0 0 0 0 0 0 0 66045 7140 595 34 1 9203]
[ 73815 66045 58905 52360 46376 40920 35960 31465 27405 23751 20475 17550 14950 12650 10626 8855 7315 5985 4845 3876 3060 2380 1820 1365 1001 715 495 330 210 126 70 35 15 5 1 0 0 0 0 0 0 0 73815 7770 630 35 1 22569]
[ 82251 73815 66045 58905 52360 46376 40920 35960 31465 27405 23751 20475 17550 14950 12650 10626 8855 7315 5985 4845 3876 3060 2380 1820 1365 1001 715 495 330 210 126 70 35 15 5 1 0 0 0 0 0 0 82251 8436 666 36 1 27627]
[ 91390 82251 73815 66045 58905 52360 46376 40920 35960 31465 27405 23751 20475 17550 14950 12650 10626 8855 7315 5985 4845 3876 3060 2380 1820 1365 1001 715 495 330 210 126 70 35 15 5 1 0 0 0 0 0 91390 9139 703 37 1 13953]
[101270 91390 82251 73815 66045 58905 52360 46376 40920 35960 31465 27405 23751 20475 17550 14950 12650 10626 8855 7315 5985 4845 3876 3060 2380 1820 1365 1001 715 495 330 210 126 70 35 15 5 1 0 0 0 0 101270 9880 741 38 1 84]
[111930 101270 91390 82251 73815 66045 58905 52360 46376 40920 35960 31465 27405 23751 20475 17550 14950 12650 10626 8855 7315 5985 4845 3876 3060 2380 1820 1365 1001 715 495 330 210 126 70 35 15 5 1 0 0 0 111930 10660 780 39 1 41353]
[123410 111930 101270 91390 82251 73815 66045 58905 52360 46376 40920 35960 31465 27405 23751 20475 17550 14950 12650 10626 8855 7315 5985 4845 3876 3060 2380 1820 1365 1001 715 495 330 210 126 70 35 15 5 1 0 0 123410 11480 820 40 1 10085]
[135751 123410 111930 101270 91390 82251 73815 66045 58905 52360 46376 40920 35960 31465 27405 23751 20475 17550 14950 12650 10626 8855 7315 5985 4845 3876 3060 2380 1820 1365 1001 715 495 330 210 126 70 35 15 5 1 0 135751 12341 861 41 1 50749]
[148995 135751 123410 111930 101270 91390 82251 73815 66045 58905 52360 46376 40920 35960 31465 27405 23751 20475 17550 14950 12650 10626 8855 7315 5985 4845 3876 3060 2380 1820 1365 1001 715 495 330 210 126 70 35 15 5 1 148995 13244 903 42 1 48232]
[ 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 102]
[ 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 108]
[ 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 97]
[ 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 103]
[ 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 123]
'''高斯消元：
def solve_eq(p):
M = copy(A)
R = Zmod(p-1)
def play(a, b):
t = M[b, a]
M[b, :-1] -= t * M[a, :-1]
M[b, :-1] %= p-1
M[b, -1] *= power_mod(inverse_mod(M[a, -1], p), t, p)
M[b, -1] %= p
# 消元，形成上三角矩阵
for row in range(47):
d = inverse_mod(M[row, row], p-1)
M[row, :-1] = (M[row, :-1] * d) % (p-1)
M[row, -1] = (M[row, -1] ^ d) % p
for i in range(row+1, 47):
play(row, i)
# 回代
for row in range(46, 0, -1):
for i in range(row):
play(row, i)
res = vector(M[:, -1])
# 验证
for row in range(47):
assert A[row, -1] % p == reduce(lambda x, y: x*y%p, [power_mod(x, y, p) for x, y in zip(res, vector(A[row, :-1]))])
return res
solve_eq(22871) # 随便选个质数测试一下高斯消元过程
# (102, 108, 97, 103, 123, 15812, 6992, 7285, 10703, 286, 353, 1668, 6109, 14564, 1453, 18301, 14418, 13530, 3397, 11163, 10174, 8128, 22656, 658, 13232, 283, 2277, 7796, 6539, 5678, 18232, 5379, 22125, 17033, 9398, 19269, 19111, 22450, 13810, 20332, 1186, 20849, 8913, 6083, 19122, 7661, 12782)枚举可行 $p$：
至此完成本题。
T2 david_homework
题目脚本：
from secret import flag
from hashlib import md5,sha256
from Crypto.Cipher import AES
cof_t = [[353, -1162, 32767], [206, -8021, 42110], [262, -7088, 31882], [388, -6394, 21225], [295, -9469, 44468], [749, -3501, 40559], [528, -2690, 10210], [354, -5383, 18437], [491, -8467, 26892], [932, -6984, 20447], [731, -6281, 11340], [420, -5392, 44071], [685, -6555, 40938], [408, -8070, 47959], [182, -9857, 49477], [593, -3584, 49243], [929, -7410, 31929], [970, -4549, 17160], [141, -2435, 36408], [344, -3814, 18949], [291, -7457, 40587], [765, -7011, 32097], [700, -8534, 18013], [267, -2541, 33488], [249, -8934, 12321], [589, -9617, 41998], [840, -1166, 22814], [947, -5660, 41003], [206, -7195, 46261], [784, -9270, 28410], [338, -3690, 19608], [559, -2078, 44397], [534, -3438, 47830], [515, -2139, 39546], [603, -6460, 49953], [234, -6824, 12579], [805, -8793, 36465], [245, -5886, 21077], [190, -7658, 20396], [392, -7053, 19739], [609, -5399, 39959], [479, -8172, 45734], [321, -7102, 41224], [720, -4487, 11055], [208, -1897, 15237], [890, -4427, 35168], [513, -5106, 45849], [666, -1137, 23725], [755, -6732, 39995], [589, -6421, 43716], [866, -3265, 30017], [416, -6540, 34979], [840, -1305, 18242], [731, -6844, 13781], [561, -2728, 10298], [863, -5953, 23132], [204, -4208, 27492], [158, -8701, 12720], [802, -4740, 16628], [491, -6874, 29057], [531, -4829, 29205], [363, -4775, 41711], [319, -9206, 46164], [317, -9270, 18290], [680, -5136, 12009], [880, -2940, 34900], [162, -2587, 49881], [997, -5265, 20890], [485, -9395, 23048], [867, -1652, 18926], [691, -7844, 11180], [355, -5990, 13172], [923, -2018, 23110], [214, -4719, 23005], [921, -9528, 29351], [349, -7957, 20161], [470, -1889, 46170], [244, -6106, 23879], [419, -5440, 43576], [930, -1123, 29859], [151, -5759, 23405], [843, -6770, 36558], [574, -6171, 33778], [772, -1073, 44718], [932, -4037, 40088], [848, -5813, 27304], [194, -6016, 39770], [966, -6789, 14217], [219, -6849, 40922], [352, -6046, 18558], [794, -8254, 29748], [618, -5887, 15535], [202, -9288, 26590], [611, -4341, 46682], [155, -7909, 16654], [935, -5739, 39342], [998, -6538, 24363], [125, -5679, 36725], [507, -7074, 15475], [699, -5836, 47549]]
def cal(i,cof):
if i <3:
return i+1
else:
return cof[2]*cal(i-3,cof)+cof[1]*cal(i-2,cof)+cof[0]*cal(i-1,cof)
s = 0
for i in range(100):
s+= cal(200000,cof_t[i])
s=str(s)[-2000:-1000]
key = md5(s).hexdigest().decode('hex')
check = sha256(key).hexdigest()
verify = '2cf44ec396e3bb9ed0f2f3bdbe4fab6325ae9d9ec3107881308156069452a6d5'
assert(check == verify)
aes = AES.new(key,AES.MODE_ECB)
data = flag + (16-len(flag)%16)*"\x00"
print (aes.encrypt(data).encode('hex'))
#4f12b3a3eadc4146386f4732266f02bd03114a404ba4cb2dabae213ecec451c9d52c70dc3d25154b5af8a304afafed87 我们显然必须恢复 key。key 是 s 的后 2000 到 1000 位，故我们全程只需要在模 $10 ^ {2000}$ 意义下进行运算。题目中的 cal() 函数是指数级复杂度，改成线性写法即可。
def cal(i,cof):
if i <3:
return i+1
else:
return cof[2]*cal(i-3,cof)+cof[1]*cal(i-2,cof)+cof[0]*cal(i-1,cof)
def fastcal(n, cof):
a, b, c = 1, 2, 3
for x in range(n):
a, b, c = b, c, (cof[2]*a+cof[1]*b+cof[0]*c) % 10**2000
return a
assert cal(10, cof_t[0]) == fastcal(10, cof_t[0])恢复 key，解密：
一些额外讨论。以 gmpy2 取代原生的大整数运算，可以获得很大的速度提升：
Golang 原生的 math/big 库需要 41.8s。
package main
import (
"fmt"
"math/big"
)
func fastcal(n int, cof []int64) *big.Int {
a, b, c := big.NewInt(1), big.NewInt(2), big.NewInt(3)
cof0, cof1, cof2 := big.NewInt(cof[0]), big.NewInt(cof[1]), big.NewInt(cof[2])
mod := big.NewInt(0)
mod.Exp(big.NewInt(10), big.NewInt(2000), nil)
for i := 0; i < n; i++ {
sum := big.NewInt(0)
tmp := big.NewInt(0)
tmp.Mul(cof2, a)
sum.Add(sum, tmp)
tmp.Mul(cof1, b)
sum.Add(sum, tmp)
tmp.Mul(cof0, c)
sum.Add(sum, tmp)
sum.Mod(sum, mod)
a, b, c = b, c, sum
}
return a
}
var cof_t [][]int64
func init() {
cof_t = [][]int64{{353, -1162, 32767}, {206, -8021, 42110}, {262, -7088, 31882}, {388, -6394, 21225}, {295, -9469, 44468}, {749, -3501, 40559}, {528, -2690, 10210}, {354, -5383, 18437}, {491, -8467, 26892}, {932, -6984, 20447}, {731, -6281, 11340}, {420, -5392, 44071}, {685, -6555, 40938}, {408, -8070, 47959}, {182, -9857, 49477}, {593, -3584, 49243}, {929, -7410, 31929}, {970, -4549, 17160}, {141, -2435, 36408}, {344, -3814, 18949}, {291, -7457, 40587}, {765, -7011, 32097}, {700, -8534, 18013}, {267, -2541, 33488}, {249, -8934, 12321}, {589, -9617, 41998}, {840, -1166, 22814}, {947, -5660, 41003}, {206, -7195, 46261}, {784, -9270, 28410}, {338, -3690, 19608}, {559, -2078, 44397}, {534, -3438, 47830}, {515, -2139, 39546}, {603, -6460, 49953}, {234, -6824, 12579}, {805, -8793, 36465}, {245, -5886, 21077}, {190, -7658, 20396}, {392, -7053, 19739}, {609, -5399, 39959}, {479, -8172, 45734}, {321, -7102, 41224}, {720, -4487, 11055}, {208, -1897, 15237}, {890, -4427, 35168}, {513, -5106, 45849}, {666, -1137, 23725}, {755, -6732, 39995}, {589, -6421, 43716}, {866, -3265, 30017}, {416, -6540, 34979}, {840, -1305, 18242}, {731, -6844, 13781}, {561, -2728, 10298}, {863, -5953, 23132}, {204, -4208, 27492}, {158, -8701, 12720}, {802, -4740, 16628}, {491, -6874, 29057}, {531, -4829, 29205}, {363, -4775, 41711}, {319, -9206, 46164}, {317, -9270, 18290}, {680, -5136, 12009}, {880, -2940, 34900}, {162, -2587, 49881}, {997, -5265, 20890}, {485, -9395, 23048}, {867, -1652, 18926}, {691, -7844, 11180}, {355, -5990, 13172}, {923, -2018, 23110}, {214, -4719, 23005}, {921, -9528, 29351}, {349, -7957, 20161}, {470, -1889, 46170}, {244, -6106, 23879}, {419, -5440, 43576}, {930, -1123, 29859}, {151, -5759, 23405}, {843, -6770, 36558}, {574, -6171, 33778}, {772, -1073, 44718}, {932, -4037, 40088}, {848, -5813, 27304}, {194, -6016, 39770}, {966, -6789, 14217}, {219, -6849, 40922}, {352, -6046, 18558}, {794, -8254, 29748}, {618, -5887, 15535}, {202, -9288, 26590}, {611, -4341, 46682}, {155, -7909, 16654}, {935, -5739, 39342}, {998, -6538, 24363}, {125, -5679, 36725}, {507, -7074, 15475}, {699, -5836, 47549}}
}
func calc() {
s := big.NewInt(0)
mod := big.NewInt(0)
mod.Exp(big.NewInt(10), big.NewInt(2000), nil)
for i := 0; i < 100; i++ {
s.Add(s, fastcal(200000, cof_t[i]))
s.Mod(s, mod)
}
fmt.Println(s.String())
}
func main() {
calc()
}
/*
(base) PS C:\Users\Mio\Desktop\work\gotest> Measure-Command -Expression {.\app.exe}
Days : 0
Hours : 0
Minutes : 0
Milliseconds : 837
Ticks : 418378605
TotalDays : 0.000484234496527778
TotalHours : 0.0116216279166667
TotalMinutes : 0.697297675
TotalSeconds : 41.8378605
TotalMilliseconds : 41837.8605
*/ 可以考虑采用 GMP 代替原生 math/big。
GitHub - ncw/gmp: Go language interface to GMP - GNU Multiprecision Library (golang)
Go language interface to GMP - GNU Multiprecision Library (golang) - GitHub - ncw/gmp: Go language interface to GMP - GNU Multiprecision Library (golang)
T3 easy_dlp
题目脚本：
from Crypto.Util.number import getPrime
import random
import flag
x = getPrime(64)
n = getPrime(1024)
m = getPrime(120)
c = pow(m,x,n)
print(m,c,n)
'''
m = 696376465415968446607383675953857997
c = 75351884040606337127662457946455960228423443937677603718170904462378938882502061014476822055783421908392386804380503123596242003758891619926133807099465797120624009076182390781918339985157326114840926784410018674639537246981505937318380179042568501449024366208980139650052067021073343322300422190243015076307
n = 135413548968824157679549005083702144352234347621794899960854103942091470496598900341162814164511690126111049767046340801124977369460415208157716471020260549912068072662740722359869775486486528791641600354017790255320219623493658736576842207668208174964413000049133934516641398518703502709055912644416582457721
'''
p = getPrime(512)
g = getPrime(512)
y = pow(g,x,p)
k = random.randint(0,p)
c1 = flag * pow(y,k,p)
c2 = pow(g,k,p)
print(c1,c2)
'''
c1 = 209941170134628207830310059622280988835086910150451946264595015050300510031560522999562095124692878755896950865676914790595999182721583547184333760954091880805688518459046880395477235753285839380764579025127254060855545
c2 = 4803339369764546990337396010353372745379378328671778873584350940089623041410194355125962064067657967062926344955874581199853582279928946579389671271191196
p = 6809372619970287379746941806942051353536181082328454067824596651780784704823185066486367854653297514943018290212240504418345108411269306758069486928594027
g = 12575636661436726898107254102531343862656456137827822292892883099464907172061178954026138165159168595086335202285503403441736394399853074532771428483593753
k = 4521228602593215445063533369342315270631623025219518143209270060218625289087470505221974748605346084266802332207199304586313352026660695691783656769488472
'''脚本分成两个部分：
- $x, n, m$ 都是随机质数，给出 $m, n$ 以及 $c = m ^ x \bmod n$.
- $p, g$ 都是随机质数，$y = g ^x \bmod p$，$k$ 是随机数。给出 $p, g, k$ 以及$$c_1 = flag \cdot (y ^k \bmod p), \quad c_2 = g ^ k \bmod p $$
显然步骤 2 是一个类似于 Elgamal 体系的加密算法（本站 2020 年有一篇博客介绍 Elgamal 加密体系）。即使不知道 Elgamal，也可以马上看出：$$\begin{aligned}c _ 1 & \equiv flag \cdot y ^ k \pmod p \\ & \equiv flag \cdot g ^ {xk} \\ & \equiv flag \cdot c_2 ^ x\end{aligned}$$于是有 $$flag \equiv c _ 1 \cdot c_2 ^ {-x} \pmod p$$所以，只要我们能获得 $x$，我们立即就能拿到 flag。
现在来考虑如何获取 $x$。这是一个离散对数问题（DLP）：$x \equiv \log _ m c \pmod n $，对 DLP 不太了解的读者可以先看本站的文章：
Pohlig-Hellman 算法
Pohlig-Hellman 算法是一种求离散对数的算法。其应用条件是底数的阶可以分解成若干个小质数之积。
大步小步算法可以在 $\sqrt n$ 复杂度内求解离散对数问题。但是本题中 n 有 1024 bit，显然不可接受。但我们详细考察大步小步算法，可以立刻发现：由于本题必定有 $x< 2 ^ {64}$（由题面脚本，$x$ 是一个 64 bit 的质数），故我们只需要在 $[0, 2 ^ {64}]$ 范围内寻找答案。这一下就把计算复杂度降低到了 $2^ {32}$ 级别。
然而，$2 ^ {32}$ 级别的复杂度，也难以在赛场上几个小时内求解。我们应当再做一些小优化。Pohlig-Hellman 算法中，是把 $n-1$ 拆成若干质数的幂，在模这些质数幂的意义下分别求解，最终用中国剩余定理（CRT）合并答案。本题的解决方法与 Pohlig-Hellman 算法几乎一模一样。
可以直接从 factor DB 查询到 $n-1$ 的几个质因数：$28142457071, 395710839697$. 它们的乘积有 74 bit，所以 CRT 之后足够恢复 64 bit 的 $x$ 了。
来看对于 $q \mid n-1$，应该如何求出 $x \pmod q$。我们设 $x = kq + r$，其中 $r < q$。那么，由于 $c \equiv m ^ x \pmod n $，有$$\begin{aligned} c ^ {\frac{n-1}{q}} & \equiv (m ^ x) ^ {\frac{n-1}{q}} \pmod n \\ & \equiv m ^ {(kq+r) \cdot \frac{n-1}{q}} \\ & \equiv m ^ {k(n-1)} \cdot (m ^ {\frac{n-1}{q}}) ^ {r} \\ & \equiv (m ^ {\frac{n-1}{q}}) ^ {r}\end{aligned}$$
等式左边可以直接计算，右边的 $m ^{\frac{n-1}{q}} $也可求。所以这个等式可以写作 $A \equiv B ^r \pmod n$，其中 $$A = c ^ \frac{n-1}{q} \bmod n, B = m ^ \frac{n-1}{q} \bmod n$$
一旦求出 $r \equiv \log _ B A \pmod n$ 就能求出原问题的解 $x$。虽然这仍然是一个 DLP 问题，但有一个很好的性质：底数 $B$ 的阶仅仅是 $q$，这是因为 $B^ q \equiv m ^ {n-1} \equiv 1 \pmod n$. 所以这个离散对数的求解复杂度仅仅是 $\sqrt q$. 获取到 $r$ 之后，可以拿到 $x \bmod q = r$.
至此，解题方法已经明了：求出 $x$ 模 $28142457071, 395710839697$ 的结果，再用 CRT 合并。
m = 696376465415968446607383675953857997
c = 75351884040606337127662457946455960228423443937677603718170904462378938882502061014476822055783421908392386804380503123596242003758891619926133807099465797120624009076182390781918339985157326114840926784410018674639537246981505937318380179042568501449024366208980139650052067021073343322300422190243015076307
n = 135413548968824157679549005083702144352234347621794899960854103942091470496598900341162814164511690126111049767046340801124977369460415208157716471020260549912068072662740722359869775486486528791641600354017790255320219623493658736576842207668208174964413000049133934516641398518703502709055912644416582457721
def solve_part(q):
assert (n-1) % q == 0
A = mod(c, n) ^ ((n-1) / q)
B = mod(m, n) ^ ((n-1) / q)
return discrete_log(A, B, ord=q)
q1, q2 = 28142457071, 395710839697
solve_part(q1), solve_part(q2)
# (14542911801, 262629324154)
x = crt([14542911801, 262629324154], [q1, q2])
assert len(x.bits()) == 64
x
# 17271504622210389511获取 $x$ 之后，立即可以解密：
R = Zmod(6809372619970287379746941806942051353536181082328454067824596651780784704823185066486367854653297514943018290212240504418345108411269306758069486928594027)
c1 = R(209941170134628207830310059622280988835086910150451946264595015050300510031560522999562095124692878755896950865676914790595999182721583547184333760954091880805688518459046880395477235753285839380764579025127254060855545)
c2 = R(4803339369764546990337396010353372745379378328671778873584350940089623041410194355125962064067657967062926344955874581199853582279928946579389671271191196)
long_to_bytes(int(c1 * c2^(-x)))
# b'flag{th1s_1s_so_3a2y_rlgh4}'T4 easywork
题目脚本：
from Crypto.Util.number import *
from random import *
import hashlib
from pwn import *
p = getPrime(128)
seed = randint(2, p - 1)
c = 114514
e = int(2e8)
class prng:
n = p
a,b = [randint(2, p - 1) for _ in range(2)]
def __init__(self,seed):
self.state = seed
def next(self):
self.state = (self.state * self.a + self.b) % self.n
return self.state
def test():
gen = prng(seed)
print(seed)
print(gen.next())
print(gen.next())
print(gen.next())
print(gen.next())
print(gen.next())
print(gen.next())
def m_func(i):
if i == 0: return 1
return a*c**i+b*m_func(i-1)+n
def encrypt_flag(sol):
sol = sol % (10**10000)
sol = str(sol)
sol_md5 = hashlib.md5(sol.encode()).hexdigest()
return xor(sol_md5.encode(),flag)
if __name__ == "__main__":
test()
sol = m_func(e)
print(encrypt_flag(sol))
'''
150532854791355748039117763516755705063
335246949167877025932432065299887980427
186623163520020374273300614035532913241
215621842477244010690624570814660992556
220694532805562822940506614120520015819
17868778653481346517880312348382129728
160572327041397126918110376968541265339
b'UUV\x04H\x01T\x01P\x03\t\x04\t\x1fW\x00T\x02LRSPT\x1d\x02\x02^\x01N[\\R\x02\tSV\x07\x06P\x01QK'
'''由于 $flag = \text{md5}(\text{m_func}(e)) \oplus enc$，我们必须恢复 $a, b, n$ 才能计算 $\text{m_func}$. 来考虑如何恢复 $a, b, n$。
题目给了一个模线性同余生成器（LCG）。生成方法是：$$s_{i+1}\equiv a \cdot s _i + b \pmod n$$先展开前几项：$$\begin{aligned} s _ 0 &\equiv s _ 0 \\ s _ 1 &\equiv a s _ 0 + b \\ s _ 2 & \equiv a ^ 2 s _ 0 + a b + b \\ s _ 3 & \equiv a ^ 3 s_0 + a ^2 b + ab +b\end{aligned}$$从题目中给出的 $6$ 个连续状态产出，我们可以完全恢复这个 LCG 的参数（$a, b, n$）。显然，一但知道 $n$，恢复 $a,b$ 的过程很简单（与仿射密码的已知明文攻击一样）。现在来考虑如何恢复 $n$.
这种「模数未知」的方程组，有一个很常用的处理手段：构造 $A\equiv 0 \pmod n, B\equiv 0 \pmod n$ 且 $A\neq B$，然后求 $\gcd(A, B)$ 获得 $n$. 现在我们尝试寻找一组这样的「桥梁」。
考虑 $t _ i = s _ i - s _ {i-1}$，那么我们立即有 $$\begin{aligned}t_i & \equiv a s_ {i-1} + b - s _ {i-1} \\ & \equiv a s _ {i-1} + b - (a s _ {i-2} +b) \\ & \equiv a (s _ {i-1} - s _ {i-2}) \\ & \equiv a \cdot t _ {i-1}\end{aligned} $$利用这个特性，我们发现 $$t _ {i+2} t _ {i} \equiv a ^ 2 t _ i \equiv t _ {i+1} ^ 2$$于是$$t _ {i+2} t _ i - t _{i+1} ^ 2 \equiv 0$$从而我们找到了多个 $n$ 的倍数，这个桥梁建立起来了。想要获得 $n$，只需求 $$\gcd(t _ 1 t _ 3 - t_ 2 ^ 2, t _ 2 t _ 4 - t _3 ^2)$$
s = [150532854791355748039117763516755705063, 335246949167877025932432065299887980427, 186623163520020374273300614035532913241, 215621842477244010690624570814660992556, 220694532805562822940506614120520015819, 17868778653481346517880312348382129728, 160572327041397126918110376968541265339]
t = [s[x] - s[x-1] for x in range(1, len(s))]
n = gcd(t[1]*t[3] - t[2]*t[2], t[2]*t[4] - t[3]*t[3])
assert is_prime(n)
n
# 339088189917874808463944743121467561531接下来求 $a, b$. 显然 $$s _ 2 - s _ 1 \equiv a (s _ 1 - s _ 0)$$于是$$a \equiv \frac{s_ 2- s _ 1}{s _1 - s _0}$$
R = Zmod(n)
a = R(s[2] - s[1]) / (s[1] - s[0])
b = R(s[1] - a * s[0])
a, b
# (259086495324961642923203668736965982268, 121870392737324465817476070178603827899) 今 $a,b,n$ 都已知。只需要计算出 m_func(2e8) 的后 10000 位，即可拿到 flag。来看这个 m_func 的定义：
def m_func(i):
if i == 0: return 1
return a*c**i+b*m_func(i-1)+n数学形式：$$f_i = a\cdot c^i + b \cdot f_ {i-1} + n$$这很明显可以矩阵快速幂加速递推。改写成矩阵递推形式：$$\begin{bmatrix} 1 & 0 & 0 \\ 0 & c & 0 \\ n & a & b\end{bmatrix}\cdot \begin{bmatrix} 1 \\ c ^ i \\ f _ {i-1}\end{bmatrix} = \begin{bmatrix} 1 \\ c ^ {i + 1} \\ n + a \cdot c ^ i + b \cdot f _{i-1}\end{bmatrix} = \begin{bmatrix} 1 \\ c ^ {i + 1} \\ f _ {i}\end{bmatrix} $$于是有$$\begin{bmatrix} 1 & 0 & 0 \\ 0 & c & 0 \\ n & a & b\end{bmatrix} ^ {\textcolor{red}{x}} \cdot \begin{bmatrix} 1 \\ c \\ f _ 0 \end{bmatrix} = \begin{bmatrix} 1 \\ c ^ {x + 1}\\ f _ {x}\end{bmatrix}$$
a, b = int(a), int(b)
c = 114514
def m_func(i):
if i == 0: return 1
return a*c**i+b*m_func(i-1)+n
def fast_f(x):
mat = matrix(Zmod(10^10000), [[1, 0, 0], [0, c, 0], [n, a, b]])
res = mat^x * vector([1, c, 1])
return res[2]
assert m_func(100) == fast_f(100)
sol = fast_f(2*10^8)
from hashlib import md5
key = md5(str(sol).encode()).hexdigest()
key
# '397c37a1569112a1d4af2ad0c08bc9ec'
from Crypto.Util.strxor import strxor
strxor((key+key)[:42].encode(), b'UUV\x04H\x01T\x01P\x03\t\x04\t\x1fW\x00T\x02LRSPT\x1d\x02\x02^\x01N[\\R\x02\tSV\x07\x06P\x01QK')
# b'flag{650e5058-6106-4a10-a2fc-b9110d54110d}'矩阵快速幂加速递推，是算法竞赛知识，极少在 CTF 中考察。本题算是比较新颖。
0x02 羊城杯2022
先鸽着。
0x03 柏鹭杯2022
这场比赛的密码学挺简单，上午上完英语课回来一小时 AK。考察点：编码类古典密码学；简单数学；抽象代数。赛后才知道 T2 Anti-Fermat 是洋比赛原题，连名字都没改就放上来。出题人有点太不上心了。
T1 混合编码
先解 hex 和 base64，获得一个奇形怪状的串。一般 CTF 里面，如果一个串与 flag 长度一致，可以猜测此串与 flag 之间存在逐字符的算术对应关系。所以把这个串与真正 flag 的前缀（例如，在柏鹭杯是 flag{ISEC- ），逐字节相加、相减、相异或，往往可以找到规律。
本题的规律是：r 串与 flag 之间相差 $\pm 47$。在可见字符中筛一下即可。
T2 Anti-Fermat
一道 RSA 题目。题目附件：
from Crypto.Util.number import isPrime, getStrongPrime
from gmpy2 import next_prime
from secret import flag2
p = getStrongPrime(1024)
q = next_prime(p ^ ((1<<1024)-1))
n = p * q
e = 65537
# Encryption
m = int(flag2.encode('hex'),16)
assert m < n
c = pow(m, e, n)
print('n = {}'.format(hex(n)))
#n = 0x31e22a7a2c5ec946692357dc51014a80530afeb46f419831fcbd896aa1d5cee2d0c69123b3017067afdb3d82b2be3535aebdf11da0fa2b4873233bae6af8a1c2a9344b6f64ade1c6c48a2828130c352053e1729b850774589e8947c8c0a472a8dc90caa542da5cec7f5fa7581747dcb558300437c30b016f769d4a85af8584f311dfb2f9e87fa7d16eaccb0303ecba491619ec7dda72e4037d96c607e666eced582d6eb2c232689fce1c08a54b80cf6d39ef1f2b467d970998c6d54d1779979c89a3b301cd1435bde8787d1141c912cf32b56610fba9205c6e86fefc490c8b2e06f5ed9f775f5b0fe945fa9fca3fc217b4c9dcd4b26676f576d0273b79417b81
print('c = {}'.format(hex(c)))
#c = 0x118dd8ab5df8685c5db5b1242896df41e8e9016f5f16276b6d311b29f0e5f9315530574b51c6e7c82d0c88ab92787d639443b921a452c850db580256ccfd55ee52ea9732821525da1d21351acb230a799ecaa1802c6f24487176c9cae537c3188e083552a84a2aebdd55c4014b41846768d7608970c1e52d9a68e550ef8bb6016adb6f8e0672e1c8198a5442799a5b8142e8d0fadb6e6146a062ef906bd58c46f31bf65263b6142b1976773289dee408ae233b6c0c534dd5092bd7f331c3457971278d335923edc044ba88852680ee39d1cc84a66dc81b70039e2435892b11f310b490c872448f7a8dc718759b2052b0911f758102a59c54dea061a8a3ff6879
我们注意到 $p+q \approx 2^{1024}$。记 $q = 2 ^ {1024} - p + r$，则依据质数分布定理，$r = \mathcal{O}(\ln 2^{1024}) $，数值上 $\ln 2 ^{1024} \approx 710$，所以我们可以枚举 $r$。那么立即有：$$\begin{aligned}n & = pq \\ & = p(2 ^ {1024} - p + r) \end{aligned}$$整理一下，得到关于 $p$ 的一元二次方程：$$p^ 2 - ( 2 ^ {1024} + r ) p + n = 0$$
根据 $\Delta = \sqrt{ (2^ {1024} + r) ^ 2 - 4n }$ 能否开尽，来判断目前枚举的 $r$ 是否正确。
import gmpy2
n = 0x31e22a7a2c5ec946692357dc51014a80530afeb46f419831fcbd896aa1d5cee2d0c69123b3017067afdb3d82b2be3535aebdf11da0fa2b4873233bae6af8a1c2a9344b6f64ade1c6c48a2828130c352053e1729b850774589e8947c8c0a472a8dc90caa542da5cec7f5fa7581747dcb558300437c30b016f769d4a85af8584f311dfb2f9e87fa7d16eaccb0303ecba491619ec7dda72e4037d96c607e666eced582d6eb2c232689fce1c08a54b80cf6d39ef1f2b467d970998c6d54d1779979c89a3b301cd1435bde8787d1141c912cf32b56610fba9205c6e86fefc490c8b2e06f5ed9f775f5b0fe945fa9fca3fc217b4c9dcd4b26676f576d0273b79417b81
for r in range(2000):
res, sig = gmpy2.iroot((2**1024 + r)**2 - 4*n, 2)
if sig:
p = (2**1024 + r + res) // 2
assert n % p == 0
break
p
# mpz(132098967105531742873047504870639055197609951019173177101671798230777865821433888917823038778161777368298104713268965870357657760711727391719230943186702876337077201988497196346565418382245386473264935668867873004662959808864928113250273132697978392727824134298261799367370517153525019431759593486155031995139)获得 $p$ 之后解密即可。
c = 0x118dd8ab5df8685c5db5b1242896df41e8e9016f5f16276b6d311b29f0e5f9315530574b51c6e7c82d0c88ab92787d639443b921a452c850db580256ccfd55ee52ea9732821525da1d21351acb230a799ecaa1802c6f24487176c9cae537c3188e083552a84a2aebdd55c4014b41846768d7608970c1e52d9a68e550ef8bb6016adb6f8e0672e1c8198a5442799a5b8142e8d0fadb6e6146a062ef906bd58c46f31bf65263b6142b1976773289dee408ae233b6c0c534dd5092bd7f331c3457971278d335923edc044ba88852680ee39d1cc84a66dc81b70039e2435892b11f310b490c872448f7a8dc718759b2052b0911f758102a59c54dea061a8a3ff6879
q = n // p
d = gmpy2.invert(0x10001, (p-1)*(q-1))
m = pow(c, d, n)
long_to_bytes(m)
# b'flag{ISEC-OyGdWk_E3gTcPtWUn_OaqD@d76xHyse1}'T3 异或密码
题的 idea 本身不错，但是出题人的工作态度堪忧。且不说出题人是用的 Python 2；事实上 flag 格式与出题人代码中声称的十六进制串并不一样。题目附件：
from Crypto.Random import random
from Crypto.Util import number
from secret import flag3 as flag
def convert(msg):
msg = msg ^ msg >> x
msg = msg ^ msg << 13 & 296229569
msg = msg ^ msg << 20 & 2345273571
msg = msg ^ msg >> 14
return msg
def transform(message):
assert len(message) % 4 == 0
new_message = ''
for i in range(len(message) / 4):
block = message[i * 4 : i * 4 +4]
block = number.bytes_to_long(block)
block = convert(block)
block = number.long_to_bytes(block, 4)
new_message += block
return new_message
enFlag = transform(flag[5:-1].decode('hex')).encode('hex')
print('transformed_flag:', enFlag)
# transformed_flag: fb9cd6ab42f2be75ae2637794196159de16e49522ed55e83462b0802a0325e1a4e9cbad3
这是 ECB 模式的块密码，加密过程是连续做了 4 次「x 位移 offset 位，再进行掩码运算，得到的结果异或上 x 输出」。这种「移位 - 掩码 - 异或」范式是 CTF 出题人经常使用的把戏，与很多 LFSR 题目一样，想要解决问题，只需要注意到一条性质：异或运算完全可以视为模 $2$ 意义下的加法；形式化地讲，群 $\left ( \{0, 1 \}, \oplus \right )$ 与群 $\mathbb{Z}/2\mathbb{Z}$ 是同构的。
既然异或运算可以视为加法，我们立刻就能拿起线性代数的武器来加以研究。举个例子，我们将演示如何针对一个 8-bit 的数 $x$，以矩阵变换的形式给出 $x \oplus (x >> 3)$。首先把 $x$ 写成列向量的形式 $(x_0, x_1, \cdots, x_7) ^ T$，那么：$\newcommand\gray{\textcolor{lightgray}}$
$$\left[ \begin{matrix} {} 1 & \gray{0} & \gray{0} & 1 & \gray{0} & \gray{0} & \gray{0} & \gray{0} \\ \gray{0} & 1 & \gray{0} & \gray{0} & 1 & \gray{0} & \gray{0} & \gray{0} \\ \gray{0} & \gray{0} & 1 & \gray{0} & \gray{0} & 1 & \gray{0} & \gray{0} \\ \gray{0} & \gray{0} & \gray{0} & 1 & \gray{0} & \gray{0} & 1 & \gray{0} \\ \gray{0} & \gray{0} & \gray{0} & \gray{0} & 1 & \gray{0} & \gray{0} & 1 \\ \gray{0} & \gray{0} & \gray{0} & \gray{0} & \gray{0} & 1 & \gray{0} & \gray{0} \\ \gray{0} & \gray{0} & \gray{0} & \gray{0} & \gray{0} & \gray{0} & 1 & \gray{0} \\ \gray{0} & \gray{0} & \gray{0} & \gray{0} & \gray{0} & \gray{0} & \gray{0} & 1 \end{matrix} \right ] \cdot \left [ \begin{matrix}x_ 0 \\ x _ 1 \\ x _ 2 \\ x _ 3 \\ x _ 4 \\ x _ 5 \\ x _ 6 \\ x _ 7 \end{matrix} \right ] = \left [ \begin{matrix}x_ 0 + x_3 \\ x _ 1 + x_4 \\ x _ 2 + x_5 \\ x _ 3 + x_6 \\ x _ 4 + x_7 \\ x _ 5 \\ x _ 6 \\ x _ 7 \end{matrix} \right ] $$
我们通过一个矩阵乘法给出了 $x \oplus (x >> 3)$；更加令人惊喜的是，它的行列式为 1，意味着矩阵可逆。另一个例子是，我们可以用以下矩阵变换给出 $x \oplus ((x << 2) \texttt{ & 0b11001010})$：
$$\left[ \begin{matrix} 1 & \gray{0} & \gray{0} & \gray{0} & \gray{0} & \gray{0} & \gray{0} & \gray{0} \\ \gray{0} & 1 & \gray{0} & \gray{0} & \gray{0} & \gray{0} & \gray{0} & \gray{0} \\ \gray{0} & \gray{0} & 1 & \gray{0} & \gray{0} & \gray{0} & \gray{0} & \gray{0} \\ \gray{0} & 1 & \gray{0} & 1 & \gray{0} & \gray{0} & \gray{0} & \gray{0} \\ \gray{0} & \gray{0} & \gray{0} & \gray{0} & 1 & \gray{0} & \gray{0} & \gray{0} \\ \gray{0} & \gray{0} & \gray{0} & \gray{0} & \gray{0} & 1 & \gray{0} & \gray{0} \\ \gray{0} & \gray{0} & \gray{0} & \gray{0} & 1 & \gray{0} & 1 & \gray{0} \\ \gray{0} & \gray{0} & \gray{0} & \gray{0} & \gray{0} & 1 & \gray{0} & 1 \end{matrix}\right ] \cdot \left [ \begin{matrix}x_ 0 \\ x _ 1 \\ x _ 2 \\ x _ 3 \\ x _ 4 \\ x _ 5 \\ x _ 6 \\ x _ 7 \end{matrix} \right ] = \left [ \begin{matrix}x_ 0 \\ x _ 1 \\ x _ 2 \\ x _ 3 + x_1 \\ x _ 4 \\ x _ 5 \\ x _ 6 + x_4 \\ x _ 7 + x_5 \end{matrix} \right ]$$ 不难看出这个矩阵的行列式也为 1，于是也可逆。
讲到这里，本题的解密方法已经呼之欲出：既然加密过程等同于给明文 $M$ 依次左乘四个矩阵 $E_1, E_2, E_3, E_4$ 得到 $C$，那么我们想要解密，只需要给 $C$ 依次左乘 $E_4 ^ {-1}, E_3 ^ {-1}, E_2 ^ {-1}, E_1 ^ {-1}$，即可恢复 $M$。
来一起看代码实现。首先，我们写一个函数用于生成变换矩阵。
# 变换矩阵：x ^ ((x >> offset) & mask)
# 若要实现左移 k 位，只需 offset 置为 -k
def get_matrix(offset, mask):
m = identity_matrix(Zmod(2), 32)
for x in range(32):
for y in range(32):
if y == x + offset and (mask & (1 << x)):
m[x, y] = 1
return m
# uint32 -> 列向量
def num2vector(x):
res = zero_vector(Zmod(2), 32)
for pos, k in enumerate(x.bits()):
res[pos] = k
return res
# 列向量 -> uint32
def vector2num(x):
return reduce(lambda a, b: a*2 + b, x.change_ring(ZZ)[::-1])
assert vector2num(num2vector(0xdeadbeaf)) == 0xdeadbeaf
# 验证
assert vector2num(get_matrix(3, 0xffffffff) * num2vector(0x114514)) == (0x114514 ^^ (0x114514 >> 3))
assert vector2num(get_matrix(-4, 0xdeadbeaf) * num2vector(0x123456)) == (0x123456 ^^ (0x123456 << 4 & 0xdeadbeaf))可见我们的变换矩阵确实能完成加密任务。现在，我们来验证一下解密过程：
123456789 ^^ (123456789 << 2 & 0xdeadbeaf)
# 460781841
E = get_matrix(-2, 0xdeadbeaf)
vector2num(E.inverse() * num2vector(460781841))
# 123456789 于是我们也掌握了解密的技术。按理来讲题目到此应该迎刃而解了；不过出题人挖了个坑：第一次变换的代码是 msg = msg ^ msg >> x ，而这里的 x 没有被定义。我们需要枚举这个 x ，看哪一个候选 x 能给出合理的解密结果：
from Crypto.Util.number import *
prob = bytes.fromhex('fb9cd6ab42f2be75ae2637794196159de16e49522ed55e83462b0802a0325e1a4e9cbad3')
# c = m ^ (m >> offset & mask)，恢复 m
def inv_convert(c, offset, mask):
c = num2vector(Integer(c))
E = get_matrix(offset, mask)
return long_to_bytes(vector2num(E.inverse() * c))
# 以指定的 x 作为第一轮 offset，解密密文块
def decrypt(c, x):
c = inv_convert(bytes_to_long(c), 14, 0xffffffff)
c = inv_convert(bytes_to_long(c), -20, 2345273571)
c = inv_convert(bytes_to_long(c), -13, 296229569)
c = inv_convert(bytes_to_long(c), x, 0xffffffff)
return c
for x in range(1, 32):
print(x, decrypt(prob[:4], x))枚举一遍，发现只有取 $7$ 可以给出可见字符的明文：
解密整个密文，获得 s1ZcYawU5fCmI-ISzQn97SCRL2tB8HNETujq ：
出题人在这里埋了最后一手坑，也是整道题目最大的败笔，如同狗尾续貂：这个串需要经过 Rail Fence 解密为本场比赛的 flag 格式 ISEC-*** ，才可提交。
0x04 TeamItaly CTF 2022
意大利比赛，赛场上只做出前两题。考察范围：MT19937；耐心。
T1 Lazy platform
题目源码：
from Crypto.Util.Padding import pad
from Crypto.Cipher import AES
import random
import signal
import os
TIMEOUT = 300
FLAG = os.environ.get("FLAG", "flag{test}").encode()
def getrandbytes(n: int) -> bytes:
return random.getrandbits(n * 8).to_bytes(n, "little")
def handle():
print("Welcome to Lazy platform! If you want to decrypt some messages, you can't do that here, you'll have to do it on your own")
while True:
print("Choose one of the following options")
print("[1] Encrypt")
print("[2] Decrypt")
print("[3] Get encrypted flag")
print("[4] Exit")
option = input("> ")
if option == "1":
message = input("Enter a message to encrypt: ")
key = getrandbytes(32)
iv = getrandbytes(16)
ciphertext = AES.new(key, AES.MODE_CBC, iv).encrypt(
pad(message.encode(), AES.block_size))
print("Ciphertext:", ciphertext.hex())
print("Key:", key.hex())
print("IV:", iv.hex())
elif option == "2":
print("I can't do that at the moment, I'm cooking a pizza")
elif option == "3":
key = getrandbytes(32)
iv = getrandbytes(16)
ciphertext = AES.new(key, AES.MODE_CBC, iv).encrypt(
pad(FLAG, AES.block_size))
print("Ciphertext:", ciphertext.hex())
elif option == "4":
print("Bye bye!\n")
break
else:
print("Invalid option")
print()
if __name__ == "__main__":
signal.alarm(TIMEOUT)
handle()明显是 MT19937，每次交互可以获得 32 + 16 个字节的状态，即相当于 12 个 uint32。只需做 $52$ 轮，即可获得 $52\times 12= 624$ 个 uint32。
梅森旋转状态恢复器：
GitHub - kmyk/mersenne-twister-predictor: Predict MT19937 PRNG, from preceding 624 generated numbers. There is a specialization for the “random” of Python standard library.
Predict MT19937 PRNG, from preceding 624 generated numbers. There is a specialization for the "random" of Python standard library. - GitHub - kmyk/mersenne-twister-predictor: Predict MT19...
exp：
from Crypto.Util.Padding import pad
from Crypto.Cipher import AES
from pwn import *
from mt19937predictor import MT19937Predictor
io = remote('lazy-platform.challs.teamitaly.eu', 15004)
p = MT19937Predictor()
def get_rand_state():
io.recvuntil(b'> ')
io.sendline(b'1')
io.recvuntil(b': ')
io.sendline(b'a')
_ = io.recvline().split()[-1]
key = io.recvline().split()[-1].decode()
iv = io.recvline().split()[-1].decode()
print(key, iv)
p.setrandbits(int.from_bytes(bytes.fromhex(key), 'little'), 256)
p.setrandbits(int.from_bytes(bytes.fromhex(iv), 'little'), 128)
def getrandbytes(n: int) -> bytes:
return p.getrandbits(n * 8).to_bytes(n, "little")
if __name__ == '__main__':
for x in range(52):
get_rand_state()
key = getrandbytes(32)
iv = getrandbytes(16)
print('+ ', key.hex(), iv.hex())
io.recvuntil(b'> ')
io.sendline(b'3')
io.recvuntil(b'Ciphertext:')
cipher = io.recvline().decode()
print(cipher)
m = AES.new(key, AES.MODE_CBC, iv).decrypt(bytes.fromhex(cipher))
print(m)
# io.recvuntil(b'> ')
# io.interactive()T2 The Missing Half
题目附件：
给了一个 Python 脚本，给了一个 out 文件。题目提示：If something seems impossible you should look at it from a different point of view, maybe a different base。来看题目脚本：
#!/usr/bin/env python3
from Crypto.Util.number import *
import os
import random
from hashlib import md5
FLAG = os.environ.get("FLAG", "flag{test}")
def a(x, y) -> int:
return x ** y
def b(f: int, x: int) -> int: # caller
func = [random.seed, getPrime, isPrime, md5]
if f == 3:
return bytes_to_long(func[f](long_to_bytes(x)).digest())
r = func[f](x)
return int(r) if r else 0
def c(z: int, x: int, y: int) -> int: # random
if z:
return random.randint(x ** 11, x ** 11 + y)
x = long_to_bytes(x)
y = long_to_bytes(y)
while len(x) < len(y):
x += x
x = x[:len(y)]
return bytes_to_long(xor(x, y))
def d(x: int) -> int:
if x == 1:
return 1
if x == 2:
return 2
if x == 3:
return 24
return (6 * d(x - 1) ** 2 * d(x - 3) - 8 * d(x - 1) * d(x - 2) ** 2) // (d(x - 2) * d(x - 3))
def fastd(n):
n = n - 1
temp = 1
for i in range(1, n + 1):
temp *= (2 ** i) - 1
esp = 2 ** ((n ** 2 + n) // 2)
return temp * esp
def e(msg: int) -> int: # rsa
n = 0x1702f4d2a98712defc05cb40b72a821479ccb9000a9bd698520082544b652bacfa721041f115da3a3cb8f4211a847706ae4dc9f048c7262a964e337bc47065de1059eccc87c19f662c21f9066805e5f75b3c62305395138d5eb71e9f9966297750ee17ccfcace1386abaf53434b264696744ae990bdebb17a4a56c4edc0cccfcf8da138fcf0c911f434d2d3e0b493b8fa9917f83f41273b4aaf7d631dabb66939f67fcb270e0a7156c7e66338027387e873c225991180fec96ea4fc0f9f88815010e5994d5f35ae21568d5641b00d44876762c392e9853045a5a92eb2354486f80946368f83469a7b37e621906f81f8005b126417fd716bcd79c84610dc093dd7575ebcf3af3d71a869830455d3ad6d68ad2254843320233e01f1cafdc73310f7ffb1deccb4df2fee6150a1a588867c5285c7049bf39e1a631badc81d61dda69e5d2e017235306ad46b0703e88a5c65807737a6a459231f5eb6bd6afd44fb46566c1
e = 0x10001
return pow(msg, e, n)
def xor(x, y):
return bytes(a ^ b for a, b in zip(x, y))
def f(x: int) -> int:
return bytes_to_long(xor(long_to_bytes(x), FLAG.encode()))
def Lukasiewicz(password: str) -> int:
stack = []
func = {'a': (a, 2), 'b': (b, 2), 'c': (c, 3),
'd': (fastd, 1), 'e': (e, 1), 'f': (f, 1)}
for t in password:
if t.isdigit():
stack.append(int(t))
else:
args = []
for _ in range(func[t][1]):
args.append(stack.pop())
args.reverse()
tmp = func[t][0](*args)
stack.append(tmp)
return stack.pop()
with open('missing-half.py.out', 'w') as file:
password = '08ae7eb31227acdb553aafec'
file.write('out:' + hex(Lukasiewicz(password)))
这题目还是很新颖的，以前没有在 Crypto 中看到出题人用后缀表达式来描述加密过程。做此题需要一点时间用于分析加密过程，我们首先把后缀表达式转中缀：
c(b(e(a(0, 8)), e(7)), b(3, d(c(1, 2, a(2, 7)))), e(f(a(5, a(5, 3)))))
= c(b(0, e(7)), b(3, d(c(1, 2, a(2, 7)))), e(f(a(5, a(5, 3)))))
= c(0, md5_to_long(d(randint(2048, 2176))), e(f(2350988701644575015937473074444491355637331113544175043017503412556834518909454345703125)))
= c(0, md5_to_long(d(2087)), e(f(2350988701644575015937473074444491355637331113544175043017503412556834518909454345703125)))
= c(0, 160041365501716368448053427917678638214, e(f(2350988701644575015937473074444491355637331113544175043017503412556834518909454345703125)))
= strxor(b'xf\xd8\x87f\\\xbc\xa8\xc0I\xac\xa4\xffR\xf4\x86', e(f(2350988701644575015937473074444491355637331113544175043017503412556834518909454345703125))) 式子简化到这个程度之后，我们发现问题的核心在于这个 e 函数执行了一个 RSA 加密。如果能解密，则通过几次异或就能拿到 flag。因此考虑分解题目中给的这个 $n$，由于出题人提示「换一个进制看看」，我们尝试给 $n$ 变换一下进制：
可见在 17 进制下 $n$ 很有规律。用等比数列求和之类的手段，可以看出$$n = 17 ^ {692} - 2 * 17 ^ {460} + 4 - 2 * 17 ^ {232}$$至此已经可以人工用十字相乘分解了。不过也可以自动分解一下：
于是 $n=(17 ^ {460} - 2) \cdot (17 ^ {232} - 2)$，剩余解题过程平凡。