背包问题 己知一长度b的背包及长度分别为a1,a2,…,an的n 个物品。假定这些物品的半径和背包相同，若从这个物品 中选出若干物品使得恰好装满这个背包。 公式化的描述为：给定一个正整数集A={a1,a2,,an},已 知b是A的某子集中元素的和。问题是，找到一个n元的0、1 向量X=(K1,X2,Xn)使得： 这是一个NP问题。 ∑ax=b i= 其中a1,a2,…，an 和b都是正整数。 13 CNR@HEU http://machunguang.hrbeu.edu.cn
背包问题 已知 长度 一 b 的背包及长度分别为 的背包及长度分别为 a1,a2,… ,an 的 n 个物品。假定这些物品的半径和背包相同，若从这 n 个物品 中选出若干物品使得恰好装满这个背包。 公式化的描述为：给定一个正整数集A={a1,a2,…,an 公式化的描 为 给定 个 数集 { 1, 2, , n}，已 知b是A的某子集中元素的和。问题是，找到一个n元的0 、1 向量X=(x1,x2,…,xn)使得： ∑ = n a x b 这是一个NP问题。 ∑ = = i a i x i b 1 13 其中a1, a2, … , an 和 b 都是正整数
超递增序列 如果序列a1,a2,…，an满足条件： a,>∑a,i=2,3nm) i=1 则称该序列为超递增序列。 例如： {1,2,4,8,…,2n} {1,3,6,13,27,52,…} 而{1,3,4,9,15,25}不是。 如果序列为超递增序列，则背包问题则是P类问题。 14 CNR@HEU http://machunguang.hrbeu.edu.cn
超递增序列 如果序列 a1, a2, … , an 满足条件： ( 2 3 ) 1 a a i n i > ∑ = − 则称该序列为超递增序列。 ( 2,3,..., ) 1 a a i n j i > ∑ j = = 例如： {1，2，4，8， … ，2n } {1，3，6，13，27，52， …} 而 {1，3，4，9，15，25} 不是。 如果序列为超递增序列 则背包问题则是P类问题 14 如果序列为超递增序列，则背包问题则是P类问题
MH背包密码的基本思想 利用实际上存在两类不同的背包问题，一类在线性时间 内可解（超递增背包问题），而另一类不能（普通背包问题）。 易解的背包问题可以转化成难解的背包问题。公钥使用难解 的背包问题，它可很容易地被用来加密明文但不能用来解密 密文。私钥使用易解的背包问题，它给出一个解密的简单方 法。不知道私钥的人要破解密文就不得不解一个难解的背包 问题。 将消息编码为背包问题的解。明文分组长度等于堆中物 品个数，且明文位与b的值相对应，密文是计算得到的和值。 15 CNR@HEU http://machunguang.hrbeu.edu.cn
MH背包密码的基本思想 背包密码的基本思想 利用实际上存在两类不同的背包问题，一类在线性时间 内可解(超递增背包问题)，而另一类不能 ，而另一类不能(普通背包问题)。 易解的背包问题可以转化成难解的背包问题。公钥使用难解 的背包问题，它可很容易地被用来加密明文但不能用来解密 密文。私钥使用易解的背包问题，它给出一个解密的简单方 法。不知道私钥的人要破解密文就不得不解一个难解的背包 问题。 将消息编码为背包问题的解。明文分组长度等于堆中物 品个数，且明文位与b的值相对应，密文是计算得到的和值。 15 品个数，且明文位与b的值相对应，密文是计算得到的和值
公私钥对的生成 公开的背包序列a1,a2,…,an是由超递增序列 b1,b2,…,b。进行以下变换得到的。 选取素数p和u,且p>∑b,,1≤u≤p-1。 u与v关于modp 运算，互为逆 利用已知u并根据uv=1(modp),可求得v。 元！ 下面作变换称为墨科-赫尔曼(Merkle-Hellman)变换： ay=ubr (mod p),k=1,2,.,n 非超递增序列{a}和p作为公钥； 超递增序列{b:}和v作为私钥； 16 CNR@HEU http://machunguang.hrbeu.edu.cn
公私钥对的生成 公开的背包序列 公开的背包序列 a1,a2,…,an 是由超递增序列 是由超递增序列 b1,b2,…,bn 进行以下变换得到的 进行以下变换得到的。 n 选取素数p和u,且 ， 。 利用已知u并根据uv=1 (mod p) 可求得v 1 n i i p b = > ∑ 1 1 ≤ u p ≤ − 利用已知u并根据uv=1 (mod p) ，可求得v。 下面作变换称为墨科 下面作变换称为墨科-赫尔曼(Merkle-Hellman)Hellman)变换： ak≡ubk（mod p），k=1,2,…,n 非超递增序列{ai}和p作为公钥； 超递增序列{bi}和v作为私钥； 16 u与v关于mod p 运算，互为逆 元！
使用greed算法求解背包问题！见 加解密的实现过程 教材page99 消息m=m1m2.mn是n位0,1二进制串 加密过程： c=am+a2m2+...+anmn c是消息m的密文 解密过程： 解密过程就是解背包问题，即已知超递增序列（私钥）和背包容量 (c),求解m(m1m2.mn) 利用超递增序列{b}求vc的解，可得消息m。 这是因为vc=vam1+va2m2+.+V anmn bim+b2m2+...+bnmn uv=1(mod p)ak=u bk (mod p)by=vak (mod p)(k=1,...,n) CNR@HEU http://machunguang.hrbeu.edu.cn
加解密的实现过程 消息m=m1m2 … mn 是n位0，1 二进制串 加密过程： c=a1m1 + a2m2 + … + a+ … + anmn c 是消息 m 的密文 解密过程： 利用超递增序列{ bi }求 vc 的解 ，可得消息m。 (这是因为 vc =va1m1 + va2m2 + … +v a+ … +v anmn = b1m1 + b2m2 + … + b+ … + bnmn ) uv≡1 (mod p) ak≡u b k (mod p) b(mod p) bk≡vak (mod p) (k =1,…,n) 17 uv 1 (mod p) a k u b k (mod p) b k vak (mod p) (k 1,…,n) 解密过程就是解背包问题，即已知超递增序列(私钥)和背包容量 (vc)，求解m(m1m2...mn) 使用greed 算法求解背包问题！ 见 教材page 99