h=a*A-se mod p,行向量a,行向量xi组成的矩阵A，行向量e ,知h,e,p求s
思路大体与HSSP相同，构造正交矩阵M,使hM=aAM-seM modp
做如下的格：
M1(h1 e1 1 0 0 0 0
M2 h2 e2 0 1 0 0 0
M3 h3 e3 0 0 1 0 0
M4 h4 e4
Mm hm em 0 0 0 0 1
k1 p 0 0 0 0 0 0
k2 0 p 0 0 0 0 0)=
0 0 M1 M2 M3 Mm之后的处理和HSSP一样
脚本：
from Crypto.Util.number import *
def ahssp(h:list, e:list, n:int, m:int, p:int):
tmp = block_matrix([[vector(h).column(), vector(e).column()]])
Ge = block_matrix([[tmp, identity_matrix(m)],[identity_matrix(2)*p,zero_matrix(2, m)]])
# Ge[:,:2] *= p
L = Ge.BKZ()
M = L[:m-n,2:]
A_ = M.right_kernel().matrix()
e_ = matrix(ZZ, [1] * m)
B = block_matrix([[-e_],[2*A_]])
L = B.BKZ()
assert set(flatten(list(map(list, L)))) == {-1,1}
E = matrix(ZZ, [[1]*L.ncols() for _ in range(L.nrows())])
L = (L + E) / 2
assert set(L[0]) == {0}
L = L[1:]
space = A_.row_space()
A = []
e_ = vector(ZZ, [1] * m)
for i in L:
if i in space:
A += [i]
continue
i = e_ - i
if i in space:
A += [i]
continue
return None
A = matrix(Zmod(p), A)
L = block_matrix(ZZ, [[vector(e).column(), matrix.identity(m)],[p, zero_matrix(1, m)]])
L[:, :1] *= p
L = L.LLL()
res = []
for row in L:
if row[0] == 0:
res.append(row[1:])
M = matrix(res)
assert all(i == 0 for i in vector(e) * M.T % p)
a = (A*M.T).solve_left(vector(h)*M.T)
s = matrix(e).solve_left(a*A-vector(h))
assert len(s) == 1
return A, a, int(s[0])
if __name__ == "__main__":
p = ...
n = ...
m = ...
e = ...
h = ...
A,a,s = ahssp(h,e,n,m,p)
发表回复