背包公钥密码体制解析

1.背包问题

在组合数学中有一个背包问题：假设有一堆物品，体积各不相同，问能否从这堆物品中找出几个正好装满一个给定容量的背包。（假定物品之间不留空隙）

记物品的体积分别为a₁，a₂，…，a_n，背包的容量为V，则背包问题可表示为

a₁x₁+a₂x₂+…+a_nx_n=V

其中，x_i（i=1，2，…，n）等于1或者0。x_i=1表示第i个物品在背包中，x_i=0表示第i个物品不在背包中，称物品体积的序列A=（a₁，a₂，…，a_n）为背包向量。

理论上讲，通过检查背包向量A的所有子集，计算出每个子集的元素之和，总可找出一个子集作为背包问题的解，因此背包问题又称为子集和问题。然而长度为n的背包向量A的全体子集共有2ⁿ个，当n很大时，对全部2ⁿ个子集进行穷举式搜索是不可能的。幸运的是并非所有的背包问题都没有有效算法，有一类特殊的背包问题是容易求解的，这就是超递增背包问题。

设背包向量A=（a₁，a₂，…，a_n）满足条件

即A中每一项都大于它前面所有项之和，则称A是一个超递增向量，或者称序列a₁，

a₂，…，a_n是一个超递增序列。

【例5-20】 可以验证，序列1，2，4，…，2ⁿ是一个超递增序列，取背包向量A=（1，2，4，

8，16，32），背包容量V=43，求解下面的背包问题：x₁+2x₂+4x₃+8x₄+16x₅+32x₆=43

【解析】 因为43＞32，则 x₆=1

将x₆=1代入上式得

x₁+2x₂+4x₃+8x₄+16x₅=11

又11＜16，则 x₅=0

再将x₅=0代入上式得

x₁+2x₂+4x₃+8x₄=11

所以该背包问题的解为

x₁=x₂=x₄=x₆=1，x₃=x₅=0

2.MH背包公钥密码体制

一个背包公钥密码体制选取一组正整数b₁，b₂，…，b_n作为公钥予以公布，明文M=m₁m₂

…m_n是n位0，1符号串。加密过程如下：C=b₁m₁+b₂m₂+…+b_nm_n解密过程是已知密文C，求解明文M=m₁m₂…m_n，等价于解背包问题。

【例5-21】 已知：b₁=28，b₂=32，b₃=11，b₄=08，b₅=71，b₆=51，b₇=43，b₈=67，M₁=

10110110，M₂=11001001，求密文。

C₁=28+11+8+51+43=141

C₂=28+32+71+67=198

1978年，由R.Merkle和M.Hellman提出了一种基于组合数学中背包问题的公钥密码体制，称为MH背包公钥密码体制。具体描述如下：

（1）参数定义和密钥生成

●私钥为将一个超递增向量A转换为非超递增向量B的参数t、t^-1和k；

●公钥为非超递增向量B。

将向量A转换为向量B的过程如下：

即t与k互素，确保t在模k下的乘法逆元t^-1存在。设

B≡t×A（modk）≡t×（a₁，a₂，…，a_n）（mod k）≡（ta₁（mod k），ta₂（mod k），…，ta_n（mod k））可知B是一个非超递增向量，B作为公钥。(www.xing528.com)

（2）加密过程

首先将二进制明文消息划分成长度与非超递增向量B长度相等的明文分组m₁m₂…m_n；然后计算明文分组向量M=（m₁，m₂，…，m_n）与非超递增向量B=（b₁，b₂，…，b_n）的内积：

C=B×M=b₁m₁+b₂m₂+…+b_nm_n所得结果为密文C。

（3）解密过程

先还原出超递增背包向量

A≡t^-1×B（mod k）

再根据密文C计算背包容量

V≡C×t^-1（mod k）

求解超递增背包问题，还原消息明文。

【例5-22】 设A=（1，3，7，13，26，65，119，267）是一个超递增背包向量，设模数k=523，乘数t=467，当明文消息M=10101100，求加密/解密过程。

【解析】 （1）加密过程

由t=467，k=523得

t^-1=28（mod 523）

计算出公钥

向外公布B。

发送方用公钥B对M加密得到密文

（2）解密过程

接收方收到密文732后，先还原出超递增背包向量

计算背包容量

解超递增背包问题

m₁+3m₂+7m₃+13m₄+26m₅+65m₆+119m₇+267m₈=99

由99＜267，99＜119，99＞65得

m₈=0，m₇=0，m₆=1

将m₆，m₇，m₈的值代入上式得

m₁+3m₂+7m₃+13m₄+26m₅=34

又34＞26，得m₅=1

所以背包问题的解为

m₁=m₃=m₅=m₆=1，m₂=m₄=m₇=m₈=0解密得到明文分组为10101100，即为原来的M。

要解决类似上例这样的背包向量仅有8个分量的背包问题并不困难，甚至对非超递增的背包向量也是如此。但实用的背包向量至少应包含250个以上的分量，每个分量的大小一般要为200～400位，模数也应为100～200位。这些值可以使用随机序列生成器来生成。对于这样的背包算法，试图用穷举式搜索攻击来破译是无用的。

3.背包公钥密码体制的安全性

背包公钥密码体制利用难解的一般背包问题作为公钥，可以方便地对明文进行加密；而私钥则利用易解的超递增背包问题给出一个解密的简单方法。那些不知道私钥的攻击者要想破译密文就不得不求解一个困难的背包问题，这在计算上看似是不可行的。背包公钥密码体制以其加密/解密速度快而引人注目，曾经在电子商务的公钥设计中具有其他技术不可替代的作用。

但背包公钥密码体制提出两年后即被破解。破解的基本思想是不必找出真正的模数k和乘数t，也不用穷举式搜索背包向量的所有子集，而是找出一对任意的k′和t′，使得用公开的背包向量B模k′乘t′后能得到一个超递增向量。究其原因是Merkle-Hellman背包体制的公钥是由超递增向量变换而来的，虽然经过模乘置乱，但超递增向量内在的规律性并不能完全被隐藏，这就给攻击者留下了可乘之机。随后Merkle又提出了多次迭代背包体制，但最终也被破解。1984年Brickell最终证明了Merkle-Hellman背包体制的不安全性，并发现了一种算法可将难解的背包问题转化为易解的背包问题。