高中数学选修5—3(密码学算法基础)选修课密码学9课件.pptVIP

公钥密码体制——背包公钥密码体制; 背包体制 构造公钥体制的原理;一、背包体制; 直观上： c表示背包的大小，每个数字ai表示能装到该背包中的物品的大小。问题是选择一些物品，使得它们正好填满这个背包。其中xi为1表示物品在背包中，xi为0表示物品不在背包中。; 原则上，只要有哪些信誉好的足球投注网站集合A ={a1, a2, …,an}的所有子集并检验其元素之和是否为c，则总可以决定此背包问题是否有解，若有解就一定能够找到。; 背包密码算法的思想是将消息编码为背包问题的解。明文分组长度等于堆中物品个数，且明文位与 0、1向量x相对应，密文是计算得到的和值。;定义：若对 均有 则称向量A=(a1, a2, …,an)为超递增背包向量，相应的背包问题称为超递增背包问题。 ; 给定超递增背包向量A=(a1,a2,…,an),对任意n比特明文m=(x1, x2, …,xn),由a得???密文 任何用户收到c后,都可容易地求得m：; 一般的背包问题是困难问题，而超递增背包问题是易解的。Merkle-Hellman公钥密码算法就利用这一性质。必威体育官网网址密钥是一个超递增背包向量A，公开密钥是A经过“置乱” 后的一般背包向量。; (5)加密 设明文m= (m1, m2, …,mn)；(mi=0,1);例：设M=89，A=(2，6，9，19，41)，取w=13求w-1，b，对明文 m=(10101)加密并脱密。;(1) 选取一个困难问题P；;三、现在流行的公钥密码体制;（一） 数学背景 介绍公钥密码学中用到的基本数学知识：包括初等数论、有限域、计算复杂性。 （二） RSA公钥密码 介绍RSA算法及其安全性，素性检测、因子分解算法和RSA的实现。 （三） ElGamal公钥密码 讲述ElGamal算法及其安全性分析和实现,离散对数问题的求解。;（五） 椭圆曲线公钥密码 主要介绍椭圆曲线上的基本运算、椭圆曲线公钥密码算法及其实现。;作业