背包密码

原理

背包问题

有一个背包承重为$S$S，对于$n$n个物品，每个物品的重量是$a_i$ai​。问选择哪些物品可以正好放满。写作数学式子就是

$\sum^n_{i=1}x_ia_i=S,x_i\in \{0,1\}$∑i=1n​xi​ai​=S,xi​∈{0,1}

这是一个NP完全问题，也就是说在一般情况下求解的时间复杂度是$O(n^2)$O(n2)，近乎不可求

然而显然可知，对于超递增序列来说在多项式时间内是可解的。

超递增序列：有序列$\{a_i\}${ai​}且$\forall a_i > \sum^{i-1}_{k=1}a_k$∀ai​>∑k=1i−1​ak​。

背包加密

明文处理：将明文改写成二进制数列$\{x_i\},x_i\in \{0,1\}${xi​},xi​∈{0,1}

私钥：选取一个超递增序列$\{r_i\}${ri​}作为私钥

公钥：选取$B>\sum_{i=1}^na_i$B>∑i=1n​ai​，确定$A,gcd(A,B)=1$A,gcd(A,B)=1，生成公钥序列$\{M_i\},M_i=Ar_i\ mod\ B${Mi​},Mi​=Ari​ mod B

加密：计算$S=\sum^n_{i=1}x_iM_i$S=∑i=1n​xi​Mi​

背包解密

$S’=A^{-1}S=\sum^n_{i=1}x_ir_i\ mod\ B$S’=A−1S=∑i=1n​xi​ri​ mod B

即可通过超递增序列求解。

攻击

通解

对于$\frac{n}{log_2\ max(M_i)}<0.9480$log2​ max(Mi​)n​<0.9480有通解。

可以构造如下的格

$(x_1,x_2,\dots,x_n,-1)\begin{pmatrix} 2& 0& \dots& 0& M_1\\ 0& 2& \dots& 0& M_2\\ \vdots&\vdots&\ddots&\vdots&\vdots\\ 0& 0& \dots& 2& M_n\\ 1& 1& \dots& 1& S\\ \end{pmatrix}=(2x_1-1,2x_2-1,\dots,2x_n-1,0)$(x1​,x2​,…,xn​,−1)​20⋮01​02⋮01​……⋱……​00⋮21​M1​M2​⋮Mn​S​​=(2x1​−1,2x2​−1,…,2xn​−1,0)

M = [?]
S = ?

ge = Matrix(ZZ,len(M)+1)
for i in range(len(M)):
    ge[i,i] = 2
    ge[i,-1] = M[i]
    ge[-1,i] = 1
ge[-1,-1] = S
Ge = ge.LLL()[0]
print(Ge)

m = ""
for i in Ge[:-1]:
    m += str(((i+1)//2^^1))
print(m)
print(int(m,2))

注意：我在实际运用过程中对于不同的实际情况，不同的构造，不同的规约方式（LLL，BKZ），发现会有两种答案的产生，并且这两个答案是01互补的。也就说要根据题给的明文长度再次限制答案。