D3CTF的D3BDD，的一堆非预期解. 有幸一血（★,°:.☆(￣▽￣)/$:.°★ 。

首先附上题目附件：d3bdd.zip

题目名字的BDD指的应该是Bounded Distance Decoding问题，是LWE规约到的一个问题，然后题目其实是一个Search-RLWE问题，即给定多项式（当然看成向量也行）：a(x)a(x)和b(x)=a(x)∗s(x)+e(x)∈Rqb(x) = a(x) * s(x) + e(x) \in R_q，需要求s(x)s(x)，其中Rq=Zq[x]xn−1R_q = \frac{\mathbb{Z}_q[x]}{x^{n}-1}，n=512n=512，q=232−5q = 2^{32} - 5，e(x)e(x)的系数落在[−4,4][-4, 4]中。

（上面几个图参考了：Balbás D. The Hardness of LWE and Ring-LWE: A Survey[J]. Cryptology ePrint Archive, 2021.）

后来题目给的提示是Dual Attack，但让我一堆非预期弄出来了，有幸一血（

（顺便恭喜烧卖战队首战Rank2）

基本RLWE解法·

先说一下RLWE问题的一个基本解法，其实和之前说的NTRU攻击有点类似，对于b(x)=a(x)∗s(x)+e(x)∈Rqb(x) = a(x) * s(x) + e(x) \in R_q，可以先消去模数，即存在u(x)∈Rqu(x) \in R_q使得

b(x)−a(x)∗s(x)+q∗u(x)=e(x)b(x) - a(x) * s(x) + q * u(x) = e(x)

然后之前在讲NTRU的多项式卷积时也说过，多项式卷积乘法可以看成是一个向量乘上一个矩阵，那么假设对于a(x)a(x)这个矩阵是AA，再把ss看成一向量，即

a(x)∗s(x):=sAa(x) * s(x) := s A

然后把上面式子用向量和矩阵表达即

b−s∗A+u∗qI=eb - s * A + u * qI = e

于是可构造格基（其中β\beta是一起平衡作用的值，规模与ee的系数一样即可）

MRLWE=[AqIIbβ](2n+1)∗(2n+1)M^{\rm{RLWE}} = \begin{bmatrix} \begin{array}{lll} A & & \\ qI & I & \\ b & & \beta \\ \end{array} \end{bmatrix}_{(2n+1) * (2n+1)}

使得以下关系成立：

vMRLWE=(−s,u,1)∗MRLWE=(e,u,β)=wv M^{\rm{RLWE}} = (-s, u, 1) * M^{\rm{RLWE}} = (e, u, \beta) = w

大致推算以下，uu的系数和β\beta都是ee系数的规模，所以向量ww非常大概率是个短向量，用LLL对MRLWEM^{\rm{RLWE}}解一下apprSVP可得ww，然后求v=wM−1v = w M^{-1}得ss。

附个测试代码：

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
# Sage
import util
from hashlib import *
import os
from Crypto.Util.number import *

# Gen
flag = b'flag'
util.n = 32

seed = sha256(b"welcome to D3CTF").digest() + sha256(b"have a nice day").digest()
A = util.sample_poly(seed , 0 , 2**32 - 5)
A = util.sample_poly(seed , 0 , 2**32 - 5)
e = util.sample_poly(os.urandom(64) , -4 , 4)
s = util.encode_m(flag)
b = A*s + e
b = b.f

# Hack
n = len(b)
q = 2^32-5
beta = 4
M = matrix(ZZ, 2*n+1)
for i in range(n):
  for j in range(n):
    M[j  , i]   = A.f[(i - j) % n]
  M[n+i, i]   = q
  M[n+i, n+i] = 1
  M[-1, i] = (b[i] + 4) % q
M[-1, -1] = beta

L = M.LLL()
L0 = L[0]
su = L0 * M^(-1)
s = int(''.join([str(-su[i]) for i in range(n)]), 2)
import libnum
flag = libnum.n2s(int(s))
print(flag)

但很明显这个方法行不通，因为MRLWEM^{\rm{RLWE}}得维度是2n+12n+1，代入n=512n=512即1025维，LLL可能需要解个几百年。

分解模数·

所以一种方法是把维度降下来。观察模数2n−12^n-1，由于n=512n=512，所以可以分解为

x512−1=(x256+1)∗(x256−1)\begin{aligned} x^{512}-1 = (x^{256} + 1)*(x^{256} - 1) \end{aligned}

于是可构造子环R1=Zq[x]x256+1R_1 = \frac{\mathbb{Z}_q[x]}{x^{256} + 1}和R2=Zq[x]x256−1R_2 = \frac{\mathbb{Z}_q[x]}{x^{256} - 1}，然后再使用格规约把维度降到256∗2+1=513256*2+1 = 513。

观察一下两个子环的性质，在R1R_1中，x256≡−1(modq)x^{256} \equiv -1 \pmod q，即如果把ss砍成两半，s∈R1s \in R_1各项的系数就是ss的低次数一半减去高次数的一半（系数对应相减）；类似地，在R2R_2中，x256≡1(modq)x^{256} \equiv 1 \pmod q，即s∈R2s \in R_2各项的系数是ss的低次数一半加上高次数的一半，形式化：

s≡(s1∥s2)≡(s0,...,s255∥s256,...s511)∈Rqs≡s1−s2≡(s0−s256,s1−s257,...,s255−s511)∈R1s≡s1+s2≡(s0+s256,s1+s257,...,s255+s511)∈R2\begin{aligned} s &\equiv (s_1 \| s_2) \equiv (s_0, ..., s_{255} \| s_{256}, ... s_{511}) &&\in R_q \\ s &\equiv s_1 - s_2 \equiv (s_0 - s_{256}, s_1 - s_{257}, ..., s_{255} - s_{511}) &&\in R_1 \\ s &\equiv s_1 + s_2 \equiv (s_0 + s_{256}, s_1 + s_{257}, ..., s_{255} + s_{511}) &&\in R_2 \end{aligned}

所以假设LLL规约可以成功计算，则最后可通过计算

s1=(s∈R1)+(s∈R2)2=(s1−s2)+(s1+s2)2s2=(s∈R2)−s1=(s1+s2)−s1\begin{aligned} s_1 &= \frac{(s \in R_1) + (s \in R_2)}{2} = \frac{(s_1 - s_2) + (s_1 + s_2)}{2} \\ s_2 &= (s \in R_2) - s_1 = (s_1 + s_2) - s_1 \end{aligned}

解出ss。

另外在构造格基时需要注意，R2R_2的卷积矩阵可以参考上面RqR_q中的构造，但R1R_1的结构有点不一样，所以需要另外构造，构造方法可以参考多项式卷积中的公式：

a(x)∗b(x)≡∑k=0N−1(∑i=0kaibk−i−∑i=k+1N−1aibk+N−i)⋅xk(in R1)a(x) * b(x) \equiv \sum^{N-1}_{k=0} (\sum^{k}_{i=0} a_{i} b_{k-i} - \sum^{N-1}_{i=k+1} a_{i} b_{k+N-i}) · x^k \text{(in $R_1$)}

构造出矩阵（即右上是正，左下是负）：

A:=[a01⋯an2−2an2−1−an2−1a0⋯an2−3an2−2⋮⋮⋱⋮⋮−a2−a3⋯a0a1−a1−a2⋯−an2−1a0]A := \begin{bmatrix} a_0 & 1 & \cdots & a_{\frac{n}{2}-2} & a_{\frac{n}{2}-1} \\ -a_{\frac{n}{2}-1} & a_{0} & \cdots & a_{\frac{n}{2}-3} & a_{\frac{n}{2}-2} \\ \vdots & \vdots & \ddots & \vdots & \vdots \\ -a_{2} & -a_{3} & \cdots & a_{0} & a_{1} \\ -a_{1} & -a_{2} & \cdots & -a_{\frac{n}{2}-1} & a_{0} \\ \end{bmatrix}

