简单算法 0-1背包问题:1972年由Karp提出的,已知向量 A=(a1,a2,an),其中a为正整数, 称其为背包向量。给定向量x=(x1,x2,,xn),x,∈{0,1} 求和S=∑x很容易,只需要n-次加法。但已知A 和S,求测非常困难,称其为背包问题,又称子 集合问题。用穷举搜索法,有”种可能,n非常 大时,相当困难。背包问题是一个NP完全问题 2021-2-20 西大字
2021-2-20 26 A a a an , ,..., 1 2 a i x x1 , x2 ,..., xn , xi 0,1 i i S ax A S n 2 x
简单算法 用背包问题构建公钥密码,关键在于有两类 背包,一类可以在线性时间内求解,而另 类则不能。把易解得背包问题转换成难解的 背包问题,便可实现。即 公开密钥使用难解的背包问题 私钥使用易解的背包问题 2021-2-20 西大字
2021-2-20 27 • 用背包问题构建公钥密码，关键在于有两类 背包，一类可以在线性时间内求解，而另一 类则不能。把易解得背包问题转换成难解的 背包问题，便可实现。即 – 公开密钥使用难解的背包问题 – 私钥使用易解的背包问题
单算法 易解的背包即简单背包:又名超递增背包,若背包向量 A=(a1,a2,an)满足a>2a,1=12…N 称为超递增背包向量,相应背包为简单背包 简单背包很易求解,因为给定A=(a1a2,,an)及S, 易知 1 S 0◇→S<a 由此可得出解此背包的所谓贪心算法。先取最大的放入 背包,若能放入,则另相应的x,为1,否则另相应 为0。从中减去,再试,以此类推,直到决定出x,的取 值。 2021-2-20 西大字
2021-2-20 28 • 易解的背包即简单背包：又名超递增背包，若背包向量 满足 称为超递增背包向量，相应背包为简单背包。 简单背包很易求解，因为给定 及 , 易知 由此可得出解此背包的所谓贪心算法。先取最大的放入 背包，若能 放入，则另相应的 为1，否则另相应 为0。从中减去，再试，以此类推，直到决定出 的取 值。 A a a an , ,..., 1 2 1 1 , 1,2 i j ai a j i N A a a an , ,..., 1 2 S n n n S a S a x 0 1 n x 1 x
简单算法 转换背包( Merkle- Hellman陷门背包):这一体制的基 本想法是将一个简单背包进行伪装,使得对所有其他人 为一个困难背包,而对合法用户则为简单的背包。构造 方法如下: (1)各用户随机地选择一个超递增序列 =(a10,a2 a)o (2)将其进行随机排列得到矢量 aN (3)随机地选择两个整数和w使 22aN0 ≥∑ 2021-2-20 西大字
2021-2-20 29 • 转换背包（Merkle-Hellman陷门背包）：这一体制的基 本想法是将一个简单背包进行伪装，使得对所有其他人 为一个困难背包，而对合法用户则为简单的背包。构造 方法如下： （1）各用户随机地选择一个超递增序列 A0=(a1 0 ,a2 0 , …, aN 0)。 （2） 将其进行随机排列得到矢量 A’=(a1 ’ ,a2 ’ , …, aN ’)。 （3）随机地选择两个整数u和w使 u2aN 0 N i i u a 1
简单算法 且 gcd(u, w)=1 O<Ku 由 Euclidean算法可得出a,b且1=au+bw,由此 可得出bW≡1modu,即W1= b mod u (4)计算a=·ai,modu,i=1,…,M构造出 新的(难的)背包矢量A=(a1,…,aN) (5)陷门信息为u和w1。且用户收到加密信息 且,先转成为整数S,而后计算S=(W1·S) modl且最后可由简单背包 s=∑ 解出x=(x1 1929。9N) 2021-2-20 西大字
2021-2-20 30 Euclidean a，b 1=au+bw bw 1 mod u，即 w -1 b mod u ai=w ai ’ mod u,i=1, …, N A=(a1 , …, aN)。 u w-1 y ， S S’=(w - 1 S) mod u x=(x1 , x2 ,…, xN ) N i i i S x a 1