基础知识前导：
右零空间：对于一个矩阵A,存在矩阵B使A*B=0,B是A的右零空间
特征：
对于 ,a是行向量，A是目标矩阵，其中一行是flag(A是二进制流）（h,M已知，a,A未知)
思路：构造列向量u,使hu=aAu=0 mod M,具体展开得到每一行，列对应的和hiui=0 mod M
u1(h1 1
u2 h2 0 1
u3 h3 0 0 1
um hm 0 0 0 0 1
-k M 0 0 0 0 0)=
(0,u1,u2, um)
#如此构造矩阵可以得到他的右0矩阵，当A*u=0,此时u是短向量(A是短向量）根据矩阵性质：这里刚刚得到的记为LX,其维数为m-n(线代知识)
此时再用python求出他的左零空间为U,有U*t(倍数）=A
（此时不能直接对U BKA,因为他是A的进一步线性组合）
构造B=(b’1’（设为e),2U)的列向量，用‘1’流来控制大小
这个时候可以对B LLL就可以得到（2Xi-e),恢复得到A ,转译每一行可否成为有意义bit
示例题干：
from Crypto.Util.number import *
from secrets import flag
from sage.all import *
def derive_M(n):
iota=0.035
Mbits=int(2 * iota * n^2 + n * log(n,2))
M = random_prime(2^Mbits, proof = False, lbound = 2^(Mbits - 1))
return Integer(M)
m = bytes_to_long(flag).bit_length()
n = 70
p = derive_M(n)
F = GF(p)
x = random_matrix(F, 1, n)
A = random_matrix(ZZ, n, m, x=0, y=2)
A[randint(0, n-1)] = vector(ZZ, list(bin(bytes_to_long(flag))[2:]))
h = x*A
with open("data.txt", "w") as file:
file.write(str(m) + "\n")
file.write(str(p) + "\n")
for item in h:
file.write(str(item) + "\n")解题：
def checkMatrix(M, wl=[-1, 1]):
M = [list(i) for i in list(M)]
ml = list(set(flatten(M)))
return sorted(ml) == sorted(wl)
def hssp_solve(n,m,M,h):
ge1 = [[0]*m for _ in range(m)]
tmp = pow(h[0], -1, M)
for i in range(1,m):
ge1[i][0] = -h[i]*tmp
ge1[i][i] = 1
ge1[0][0] = M
Ge1 = Matrix(ZZ,ge1)
L1 = Ge1.BKZ()
Lx_orthogonal = Matrix(ZZ, L1[:m-n])
Lx = Lx_orthogonal.right_kernel(algorithm='pari').matrix()
e = Matrix(ZZ, [1] * m)
B = block_matrix([[-e], [2*Lx]])
L2 = B.BKZ()
assert checkMatrix(L2)
E = matrix(ZZ, [[1]*L2.ncols() for _ in range(L2.nrows())])
L2 = (L2 + E) / 2
assert set(L2[0]) == {0}
L2 = L2[1:]
space = Lx.row_space()
Lx2 = []
e = vector(ZZ, [1] * m)
for lx in L2:
if lx in space:
Lx2 += [lx]
continue
lx = e - lx
if lx in space:
Lx2 += [lx]
continue
return None
Lx = matrix(Zmod(M), Lx2)
vh = vector(Zmod(M), h)
va = Lx.solve_left(vh)
return Lx, va
n = ?
m = ?
M = ?
h = ?
A,a = hssp_solve(n,m,M,h)
for row in A:
ans = "".join(str(i) for i in row)
try:
print(long_to_bytes(int(ans,2)).decode())
except:
None
发表回复