最后测试代码：

R1R_1的：

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
# Sage
n = len(b)
q = 2^32 - 5
print(n)

R_  = PolynomialRing(GF(q),'x')
x = R_.gen()
R  = R_.quotient(x^n - 1, 'y')

#x^512-1 = (x^256 + 1)*(x^128 + 1)*(x^64 + 1)*(x^32 + 1)*(x^16 + 1)*(x^8 + 1)*(x^4 + 1)*(x^2 + 1)*(x + 1)*(x - 1)
#for ni in [1, 2, 4, 8, 16, 32, 64, 128, 256]:
for ni in [256]:
  R2  = R_.quotient(x^ni + 1, 'y2')
  AA = R(A.f)
  bb = R(b)
  AAA = R2(AA)
  bbb = R2(bb)

  beta = 4
  M = matrix(ZZ, 2*ni+1)
  for i in range(ni):
    for j in range(ni):
      if j <= i:
        M[j, i]   = ZZ(AAA[(i - j) % ni])
      else:
        M[j, i]   = -ZZ(AAA[(i - j + n) % ni])
    M[ni+i, i]    = q
    M[ni+i, ni+i] = 1
    M[-1, i] = (ZZ(bbb[i])) % q
  M[-1, -1] = beta
  L = M.LLL()
  print(ni)
  print(L[0])
  s = (L[0] * M^(-1))[: ni]
  print(s)
  print()
  
  ''' s 忘记取负了
1
(-8, -22, 4)
(63)

2
(43, 11, -17, -29, 4)
(57, -18)

4
(-18, 28, -15, -3, -44, 15, 15, 8, 4)
(17, -20, -28, 10)

8
(26, 1, -4, -16, 0, 17, -1, -9, -1, -7, 0, -1, 0, 0, -2, 4, 4)
(0, 3, -3, -1, 1, -1, 1, -5)

16
(-12, -4, 3, -1, 2, -10, 8, -6, -6, 9, -19, 13, -12, -19, 9, -21, -2, -9, -2, -5, 3, -5, 2, 1, 0, -4, 0, -1, 0, 2, 8, 6, 4)
(0, 1, -1, -1, -2, 1, -5, 2, 0, 2, 0, -2, 1, -4, 0, -1)

32
(-13, 13, 8, -5, 12, 5, 5, -7, 1, -5, -9, 20, 1, -2, -10, 4, -1, 7, 9, 12, -6, 1, 13, -3, 9, -4, -10, 1, 13, -5, -15, 3, 5, 6, 6, 6, 17, 7, 8, 10, 7, 11, 6, 8, 8, 8, 6, -6, 8, 6, 8, -1, -3, 3, -1, 3, 0, 5, 8, -6, 2, -5, 4, -2, 4)
(0, -4, 0, -2, -1, 0, -2, 4, 0, -3, 0, 2, 2, -4, 2, 3, 0, 1, -3, 1, 3, 1, 1, -2, 0, -1, 0, 2, 1, 2, -2, 2)

64
(-7, -1, -3, -2, 8, -2, -5, 7, -9, -7, 4, -4, -7, -8, 0, -3, -5, 14, 6, 7, 0, -9, 1, 8, 6, -11, -5, -2, 1, 6, 5, -1, -4, 12, -9, 7, 0, 3, 4, -10, 6, 2, 9, 14, -2, -2, -4, 9, 2, -9, 5, -17, 2, -6, -16, -3, -3, -3, -1, -5, -8, 5, -10, -18, -8, -4, -3, -7, -7, -4, -11, -10, -10, -10, -10, -8, -7, -7, -12, -15, -13, -12, -12, -11, -11, -10, -9, -6, -14, -11, -12, -10, -11, -12, -7, -8, -8, -4, -12, -8, -5, -6, -2, 3, -1, 0, 4, 2, 2, -3, -1, 5, 2, 2, 1, 7, 3, 3, 7, 4, 3, 5, 6, 2, 4, 2, 5, 8, 4)
(0, 0, -1, 1, 1, -2, 3, 1, 0, 0, 0, -1, -1, 1, 0, 1, 0, 0, 0, -1, 0, 0, -1, 1, 0, 0, 0, 0, 0, 0, -2, -1, 0, -2, 1, -1, 0, -2, -1, -1, 0, -1, 0, -1, 1, 1, -2, -2, 0, -1, -1, -2, 1, -1, 0, 1, 0, 1, 0, 0, 1, 0, -2, -1)

128
(8, 0, -6, 3, 1, -8, 8, 7, 6, -2, 3, 0, -5, 0, 3, 6, 1, -3, -6, -8, 2, -6, 5, 6, -7, 0, 1, 3, -3, -1, 2, -2, 6, -8, -7, -6, 3, -2, -2, -8, -3, 1, 10, -7, 5, -8, -4, 4, -3, -4, 7, -2, -4, 11, 0, -10, -6, 2, 4, -9, 10, -7, 0, -6, 9, -3, 7, -7, 1, 2, -9, 8, 3, -1, -7, 0, 4, -4, -5, 3, 0, -5, -2, 1, 2, 3, 4, -4, -11, -1, 4, -1, 2, -1, -3, 5, 8, -6, -4, -1, -3, 1, -8, 0, -1, 7, 1, 1, -1, 4, 6, 3, 9, -7, 2, 1, -4, 9, 8, -7, 3, 3, -5, -2, 0, -14, 4, 0, 6, 5, 8, 8, 3, 10, 1, -3, 2, 4, 4, 1, 7, 8, 10, 5, 7, 11, 9, 4, 8, 13, 15, 12, 12, 10, 5, 10, 7, 9, 9, 3, 7, 5, 5, 8, 5, 5, 0, 6, 3, 3, 5, 0, 2, 5, 6, 5, -1, 9, 5, 6, 9, 10, 11, 4, 3, 6, 4, 3, 0, -2, -1, -2, -1, 4, 4, 0, 1, 2, 5, 3, 5, 8, 4, 3, 2, 1, 4, 4, 6, -1, 6, 7, 6, 5, 7, 5, 3, -3, 1, 2, -5, 0, -1, -5, -4, 0, 1, 2, 0, 0, 3, 6, -2, 6, 0, 4, -2, 0, 8, -2, -1, -1, 3, 5, 1, 6, 2, -2, -1, -1, -1, -9, 0, -10, -6, 3, 4)
(0, 0, 0, 2, -1, 1, -1, -1, 0, 0, -1, 0, -1, -1, -1, 1, 0, -1, 0, 0, 0, -2, 1, 1, 0, 0, 1, -1, 1, -1, 1, 2, 0, 1, -1, 0, 1, 1, 0, 0, 0, -1, -1, 1, 1, 1, -1, 0, 0, 0, -1, -1, 1, -1, 1, 2, 0, 1, -1, 0, 1, 0, 0, 1, 0, 0, -1, 1, -2, -1, 0, 0, 0, 0, 1, 1, 0, 0, -1, 0, 0, 1, 0, -1, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, -1, 0, -1, 0, 1, -1, -1, -1, 1, 0, 0, 1, 0, 0, -2, -1, 2, 0, -1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 2, 0, 0, 2)
'''

PS：上面规约后忘记对结果取负了，准确来说是若L[0][-1]这一项与β\beta的符号不一样就要取负，注意一下就好。

R2R_2的：

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
# Sage
n = len(b)
q = 2^32 - 5
print(n)

R_  = PolynomialRing(GF(q),'x')
x = R_.gen()
R  = R_.quotient(x^n - 1, 'y')

