格密码经典问题学习(LWE)

LWE容错学习问题

最近susctf出了一道这类题，通过复现这个题来学习一下LWE

定义

随机选取一个矩阵 **A ** (m×n)，一个随机向量 **s ** (n)，和一个随机的噪音 e (m)。

一个LWE系统的输出 B=A * s + e **(mod p)**。

一个LWE问题是，给定一个矩阵 A，和LWE系统的输出 B，还原 s。

无法直接求解的简单解释

因为加入了一些误差，如果使用高斯消元法的话，这些误差会聚集起来，使得解出来的东西跟实际值差很多。

构造格的形式(CVP问题)

​ A E

​ B 0

代码

import numpy as np
A=np.array(np.zeros([m,m])).tolist()#要保证m>=n
B=np.array(np.zeros(m)).tolist()
from sage.modules.free_module_integer import IntegerLattice
IntegerLattice(B, lll_reduce=True).reduced_basis
def solve_LWE(A:list,B:list):
    M = []
    for i in range(m):
        M.append(A[i] + [0] * i + [1] + [0] * (m - 1 - i))
    M.append(B + [0] * m)
    M = Matrix(ZZ, M)
    L = M.LLL()
    res = L[0][m:]
    return res
def solve_LWE_mod_p(A,B,p):
    pIr = p*identity_matrix(r)
    A = block_matrix([[pIr], [A.transpose()]])
    M = []
    m=len(A)
    n=len(B)
    assert len(A[0])==n
    for i in range(m):
        M.append(A[i] + [0] * i + [1] + [0] * (n - 1 - i))
    M.append(B + [0] * m)
    M = Matrix(ZZ, M)
    L = M.LLL()
    res = L[0][m:]
    
    

from sage.modules.free_module_integer import IntegerLattice
from random import randint
import sys
from itertools import starmap
from operator import mul

# Babai's Nearest Plane algorithm
# from: http://mslc.ctf.su/wp/plaidctf-2016-sexec-crypto-300/
def Babai_closest_vector(M, G, target):
  small = target
  for _ in range(1):
    for i in reversed(range(M.nrows())):
      c = ((small * G[i]) / (G[i] * G[i])).round()
      small -= M[i] * c
  return target - small

m = 
n = 
q = 

A_values = 
b_values = 

A = matrix(ZZ, m + n, m)
for i in range(m):
  A[i, i] = q
for x in range(m):
  for y in range(n):
    A[m + y, x] = A_values[x][y]
lattice = IntegerLattice(A, lll_reduce=True)
print("LLL done")
gram = lattice.reduced_basis.gram_schmidt()[0]
target = vector(ZZ, b_values)
res = Babai_closest_vector(lattice.reduced_basis, gram, target)
print("Closest Vector: {}".format(res))

R = IntegerModRing(q)
M = Matrix(R, A_values)
ingredients = M.solve_right(res)

print("Ingredients: {}".format(ingredients))

for row, b in zip(A_values, b_values):
  effect = sum(starmap(mul, zip(map(int, ingredients), row))) % q
  assert(abs(b - effect) < 2 ** 37)

print("ok")

Babai(CVP)

def Babai(B, t):
    # not square when using .LLL(), so use IntegerLattice ...
    B = IntegerLattice(B, lll_reduce=True).reduced_basis
    G = B.gram_schmidt()[0]
    b = t
    for i in reversed(range(B.ncols())):
        b -=  B[i] * ((b * G[i]) / (G[i] * G[i])).round()
    return t - b

br = Babai(M, b)
print('e = %s' % (b-br))
R = IntegerModRing(p)
Ar = matrix(R, mx)
secret = Ar.solve_right(br)

m = ''.join(chr(x) for x in secret)
print('m = %s' % m)

历年题目

2020 祥云杯 easy matrix

#!/usr/bin/env sage
from sage.modules.free_module_integer import IntegerLattice
import numpy as np

def Babai(B, t):
    # not square when using .LLL(), so use IntegerLattice ...
    B = IntegerLattice(B, lll_reduce=True).reduced_basis
    G = B.gram_schmidt()[0]
    b = t
    for i in reversed(range(B.ncols())):
        b -=  B[i] * ((b * G[i]) / (G[i] * G[i])).round()
    return t - b

mx = list(np.load('./matrix.npy'))
rt = list(np.load('./result.npy'))

A = matrix(ZZ, mx)
b = vector(ZZ, rt)
p = 2129
r = A.nrows()
c = A.ncols()

pIr = p*identity_matrix(r)
#M = block_matrix([[A.transpose()], [pIr]])  # [x, k]*[[A.t], [pIr]] = (b-e).t  (but not work ...
M = block_matrix([[pIr], [A.transpose()]])  # [k, x]*[[pIr], [A.t]] = (b-e).t   (this works ...
br = Babai(M, b)

print('e = %s' % (b-br))
R = IntegerModRing(p)
Ar = matrix(R, mx)
secret = Ar.solve_right(br)

m = ''.join(chr(x) for x in secret)
print('m = %s' % m)