做Ant&d3的时候发现自己Lattice还不会, 所以就去学了一波Lattice, 顺便就了解了一下LWE, 发现这玩意居然有三次比赛用的都是同一个板子, 也每个都去做了分析了一下, 然后就集中在这里了.

感谢一位大大大大大师傅详细的wp，我才能这么快的明白原理，指路 —> https://blog.soreatu.com/

X-NUCA Diamond

题目

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
#!/usr/bin/env sage
import os
from hashlib import sha256
from Crypto.Cipher import AES
from sage.crypto.lwe import LWE
from sage.stats.distributions.discrete_gaussian_integer import DiscreteGaussianDistributionIntegerSampler as DGDIS

from secret import FLAG
assert FLAG.startswith(b"X-NUCA{") and FLAG.endswith(b"}")

A = random_matrix(ZZ, 320, 5, x = 10, y = 1000)
B = Matrix(A * vector([randint(1, 2^1024) for _ in range(5)]) for _ in range(7))

L = LWE(n = 25, q = 1000, D = DGDIS(3))
S = [L() for _ in range(64)]

M = Matrix(64, 25, [int(i).__xor__(int(j)) for i,j in zip(A.list(), (Matrix([x for x, _ in S])).list())])
T = Matrix([randint(1, 2^1024) for _ in range(64)])
R = T.transpose().stack(T * vector([y for _, y in S]).change_ring(ZZ))

if __name__ == "__main__":
	key = sha256(''.join(list(map(str, L._LWE__s))).encode()).digest()
	iv = os.urandom(16)
	cipher = AES.new(key, AES.MODE_CBC, iv)
	ct = cipher.encrypt(FLAG)

	f = open("output.txt", "wb")
	f.write(str(B.list()).encode() + b'\n')
	f.write(str(M.list()).encode() + b'\n')
	f.write(str(R.list()).encode() + b'\n')
	f.write((iv + ct).hex().encode())
	f.close()

一些新见到的函数

  1. random_matrix(ZZ, 5, 320, x = 10, y = 1000): 随机生成一个整数的$320 \cdot 5$矩阵, 其元素的取值范围是$[x,y)$也就是$[10,1000)$

  2. LWE(n = 25, q = 1000, D = DGDIS(3)): 生成一个25维 $mod \ 1000$的LWE对象

    D - an error distribution such as an instance of DiscreteGaussianDistributionIntegerSampler

  3. stack(): 在末尾添加一行

题目中给出的一些条件

  • 首先是一个320*5的矩阵$A$，乘上了一个随机变换矩阵5*7的矩阵$R$，得到了一个320*7的矩阵B
  • 然后是一个LWE，生成了64组数据，$s⋅A_{lwe}+e=a$，没有直接给我们$A_{lwe}$和$a$。只给了$M=A{lwe}\bigoplus A$，以及用$s$作为AES的key，对flag进行了加密。
  • 再就是一个knapsack problem，用长度为64的向量$a$与一个另外一个很大的长度为64的随机向量$T$相乘，得到一个很大的数$sum$。给了$T$以及$sum$。

knapsack problem

这里有一个背包问题
$$
a_0T_0+a_1T_1+…+a_{63}T_{63} = sum
$$
其中已知$T_0,T_1,…,T_{63},sum$,而且$T_i$非常大, $a_i \le 1000$ , 可以由上述式子构造格子
$$
A=
\begin{pmatrix}
1&0&\cdots&0&T_0\\
0&1&\cdots&0&T_1\\
\vdots&\vdots&\ddots&0&\vdots\\
0&0&\cdots&1&T_{63}\\
0&0&\cdots&0&-sum
\end{pmatrix}
$$
则有
$$
\begin{pmatrix}
a_0,a_1,…,a_{63},{1}
\end{pmatrix}
\begin{pmatrix}
1&0&\cdots&0&T_0\\
0&1&\cdots&0&T_1\\
\vdots&\vdots&\ddots&0&\vdots\\
0&0&\cdots&1&T_{63}\\
0&0&\cdots&0&-sum
\end{pmatrix}
=
\begin{pmatrix}
a_0,a_1,…,a_{63},{0}
\end{pmatrix}
$$
可以看到$\begin{pmatrix}a_0,a_1,…,a_{63},0\end{pmatrix}$是其中一个格点, 而且非常的小, 可以尝试用LLL将其规约出来

