7.2背包公钥加密算法

1、R.Merkle和M.Hellman在1978年根据组合数学中背包问题提出了
第一个公钥密码算法。又称为MH背包算法。
2、背包问题
设有一堆物品，体积各不相同，问能否从这堆物品中找出几个正好装满一个给定容量的背包？
3、理论上讲，通过检查背包向量V的所有子集，计算出每个子集的元素之和，总可找出一个子集作为背包问题的解，因此背包问题又称为子集合问题。
当背包的长度n过大时，堆全部子集进行穷举式搜索是不可能的

有一类特殊的背包问题是容易求解的
超递增背包问题

4、背包算法的描述
背包密码**对产生的具体过程：

1、产生一个超递增向量V
2、将超递增向量V转化为非超递增向量U
3、公钥是非超递增向量U
4、私钥是转换因子t和k

5、加密变换：
1）将二进制明文消息划分成长度与非超递增向量U长度相等的明文分组b1b2…bn
2)计算明文分组向量B=（b1，b2，.。。。，bn）与非超递增向量
U=（u1，u2，。。。，un）的内积B。U=b1u1+b2u2+…+bnun

所得结果为密文
6、解密变换
1）先还原出超递增背包向量V=t的-1次方Umod k =t的-1次方tV mod k
2）再将密文BX（点乘)U模k乘以t的-1次方的结果作为超递增背包问题的背包容量，求解超递增背包问题，得到消息明文。
7、背包算法的安全性
背包算法利用难解的一般背包问题作为公开**，对明文进行加密
私有**则利用易解的超递增背包问题给出了一个解密的简单方法
8、背包算法**
基本思想：
找出一对任意的k‘和t’，使得用公开的背包向量U模k‘乘t’后得到一个超递增向量

WHY？
MH背包*公开**是由超递增向量变换而来，虽经过模乘置乱，但超递增向量内在的规律并不能完全被隐藏，给攻击者留下可乘之机

9、背包算法是第一个使公钥密码*成为现实的密码算法，他说明了如何将数学难题应用于公钥密码算法的设计
优点：加解密速度很快
缺点：不安全性