密码学——公钥密码体系之背包算法1
众所周知，公钥密码，又称非对称密码，比较常见的是基于以下三种数学难题的公钥密码体制；
背包算法的安全性起源于背包难题，他是一个NP完全问题，但后来发现该算法并不安全，但是由于它证明了如何将NP完全问题用于公开秘钥密码学，因此，值得去学习。
对于易解的背包问题，可以选择超递增序列，那么相应的背包问题容易求解。
超递增序列：它的每一项都大于它之前所有项之和，例如{1，3,6，13，27，52}是一个超递增序列，而{1，3，4，9，15，25}则不是。
超递增背包问题的解很容易找到，计算其总量并与序列中最大的数比较，如果总重量小于这个数，则它不在背包中，如果总重量大于这个数，则它在背包中，背包重量减去这个数，进而考察序列中下一个最大的数，重复直到结束。如果总重量减为0，那么只有一个解，否则，无解。
例如，总重量为70的一个背包，超递增序列为{2，3，6，13，27，52}；最大重量为52，小于70，所以52在背包中，70-52 = 18，下一个重量27 >18，因此，27不在背包中，在下一个13<18，13在背包中，18-13 = 5，以此类推，再下一个，3与2均在背包中，总重量减为0，表明已求出一个解，如果这个一个M-H背包加密分组，那么对应的密文70的解为.
非超递增序列的背包是困难的问题，它们没有快速算法。要决定哪一项在背包中的唯一方法，是依次测试所有解，直到你得到正确的解为止。最快的算法仍随背包中物品超递增问题困难，对于后者，当你加入一项到序列中，求解只需要再进行一次运算。
Merkle-Hellman背包算法就是利用这个性质。私人秘钥是一个超递增背包问题的重量序列。公开秘钥是有相同解的普通背包问题的序列，Merkle和Hellman设计了一种方法可将超递增背包问题转化为普通的背包问题，它们用模运算来完成此变化。
消息 = 011000
011000对应 93 + 81 = 174
对应 62 + 93 + 88 + 37 = 280
对应 62 + 81 + 88 + 102 = 333
因此，密文为 174， 280， 333
接收者直到私人秘钥：原始的超递增背包、用于把它转换成一般背包的n和m的值，为解密消息，接收者必须首先计算出以满足。用模m乘密文值得每项，然后用私人背包对它进行划分就可获得明文。
要解决仅有6项背包序列的问题不是很难，甚至对非超增序列也是一样。实际使用的背包算法至少应该包含250项。在超递增背包中，每项值一般为200~400位。模数一般为100 ~ 200位。该算法在实际使用中，用随机序列发生器来产生这些值。
对这样的背包，试图用穷举攻击来破译是无用的。即使一台计算机每秒能计算100万次，试完所有可能的背包值，也需要年。
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容，请联系我们，一经查实，本站将立刻删除。
如需转载请保留出处：https://51itzy.com/kjqy/150032.html