#x^512-1 = (x^256 + 1)*(x^128 + 1)*(x^64 + 1)*(x^32 + 1)*(x^16 + 1)*(x^8 + 1)*(x^4 + 1)*(x^2 + 1)*(x + 1)*(x - 1)
#for ni in [1, 2, 4, 8, 16, 32, 64, 128, 256]:
for ni in [256]:
  R2  = R_.quotient(x^ni - 1, 'y2')
  AA = R(A.f)
  bb = R(b)
  AAA = R2(AA)
  bbb = R2(bb)

  beta = 16
  M = matrix(ZZ, 2*ni+1)
  for i in range(ni):
    for j in range(ni):
      M[j  , i]   = ZZ(AAA[(i - j) % ni])
    M[ni+i, i]   = q
    M[ni+i, ni+i] = 1
    M[-1, i] = (ZZ(bbb[i])) % q
  M[-1, -1] = beta

  L = M.LLL()
  print(ni)
  print(L[0])
  s = (-L[0] * M^(-1))[:ni]
  print(s)
  print(sum(s))
  print()


'''
1
(-182, 92, 16)
(245)
245

2
(-95, -87, 158, 179, 16)
(91, 154)
245

4
(-26, -38, -69, -49, 125, 180, 123, 152, 16)
(17, 86, 74, 68)
245

8
(-22, -5, -42, -26, -4, -33, -27, -23, 129, 134, 105, 141, 137, 131, 121, 171, 16)
(0, 53, 51, 29, 17, 33, 23, 39)
245

16
(2, -2, -23, -21, -2, -8, -14, -16, -24, -3, -19, -5, -2, -25, -13, -7, 136, 121, 123, 125, 125, 139, 136, 120, 134, 119, 126, 123, 127, 135, 136, 119, 16)
(0, 25, 27, 15, 8, 17, 11, 22, 0, 28, 24, 14, 9, 16, 12, 17)
245

32
(-5, -3, -10, -11, 0, -9, -3, -11, -15, 3, -19, 4, -7, -22, -2, -14, 7, 1, -13, -10, -2, 1, -11, -5, -9, -6, 0, -9, 5, -3, -11, 7, 108, 110, 120, 106, 102, 104, 113, 112, 111, 109, 120, 107, 104, 103, 113, 111, 113, 114, 121, 108, 99, 105, 109, 110, 110, 110, 120, 108, 103, 107, 108, 109, 16)
(0, 12, 14, 8, 5, 8, 8, 10, 0, 13, 12, 8, 4, 10, 6, 9, 0, 13, 13, 7, 3, 9, 3, 12, 0, 15, 12, 6, 5, 6, 6, 8)
245

64
(-9, 5, -1, -8, 6, -2, 1, -9, -7, -1, -14, 12, -3, -12, -6, -5, 3, 4, -2, 1, -4, 1, 1, -4, 0, -5, -5, -4, 9, -4, -13, 5, 4, -8, -9, -3, -6, -7, -4, -2, -8, 4, -5, -8, -4, -10, 4, -9, 4, -3, -11, -11, 2, 0, -12, -1, -9, -1, 5, -5, -4, 1, 2, 2, 115, 135, 126, 117, 123, 119, 130, 124, 117, 127, 130, 120, 122, 126, 123, 125, 115, 130, 127, 114, 129, 113, 129, 124, 117, 127, 125, 118, 123, 123, 130, 128, 114, 127, 130, 118, 127, 121, 125, 122, 117, 129, 125, 116, 128, 120, 127, 129, 114, 129, 130, 121, 124, 124, 130, 123, 115, 128, 131, 114, 129, 119, 127, 121, 16)
(0, 8, 7, 5, 3, 4, 5, 3, 0, 8, 6, 3, 1, 7, 2, 3, 0, 6, 8, 3, 0, 4, 1, 7, 0, 8, 6, 2, 2, 2, 4, 3, 0, 4, 7, 3, 2, 4, 3, 7, 0, 5, 6, 5, 3, 3, 4, 6, 0, 7, 5, 4, 3, 5, 2, 5, 0, 7, 6, 4, 3, 4, 2, 5)
245

128
(-8, 2, -2, -5, 7, -2, -2, -1, -8, -4, -5, 4, -5, -10, -3, -4, -1, 9, 2, 4, -2, -4, 1, 2, 3, -8, -5, -3, 5, 1, -4, 2, 0, 2, -9, 2, -3, -2, 0, -6, -1, 3, 2, 3, -3, -6, 0, 0, 3, -6, -3, -14, 2, -3, -14, -2, -6, -2, 2, -5, -6, 3, -4, -8, -1, 3, 1, -3, -1, 0, 3, -8, 1, 3, -9, 8, 2, -2, -3, -1, 4, -5, -4, -3, -2, 5, 0, -6, -3, 3, 0, -1, 4, -5, -9, 3, 4, -10, 0, -5, -3, -5, -4, 4, -7, 1, -7, -11, -1, -4, 4, -9, 1, 3, -8, 3, 0, 3, 2, 1, -3, 1, 3, 0, 2, -2, 6, 10, 125, 127, 134, 128, 129, 126, 122, 129, 125, 122, 135, 125, 129, 129, 124, 131, 122, 129, 133, 130, 125, 125, 130, 128, 126, 123, 132, 127, 127, 126, 127, 132, 127, 123, 137, 128, 127, 127, 126, 127, 126, 123, 136, 132, 134, 125, 129, 125, 128, 121, 134, 131, 130, 137, 124, 131, 129, 125, 136, 125, 132, 129, 122, 128, 127, 126, 132, 129, 133, 127, 129, 124, 127, 126, 135, 127, 130, 130, 130, 126, 122, 127, 134, 130, 128, 129, 130, 131, 127, 126, 137, 129, 126, 129, 132, 128, 125, 125, 134, 134, 128, 131, 129, 130, 126, 124, 137, 128, 133, 129, 131, 127, 128, 122, 131, 129, 127, 132, 122, 130, 129, 123, 136, 127, 133, 127, 124, 132, 16)
(0, 4, 4, 2, 1, 3, 1, 1, 0, 4, 3, 2, 1, 3, 1, 1, 0, 3, 4, 2, 0, 2, 1, 3, 0, 4, 3, 1, 1, 1, 3, 2, 0, 3, 3, 2, 1, 3, 2, 4, 0, 3, 3, 3, 1, 1, 3, 4, 0, 4, 3, 3, 1, 3, 1, 2, 0, 3, 3, 2, 1, 2, 2, 3, 0, 4, 3, 3, 2, 1, 4, 2, 0, 4, 3, 1, 0, 4, 1, 2, 0, 3, 4, 1, 0, 2, 0, 4, 0, 4, 3, 1, 1, 1, 1, 1, 0, 1, 4, 1, 1, 1, 1, 3, 0, 2, 3, 2, 2, 2, 1, 2, 0, 3, 2, 1, 2, 2, 1, 3, 0, 4, 3, 2, 2, 2, 0, 2)
245
'''

但很遗憾经测试（在比赛时间内）并没跑出来。

用和值消去已知量·

进一步分解模数，会得到

x512−1=(x256+1)∗(x128+1)∗(x128−1)\begin{aligned} x^{512}-1 = (x^{256} + 1)*(x^{128} + 1)*(x^{128} - 1) \end{aligned}

令Rq−=Zq[x]x128+1R^-_q = \frac{\mathbb{Z}_q[x]}{x^{128} + 1}、Rq+=Zq[x]x128−1R^+_q = \frac{\mathbb{Z}_q[x]}{x^{128} - 1}，则用上面方法可以解出s∈Rq−s \in R^-_q和s∈Rq+s \in R^+_q（在我渣机上测试，257257维度的LLL一小时内可以跑完），类似地，把ss切成s0∼s3s_0 \sim s_3四等分，有

s≡s0−s1+s2−s3≡(s0−s128+s256−s384,...,s127−s255+s383−s511)∈Rq−s≡s0+s1+s2+s3≡(s0+s128+s256+s384,...,s127+s255+s383+s511)∈Rq+\begin{aligned} s &\equiv s_0 - s_1 + s_2 - s_3 \equiv (s_0 - s_{128} + s_{256} - s_{384}, ..., s_{127} - s_{255} + s_{383} - s_{511}) &&\in R^-_q \\ s &\equiv s_0 + s_1 + s_2 + s_3 \equiv (s_0 + s_{128} + s_{256} + s_{384}, ..., s_{127} + s_{255} + s_{383} + s_{511}) &&\in R^+_q \\ \end{aligned}

