原理

背包问题

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

$$\sum^n_{i=1}x_ia_i=S,x_i\in \{0,1\}$$

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

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

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

背包加密

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

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

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

加密：计算$S=\sum^n_{i=1}x_iM_i$

背包解密

$S’=A^{-1}S=\sum^n_{i=1}x_ir_i\ mod\ B$

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

攻击

通解

对于$\frac{n}{log_2\ max(M_i)}<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)$$

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互补的。也就说要根据题给的明文长度再次限制答案。