背包密码

原理

背包问题

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

$\\sum^n\_{i=1}x\_ia\_i=S,x\_i\\in \\{0,1\\}$sumn_i=1x_ia_i=S,x_iin0,1

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

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

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

背包加密

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

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

公钥：选取$B>\\sum\_{i=1}^na\_i$B>sum_i=1na_i，确定$A,gcd(A,B)=1$A,gcd(A,B)=1，生成公钥序列$\\{M\_i\\},M\_i=Ar\_i\\ mod\\ B$M_i,M_i=Ar_imodB

加密：计算$S=\\sum^n\_{i=1}x\_iM\_i$S=sumn_i=1x_iM_i

背包解密

$S’=A^{-1}S=\\sum^n\_{i=1}x\_ir\_i\\ mod\\ B$S’=A−1S=sumn_i=1x_ir_imodB

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

攻击

通解

对于$\\frac{n}{log\_2\\ max(M\_i)}<0.9480$fracnlog_2max(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互补的。也就说要根据题给的明文长度再次限制答案。