本系列博客大概写一些较大比赛解数量较少的writeup，主要提供思路，具体流程可能不会过于细节
ByteCTF 2020 crypto2
crypto1和crypto3都没啥好说的，这里就放下cry2的writeup~
分析可以构造 \(B = (H(m)+1)*G \Rightarrow encK = H(kc*G) = H(A-H(m)*G)\)
故做签名的sk为\(flag \otimes Cprime\)，使\(Cprime = cipher = flag \otimes private\_key\)
则对s,e 有\(s \equiv r - e * private\_key \mod (n)\)，即有\(r*G =s*G + e*pk\)，又\(rG.x = e\)，故可做verify判断，这里考虑可以诸位爆破，从低位对\(Cprime\) 诸位取反，则最终得到的sk为private_key某一位取反后的值，即\(sk = private\_key \pm 2^i\)，通过verify即可判断为加还是减，即可判断private_key那一位为0/1，256次后得到private_key，再与cipher异或即得到flag，exp如下：
1 | from winpwn import * |
XNUCA 2020 crypto3
crypto1利用Blomer May的连分数求出x和y再利用Copper Smith恢复p，再恢复Twisted Edward即可，crypto2因为是分组我就没看，这里只给出crypto3的writeup~
这一题算是我第一次遇见格套娃，最难的一层应该就是恢复A了，比赛的时候7点多恢复出来了A，但忘记A的列顺序不影响B，故应该对A的所有列做个全排列再恢复LWE，恰逢S10决赛，于是乎并没有拿到三血orz，晚上十二点多经学长提醒才意识到2333
本题审题后发现有三层嵌套：
第一层是类背包问题，已知向量R，可知有
\[R_{64} = \sum_{i=0}^{63} T_i * S_{yi}, R_i = T_i \]
可以发现和背包问题非常相似，但是系数\(S_{yi}\) 并非为\(0/1\)， 而是落在\([0,1000)\) 上，故考虑对解决背包问题的格子做修改，可知一般解决背包问题使用如下格子：
最后一行的向量1是用来均衡系数的，使得最后的解向量为\(2x_i - 1 = -1/1\)
这里考虑到系数为\([0, 1000)\)，故最后一行将1修改为1000，则有\(2x_i - 1000 \in [-1000, 1000)\)，则可成功规约出解向量，此部分代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23T = Matrix([i for i in R[:64]]).transpose()
def decrypt(enc, publickey):
n = len(publickey)
d = 2 * identity_matrix(ZZ, n, n)
col = publickey + [enc]
col = matrix(col).transpose()
last = matrix(ZZ, [[1000] * n])
tmp = block_matrix(ZZ, [[d], [last]])
grid = block_matrix(ZZ, [[tmp, col]])
M = grid.LLL()
return M[0][:-1]
# got Sy with R
Sy = decrypt(R[64], R[:64])
Sy = [(x+1000)//2 for x in Sy]
print(Sy)第二层，也是最难的一层，即是通过矩阵B恢复矩阵A。
这看起来是件很离谱的事情，只通过矩阵积恢复出来相乘的两个矩阵，但利用这题的bound确实可以做到这点orz。
已知有\(A r = B\)， 其中A为\(320\times5\)的矩阵，r为\(5\times 7\)的随机矩阵，B即为\(320 \times 7\)的矩阵，特殊的地方在于，A的元素均在\([10, 1000)\)上，而r的元素基本在1000位以上，故想到，我们可以对B为基底的格进行规约，从而可能得到A中某一列（因为考虑到广义逆，大概率有一个线性变换\(r'\)，使得\(A = Br'\)），但由于可能有多解，所以需要使用bound\([10, 1000)\)约束一下。
这里如果直接对B中的6列/7列进行全排列构造格子规约，则可以规约出两组320维的满足条件的A的列向量，但还有三列并不知道，这一点也是比赛中困扰我最久的问题，后来想到其实我们可以通过降低维度去扩大解空间范围，然后再取top5大概率即可找出A中所有的列向量。
具体操作即是选取6/7个B的列向量部分，做全排列，我一开始取的是前140-220行遍历，这样可以找到7-8个满足条件的部分列向量，之前规约出的两个完整列向量也在其中，后来提高了维数为200-300行便只有五个了，这样成功找到了A的前200行，此部分代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16for limit in tqdm(range(200, 300)):
base = []
for i in range(7):
base.append(B[i*320:(i+1)*320][:limit])
for rows in range(6, 8):
tmp = list(itertools.combinations(base, rows))
for l in tmp:
M = Matrix(ZZ, l)
M = M.LLL()
for i in M:
v = [abs(x) for x in list(i)]
if min(v) >= 10 and max(v) <= 1000 and v[0] not in had:
print(v)
print(limit)
had.append(v[0])
# had = [706, 808, 626, 428, 717]找到了A的前200行后，可知有\(A_{part} r = B_{part}\)，故我们对得到五个列向量全排列，然后结合B矩阵前200行，即可解出r矩阵，再利用r矩阵，即可成功恢复A矩阵，此部分代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18B_matrix = Matrix(ZZ, _B).transpose()
tmp = list(itertools.permutations(possible_A, int(cols)))
A_num = 0
for l in tqdm(tmp):
A = Matrix(ZZ, l).transpose()
try:
R = A.solve_right(B_matrix)
_B = []
for i in range(7):
_B.append(B[i * 320:(i + 1) * 320])
B_matrix = Matrix(ZZ, _B).transpose()
A = R.solve_left(B_matrix)
for j in R.list():
assert 1000 < int(j).bit_length() <= 1024
break
except:
continue需要注意的是，由于B中元素是A中行元素线性和，故而其实A的列顺序不影响B的列顺序，故需要对A的5个列做个全排列才能找到正确的A。
最后一层，比较简单，即是恢复LWE，这里我直接用了之前N1CTF那个LWE的代码，加上A的列全排列即可：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32assert A.nrows() == 320
assert len(A.columns()) == 5
all_cols_comb = list(itertools.permutations(A.columns(), int(5)))
total_sk = []
for cols_comb in tqdm(all_cols_comb):
tmp_A = Matrix(ZZ, cols_comb).transpose()
tmp = [int(x).__xor__(int(y)) for x, y in zip(tmp_A.list(), xor_M)]
LWE_a = []
for i in range(64):
LWE_a.append(tmp[i * 25:(i + 1) * 25])
LWE_c = Sy
module = 1000
row = 64
column = 25
M = matrix(ZZ, row + column, row)
for i in range(row):
for j in range(column):
M[row + j, i] = LWE_a[i][j]
M[i, i] = module
lattice = IntegerLattice(M, lll_reduce=True)
target = vector(ZZ, LWE_c[:row])
res = CVP(lattice.reduced_basis, target)
R = IntegerModRing(module)
M = Matrix(R, LWE_a[:row])
total_sk.append(M.solve_right(res))
print('total_sk =', total_sk)
最后的最后，遍历得到的所有可能私钥，解AES即可，代码如下：
1 | iv_cipher = 0xc338be5406289b99332176593ae94b5e254df0e6b31b3155f370845e99d55f3a5b8b9e5576a126512b93eacacb6b7865f925120c3a221d0a2fcff362d841ad6be183a796f0c0a8111704737b6fc412f4 |
最终得到flag：
HXB2020 crypto4
除了crypto4都比较简单，就crypto1还有点意思
这题其实即是改版的Wiener Attack，通过这篇paper 知道当存在\(|ap - bq|\) 较小时，我们可以得到\(p+q\) 的一个估计，$q<p<2q $ 时，这个估计为\(\sqrt{\frac{(a+b)^2 N}{ab}}\) ，
于是有exp：
1 | from Crypto.Util.number import * |