同样类似地，可以算出偶数两部分之和与奇数两部分之和

seven=(s∈Rq−)+(s∈Rq+)2=s0+s2sodd=(s∈Rq+)−sq−=s1+s3\begin{aligned} s_{\text{even}} &= \frac{(s \in R^-_q) + (s \in R^+_q)}{2} = s_0 + s_2 \\ s_{\text{odd}} &= (s \in R^+_q) - s^-_q = s_1 + s_3 \end{aligned}

然后可以利用一些性质恢复部分比特（参考代码的run(sp_eve, sp_odd)函数）；

  1. flag头和尾已知为antd3ctf{}，共10Bytes
  2. 如果偶数段之和或奇数段之和中出现0，则s对应的两个位置都是0，如果出现2则都是1
  3. 如果s的前半部分已知，后半部分未知，则可通过和值减去已知值求得未知值，反之亦然

以上三步处理完后剩余142142位未知比特，并得到antd3ctf{-------t--------------inteRest1n-------t--------------}

参考代码：

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
98
99
100
101
102
103
104
105
# Sage
from hashlib import *
from Crypto.Util.number import *

flag_h9 = b'antd3ctf{' 
flag_l1 = b'}' 
flag_len = 64
flag_sha256 = '8ea9f4a9de94cda7a545ae8e7c7c96577c2e640b86efe1ed738ecbb5159ed327'

def encode_m(m):
  n = len(m) * 8
  m = bytes_to_long(m)
  flist = []
  for i in range(n):
    flist = [m&1] + flist
    m >>= 1
  return flist

n = 512
flag_bin = [-1 for i in range(n)]
fh9_bin = encode_m(flag_h9)
fl1_bin = encode_m(flag_l1)
for i in range(len(fh9_bin)):
  flag_bin[i] = fh9_bin[i]
for i in range(len(fl1_bin)):
  flag_bin[-i-1] = fl1_bin[-i-1]


sm128 = (0, 0, 0, 2, -1, 1, -1, -1, 0, 0, -1, 0, -1, -1, -1, 1, 0, -1, 0, 0, 0, -2, 1, 1, 0, 0, 1, -1, 1, -1, 1, 2, 0, 1, -1, 0, 1, 1, 0, 0, 0, -1, -1, 1, 1, 1, -1, 0, 0, 0, -1, -1, 1, -1, 1, 2, 0, 1, -1, 0, 1, 0, 0, 1, 0, 0, -1, 1, -2, -1, 0, 0, 0, 0, 1, 1, 0, 0, -1, 0, 0, 1, 0, -1, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, -1, 0, -1, 0, 1, -1, -1, -1, 1, 0, 0, 1, 0, 0, -2, -1, 2, 0, -1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 2, 0, 0, 2)
sm128 = [-x for x in sm128]   # mistake fixed
sp128 = (0, 4, 4, 2, 1, 3, 1, 1, 0, 4, 3, 2, 1, 3, 1, 1, 0, 3, 4, 2, 0, 2, 1, 3, 0, 4, 3, 1, 1, 1, 3, 2, 0, 3, 3, 2, 1, 3, 2, 4, 0, 3, 3, 3, 1, 1, 3, 4, 0, 4, 3, 3, 1, 3, 1, 2, 0, 3, 3, 2, 1, 2, 2, 3, 0, 4, 3, 3, 2, 1, 4, 2, 0, 4, 3, 1, 0, 4, 1, 2, 0, 3, 4, 1, 0, 2, 0, 4, 0, 4, 3, 1, 1, 1, 1, 1, 0, 1, 4, 1, 1, 1, 1, 3, 0, 2, 3, 2, 2, 2, 1, 2, 0, 3, 2, 1, 2, 2, 1, 3, 0, 4, 3, 2, 2, 2, 0, 2)

