赛中秒了badrlwe，但是一直怼不出guess，赛后复盘一下，发现了以前搞AGCD和HNP的一点小问题，所以顺便记录一下

can_you_guess_me·

这题比赛时算漏了数据没搞出来，赛后用@Van1sh给的他学弟的构造复盘了一下，发现以前做AGCD和HNP的时候都有点小漏洞，下面细说

题目：can_you_guess_me.zip

题目分析·

这题也不长，是一个带模的AGCD，有n=5n=5组的

ai≡mti−ei(modq)a_i \equiv m t_i - e_i \pmod q

知道aia_i，求mm

和传统的AGCD一样，先把mm消去，照两个式子分别乘上对方的tt

aitj≡mtitj−eitj(modq)ajti≡mtitj−ejti(modq)a_i t_j \equiv m t_i t_j - e_i t_j \pmod q \\ a_j t_i \equiv m t_i t_j - e_j t_i \pmod q \\

两式相减就可以消去相同的mtitjm t_i t_j，得到

aitj−ajti≡ejti−eitj(modq)a_i t_j - a_j t_i \equiv e_j t_i - e_i t_j \pmod q

最后展开模数，再令xij=ejti−eitjx_{ij} = e_j t_i - e_i t_j，就可以得到：

aitj−ajti−kij=xija_i t_j - a_j t_i - k_{ij} = x_{ij}

延续了以前的习惯，为了方便格基构造，在比赛中我令了j=0j=0，然后用4组式子去构造格基

B=[Ea1⋯a4−a0⋱−a0−qE⋱⋱−qE]B = \begin{bmatrix} \begin{array}{llll|lll} E & a_1 & \cdots & a_4 \\ & -a_0 & \\ & & \ddots \\ & & & -a_0 \\ \hline & -q & & & E \\ & & \ddots & & & \ddots\\ & & & -q & & & E \end{array} \end{bmatrix}

发现被卡界了，就没搞出来

复盘1·

实际上这是个坏的习惯，因为以上式子中实际可以提取出4+3+2+1=104+3+2+1=10组的式子，如果把10组全用上的话会发现界还是挺松的，不过就是构造的过程有点复杂

下面用n=3n=3做个栗子，n=5n=5或者更大的情况照猫画虎一下就好了

求向量t·

为了方便计算行列式，我首先构造了第一种格基

B3=[Ea1a2−q−q−a0Ea2−q−a0−a1E]B_3 = \begin{bmatrix} \begin{array}{lll|ll|l} E & a_1 & a_2 & \\ & -q & & \\ & & -q & \\ \hline & -a_0 & & E & a_2 \\ & & & & -q \\ \hline & & -a_0 & & -a_1 & E \\ \end{array} \end{bmatrix}

由这个格基可得

vB3=(t0,k01,k02∣t1,k12∣t2)⋅B=(Et0,x01,x02∣Et1,x12∣Et2)=w\begin{aligned} v B_3 &= (t_0, k_{01}, k_{02} | t_1, k_{12} | t_2) \cdot B \\ &= (E t_0, x_{01}, x_{02} | E t_1, x_{12} | E t_2) \\ &= w \end{aligned}

下面来算一下界，首先是B3B_3的行列式，B3B_3是一个块的三角矩阵，所以其行列式就是这三个块的行列式之积

再来分析对角的3个块，都是形如

Bi=[Eai+1⋯an−1−q⋱−q](n−i)×(n−i)B_i = \begin{bmatrix} E & a_{i+1} & \cdots & a_{n-1} \\ & -q & \\ & & \ddots & \\ & & & -q \end{bmatrix}_{(n-i) \times (n-i)}

也是三角矩阵，所以

∣det(Bi)∣=Eqn−i−1|det(B_i)| = E q^{n-i-1}

然后BnB_n的行列式就是

