背包算法简介 >由默克尔 (Merkle)和赫尔曼(Hellman)提出的; >最早提出的公开密钥算法; >安全性源于背包问题,是一个NP问题; >大部分是不安全的,很少使用; 12 CNR@HEU http://machunguang.hrbeu.edu.cn
背包算法简介 ¾由默克尔(Merkle)和赫尔曼(Hellman Hellman)提出的; ¾最早提出的公开密钥算法; ¾安全性源于背包问题,是一个NP问题; ¾大部分是不安全的,很少使用; 12
背包问题 己知一长度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并根据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