1
2
3
4
5
6
7
8
9
10
11
12
R = [...]
Lattice = [[0 for _ in range(65)] for _ in range(65)]
for i in range(65):
    for j in range(65):
        if i==j and i!= 64:
            Lattice[i][j] = 1
        if j== 64:
            Lattice[i][j] = R[i]
Lattice[64][64] = -Lattice[64][64]
Lattice = Matrix(Lattice)
a = Lattice.LLL()[0][:-1]
# (868, 798, 863, 260, 206, 550, 326, 908, 49, 50, 273, 528, 584, 569, 975, 261, 885, 680, 116, 33, 677, 664, 922, 178, 999, 336, 60, 655, 102, 438, 269, 754, 988, 124, 10, 380, 589, 382, 668, 623, 335, 845, 104, 117, 961, 917, 114, 590, 255, 26, 81, 846, 925, 548, 446, 796, 543, 997, 492, 651, 485, 137, 701, 247)

恢复$A_{lwe}$

这部分还有些不明白,先放着

LWE

$$
s \cdot A + e = a
$$

可以将这个等式理解成$A$是一个格子, $s$是一个线性组合, 那么$b = s \cdot A$是一个格点, $e$是误差, $a = b+e$是一个非格点. LWE就是要找到这么离这个非格点最近的格点. 也就是CVP了

当$s$的长度不是很长的时候, 也就是说维度比较小的时候, 这个CVP还是可以解决的, 而这里$s$的长度是25, 观察一下LWE的式子.
$$
s_0A_{i,0}+s_1A_{i,1}+…+s_{24}A_{i,24} + e_i = a_i \ (mod \ p)
$$
熟悉的造格子前的套路, 将式子化为:
$$
s_0A_{i,0}+s_1A_{i,1}+…+s_{24}A_{i,24} + k_ip + e_i= a_i
$$
那么可以构造出等式:
$$
s \cdot L + e =
(s_0,s_1,…,s_{24},k_0,k_1,…,k_{39})
\begin{pmatrix}
A_{0,0}&A_{1,0}&\cdots&A_{39,0}\\
A_{0,1}&A_{1,1}&\cdots&A_{39,1}\\
\vdots&\vdots&\ddots&\vdots\\
A_{0,24}&A_{1,24}&\cdots&A_{39,24}\\
p&0&\cdots&0\\
0&p&\cdots&0\\
\vdots&\vdots&\ddots&\vdots\\
0&0&\cdots&p\\
\end{pmatrix}
+
(e_0,e_1,…,e_{39})
=
(c_0,c_1,…,c_{39})
$$
先对矩阵$L$进行规约, 得到一个good basis, 再用Babai’s algorithm求解CVP，即可得到离$a$最近的格点$b$。

最后解方程$A_{lwe} \cdot s = b^{T} (mod \ 1000)$

解出$s$这道题基本上就做完了

下面是Babai’s algorithm的板子

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def BabaisClosestPlaneAlgorithm(L, w):
    '''
    Yet another method to solve apprCVP, using a given good basis.
    INPUT:
    * "L" -- a matrix representing the LLL-reduced basis (v1, ..., vn) of a lattice.
    * "w" -- a target vector to approach to.
    OUTPUT:
    * "v" -- a approximate closest vector.
    Quoted from "An Introduction to Mathematical Cryptography":
    In both theory and practice, Babai's closest plane algorithm
    seems to yield better results than Babai's closest vertex algorithm.
    '''
    G, _ = L.gram_schmidt()
    t = w
    i = L.nrows() - 1
    while i >= 0:
        w -= round( (w*G[i]) / G[i].norm()^2 ) * L[i]
        i -= 1
    return t - w

总的exp就没写了, 具体的可以参照着下面两题来写, 反正都是一个板子的

2020祥云杯 Easy Matrix

Problem

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
import numpy as np
from secret import *

def random_offset(size):
    x = np.random.normal(0, 4.7873, size)
    return np.rint(x)

secret = np.array(list(flag))

