The learning of LWE

Posted on Edited on In Word count in article: 12k Reading time ≈ 11 mins.

做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): 随机生成一个整数的矩阵, 其元素的取值范围是也就是

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

    D - an error distribution such as an instance of DiscreteGaussianDistributionIntegerSampler

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

题目中给出的一些条件

  • 首先是一个320*5的矩阵，乘上了一个随机变换矩阵5*7的矩阵，得到了一个320*7的矩阵B
  • 然后是一个LWE，生成了64组数据，，没有直接给我们和。只给了，以及用作为AES的key，对flag进行了加密。
  • 再就是一个knapsack problem，用长度为64的向量与一个另外一个很大的长度为64的随机向量相乘，得到一个很大的数。给了以及。

knapsack problem

这里有一个背包问题

其中已知,而且非常大, , 可以由上述式子构造格子

则有

可以看到是其中一个格点, 而且非常的小, 可以尝试用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)

恢复

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

LWE

可以将这个等式理解成是一个格子, 是一个线性组合, 那么是一个格点, 是误差, 是一个非格点. LWE就是要找到这么离这个非格点最近的格点. 也就是CVP了

当的长度不是很长的时候, 也就是说维度比较小的时候, 这个CVP还是可以解决的, 而这里的长度是25, 观察一下LWE的式子.

熟悉的造格子前的套路, 将式子化为:

那么可以构造出等式:

先对矩阵进行规约, 得到一个good basis, 再用Babai’s algorithm求解CVP，即可得到离最近的格点。

最后解方程

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

下面是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的矩阵

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

然后计算, 结果应该是一个的矩阵

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

最后计算

题目给了和

分析

来看一下加密的式子

显然是一个LWE, 现在已知的是和, 要求, 将式子写具体

也就是说

老套路, 改写成等式有

解决LWE可以构造格子, 然后用LLL和babai’s nearest plane来解决, 下面就根据等式构造格子

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

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

解出CVP也就意味着找到了中的 , 又是已知的, 解方程即可

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到底是怎么通过格子解出来的

先看看这题造的格子
加密的式子还是, 这里的长度32,一共64个式子
这里只知道和要求, 思路都是记, 是格子的一个格点, 是格外一个点, 通过对规约找到 再利用最近平面算法解决一个CVP, 也就是找到离最近的向量, 也就是

把再详细点就是

那么造出来的格子应该是下面这个矩阵

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

通过对构造出来的格子进行规约得到good basis然后用最近平面算出
再解方程即可得到

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维的秘密向量都可以规约出来, 很牛逼

在中

我们可以把矩阵和向量看成,

所以咱们就可以构造出这么一个格子

规约出来的就直接是噪音了, 有了就能解出, 不过这边还是有几个点要去注意

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

暂时就这两个点了

为了写个板子供以后做题用, 我把祥云杯那道题的数据拿过来写了个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='')