分类： HSSP

AHSSP

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)

2026年3月17日

HSSP

基础知识前导：

右零空间：对于一个矩阵A,存在矩阵B使A*B=0,B是A的右零空间

特征：

对于 $h=a*A mod M$ ,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’流来控制大小

(e**T,t)*B=(2Xi-e)(列向量）（Xi为A的每一行）

这个时候可以对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

2026年3月17日