高中数学选修5-3(密码学算法基础)选修课密码学9课件.ppt
《高中数学选修5-3(密码学算法基础)选修课密码学9课件.ppt》由会员分享,可在线阅读,更多相关《高中数学选修5-3(密码学算法基础)选修课密码学9课件.ppt(16页珍藏版)》请在三一文库上搜索。
1、公钥密码体制 背包公钥密码体制,背包体制 构造公钥体制的原理,主要内容,一、背包体制,下面以背包问题为例来介绍如何构造公钥密码体制。,背包问题:给定一堆物品,重量各不相同,能否将这些物品放入一个背包中,使之等于一个给定的重量?,例:这些物品的重量分别为:1,5,6,11,14,20。问能否组成重量分别为22和24的背包?,直观上: c表示背包的大小,每个数字ai表示能装到该背包中的物品的大小。问题是选择一些物品,使得它们正好填满这个背包。其中xi为1表示物品在背包中,xi为0表示物品不在背包中。,1、背包问题的数学描述 给定 n个正整数的集合A=a1, a2, ,an及正整数c,求0、1向量x
2、=(x1, x2, ,xn),使得: 其中a=(a1, a2, ,an)称为背包向量。,原则上,只要搜索集合A =a1, a2, ,an的所有子集并检验其元素之和是否为c,则总可以决定此背包问题是否有解,若有解就一定能够找到。,但注意到A的子集个数为:,背包问题是NP完全问题。,单向函数: 由集合A和0、1向量x很容易求得c; 但由集合A和c却很难求得0、1向量x,1、背包问题的数学描述,背包密码算法的思想是将消息编码为背包问题的解。明文分组长度等于堆中物品个数,且明文位与 0、1向量x相对应,密文是计算得到的和值。,例:设背包向量为:A=1,5,6,11,14,20,明文:111001 01
3、0110 100101,密文:1+5+6+20 5+11+14 1+11+20 =32 =30 =32,解密时,合法接收者也必须解背包问题;且不同明文有可能加密成同一密文。这不符合公钥密码体制的要求。,1、背包问题的数学描述,定义:若对 均有 则称向量A=(a1, a2, ,an)为超递增背包向量,相应的背包问题称为超递增背包问题。,2、利用超递增背包构造公钥密码体制,超递增背包问题是易解的。,超递增背包中的每一项都大于它之前所有项之和。,给定超递增背包向量A=(a1,a2,an),对任意n比特明文m=(x1, x2, ,xn),由a得到密文 任何用户收到c后,都可容易地求得m:,首先比较c和
4、an,若 ,则an不在该背包中xn=0;若 ,则an必在该背包中xn=1,因为所有其它分量的和a1+a2+an-1 an ,记c=c-an 。对c和an-1重复上述过程,当到达a1时,整个过程结束。若变为0,则有唯一解m ;否则无解。,例:背包A=(2,3,6,13,27,52) ,c=70,该背包的解为:110101,2、利用超递增背包构造公钥密码体制,一般的背包问题是困难问题,而超递增背包问题是易解的。Merkle-Hellman公钥密码算法就利用这一性质。保密密钥是一个超递增背包向量A,公开密钥是A经过“置乱” 后的一般背包向量。,Merkle-Hellman公钥密码算法:,(1)选取一
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 高中数学 选修 密码学 算法 基础 选修课 课件
链接地址:https://www.31doc.com/p-2076270.html