∣det(Bn)∣=∏i=0n−1∣det(Bi)∣=nE⋅q∑i=0n−1i|det(B_n)| = \prod_{i=0}^{n-1}|det(B_i)| = nE \cdot q^{\sum_{i=0}^{n-1}i}

把n=5n=5、E=232E=2^{32}和q≈2128q \approx 2^{128}代入的话就是

∣det(B5)∣≈21440|det(B_5)| \approx 2^{1440}

所以代回题目中就可得

σ≈296>280≈∥w∥\sigma \approx 2^{96} > 2^{80} \approx \|w\|

于是可通过LLL解出vv中的tt

求向量e·

接着为了恢复mm还需要知道ee，因为这里的AGCD带模，所以不能像不带模的AGCD那样直接通过除法消去误差，这里应该有很多的解法，我选择再来一次LLL规约来解

由以上计算中可得（这里不会被卡界，可以直接令i=0i=0）

a0tj−ajt0−k0j=ejt0−e0tja_0 t_j - a_j t_0 - k_{0j} = e_j t_0 - e_0 t_j

等号左边都是已知量，所以可以令Ai=a0tj−ajt0−k0jA_i = a_0 t_j - a_j t_0 - k_{0j}，化简得

tje0−t0ej+Ai=0t_j e_0 - t_0 e_j + A_i = 0

根据这个式子构造格基

B=[1t1t2t3t4−t0−t0−t0−t0A1A2A3A4E]B = \begin{bmatrix} 1 & t_1 & t_2 & t_3 & t_4 & \\ & -t_0 & & & & \\ & & -t_0 & & & \\ & & & -t_0 & & \\ & & & & -t_0 & \\ & A_1 & A_2 & A_3 & A_4 & E \end{bmatrix}

可得

vB=(e0,⋯ ,e4,1)⋅B=(e0,0,0,0,0,E)vB = (e_0, \cdots, e_4, 1) \cdot B = (e_0, 0, 0, 0, 0, E)

稍微计算一下，σ>237>232≈∥w∥\sigma > 2^{37} > 2^{32} \approx \|w\|，所以LLL规约可解ee

最后计算flag：m≡(ai+ei)ti−1(modq)m \equiv (a_i + e_i) t_i^{-1} \pmod q

PS：如果TT和EE的值再接近一点估计这一步也会被卡吧

参考Exp·

参考代码：

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
#!/usr/bin/env sage
# Ver. easy to calculate det.
# det(B) \approx c*n + sum(range(n))

q = 313199526393254794805899275326380083313
a = [258948702106389340127909287396807150259, 130878573261697415793888397911168583971, 287085364108707601156242002650192970665, 172240654236516299340495055728541554805, 206056586779420225992168537876290239524]
n = 5
T = 2**48
E = 2**32

def matrix_overview(BB):
  for ii in range(BB.dimensions()[0]):
    a = ('%02d ' % ii)
    for jj in range(BB.dimensions()[1]):
      if BB[ii, jj] == 0:
        a += ' '
      else:
        a += 'X'
      if BB.dimensions()[0] < 60:
        a += ' '
    print(a)
  print()

Bs = []
for i in range(n):
  Bi = matrix(ZZ, n-i)
  Bi[0, 0] = E
  for j in range(1, n-i):
    Bi[0, j] = a[i+j]
    Bi[j, j] = -q
  Bs += [Bi]
  #matrix_overview(Bi)

B = block_diagonal_matrix(Bs)
#matrix_overview(B)

r0 = 0
c = 0
for i in range(n)[::-1]:
  r0 += i+1
  c += 1
  r = r0
  for j in range(1, i+1)[::-1]:
    B[r, c] = -a[n-1-i]
    r += j
    c += 1
matrix_overview(B)

L = B.BKZ()
w = L[0]
v = w * B^(-1)
print(v)

t = []
p = 0
for i in range(1, n+1)[::-1]:
  t += [abs(v[p])]
  p += i
print(t)

sign = t[0] / v[0]
k0 = [0] + [sign * x for x in v[1:n]]
print()

