lwe_误差学习

lwe是格问题的一种，简单描述就是使用使用格基规约在已知矩阵、目标向量的情形下求出误差向量，并从而得到初始向量

从cvp问题的角度来看这个问题就是在由A的列向量构成的格空间里找B的最近向量

误差向量

误差来自一些导致式子出现了数据错误的操作，比如浮点数转化为整型的时候丢失了小数部分，这时候就产生了误差

误差向量则是对应的初始向量在矩阵中计算后经过上述操作之后导致所得到的向量和目标向量之间的误差

原理

通常情况下有如下的一个矩阵乘法

latex
A\vec {x}  = \vec{b}

产生误差

latex
A\vec {x} + \vec{e}  = \vec{b}

构建矩阵如下

latex
\begin{pmatrix}
 x_{1*n} & 1 \\

\end{pmatrix}
\begin{pmatrix}
 A_{n*n} & 0_{n*1} \\
 -b_{1*n} & 1 
\end{pmatrix}
=
\begin{pmatrix}
e_{1*n} &1
\end{pmatrix}

例题

susctf2022InverseProblem

题目

import numpy as np
from secret import flag

def gravity(n,d=0.25):
    A=np.zeros([n,n])
    for i in range(n):
        for j in range(n):
            A[i,j]=d/n*(d**2+((i-j)/n)**2)**(-1.5)
    return A

n=len(flag)
A=gravity(n)
x=np.array(list(flag))
b=A@x
np.savetxt('b.txt',b)

分析

exp

import numpy as np

def gravity(n,d=0.25):
    A=np.zeros([n,n])
    for i in range(n):
        for j in range(n):
            A[i,j]=d/n*(d**2+((i-j)/n)**2)**(-1.5)
    return A

enc = []
with open("C:\\Users\\Menglin\\Desktop\\b.txt","rb") as f:
    for line in f.readlines():
        enc.append(float(line.strip().decode()))

b = enc
n = 85
multiple = 10 ^ 20
A = gravity(n)

A = [[int(j * multiple) for j in i] for i in A]
b = [int(i * (-1) * multiple) for i in b]
M = [A[i] + [0] for i in range(n)]
M.append(b + [1])
M = Matrix(ZZ, n + 1, n + 1, M)
ans = M.LLL()[0]
# print(ans)
flag = M.solve_left(ans)
# print(bytes(flag))
print(bytes(flag[:-1]).decode())

rlwe

lwe的一个主要问题是它需要很大的密钥。要加密一位消息，需要在参数中使用大小为n^2的公钥，所以后面就有了rlwe体制,由于使用了多项式,所以每一项都会显得小很多

还没做过相关题目，以后做到了会在个人博客更新的

agcd(近似最大公约数问题)

原理分析

the Approximate Common Divisor Problem

这也是一个误差导致的问题

已知x1,x2,...,xn满足如下式子

latex
\begin{cases}
  x_1 = p*q_1  \\
  x_2 = p*q_2  \\
  \vdots       \\
  x_n=  p*q_n
\end{cases}\\

这种情况下如果想要求出p的值就只需要进行gcd操作，非常的简单

但是有的情况下这里面会混入一些噪声数据

latex
\begin{cases}
  x_1 = p*q_1 + e_1  \\
  x_2 = p*q_2 + e_2 \\
  \vdots       \\
  x_n=  p*q_n + e_n
\end{cases}\\

简单点说就是一个公因数因为误差求不出来了，所以使用格的方法来求这个公因数

部分攻击方法

OL 格攻击

概念看着有些复杂，我的理解是构造出格然后进行规约，用规约后的数据再造一个子格，然后再做规约得到目标向量
构造如下的一个格子

latex
\begin{pmatrix}
1 &         &   & a_1   \\
  & \ddots  &   & \vdots \\
  &         & 1 & a_{n-1} \\
  &         &   & a_n
\end{pmatrix}_{n*n}

对这个格进行规约可以得到一组基，然后使用这组基得到多组线性无关的向量组成一个核空间，然后对这核空间再求核就得到了需求的q向量，然后也即可以求出p

例题

2023 DASCTF X 0psu3 FindPrime

题目

from Crypto.Util.number import *
from gmpy2 import *
P=getPrime(int(512))
p_list=[]
for i in range(30):
    q=getPrime(1024)
    r=getPrime(450)
    l=q*P+r
    p_list.append(l)
path1="D:/CTF题目\密码\出题1/"
with open("output.txt",'w')as f1:
    for val in p_list:
        f1.write(str(val))
        f1.write("\n")


Q=getPrime(512)
N=P*Q
e=e1*e2
m=bytes_to_long(flag2)
c=pow(m,e,N)
assert m<N
print("N=",N)
print("e=",e)
print("c=",c)



#N=68770027076980723946939075792572969610228738501865973895618044035550466673326811210718966610231582633896160130057212343512606374318082678735227998163020559923237005947682357783487924911009663067842443440348588088325506801639924926097944176357432282915587075930988972621730524537492705984723766652062305363027
#e=30899846873
#c=46935517038224473812546067305866276864169387205589347201858550096671613860700878462369638807831295923952343159795466895818221029692119135003812788250010552362110290387383510093277209478665971066986914981717774698233220968427990066291572377851164878122374241804989577737820368814455456808941766309324614067608

分析

for i in range(30):
    q=getPrime(1024)
    r=getPrime(450)
    l=q*P+r
    p_list.append(l)

这一段很容易看出是考察agcd的部分，使用如前面介绍的方法获取P，然后就是一个使用AMM算法的rsa题目了

exp

agcd部分

#sage
with open(path1+"output.txt","r")as f1:
    f1=f1.readlines()
p_list=[]
for val in f1:
    p_list.append(int(val.strip()))
n=len(p_list)
M=Matrix(ZZ,n,n)
M[0,0]=2^450
for i in range(1,n):
    M[0,i]=p_list[i]
    M[i,i]=-p_list[0]
ans = M.LLL()[0]
# print((ans))
Q = []
Q.append(ans[0]>>450)
for i in range(1,len(ans)):
    Q.append(-(ans[i]-Q[0]*p_list[i])//p_list[0])
print(Q[0])
P =p_list[0] // abs(int(Q[0]))
N=68770027076980723946939075792572969610228738501865973895618044035550466673326811210718966610231582633896160130057212343512606374318082678735227998163020559923237005947682357783487924911009663067842443440348588088325506801639924926097944176357432282915587075930988972621730524537492705984723766652062305363027
e=30899846873
c=46935517038224473812546067305866276864169387205589347201858550096671613860700878462369638807831295923952343159795466895818221029692119135003812788250010552362110290387383510093277209478665971066986914981717774698233220968427990066291572377851164878122374241804989577737820368814455456808941766309324614067608

Q=N//P

AMM部分

#sage
R.<x>=Zmod(P)[]
f=x^e1-int(m)
x1=f.roots()
list1=[]
for i in x1:
    list1.append(int(i[0]))
len(list1)
R.<y>=Zmod(Q)[]
f1=y^e1-int(m)
x2=f1.roots()
list2=[]
for i in x2:
    list2.append(int(i[0]))
len(list2)