1.背包问题

    背包问题(Knapsack problem)是一种组合优化的NPC完全问题。问题可以描述为：给定一组物品，每种物品都有自己的重量和价格，在限定的总重量内，我们如何选择，才能使得物品的总价格最高。问题的名称来源于如何选择最合适的物品放置于给定背包中。相似问题经常出现在商业、组合数学、计算复杂性理论、密码学和应用数学等领域中。也可以将背包问题描述为决定性问题，即在总重量不超过W的前提下，总价值是否能达到V？它是在1978年由Merkle和Hellman提出的。

    背包问题已经研究了一个多世纪，早期的作品可追溯到1897年数学家托比亚斯·丹齐格（Tobias Dantzig，1884-1956）的早期作品 ，并指的是包装你最有价值或有用的物品而不会超载你的行李的常见问题。

2.背包算法（Merkle-Hellman）

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

2.1简介

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

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

2.2分类

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

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

    1<2,
    1+2<4,
    1+2+4<8,
    1+2+4+8<16,
    ……，

那么如果我们选择这样一些数，这些数从小到大排列，如果前面所有的数加起来的值总小于后面的数，那么这些数就可以构成一个背包，我们给一个这个背包里面的某些数的和，这个数就是被加密的数，由这个背包组成这个数只有一种组合方式，这个方式就是秘密了，例如给大家一个封包（2，3，6，12，24，48），由这个背包里的某些数构成的数：86，你知道86怎么来的吗？当然，你看着背包里面的内容，可以知道是由2+12+24+48得到的，如果你没有这个背包，而是直接得到这个86，你知道组成这个86的最小的数是多少吗？你无法知道，因为加起来等于86的数非常多：85+1=86，84+2=86等等，你是无法知道的，所以，背包加密非常难破。

    2、乘法背包：乘法背包比加法背包更复杂，不仅是运算量大了很多，更重要的是你得到的一个被加密了的数据更大，一般都是上亿的，而且在许多机密的机关里面，背包的数据都不是有这个单位，而是用位。我们知道，

    1<2,    
    1*2<3,
    1*2*3<7,
    1*2*3*7<43,
    1*2*3*7*42<1765,

数字的增长还是很快的，之所以复杂，就是因为数字很大！背包的特点是：如果背包里面的数据按小到大排列，那么，前面所有数据的乘积小于后面的任何一个元素，这个就是背包的特点，是不是很简单，但是要知道乘积的数字的增长是非常快的！

3.背包密码

背包问题：超递增背包

如递增序列为1   4   6   13   27   52

首先背包质量与最大元素比较，若背包质量大，则该元素在背包中，用背包质量减去该元素质量，然后再比较下一个，以此类推，如果背包质量小，则直接比较下一个，依次类推。

例一：

如背包总重量为70，重量序列为｛1，4，6，13，27，52｝

最大质量52小于70，因此52在此背包中

下一个重量27大于70-52=18，因此27不在背包中

继续以此类推，直到总重量减少到0或者无法继续减少，则表示已经找到

此处对应的明文是110101

例二：

表3-1    英文字母表及字母的二进制表示

    取背包向量A=（43，129，215，473，903，302，561，1165，697，1523）。设待加密的明文是c=HELLO。求明文c的密文m。

为了方便阅读，在这里选用了Bash/Shell代码语言
因为背包A的长度为10，所以将明文c分成长为10比特（即两个明文字母）的分组
        HE，LL，O_
相应的二元序列为
        0100000101，0110001100，011110000
相应的十进制序列
        261，396，240
分别对以上二元序列作用于函数f
        f(261) = f(01000 00101) = 129 + 1165 + 1523 = 2817
        f(396) = f(01100 01100) = 129 + 215 + 561 + 1165 = 2070
        f(240) = f(01111 00000) = 129 + 215 + 473 + 903 = 1720
得密文为
        （2817，2070，1720）
密文破解补充（以密文2817为例）
        前提条件：已知背包向量A=（43，129，215，473，903，302，561，1165，697，1523）
        此时密文2817是背包的容积
        为了方便寻找构成容积2817的背包向量，先将背包向量A进行排序A=（43，129，215，302，473，561，697，903，1165，1523）
        最大质量   1523 ＜ 2817    剩余容量：2817 - 1523 = 1294
        下一个容量  1165 ＜ 1294    剩余容量：1294 - 1165 = 129
        .........（机器要进行依次比较，人工可以进行快速定位）  
        下一个容量  129  ≤ 129    剩余容量：129  - 129 = 0
            
        对照原背包向量A=（43，129，215，473，903，302，561，1165，697，1523）找出对应关系（1表示在包内，0则表示不在）
        对应二进制明文序列：01000 00101
        根据表3-1找出二进制对应的字母，可得明文为HE。

    解密运算分别以每一密文分组作为背包容积，求背包问题的解。为了使接收方能解密，就需要找出单向函数f（x）的陷门。为此需引入一种特殊类型的背包向量。

接例二：

    设背包向量B=（1，3，5，11，21，44，87，175，349，701）是一个超递增背包向量。k = 1590,t = 43，试解密密文m = (2817，2070，1720)

        gcd(43，1590) = 1     ①43与1590互为素数
        1590 = 43 × 37 - 1   ②求43的逆元
        gcd(37，1590) = 1     ③37与1590互为素数
        由
        37 × 2817 = 879 mod 1590，
        37 × 2070 = 270 mod 1590，
        37 × 1720 = 40  mod 1590
        得（879，270，40），依次构造（879，270，40）的背包向量
        s = 879    701 ＜ 879    剩余容量：879 - 701 = 178    x10 =  1
                   349 ＞ 178                                 x9  =  0
                   175 ＜ 178    剩余容量：178 - 175 = 3      x8  =  1
                   87  ＞ 3                                   x7  =  0
                   44  ＞ 3                                   x6  =  0
                   
                   21  ＞ 3                                   x5  =  0
                   11  ＞ 3                                   x4  =  0
                   5   ＞ 3                                   x3  =  0
                   3   ≤ 3      剩余容量：3 - 3 = 0          x2  =  1
                                                              x1  =  0
        第一个明文分组为（01000 00101）根据表三可知它对应的英文文本是HE；类似地，可以得到其他明文分组，解密结果为HELLO。

参考：

古典密码，背包密码，RSA - #哈哈哈哈哈# - 博客园