# get e from t and k
B = matrix(ZZ, n+1)
for i in range(1, n):
  B[0, i] = t[i]
  B[i, i] = -t[0]
  B[-1, i] = a[i]*t[0] - a[0]*t[i] - k0[i]*q
B[0, 0] = 1
B[-1, -1] = E
L = B.LLL()
w = L[0]
v = w * B^(-1)
assert w[1] == 0
print(v)

e = [abs(x) for x in v[:n]]
print(e)

m0 = (a[0] + e[0]) * Integer(t[0]).inverse_mod(q) % q
m1 = (a[1] + e[1]) * Integer(t[1]).inverse_mod(q) % q
assert m0 == m1

flag = m0
flag = "L3HSEC{" + hex(flag)[2:] + "}"
print(flag)

'''
(-70461467654746, -22849328340601, 83526243708890, 107223364615664, 73677848257181, -7976473815457, 67548140656997, 69391443545774, 55420653404403, -179142956465832, 63316184541348, 15218068970587, -176554799971356, -36315145326698, -145182873667321)
[70461467654746, 7976473815457, 179142956465832, 176554799971356, 145182873667321]

(-1207385170, -2227664800, -194948058, -2380502097, -893798212, 1)
[1207385170, 2227664800, 194948058, 2380502097, 893798212]
L3HSEC{ad4adc3d4b2001d0ddfa81e313cff80}
'''

复盘2·

可以看到上面的代码非常复杂，实际上上面那种格基构造只是为了方便计算行列式，并不方便写代码

于是可以进行一波优化，首先需要知道一个事实：如果对矩阵进行行变换或列变换，其实并不会改变行列式的绝对值，只会改变正负符号

所以可以对以上格基通过行变换得到以下新格基（同样以n=3n=3为栗子，照猫画虎即可）

B3=[Ea1a2−a0Ea2−a0−a1E−q−q−q]B_3 = \begin{bmatrix} \begin{array}{lll|ll|l} E & a_1 & a_2 & \\ & -a_0 & & E & a_2 & \\ & & -a_0 & & -a_1 & E \\ \hline & -q & \\ & & -q \\ \hline & & & & -q \\ \end{array} \end{bmatrix}

由这个格基可得（n=3n=3为例）

vB3=(t0,t1,t2∣k01,k02∣k12)⋅B=(Et0,x01,x02∣Et1,x12∣Et2)=w\begin{aligned} v B_3 &= (t_0, t_1, t_2 | k_{01}, k_{02} | k_{12}) \cdot B \\ &= (E t_0, x_{01}, x_{02} | E t_1, x_{12} | E t_2) \\ &= w \end{aligned}

于是LLL对B5B_5规约可解得tt

这里规约后直接取vv的前nn项作为tt即可，不用像前面那样还要写代码去挑每个tit_i，另外在用代码怼格基的时候也不用这么复杂

参考代码：

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
#!/usr/bin/env sage

q = 313199526393254794805899275326380083313
a = [258948702106389340127909287396807150259, 130878573261697415793888397911168583971, 287085364108707601156242002650192970665, 172240654236516299340495055728541554805, 206056586779420225992168537876290239524]
n = 5
T = 2**48
E = 2**32

def matrix_overview(BB):
  for ii in range(BB.dimensions()[0]):
    a = ('%02d ' % ii)
    for jj in range(BB.dimensions()[1]):
      if BB[ii, jj] == 0:
        a += ' '
      else:
        a += 'X'
      if BB.dimensions()[0] < 60:
        a += ' '
    print(a)
  print()

Bs = []
size = sum(range(n+1))
for i in range(n):
  Bi = matrix(ZZ, size, n-i)
  Bi[i, 0] = E
  for j in range(1, n-i):
    Bi[i, j] = a[i+j]
    Bi[i+j, j] = -a[i]
    Bi[sum(range(n-i, n+1)) + (j-1), j] = -q
  Bs += [Bi]
