密码学 - 公钥密码学的背包算法 1
众所周知，公钥密码体制又称为非对称密码体制，它是基于以下三个数学问题而建立的通用公开密钥密码体制：
大数分解的难度（RSA）
离散对数难解性
椭圆曲线离散对数硬度 (ECC)
1.背包算法
本文不介绍以上三类公钥密码体制，而是介绍在公钥密码出现之前就存在的公钥加密算法：背包算法；
背包算法是由和开发的一种背包算法，只能用于加密，后来被和改进，也可以用于数字签名；
背包算法的安全性源于背包问题，背包问题是一个NP完全问题，但后来发现该算法并不安全，不过由于它证明了如何在公钥密码学中使用NP完全问题，所以值得借鉴。
这里介绍一下什么是背包算法：
描述：给定一个物品，每个物品的重量不同，你能将其中几个物品放入背包中以达到给定的重量吗？
公式描述：给定一系列值M1，M2，…，Mn和一个S值，计算bi，使得其满足：
S = b1 M1 + b2M2 + ... + bnMnS=b1M1+b2M2+...+bnMn
bibi值可以为0或者1，1表示物品在背包中，0表示不存在；
我们来看一个简单的例子：
这些物品的重量分别为 1、5、6、11、14 和 20。你可以用 5、6 和 11 组装一个重量为 22 的背包，但不可能组装一个重量为 24 的背包。
一般来说，解决这个问题所需的时间似乎随着项目数量的增加而呈指数增加；
-背包算法的思想是将消息编码为背包问题的解。明文块的长度等于堆中的项数，明文位对应于b的值。密文是计算出来的和。下图是示例中利用背包问题加密的一段明文；
实际上，背包问题有两种不同类型：
线性时间内可解；
无法在线性时间内解决；
易解的背包问题可以修改为难解的背包问题。公钥采用难解的背包问题，可以很方便地加密明文，但不能解密密文。私钥采用易解的背包问题，并给出了简单的解密方法。不知道私钥的人必须解决难解的背包问题才能破解密文。
2.超级加大背包
对于容易解决的背包问题，可以选择超递增序列，则相应的背包问题就很容易解决了。
超递增序列：每个项都大于前面所有项的总和。例如，{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在背包里。
具有非超递增序列的背包问题是一个难题，没有快速算法可以解决。确定哪个物品在背包中的唯一方法是依次测试所有解决方案，直到找到正确的解决方案。对于背包中物品超递增的问题，最快的算法仍然很难，因为当你将一个物品添加到序列中时，解决方案只需要再进行一次操作。
-背包算法就是利用了这个性质，私钥是超递增背包问题的权重序列，公钥是具有相同解的普通背包问题序列，并设计了一种方法，将超递增背包问题转化为普通背包问题，利用模运算完成这种转化。
3. 根据私钥生成公钥
以下是使用背包算法从私钥生成公钥的方法：
取一个递增序列，如{2, 3, 6, 13, 27, 52}，将所有项乘以 n，然后以 m 作为模数进行模运算。这个模数应该大于序列中所有数字的总和，如 105。乘数应该与序列中的任何数字都没有共同的因子，如 31。因此，一般的背包序列为：
2*31 = 623*31 = 936*31 = 8113*31 = 8827*31 = 10252*31 = 37
因此最终的背包结果是{62,93,81,88,102,37}。
超递增背包序列即为私钥，得到的背包序列即为公钥。
4.加密过程
要加密二进制消息，首先将其分成多个块，长度等于背包序列中详细说明的长度。然后，使用 1 表示物品存在，使用 0 表示物品不存在，并计算背包的总重量。对所有块重复此操作。
例如，如果消息是二进制数，则使用上述背包算法的加密过程如下：
消息 =
对应93+81=174
对应62+93+88+37=280
对应62+81+88+102=333
因此密文为174,280,333
5.解密过程
接收者知道私钥：原始的超增量背包，用于将其转换为一般背包的 n 和 m 的值。要解密消息，接收者必须先计算 n^{-1}n−1 以满足 n*n^{-1} == 1 mod mn∗n−1==1modm。将密文值的每一项乘以 n^{-1}n−1 模 m，然后除以私人背包即可得到明文。
在这个例子中，超递增背包：
{2, 3, 6, 13, 27, 52}
m = 105，n = 31，密文消息为 174,280,333。n^{-1} = 61n−1=61，因此必须将密文值乘以 61 模 105。
174*61 mod 105=9=3+6对应；
对应280*=70=2+3+13+52；
333*61 mod 105=48=2+6+13+27对应；
因此恢复的明文是
6. 实际实施方案
仅包含 6 个物品的背包序列，即使对于非超递增序列，求解该序列问题也不是很困难。实际的背包算法至少应包含 250 个物品。在超递增背包中，每个值通常为 200-400 位。模数通常为 100-200 位。在实际使用中，算法使用随机序列生成器来生成这些值。
试图用暴力攻击来破解这样的背包是毫无意义的。即使计算机每秒可以计算 100 万次，也需要 10^{46}1046 年才能尝试完所有可能的背包值。
7.背包安全
既然上面说了即使使用暴力攻击也无法破解，那么为什么该算法被证明是可破解的呢？
在某些情况下，背包算法是可以被破解的，具体可以参考相关文献。