column = len(list(secret))
row = 128
prime = 2129

matrix = np.random.randint(512, size=(row, column))
product = matrix.dot(secret) % prime
offset = random_offset(size=row).astype(np.int64)
result = (product + offset) % prime

np.save("matrix.npy", matrix)
np.save("result.npy", result)

条件

读取了matrix后就可以知道column = 42

将flag转成一个1*42的矩阵$secret$

来看看过程, 先是生成一个42*128 的随机矩阵$matrix$, 元素都$\leq 512$

然后计算$product = matrix \cdot secret \ (mod \ prime)$, 结果应该是一个$1*128$的矩阵

继续生成一个1*128随机矩阵$offset$

最后计算$result = (product + offset) \ (mod \ prime)$

题目给了$result$和$matrix$

分析

来看一下加密的式子
$$
R = S \cdot M + e \ (mod \ p)
$$
显然是一个LWE, 现在已知的是$M$和$R$, 要求$S$, 将式子写具体
$$
R = (r_0,r_1,..,r_{127}) =
(s_0,s_1,…,s_{41})
\begin{pmatrix}
m_{0,0}&m_{1,0}&\cdots&m_{127,0}\\
m_{0,1}&m_{1,1}&\cdots&m_{127,1}\\
\vdots&\vdots&\ddots&\vdots\\
m_{0,41}&m_{1,42}&\cdots&m_{127,41}
\end{pmatrix}
+
(e_0,e_1,…,e_{41})
(mod \ p)
$$
也就是说
$$
r_i = s_0m_{i,0} + s_1m_{i,1}+…+s_{41}m_{i,41} + e_i (mod \ p)
$$

老套路, 改写成等式有
$$
s_0m_{i,0} + s_1m_{i,1}+…+s_{41}m_{i,41} + e_i + k_ip = r_i \
s \cdot A + e = r
$$

解决LWE可以构造格子, 然后用LLL和babai’s nearest plane来解决, 下面就根据等式构造格子
$$
A=
\begin{pmatrix}
m_{0,0}&m_{1,0}&\cdots&m_{127,0}\\
m_{0,1}&m_{1,1}&\cdots&m_{127,1}\\
\vdots&\vdots&\ddots&\vdots\\
m_{0,41}&m_{1,42}&\cdots&m_{127,41}\\
p&0&\cdots&0\\
0&p&\cdots&0\\
\vdots&\vdots&\ddots&\vdots\\
0&0&\cdots&p
\end{pmatrix}
\begin{pmatrix}
p&0&\cdots&0\\
0&p&\cdots&0\\
\vdots&\vdots&\ddots&\vdots\\
0&0&\cdots&p\\
m_{0,0}&m_{1,0}&\cdots&m_{127,0}\\
m_{0,1}&m_{1,1}&\cdots&m_{127,1}\\
\vdots&\vdots&\ddots&\vdots\\
m_{0,41}&m_{1,42}&\cdots&m_{127,41}\\
\end{pmatrix}\\
$$

实际上做的时候右边的格子才有用, 左边的不行, 具体原因我也搞不清楚, 问了老师也没问出什么结果

然后就可以用LLL格约出good basis 再用babai’s nearest plane解CVP了

解出CVP也就意味着找到了$s \cdot A = b$中的$b$ , $A$又是已知的, 解方程即可

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
import numpy as np
from sage.modules.free_module_integer import IntegerLattice

def BabaisClosestPlaneAlgorithm(L, w):
    '''
    Yet another method to solve apprCVP, using a given good basis.
    INPUT:
    * "L" -- a matrix representing the LLL-reduced basis (v1, ..., vn) of a lattice.
    * "w" -- a target vector to approach to.
    OUTPUT:
    * "v" -- a approximate closest vector.
    Quoted from "An Introduction to Mathematical Cryptography":
    In both theory and practice, Babai's closest plane algorithm
    seems to yield better results than Babai's closest vertex algorithm.
    '''
    G, _ = L.gram_schmidt()
    t = w
    i = L.nrows() - 1
    while i >= 0:
        w -= round( (w*G[i]) / G[i].norm()^2 ) * L[i]
        i -= 1
    return t - w
row = 128
col = 42
p = 2129