B = block_matrix([Bs])
matrix_overview(B)

L = B.BKZ()
w = L[0]
v = w * B^(-1)
print(v)

t = [abs(x) for x in v[:n]]
print(t)

sign = t[0] / v[0]
k0 = [0] + [sign * x for x in v[n: 2*n-1]]
print()

# get e from t and k
B = matrix(ZZ, n+1)
for i in range(1, n):
  B[0, i] = t[i]
  B[i, i] = -t[0]
  B[-1, i] = a[i]*t[0] - a[0]*t[i] - k0[i]*q
B[0, 0] = 1
B[-1, -1] = E
L = B.LLL()
w = L[0]
v = w * B^(-1)
assert w[1] == 0
print(v)

e = [abs(x) for x in v[:n]]
print(e)

m0 = (a[0] + e[0]) * Integer(t[0]).inverse_mod(q) % q
m1 = (a[1] + e[1]) * Integer(t[1]).inverse_mod(q) % q
assert m0 == m1

flag = m0
flag = "L3HSEC{" + hex(flag)[2:] + "}"
print(flag)

'''
(70461467654746, 7976473815457, 179142956465832, 176554799971356, 145182873667321, 22849328340601, -83526243708890, -107223364615664, -73677848257181, -67548140656997, -69391443545774, -55420653404403, -63316184541348, -15218068970587, 36315145326698)
[70461467654746, 7976473815457, 179142956465832, 176554799971356, 145182873667321]

(-1207385170, -2227664800, -194948058, -2380502097, -893798212, 1)
[1207385170, 2227664800, 194948058, 2380502097, 893798212]
L3HSEC{ad4adc3d4b2001d0ddfa81e313cff80}
'''

badrlwe·

附送一道badrlwe，题目：badrlwe.zip

题目不长，是一个环R=Zq[x]x1024−1R = \frac{\mathbb{Z}_q[x]}{x^{1024}-1}上的RLWE，有

b=as+e (in R)b = as + e \text{ (in $R$)}

知道aa和bb，求ss

按照历史经验，如果要用格去做的话的维度大概是2n+1=20492n+1 = 2049，不可能用LLL去解，于是继续分析：aa是RR上的随机数没啥漏洞，ee是高斯分布采样也没啥漏洞，bb就是正常的RLWE计算，也没啥问题

最后就剩下ss有问题，分析代码前面的两个assert可以知道，ss只有64个低次项的系数不为0，其余高次项的系数都为0，于是就可以利用这个性质去做降维打击

另外，ss的每个系数都是0~255的字节，符合LLL的短向量要求

复习一下RLWE的基本解法，首先需要把环RR上式子都转成向量，另外环RR上的乘法是模多项式卷积乘法，这种卷积乘法在转换成向量后都可以变成向量乘矩阵的形式，于是以上式子用向量表示就是

b≡sA+e(modq)b \equiv sA + e \pmod q

其中环RR对应的卷积矩阵AA为

A=(a0a1a2⋯aN−1aN−1a0a1⋯aN−2aN−2aN−1a0⋯aN−3⋮⋮⋮⋱⋮a1a2a3⋯a0)A = \begin{pmatrix} a_0 & a_1 & a_2 & \cdots & a_{N-1} \\ a_{N-1} & a_0 & a_1 & \cdots & a_{N-2} \\ a_{N-2} & a_{N-1} & a_0 & \cdots & a_{N-3} \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ a_1 & a_2 & a_3 & \cdots & a_0 \\ \end{pmatrix}

利用这个式子就可以构造格基，但是在这题中需要先进行降维，刚才说了ss的高次项系数为0，所以不妨把ss向量切分为非零与零的两部分，其他向量和矩阵也对应切分，得

