[科普中国]-Merkle-Hellman背包算法

1977年，Merkle与Hellman合作设计了使用背包算法，该算法提出后密码学界提出了很多背包型加密算法1。

简介其工作原理是：假定甲想加密，则先产生一个较易求解的背包问题，并用它的解作为专用密钥；然后从这个问题出发，生成另一个难解的背包问题，并作为公共密钥。如果乙想向甲发送报文，乙就可以使用难解的背包问题对报文进行加密，由于这个问题十分难解，所以一般没有人能够破译密文；甲收到密文后，可以使用易解的专用密钥解密。

但是，在它发表几年后，就找到了攻破它的方法。即使如此，它仍然代表着一类很难问题的算法。

分类背包加密分为加法背包和乘法背包。

1、加法背包：我们知道，1