M = Matrix(list(np.load('matrix.npy')))
R = vector(list(np.load('result.npy')))

A = [[0 for _ in range(row)] for _ in range(row)]
for i in range(128):
    for j in range(128):
        if i==j:
            A[i][j] = p
A = Matrix(A)
L = Matrix(A.stack(M.transpose()))
lattice = IntegerLattice(L, lll_reduce=True)
closest_vector = BabaisClosestPlaneAlgorithm(lattice.reduced_basis, R)

FLAG = Matrix(Zmod(p), M)
flag = FLAG.solve_right(closest_vector)
print(''.join( chr(i) for i in flag))

2020纵横杯 babyLWE

problem

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
from sage.crypto.lwe import LWE
from sage.stats.distributions.discrete_gaussian_integer \
    import DiscreteGaussianDistributionIntegerSampler as DGDIS
import uuid

FLAG = 'flag{' + str(uuid.uuid4()) + '}'
FLAG = FLAG.encode().replace(b'-',b'')

assert FLAG.startswith(b'flag{') and FLAG.endswith(b'}')
s = list(FLAG[5:-1])

n = len(s)
q = random_prime(1<<512, proof=False, lbound=1<<511)

lwe = LWE(n=n, q=q, D=DGDIS(1<<128))
lwe._LWE__s = vector(Zmod(q), s)

L = [lwe() for _ in range(2*n)]

with open('task.txt', 'w') as f:
    _ = f.write(f"q = {q}\n")
    _ = f.write(f"L = {L}\n")

分析

太离谱了, 一个板子三个比赛用, 这题用的还是X-NUCA Diamond的LWE的板子…
但是为了充分理解(就是还没理解)LWE到底是怎么通过格子解出来的

先看看这题造的格子
加密的式子还是$s \cdot M + e = a \ (mod \ q)$, 这里的$s,M$长度32,一共64个式子
这里只知道$M$和$a$要求$s$, 思路都是记$s \cdot M = b $, $b$是格子$M$的一个格点, $a$是格外一个点, 通过对$M$规约找到$good \ basis$ 再利用最近平面算法解决一个CVP, 也就是找到离$a$最近的向量, 也就是$b$

把$s \cdot M = b \ (mod \ q)$再详细点就是
$$
s_0M_{i,0}+s_1M_{i,1}+…+s_{31}M_{i,31} = b_i + k_iq\\
s_0M_{i,0}+s_1M_{i,1}+…+s_{31}M_{i,31}+ k_iq = b_i
$$
那么造出来的格子应该是下面这个矩阵
$$
(s_0,s_1,\cdots,s_{31},k_0,k_1,\cdots,k_{63})
\begin{pmatrix}
M_{0,0}&M_{1,0}&\cdots&M_{63,0}\\
M_{0,1}&M_{1,1}&\cdots&M_{63,1}\\
\vdots&\vdots&\ddots&\vdots\\
M_{0,31}&M_{1,31}&\cdots&M_{63,31}\\
q&0&\cdots&0\\
0&q&\cdots&0\\
\vdots&\vdots&\ddots&\vdots\\
0&0&0&q
\end{pmatrix}
=
(b_0,b_1,\cdots,b_{63})
$$

实际上做题的时候矩阵是上面$p$下面$M$的, 然后还有关于为什么要用64组LWE的问题, 根据某个大佬的博客, 组数越多越好, 所以基本上题目给了多少组就用上多少组

通过对构造出来的格子进行规约得到good basis然后用最近平面算出$(b_0,b_1,…,b_{63})$
再解方程$s \cdot M = b \ (mod \ p)$即可得到$s$

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
from sage.modules.free_module_integer import IntegerLattice
def BabaisClosestPlaneAlgorithm(L, w):
    '''
    Yet another method to solve apprCVP, using a given good basis.
    INPUT:
    * "L" -- a matrix representing the LLL-reduced basis (v1, ..., vn) of a lattice.
    * "w" -- a target vector to approach to.
    OUTPUT:
    * "v" -- a approximate closest vector.
    Quoted from "An Introduction to Mathematical Cryptography":
    In both theory and practice, Babai's closest plane algorithm
    seems to yield better results than Babai's closest vertex algorithm.
    '''
    G, _ = L.gram_schmidt()
    t = w
    i = L.nrows() - 1
    while i >= 0:
        w -= round( (w*G[i]) / G[i].norm()^2 ) * L[i]
        i -= 1
    return t - w