(b0∣b1)≡(s0∣0)[A0A1A2A3]+(e0∣e1)(modq)(b_0 | b_1) \equiv (s_0 | 0) \begin{bmatrix} A_0 & A_1 \\ A_2 & A_3 \end{bmatrix} + (e_0|e_1) \pmod q

展开该式子可以发现，0会消除A2A_2和A3A_3，所以可得

(b0∣b1)≡s0[A0A1]+(e0∣e1)(modq)(b_0 | b_1) \equiv s_0 \begin{bmatrix} A_0 & A_1 \end{bmatrix} + (e_0|e_1) \pmod q

然后构造格基式其实只需要矩阵中的64列，即A1A_1是多余的部分，可以忽略，只保留A0A_0用作格基构造（其中A0A_0是64×64的矩阵），可得

b0≡s0A0+e0(modq)b_0 \equiv s_0A_0 + e_0 \pmod q

可以发现这个式子和RLWE的式子基本一样，于是按老套路走，先展开模数

b0−s0⋅A0+u⋅qI=e0b_0 - s_0 \cdot A_0 + u \cdot qI = e_0

然后构造格基

B=[A0qIIb0128]129×129B = \begin{bmatrix} \begin{array}{lll} A_0 & & \\ qI & I & \\ b_0 & & 128 \\ \end{array} \end{bmatrix}_{129 \times 129}

得

vB=(−s0∣u∣1)⋅B=(e0∣u∣128)=wv B = (-s_0 | u | 1) \cdot B = (e_0 | u | 128) = w

于是LLL解之可得s0s_0，就是flag

参考代码：

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#!/usr/bin/env sage

q = 1219077173
a = ... ...
b = ... ...
from Crypto.Util.number import *
from random import *
import random
import numpy as np

R.<x> = PolynomialRing(Zmod(q), 'x')
n = 1024
f = x^n - 1
a = R(a)
b = R(b)
va = vector(ZZ, list(a) + [0]*(n-len(list(a))))  # padding
vb = vector(ZZ, list(b) + [0]*(n-len(list(b))))

nn = 64
A = matrix(ZZ, nn, nn)
for i in range(nn):
  for j in range(nn):
    A[j, i] = va[(i - j) % n]

M = matrix(ZZ, nn*2+1, nn*2+1)
for i in range(nn):
  for j in range(nn):
    M[i, j] = A[i, j]
  M[i+nn, i] = q
  M[i+nn, i+nn] = 1
  M[-1, i] = b[i]
M[-1, -1] = 1
L = M.BKZ()
w = L[0]
v = w * M^(-1)
print(v)

sk = [abs(x) for x in v[:64]]
sk = ''.join([chr(x) for x in sk])
print(sk)

'''
(89, 48, 117, 95, 82, 64, 52, 49, 49, 89, 95, 75, 110, 48, 119, 95, 67, 121, 99, 108, 79, 116, 111, 109, 49, 99, 95, 80, 111, 108, 121, 33, 65, 75, 64, 67, 111, 33, 60, 74, 62, 94, 53, 35, 68, 81, 125, 111, 68, 111, 61, 111, 40, 106, 55, 36, 37, 60, 49, 84, 56, 104, 49, 114, -2742, -2582, -2741, -2643, -2809, -2780, -2769, -2648, -2624, -2605, -2738, -2621, -2861, -2631, -2666, -2633, -2764, -2715, -2828, -2759, -2775, -2755, -2561, -2780, -2664, -2545, -2557, -2682, -2661, -2760, -2687, -2750, -2631, -2694, -2647, -2658, -2771, -2609, -2682, -2737, -2778, -2623, -2715, -2592, -2699, -2583, -2543, -2686, -2669, -2755, -2765, -2795, -2774, -2617, -2734, -2639, -2571, -2629, -2435, -2556, -2443, -2625, -2530, -2720, -1)
Y0u_R@411Y_Kn0w_CyclOtom1c_Poly!AK@Co!<J>^5#DQ}oDo=o(j7$%<1T8h1r
'''

总结·

菜：（