assert len(sm128) == len(sp128)
sp4_eve = [(sm128[i] + sp128[i]) // 2 for i in range(len(sm128))]
sp4_odd = [sp128[i] - sp4_eve[i] for i in range(len(sm128))]
for i in range(len(sm128)):
  assert sp4_eve[i] - sp4_odd[i] == sm128[i]
print(sp4_eve)
print(sp4_odd)

import string
def hint(fbi):
  hl = []
  for s in string.printable:
    sl = encode_m(bytes(s, encoding='utf8'))
    for i in range(8):
      if fbi[i] != -1 and fbi[i] != sl[i]:
        break
    else:
        hl += [s]
  return ''.join(hl)

def show(debug=False):
  flag = ''
  for i in range(n//8):
    fbi = flag_bin[i*8: (i+1)*8][::-1]
    if not -1 in fbi:
      flag += chr(sum([fbi[j] * 2^j for j in range(8)]))
    else:
      if debug:
        print(i, fbi, hint(fbi[::-1]))
      flag += '-'
  print(flag)
  print(flag[32:])
  print(flag_bin.count(-1))
  return flag

def run(sp_eve, sp_odd):
  assert len(sp_eve) == len(sp_odd)
  ni = len(sp_eve)
  
  for i in range(ni):
    if sp_eve[i] == 0:
      for j in range(0, n, 2*ni):
        flag_bin[j + i] = 0
    if sp_eve[i] == n // (2*ni):
      for j in range(0, n, 2*ni):
        flag_bin[j + i] = 1
    if sp_odd[i] == 0:
      for j in range(0, n, 2*ni):
        flag_bin[j + ni + i] = 0
    if sp_odd[i] == n // (2*ni):
      for j in range(0, n, 2*ni):
        flag_bin[j + ni + i] = 1

  for i in range(ni):
    evei = [flag_bin[j + i] for j in range(0, n, 2*ni)]
    if not -1 in evei:
      continue
    if evei.count(-1) == 1:
      j = evei.index(-1)
      flag_bin[j*2*ni + i] = sp_eve[i] - sum(evei) - 1

  for i in range(ni):
    oddi = [flag_bin[j + ni +i] for j in range(0, n, 2*ni)]
    if not -1 in oddi:
      continue
    if oddi.count(-1) == 1:
      j = oddi.index(-1)
      flag_bin[j*2*ni + ni + i] = sp_odd[i] - sum(oddi) - 1

def run2():
  run(sp4_eve, sp4_odd)
  return show()
run2()

猜单词？·

由于题目给了flag的哈希值，所以可以考虑下爆破。首先上面的inteRest1n就是"interesting"，所以flag值大概率是英文单词的组合，于是可以猜一下单词。

另外上面操作后，有一部分凑不够一个Byte的已知比特可以用上面hint函数列出可能的（字母）取值，比如最后三个是"!!!"。然后用前半恢复后半，后半恢复前半，再猜单词的方法依次猜出：really、master、lattice、dual attack、!@#$（键盘对应1234）。

最后枚举大小写歧义的地方出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
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
# Sage
... ...
def patchB(cb, j):
  c_bin = encode_m(cb)
  for i in range(8):
    flag_bin[j*8 + i] = c_bin[i]

# inteRest1n + g ?
# 41: g or G
#patchB(b'g', 41)
run2()

# !!! end
flag_bin[28*8 + 3] = 1
patchB(b'!', 61)
patchB(b'!', 62)
run2()

# really
patchB(b'_', 23)
# 24: R or r ?
#patchB(b'R', 24)
patchB(b'e', 25)
patchB(b'a', 26)
patchB(b'l', 27)
run2()

# _is ?
patchB(b'_', 20)
patchB(b'1', 21)
# 22: s or S
#patchB(b's', 22)
run2()

# lattice
# 46: l or L
#patchB(b'L', 46)
patchB(b'@', 47)
# 49: t or T
#patchB(b't', 49)
patchB(b'1', 50)
patchB(b'c', 51)
run2()

# dual
patchB(b'u', 10)
patchB(b'a', 11)
patchB(b'l', 12)
run2()

# !@#$ <- 1234
patchB(b'$', 45)
flag = run2()

import itertools
from tqdm import tqdm
def emu2():
  flag = b'antd3ctf{-ual^-tt-ck_1-_-eal1y_inteRest1n-!@#$-@t-1ce_-a-ter!!!}' 
  flag = list(flag)
  assert len(flag) == 64
  pos = []
  for i in range(len(flag)):
    if flag[i] == '-':
      pos += [i]
  pos = [9, 14, 17, 22, 24, 41, 46, 49, 54, 56]
  em = list(itertools.product(
    ['d', 'D'], 
    ['a', 'A', '@'], 
    ['a', 'A', '@'], 
    ['s', 'S'],
    ['r', 'R'],
    ['g', 'G'],
    ['l', 'L'],
    ['t', 'T'],
    ['m', 'M'],
    ['s', 'S']
  ))
  for emi in em:
    for i in range(len(emi)):
      flag[pos[i]] = ord(emi[i])
    #print(bytes(flag))
    if flag_sha256 == sha256(bytes(flag)).hexdigest():
      print(bytes(flag))
      return flag

emu2()

进一步消去已知量·

赛后瞄了一下Nu1l的WP，发现其实还可以把已知量代入原格基实现进一步降维，这样就不用猜单词了。

对于关系（为了直观我就用向量表示了）：

b−s∗A+u∗qI=eb - s * A + u * qI = e

用微观视角看每一个元素，得

bi−sA⋅i+qui=eibi−∑j(sjAji)+qui=eib_i - s A_{·i} + q u_i = e_i \\ b_i - \sum_{j} (s_j A_{ji}) + q u_i = e_i

此时把ss切分成长为512−l512-l的已知和长为ll的未知两部分，姑且称作sKNs^\text{KN}和sKNs^\text{KN}，则可以表示为（其中AKNA^\text{KN}为矩阵AA中sKNs^\text{KN}对应的行组成的“胖矮”矩阵，ANKA^\text{NK}为矩阵AA中sNKs^\text{NK}对应的行组成的矩阵）

bi−∑j(sjKNAjiKN)−∑j(sjNKAjiNK)+qui=eib_i - \sum_{j} (s^\text{KN}_j A^\text{KN}_{ji}) - \sum_{j} (s^\text{NK}_j A^\text{NK}_{ji}) + q u_i = e_i

由于现在sKNs^\text{KN}已知，所以不妨令biKN=bi−∑j(sjKNAjiKN)b^\text{KN}_i = b_i - \sum_{j} (s^\text{KN}_j A^\text{KN}_{ji})、bKN=(b0KN,...,bl−1KN)b^\text{KN} = (b^\text{KN}_0, ..., b^\text{KN}_{l-1})，则

biKN−∑jl(sjNKAjiNK)+qui=eib^\text{KN}_i - \sum_{j}^l (s^\text{NK}_j A^\text{NK}_{ji}) + q u_i = e_i

于是类似地构造格基，注意现在未知量sNKs^\text{NK}长度只是ll，所以只需要取其中的ll个biKNb^\text{KN}_i和对应的ANKA^\text{NK}中的列构造格基即可（理论上可以随机取ll个，参考代码为了方便去了前ll个），最终构造出维度2l+1=2852l+1 = 285的格基MKNM^{\rm{KN}}：

MKN=[ANKqIIbKNβ](2l+1)∗(2l+1)M^{\rm{KN}} = \begin{bmatrix} \begin{array}{lll} A^\text{NK} & & \\ qI & I & \\ b^\text{KN} & & \beta \\ \end{array} \end{bmatrix}_{(2l+1) * (2l+1)}

使得以下关系成立

vMKN=(−sNK,u,1)∗MKN=(e,u,β)=wv M^{\rm{KN}} = (-s^\text{NK}, u, 1) * M^{\rm{KN}} = (e, u, \beta) = w

最终LLL规约解出sNKs^\text{NK}然后结合sKNs^\text{KN}恢复ss。

参考代码：

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
# Sage
... ...
n = 512
flag_bin = [-1 for i in range(n)]
... ...
run(sp4_eve, sp4_odd)

from util import *
from hashlib import *
seed = sha256(b"welcome to D3CTF").digest() + sha256(b"have a nice day").digest()
A = sample_poly(seed , 0 , 2**32 - 5)
b = [3926003029, 1509165306, 3106651955, 2983949872, 2393378576, 284179519, 2886272223, 1233125702, 3238739406, 2644118828, 3957954911, 3691185583, 1700019866, 2347785071, 1123825909, 2465646007, 401380313, 2707319872, 4202699559, 931784437, 3583947386, 2536644387, 2751259493, 1013056277, 1594454226, 3085910471, 3351540180, 2578522714, 2124408803, 1473642602, 2384063470, 215471267, 2252434344, 840082094, 1706153260, 628595906, 2138641953, 1768585251, 3672294042, 2648955311, 1101545943, 1462829980, 2490861499, 3154433480, 3991951537, 4073147435, 3072173371, 2030645383, 2273617209, 610264621, 698372144, 965611111, 3030212709, 3123517391, 1661563411, 2903488892, 4125601987, 3275402564, 3358433812, 1301393717, 183795461, 1088441539, 2652556595, 2457427974, 358582424, 3817487396, 3425059438, 3815131707, 3220004354, 3593522122, 323522616, 2934869693, 1474202000, 3934228907, 2196320858, 789973717, 2041502218, 3287331728, 4058939697, 4049446313, 348017657, 312085362, 2087430022, 2409976112, 4182313358, 2820922003, 3439144715, 2835376655, 4164304483, 3992296837, 713727154, 3972583007, 2995414574, 2136905409, 2369686792, 4225590417, 2855379895, 2894275304, 4218198385, 1863573123, 152470219, 209356356, 2181932671, 87528118, 1509977039, 4251082194, 2394181037, 2698855020, 2791852460, 2343631203, 3588377079, 3883095017, 950749052, 1959173107, 444526794, 1655217840, 1576152947, 1208885396, 1891439027, 2519060478, 3957349805, 2330774404, 1021949515, 626605966, 1495609785, 3059250785, 10735841, 631635858, 2165633772, 1024411702, 1473058591, 1486765493, 1116319646, 2246642032, 136293218, 2809056783, 1207288553, 2490191164, 2022388061, 685418618, 1646546899, 2121499626, 1520638759, 2692413636, 1600251896, 1096615514, 377802389, 2828283506, 1184471637, 1095772453, 2518678208, 2091649527, 2790341258, 2122133496, 2008741414, 1931789532, 3407552039, 2037926317, 3785173109, 537388020, 1347520697, 555823746, 45926964, 2223751155, 2244475841, 1543489738, 722236260, 509055199, 3467634480, 580843748, 1285583898, 762172276, 174622846, 3028903527, 3614079217, 1967089235, 2384435424, 2300454112, 1916488680, 1677513486, 3104896162, 3091029091, 2119463387, 4203135624, 2423205596, 4230847292, 2736568150, 1684068, 4250784177, 741156803, 3460657451, 3249083929, 2818353339, 1641238652, 2040105975, 4195607442, 1149072667, 3335478071, 1960764664, 3978941663, 3482443697, 2656259541, 2956574333, 1327577034, 2436857858, 2073805906, 1802723277, 2678500274, 2972947230, 3132107182, 3467032578, 2426347344, 882119229, 3525375754, 10703769, 2277849193, 2317934043, 4065668868, 1502526735, 2829798591, 491620775, 996910215, 917195400, 1260108701, 2336814388, 37709213, 2901142063, 237197224, 1598485695, 2742667143, 1006207745, 1310704554, 534238429, 3112353574, 2380924842, 488678141, 2362251562, 3671650202, 1373474649, 3770563775, 938589647, 1910576969, 2028715086, 2361257827, 2670923858, 3965429861, 3439583492, 2533589001, 3994264580, 939094829, 3362711263, 704355043, 2954166903, 3966370527, 507768808, 556128950, 113005142, 801326514, 2148700895, 3781985160, 509773408, 3517580267, 2066978314, 2580741498, 3483049277, 3402728951, 1376657292, 1005665197, 2226368584, 1962189041, 671306169, 3775557986, 829941861, 2266480501, 3373215874, 2066458459, 3942151992, 836495238, 3356308384, 1790629422, 577081693, 3896293081, 3143007239, 29998790, 3635296087, 1778531590, 3529468062, 1032288519, 4158133379, 670147084, 786100224, 4145211264, 3106208132, 2414940297, 816565256, 2421147924, 1115269055, 84397462, 450125894, 2616534041, 933989700, 2830477525, 3491928047, 1947624924, 2686771420, 2902325901, 160232448, 3325505253, 2612766083, 2059426891, 3360947950, 2872564882, 1622992720, 2098871616, 431960929, 4066245272, 846589370, 3614792013, 869087998, 3621673292, 3219192545, 3554446061, 2122297338, 1894053711, 3712869523, 3175426433, 1121610839, 1230706582, 883221652, 3378895464, 4209309584, 2997558184, 409046034, 2009074657, 3796666708, 3103438558, 3534784496, 1554926466, 3746409084, 644630989, 847404069, 3238052834, 3158156927, 2168700780, 2867150561, 462828594, 3242835677, 3788069093, 2758603660, 1152155811, 1634934432, 3750823533, 1966238016, 3434703051, 2587050497, 369972874, 1571180588, 502826002, 1394977871, 4209562869, 3661291539, 655998304, 3002301529, 738694423, 1318870183, 1813578224, 2117155417, 2792274549, 469969773, 2885986431, 1205074516, 2141754983, 2119779464, 1794537683, 2109156365, 4041147529, 4112783190, 3639979267, 2833631339, 4023397109, 3724794745, 2898586369, 4243064815, 3173181480, 3547135838, 4216682410, 2537261684, 2850433542, 219483902, 243293295, 3201931974, 3383998262, 2891064412, 2210611534, 1659936487, 2238921384, 1601586549, 1727355629, 2573540630, 397538418, 3982181296, 592903988, 1371833230, 2459822880, 3557146354, 2701900698, 3989213446, 3905799266, 2347299592, 2697290465, 1591743964, 2197267136, 1589688875, 2236270312, 522765112, 3207165428, 1317506342, 3816533175, 1982758394, 3243657510, 3691510923, 3611761928, 1421484363, 2228564874, 2666808060, 340876439, 1909587779, 3453796155, 563826858, 3667231388, 3801779454, 1450891603, 114865654, 1771017530, 1269957854, 3247368682, 829473682, 765526246, 2549194701, 1799890469, 4040022163, 2804947409, 723163470, 2851338295, 743766905, 1623487669, 3706971079, 1857049314, 3001074984, 2428057325, 965966662, 4147994952, 3435363246, 840837590, 1851376608, 1264280015, 3969646217, 2330457493, 3252447459, 1425491214, 1800245805, 1416249314, 3749252176, 617972101, 2161483583, 507648049, 4125775896, 225981076, 1543568816, 1606049079, 3418639383, 4203621112, 2298305661, 918844283, 1829417811, 3035193519, 899008380, 1911356195, 2266791547, 3222899067, 40452845, 285832361, 3748962583, 1501732506, 3660444087, 115130006, 2069772771, 1407520491, 1003548491, 1077094436, 1418848957, 3098099734, 3358357308, 1389355789, 3500246690, 67778141, 630658758, 1075172903, 2989608028, 1987981397, 254794036, 2707266088, 950342808, 1590742759, 2671217284, 494050210, 1914378487, 4230572038, 1798463290, 1484078510, 2214019553, 2674514189]

AA = matrix(ZZ, 512)
for i in range(n):
  for j in range(n):
    AA[i, j] = A.f[(j - i) % n]

n = flag_bin.count(-1)
q = 2^32 - 5
posNkn = []
posKn = []
for i in range(len(flag_bin)):
  if flag_bin[i] == -1:
    posNkn += [i]
  else:
    posKn += [i]

print(n)
beta = 4
M = matrix(ZZ, 2*n+1)
for i in range(n):
  for j in range(n):
    M[j, i] = AA[posNkn[j]][i]    # random n column of AA?
  M[n+i, i] = q
  M[n+i, n+i] = 1
  M[-1, i] = (b[i] - sum([AA[j][i] * flag_bin[j] for j in posKn])) % q
M[-1, -1] = beta
print(len(M[0]))

L = M.LLL()
print(L[0])
s = (-L[0] * M^(-1))[:n]
print(s)
print(sum(s))
print()

# Get flag
import libnum
for i in range(len(s)):
  flag_bin[posNkn[i]] = s[i]
flag_bin = flag_bin[::-1]
flag = sum([2^i * flag_bin[i] for i in range(len(flag_bin))])
flag = libnum.n2s(int(flag))
print(flag)

'''
142
285
(3, 0, -2, 0, 1, -1, 1, 3, -2, -4, -1, 1, -1, -2, 0, 1, 2, 1, -3, 0, -1, -3, 1, 2, -3, 0, -1, 0, 2, 2, 1, -3, 1, 0, -4, -4, 2, -4, -4, -4, 2, 2, 3, 1, 3, -4, -3, 2, -2, -2, 3, -4, 1, 2, -3, -4, -2, 3, 1, -3, 2, -2, 1, -3, 1, 2, 1, -2, 0, 1, -2, 0, 2, 3, -4, 2, 3, 0, -2, 3, 2, -1, -1, 0, -1, 1, -1, -2, -3, -1, 3, -2, 3, -1, -4, 3, 3, -4, -1, 0, 0, 1, -3, 0, 0, 2, -1, -1, -3, 1, 2, -3, 2, 0, -3, 1, 2, 3, 3, 1, -1, 2, -3, -4, 0, -4, 2, 3, -4, 2, -1, 0, 2, 2, -1, -3, -3, 1, -4, 0, -1, -3, 32, 30, 31, 32, 32, 32, 33, 34, 33, 30, 34, 31, 34, 37, 36, 35, 33, 40, 30, 33, 36, 36, 34, 33, 33, 38, 33, 31, 34, 33, 34, 35, 35, 33, 33, 34, 34, 33, 37, 30, 35, 35, 31, 31, 30, 33, 34, 29, 30, 33, 34, 33, 33, 37, 34, 30, 29, 33, 34, 39, 34, 35, 35, 30, 35, 32, 34, 29, 30, 31, 34, 34, 33, 33, 34, 31, 33, 35, 31, 34, 32, 33, 35, 31, 36, 33, 33, 30, 36, 32, 36, 34, 35, 35, 33, 36, 37, 37, 34, 33, 36, 34, 33, 34, 33, 34, 31, 36, 34, 37, 36, 35, 34, 36, 34, 34, 35, 33, 34, 33, 32, 33, 32, 39, 33, 34, 34, 30, 33, 32, 34, 33, 33, 32, 35, 38, 31, 35, 34, 33, 34, 36, 4)
(0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 1, 0, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 0, 0, 1, 1, 0, 1, 1, 0, 1, 1, 1, 0, 1, 0, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 1, 1, 1, 0, 0, 1, 0, 0, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 1, 1, 0, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 1, 1, 1, 0, 0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 1, 1, 0, 1, 1, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0)
71

b'antd3ctf{Dual^attack_1s_real1y_inteRest1ng!@#$L@tT1ce_MaSter!!!}'
'''

继续消去一半已知·

更进一步，以上sNKs^\text{NK}中的元素都有一个属性，即若其对应的和值都为11（否则为00或22都可以恢复出对应位置都为00或11，可以复习一下前面）：

若si∈sNK，则{si+si+n2=1若i<n2si+si−n2=1若i≥n2\text{若$s_i \in s^\text{NK}$，则} \begin{cases} s_i + s_{i + \frac{n}{2}} = 1 & \text{若$i < \frac{n}{2}$} \\ s_i + s_{i - \frac{n}{2}} = 1 & \text{若$i \ge \frac{n}{2}$} \\ \end{cases}

拿i<n2i < \frac{n}{2}的情况举个例子（i≥n2i \ge \frac{n}{2}的类似）：

si⋅ai+si+n2⋅ai+n2=si⋅ai+(1−si)⋅ai+n2=si⋅ai−si⋅ai+n2+ai+n2=si⋅(ai−ai+n2)+ai+n2\begin{aligned} &s_i · a_i + s_{i + \frac{n}{2}} · a_{i + \frac{n}{2}} \\ =&s_i · a_i + (1 - s_i) · a_{i + \frac{n}{2}} \\ =&s_i · a_i - s_i · a_{i + \frac{n}{2}} + a_{i + \frac{n}{2}} \\ =&s_i · (a_i - a_{i + \frac{n}{2}}) + a_{i + \frac{n}{2}} \end{aligned}

把这个关系代进biKN−∑j(sjNKAjiNK)+qui=eib^\text{KN}_i - \sum_{j} (s^\text{NK}_j A^\text{NK}_{ji}) + q u_i = e_i中，有

biKN−∑jl/2(sjNK(Aj,iNK−Aj+l2,iNK)+Aj+l2,iNK)+qui=eib^\text{KN}_i - \sum_{j}^{l/2} (s^\text{NK}_j (A^\text{NK}_{j, i} - A^\text{NK}_{j+\frac{l}{2}, i}) + A^\text{NK}_{j+\frac{l}{2}, i}) + q u_i = e_i

稍微化简一下：

(biKN−∑jl/2Aj+l2,iNK)−∑jl/2(sjNK(Aj,iNK−Aj+l2,iNK))+qui=ei(b^\text{KN}_i - \sum_{j}^{l/2} A^\text{NK}_{j+\frac{l}{2}, i}) - \sum_{j}^{l/2} (s^\text{NK}_j (A^\text{NK}_{j, i} - A^\text{NK}_{j+\frac{l}{2}, i})) + q u_i = e_i

记biNK2=biKN−∑jl/2Aj+l2,iNKb^\text{NK2}_i = b^\text{KN}_i - \sum_{j}^{l/2} A^\text{NK}_{j+\frac{l}{2}, i}，bNK2=(b0NK2,...,bn−1NK2)b^\text{NK2} = (b^\text{NK2}_0, ..., b^\text{NK2}_{n-1})，ANK2A^\text{NK2}为ANKA^\text{NK}前半列减去后半列得到的矩阵（即AjNK−Aj+l2,iNKA^\text{NK}_j - A^\text{NK}_{j+\frac{l}{2}, i}），令sNK2s^\text{NK2}为sNKs^\text{NK}的前半，大概得：

bNK2−∑jl/2(sjNK2⋅Aj,iNK2)+qui=eib^\text{NK2} - \sum_{j}^{l/2} (s^\text{NK2}_j · A^\text{NK2}_{j, i}) + q u_i = e_i

然后取l/2l/2个bNK2b^\text{NK2}和ANK2A^\text{NK2}对应的列构造格基：

MKN2=[ANK2qIIbKN2β](l+1)∗(l+1)M^{\rm{KN2}} = \begin{bmatrix} \begin{array}{lll} A^\text{NK2} & & \\ qI & I & \\ b^\text{KN2} & & \beta \\ \end{array} \end{bmatrix}_{(l+1) * (l+1)}

使得以下关系成立

vMKN2=(−sNK2,u,1)∗MKN2=(e,u,β)=wv M^{\rm{KN2}} = (-s^\text{NK2}, u, 1) * M^{\rm{KN2}} = (e, u, \beta) = w

最终LLL规约解出sNK2s^\text{NK2}，然后恢复sNKs^\text{NK}，再结合sKNs^\text{KN}恢复ss，维度降到l+1=143l+1 = 143。

参考代码：

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
# Sage
... ...
n = 512
flag_bin = [-1 for i in range(n)]
... ...
run(sp4_eve, sp4_odd)

from util import *
from hashlib import *
seed = sha256(b"welcome to D3CTF").digest() + sha256(b"have a nice day").digest()
A = sample_poly(seed , 0 , 2**32 - 5)
b = [3926003029, 1509165306, 3106651955, 2983949872, 2393378576, 284179519, 2886272223, 1233125702, 3238739406, 2644118828, 3957954911, 3691185583, 1700019866, 2347785071, 1123825909, 2465646007, 401380313, 2707319872, 4202699559, 931784437, 3583947386, 2536644387, 2751259493, 1013056277, 1594454226, 3085910471, 3351540180, 2578522714, 2124408803, 1473642602, 2384063470, 215471267, 2252434344, 840082094, 1706153260, 628595906, 2138641953, 1768585251, 3672294042, 2648955311, 1101545943, 1462829980, 2490861499, 3154433480, 3991951537, 4073147435, 3072173371, 2030645383, 2273617209, 610264621, 698372144, 965611111, 3030212709, 3123517391, 1661563411, 2903488892, 4125601987, 3275402564, 3358433812, 1301393717, 183795461, 1088441539, 2652556595, 2457427974, 358582424, 3817487396, 3425059438, 3815131707, 3220004354, 3593522122, 323522616, 2934869693, 1474202000, 3934228907, 2196320858, 789973717, 2041502218, 3287331728, 4058939697, 4049446313, 348017657, 312085362, 2087430022, 2409976112, 4182313358, 2820922003, 3439144715, 2835376655, 4164304483, 3992296837, 713727154, 3972583007, 2995414574, 2136905409, 2369686792, 4225590417, 2855379895, 2894275304, 4218198385, 1863573123, 152470219, 209356356, 2181932671, 87528118, 1509977039, 4251082194, 2394181037, 2698855020, 2791852460, 2343631203, 3588377079, 3883095017, 950749052, 1959173107, 444526794, 1655217840, 1576152947, 1208885396, 1891439027, 2519060478, 3957349805, 2330774404, 1021949515, 626605966, 1495609785, 3059250785, 10735841, 631635858, 2165633772, 1024411702, 1473058591, 1486765493, 1116319646, 2246642032, 136293218, 2809056783, 1207288553, 2490191164, 2022388061, 685418618, 1646546899, 2121499626, 1520638759, 2692413636, 1600251896, 1096615514, 377802389, 2828283506, 1184471637, 1095772453, 2518678208, 2091649527, 2790341258, 2122133496, 2008741414, 1931789532, 3407552039, 2037926317, 3785173109, 537388020, 1347520697, 555823746, 45926964, 2223751155, 2244475841, 1543489738, 722236260, 509055199, 3467634480, 580843748, 1285583898, 762172276, 174622846, 3028903527, 3614079217, 1967089235, 2384435424, 2300454112, 1916488680, 1677513486, 3104896162, 3091029091, 2119463387, 4203135624, 2423205596, 4230847292, 2736568150, 1684068, 4250784177, 741156803, 3460657451, 3249083929, 2818353339, 1641238652, 2040105975, 4195607442, 1149072667, 3335478071, 1960764664, 3978941663, 3482443697, 2656259541, 2956574333, 1327577034, 2436857858, 2073805906, 1802723277, 2678500274, 2972947230, 3132107182, 3467032578, 2426347344, 882119229, 3525375754, 10703769, 2277849193, 2317934043, 4065668868, 1502526735, 2829798591, 491620775, 996910215, 917195400, 1260108701, 2336814388, 37709213, 2901142063, 237197224, 1598485695, 2742667143, 1006207745, 1310704554, 534238429, 3112353574, 2380924842, 488678141, 2362251562, 3671650202, 1373474649, 3770563775, 938589647, 1910576969, 2028715086, 2361257827, 2670923858, 3965429861, 3439583492, 2533589001, 3994264580, 939094829, 3362711263, 704355043, 2954166903, 3966370527, 507768808, 556128950, 113005142, 801326514, 2148700895, 3781985160, 509773408, 3517580267, 2066978314, 2580741498, 3483049277, 3402728951, 1376657292, 1005665197, 2226368584, 1962189041, 671306169, 3775557986, 829941861, 2266480501, 3373215874, 2066458459, 3942151992, 836495238, 3356308384, 1790629422, 577081693, 3896293081, 3143007239, 29998790, 3635296087, 1778531590, 3529468062, 1032288519, 4158133379, 670147084, 786100224, 4145211264, 3106208132, 2414940297, 816565256, 2421147924, 1115269055, 84397462, 450125894, 2616534041, 933989700, 2830477525, 3491928047, 1947624924, 2686771420, 2902325901, 160232448, 3325505253, 2612766083, 2059426891, 3360947950, 2872564882, 1622992720, 2098871616, 431960929, 4066245272, 846589370, 3614792013, 869087998, 3621673292, 3219192545, 3554446061, 2122297338, 1894053711, 3712869523, 3175426433, 1121610839, 1230706582, 883221652, 3378895464, 4209309584, 2997558184, 409046034, 2009074657, 3796666708, 3103438558, 3534784496, 1554926466, 3746409084, 644630989, 847404069, 3238052834, 3158156927, 2168700780, 2867150561, 462828594, 3242835677, 3788069093, 2758603660, 1152155811, 1634934432, 3750823533, 1966238016, 3434703051, 2587050497, 369972874, 1571180588, 502826002, 1394977871, 4209562869, 3661291539, 655998304, 3002301529, 738694423, 1318870183, 1813578224, 2117155417, 2792274549, 469969773, 2885986431, 1205074516, 2141754983, 2119779464, 1794537683, 2109156365, 4041147529, 4112783190, 3639979267, 2833631339, 4023397109, 3724794745, 2898586369, 4243064815, 3173181480, 3547135838, 4216682410, 2537261684, 2850433542, 219483902, 243293295, 3201931974, 3383998262, 2891064412, 2210611534, 1659936487, 2238921384, 1601586549, 1727355629, 2573540630, 397538418, 3982181296, 592903988, 1371833230, 2459822880, 3557146354, 2701900698, 3989213446, 3905799266, 2347299592, 2697290465, 1591743964, 2197267136, 1589688875, 2236270312, 522765112, 3207165428, 1317506342, 3816533175, 1982758394, 3243657510, 3691510923, 3611761928, 1421484363, 2228564874, 2666808060, 340876439, 1909587779, 3453796155, 563826858, 3667231388, 3801779454, 1450891603, 114865654, 1771017530, 1269957854, 3247368682, 829473682, 765526246, 2549194701, 1799890469, 4040022163, 2804947409, 723163470, 2851338295, 743766905, 1623487669, 3706971079, 1857049314, 3001074984, 2428057325, 965966662, 4147994952, 3435363246, 840837590, 1851376608, 1264280015, 3969646217, 2330457493, 3252447459, 1425491214, 1800245805, 1416249314, 3749252176, 617972101, 2161483583, 507648049, 4125775896, 225981076, 1543568816, 1606049079, 3418639383, 4203621112, 2298305661, 918844283, 1829417811, 3035193519, 899008380, 1911356195, 2266791547, 3222899067, 40452845, 285832361, 3748962583, 1501732506, 3660444087, 115130006, 2069772771, 1407520491, 1003548491, 1077094436, 1418848957, 3098099734, 3358357308, 1389355789, 3500246690, 67778141, 630658758, 1075172903, 2989608028, 1987981397, 254794036, 2707266088, 950342808, 1590742759, 2671217284, 494050210, 1914378487, 4230572038, 1798463290, 1484078510, 2214019553, 2674514189]

AA = matrix(ZZ, 512)
for i in range(n):
  for j in range(n):
    AA[i, j] = A.f[(j - i) % n]

n = flag_bin.count(-1)
print(n)
q = 2^32 - 5
posNkn = []
posKn = []
for i in range(len(flag_bin)):
  if flag_bin[i] == -1:
    posNkn += [i]
  else:
    posKn += [i]
print(posNkn)

AAA = matrix(ZZ, n)
for i in range(n):
  for j in range(n):
    AAA[j, i] = AA[posNkn[j]][i]    # random n column of AA?

AAAA = matrix(ZZ, n//2)
for i in range(n//2):
  for j in range(n//2):
    AAAA[j, i] = AAA[j, i] - AAA[j + n//2, i]

bNk = [(b[i] - sum([AA[j][i] * flag_bin[j] for j in posKn])) % q for i in range(n)]
bbNk = [bNk[i] - sum([AAA[j+n//2, i] for j in range(n//2)]) for i in range(n//2)]
beta = 16
M = matrix(ZZ, n+1)
for i in range(n//2):
  for j in range(n//2):
    M[j, i] = AAAA[j][i]
  M[n//2+i, i] = q
  M[n//2+i, n//2+i] = 1
  M[-1, i] = bbNk[i]
M[-1, -1] = beta
print(len(M[0]))
print()

L = M.LLL()
print(L[0])
s = (- L[0][-1]//beta * L[0] * M^(-1))[:n//2]
print(s)

# Get flag
import libnum
for i in range(len(s)):
  flag_bin[posNkn[i]] = s[i]
  flag_bin[posNkn[i + n//2]] = 1 - s[i]
flag_bin = flag_bin
flag = int(''.join([str(x) for x in flag_bin]), 2)
flag = libnum.n2s(int(flag))
print(flag)


'''
(3, 0, -2, 0, 1, -1, 1, 3, -2, -4, -1, 1, -1, -2, 0, 1, 2, 1, -3, 0, -1, -3, 1, 2, -3, 0, -1, 0, 2, 2, 1, -3, 1, 0, -4, -4, 2, -4, -4, -4, 2, 2, 3, 1, 3, -4, -3, 2, -2, -2, 3, -4, 1, 2, -3, -4, -2, 3, 1, -3, 2, -2, 1, -3, 1, 2, 1, -2, 0, 1, -2, 32, 30, 31, 32, 32, 32, 33, 34, 33, 30, 34, 31, 34, 37, 36, 35, 33, 40, 30, 33, 36, 36, 34, 33, 33, 38, 33, 31, 34, 33, 34, 35, 35, 33, 33, 34, 34, 33, 37, 30, 35, 35, 31, 31, 30, 33, 34, 29, 30, 33, 34, 33, 33, 37, 34, 30, 29, 33, 34, 39, 34, 35, 35, 30, 35, 32, 34, 29, 30, 31, 34, 16)
(0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 1, 0, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 0, 0, 1, 1, 0, 1, 1, 0, 1, 1, 1, 0, 1, 0, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 1, 1, 1, 0, 0, 1, 0, 0, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1)
b'antd3ctf{Dual^attack_1s_real1y_inteRest1ng!@#$L@tT1ce_MaSter!!!}'
'''

正解·

附上官方预期解：https://github.com/shal10w/d3ctf2023-d3bdd/tree/main

有空再去研究一下（留坑

伪随机数·

最后其实那个伪随机数生成也有点意思，虽然好像没有可利用的漏洞。

PRNG的计算大概类似斐波那契的计算，即

(sti,sti+1,...,sti+d−1)[00⋯0f010⋯0f101⋯0f2⋮⋮⋱⋮⋮00⋯1fd−1]=(sti+1,sti+2,...,sti+d)(st_i, st_{i+1}, ..., st_{i+d-1}) \begin{bmatrix} 0 & 0 & \cdots & 0 & f_0 \\ 1 & 0 & \cdots & 0 & f_1 \\ 0 & 1 & \cdots & 0 & f_2 \\ \vdots & \vdots & \ddots & \vdots & \vdots \\ 0 & 0 & \cdots & 1 & f_{d-1} \\ \end{bmatrix} \\= (st_{i+1}, st_{i+2}, ..., st_{i+d})