q = 8934325385505568130914092337950620590424921674062792756625169144539462888362199042365894202712873706261308891694743761726859424971637596576879385466842113
L = [...]
n = 32

Q = [[0 for _ in range(2*n)] for _ in range(2*n)]
R = [0 for _ in range(2*n)]
LL = [[0 for _ in range(n)] for _ in range(2*n)]

for i in range(2*n):
    for j in range(n):
        LL[i][j] = L[i][0][j] 
M = Matrix(LL).transpose()

for i in range(2*n):
    for j in range(2*n):
        if i == j:
            Q[i][j] = q

for i in range(2*n):
    R[i] = L[i][1]

R = vector(R)
L = Matrix(Q).stack(Matrix(M))
lattice = IntegerLattice(L, lll_reduce=True)
closest_vector = BabaisClosestPlaneAlgorithm(lattice.reduced_basis, R)

FLAG = Matrix(Zmod(q), M.transpose())
flag = FLAG.solve_right(closest_vector)
print(''.join( chr(i) for i in flag))

2021/3/31 update

因为最近在做大学生密码挑战赛的LWE, 所以学了挺多造格子的姿势
这边记录一个好用的格子, 80维的秘密向量都可以规约出来, 很牛逼

在$As + e = b \mod q$中

我们可以把矩阵$A$和向量$b$看成$A=\begin{pmatrix}A_1 \\ A_2\end{pmatrix}$,$b=\begin{pmatrix}b_1 \\ b_2\end{pmatrix}=\begin{pmatrix}A_1 \\ A_2\end{pmatrix}s + \begin{pmatrix}e_1 \\ e_2\end{pmatrix} $

所以咱们就可以构造出这么一个格子
$$
\begin{pmatrix}
I_n&0&b_1 \\
A_2A_1^{-1}&qI_{m-n}&b_2 \\
0&0&1
\end{pmatrix}
\begin{pmatrix}
A_1s \\
k \\
-1
\end{pmatrix}
=
\begin{pmatrix}
-e_1 \\
-e_2 \\
-1
\end{pmatrix}
$$
规约出来的就直接是噪音$e$了, 有了$e$就能解出$s$, 不过这边还是有几个点要去注意

  1. 上面式子给出的格子并不是扔进sage里规约的格子, 真正扔进去规约的是它的转置, 也不知道是不是sage默认对行向量规约, 只能把它转置才能规约出结果, 结果也是行向量来的
  2. 格子中有一个$A_2A_1^{-1}$, 其中的逆矩阵$A_1^{-1}$是模$q$的逆, 有时候会出现模$q$不能求逆的情况, 这个时候可以适当的调换$A$中的行向量, 使得$A_1 \mod q$的逆存在, 但要记得向量$b$也要跟着调换, 而且最后求到的结果也是调换之后的, 需要还原回去

暂时就这两个点了

为了写个板子供以后做题用, 我把祥云杯那道题的数据拿过来写了个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
import numpy as np
row = 128
col = 42
p = 2129

M = Matrix(list(np.load('matrix.npy')))
R = vector(list(np.load('result.npy')))

A1 = M[:col]
A2 = M[col:]
A12 = A2 * A1.inverse() % p

L = Matrix([[0 for _ in range(row+1)] for _ in range(row+1)])
for i in range(col):
    for j in range(col):
        if i == j:
            L[i,j] = 1         
for i in range(row - col):
    for j in range(row - col):
        if i == j:
            L[i+col,j+col] = p
for i in range(row-col):
    for j in range(col):
        L[i+col,j] = A12[i,j]
for i in range(row):
    L[i,-1] = R[i]
L[-1,-1] = 1


reduced = L.transpose().LLL()
error = []
for i in reduced[0][:-1]:
    error.append(-i)
e = vector(error)
As = R - e
A = Matrix(Zmod(p),M)
for i in A.solve_right(As):
    print(chr(i),end='')