转发注明出处:http://www.cnblogs.com/0zcl/p/6111686.html

前言

本来我是想学RSA算法的，但发现太难了，不是我能理解的，于是我先看教材前面的背包算法。不出意料的话会在下一篇博客介绍下RSA算法！

背包问题介绍:

给定一些物体，每个物体有不同的重量，是否有可能将这些物体放入一个背包，使背包的重量等于一个给定的值。

• 背包算法为第一个推广的公开密钥加密算法。
• 虽然后来发现这个算法不安全，但仍值得研究，因为它表示了如何将NP完全问题用于公开密钥算法(好吧,这个我不知道是什么意思~)。

举例：

这些物体的重量分别为1,5,6,11,14,20，则可将重5，6，11的物体放入，装成一个重22的背包。但是无法装成一个重24的背包。

• 背包问题：等于一个给定的值。
• 解为选择物品装入的情况，装入用1，未装入用0.例子中对给定值22的解为{0,1,1,1,0,0}
• 这个问题需要的时间随物体的数量的增加成指数时间。

基本原理

这个算法我没有编程，时值考试月，时间紧张，等我有时间再回来搞~

首先，背包算法用于信息安全(密码法)，我们总得搞清楚什么是明文，密文，密钥吧？！

举例：

明文： 1  1  1  0  0  1　　　　 0  1  0  1  1  0　　　  　0  1  1  0  0  0  

密钥： 1  5  6  11  14  20　　 1  5  6  11  14  20　　  1  5  6  11  14  20

密文： 1+5+6+20＝32　　　   5+11+14＝30　　　　   5+6＝11

从上面可以总结：

• 明文为物品的装入情况，是1/0的序列，而且明文长度等于物体的个数，表示从中选取物体装入背包
• 密文为选取物体的质量和
• 密钥为背包问题中物品重量序列

算法安全性体现为：

若攻击者获得密文、密钥，也无法在线性时间内求明文(物品的装入情况)

算法的关键

算法的关键是有两个不同的背包重量序列，这两个重量序列对于给定的相同的值，解相同（物品的装入情况相同）

前者物品的重量列表是递增的，后者则是无序的

前者可以解密，看下面~~

1、构造递增序列背包

易解的背包问题：若物品的重量列表为一个超递增序列，则该背包问题很容易解的。

比如递增序列：1  3  6  13  27  52

 举例：

•  非递增背包是一个难问题
• 背包算法先找到一个递增背包的重量序列作为私钥，再由此构造一个序列(有相同解的一般背包问题的序列)作为公钥(重要!)

如何构造公钥呢？

2、从私钥构造公钥

 经过上面的计算，序列为：{62  93  81  88  102  37}作为公钥

 3、加密

 4、解密

 解密这里我遇到一个问题：如何求n^－1，即如何求n关于模m的逆元？？(注意:这里必须搞懂，不然下一篇博客RSA算法就肯定不懂的!)

我百度找了好多，也看了别了的博客，比如http://blog.sina.com.cn/s/blog_65a5cf5e0100nyqo.html，但我看不懂啊！！终于我找到了一个我能看懂的求逆元方法<辗转相除法求模的逆元>！(已经编程实现),下篇博客会发出来~~

为了方便我整理，我把求逆元相关的过程截图出来，大家也可以点链接去看~  ending~

……

信息安全－4:公钥密码体制之背包算法[原创]