背包密码*及python实现
1.背包问题
设A = (a
1
_1
1,a
2
_2
2,…,a
n
_n
n)是由n个不同的正整数构成的n元组，s是另一已知的正整数。背包问题就是从A中求出所有的 a
i
_i
i,使其和等于s。其中A称为背包向量，s是背包的容积。
从原则上讲，如果背包问题有解的话，通过检查A的所有子集，总可以找到问题的解。然而如果A中元素个数n很大，子集个数
2
n
2^n
2n将非常大，寻找满足要求的子集没有比穷举法更好的算法，因此背包问题是NPC问题。
2.超递增序列
由于背包问题是NPC问题，因此需引入一种特殊类型的背包向量，使得背包问题较容易去求解。
这里将介绍超递增序列，背包向量A = (a
1
_1
1,a
2
_2
2,…,a
n
_n
n)称为超递增的，如果满足a
j
_j
j>
∑
i
=
0
j
−
1
\sum_{i=0}^{j-1}
∑i=0j−1 a
i
_i
i , j = 2,…,n。超递增背包向量对应的背包问题很容易通过贪心算法求解，即已知s为背包容积，对A从右向左检查每一元素，若s≥an,则an在解中；若s<an,则an不在解中。
然而，如果敌手知道超递增背包向量，同样也很容易解密。为此可用模乘对A进行伪装，选取常量模数k和乘数t，满足 k >
∑
i
=
1
n
\sum_{i=1}^{n}
∑i=1n a
i
_i
i ,(t,k)=1，即t在模k下有乘法逆元。设bi ≡ t* a
i
_i
i mod k, i = 1,2,…,n，得到一个新的背包向量B = (b1,b2,…bn)，用户以B作为自己的公钥。
3.背包密码*
（1）**生成
选择一个超递增序列A = (a
1
_1
1,a
2
_2
2,…,a
n
_n
n)，选择随机数M，满足M>
∑
i
=
1
n
\sum_{i=1}^{n}
∑i=1n a
i
_i
i ，再选择随机数U，满足(U,M)=1且M > U，计算bi = Uai mod M, 1≤i≤n，得到公钥B = (b1,b2,…,bn)，私钥则为A,M,U。
（2）加密
明文m = (m1,m2,…,mn)是长度为n的比特串。使用公钥B = (b1,b2,…,bn)计算密文:c = m1b1+m2b2+…+mnbn。
（3）解密
计算UU-1 ≡ 1 mod M，S = U-1c mod M，由S和超递增序列A根据贪心算法即可恢复明文m。
（4）示例
有超递增序列A=(3,11,24,50,115)，选取M=250，U=113，计算bi = Uai mod M, 1≤i≤n，得到公钥B = (89，243，212，150，245)。有明文序列m=(1,0,1,0,1)，加密后有c=m1b1+m2b2+m3b3+m4b4+m5b5=546。
由UU-1 ≡ 1 mod M计算得U-1=177，S = U-1c mod M = 142，由S对A=(3,11,24,50,115)从右向左比对，142>115，则令x5=1，142-115=27<50，则x4=0，同理x3=1,x2=0,x1=1，因此得到明文m=(1,0,1,0,1)。
4.实现