密码学第四章课件.pptxVIP

本科生必修课《现代密码学》第四章 公钥密码主讲教师：董庆宽 副教授研究方向：密码学与信息安全电子邮件：qkdong@个人主页：/qkdong/ 第四章 公钥密码内容提要4.1 公钥密码常用知识和算法4.2 公钥密码体制的基本概念4.3 RSA算法4.4 Rabin体制 4.5 背包体制4.6 NTRU公钥密码系统4.7 ElGamal密码体制与DH密钥交换4.8 椭圆曲线密码体制4.9 基于身份的密码体制4.10公钥密码体制的可证明安全性/第四章 公钥密码：4.1 公钥密码常用知识和算法4.1 公钥密码常用知识和算法一、基本数学知识群、环、域、素数模运算费尔马定理ap-1=1 mod p ，p是素数欧拉函数?(n)：小于n的且与n互素的正整数个数a?(n)=1 mod n 素性检验1.爱拉托斯散筛法(Eratosthenes)依次删去小于 素数的倍数2. Miller-Rabin概率检测法3.AKS欧几里得算法、扩展欧几里德算法求最大公约数和乘法的逆元中国剩余定理求一次同余方程组的解离散对数，本原根平方剩余计算复杂性/第四章 公钥密码：4.1 公钥密码常用知识和算法4.1 公钥密码常用知识和算法二、扩展欧几里得算法，有限域上求逆元计算d mod f 的逆元1. (X1, X2, X3)?(1, 0, f); (Y1, Y2, Y3)?(0, 1, d);2. if Y3=0, then return X3=gcd(f, d) //此时无逆元3. if Y3=1, then return Y3=gcd(f, d); Y2=d-1 mod f4. Q=?X3/Y3?5. (T1, T2, T3)?(X1-QY1, X2-QY2, X3-QY3); 6. (X1, X2, X3)?(Y1, Y2, Y3)7. (Y1, Y2, Y3) ? (T1, T2, T3)8. goto 2/第四章 公钥密码：4.1 公钥密码常用知识和算法4.1 公钥密码常用知识和算法三、Miller-Rabin概率检测法，找大素数原理：若p是大于2的素数，则x2=1 mod p只有1和-1两个解，所以如果方程x2=1 mod p有一解x0?{-1, 1}，那么p不为素数算法：(an是随机选择的一个数，n是待检验的数，返回False则一定不是素数，返回True则不一定是素数）令d=1；n-1的二进制表示为bkbk-1…b0for i=k downto 0 do { x?d;d?(d?d) mod n; (此时d刚好是x的平方) if d=1 and x?1 and x?n-1 then return False; if bi=1 then d?(d?a) mod n;}if d?1 then return False;Return True; 循环结束后有d=an-1 mod n，若d?1，则n不是素数。 x?1 and x?n-1 意指x2=1 mod p有不在{-1, 1}中的根该测试如果进行s次，如果都是真T，则n是素数的概率最小为1-2-s/第四章 公钥密码：4.1 公钥密码常用知识和算法4.1 公钥密码常用知识和算法四、蒙哥马利算法，避免求模运算中的除法避免求模过程中复杂耗时的除法（P.L.Montgomery,1985年提出)计算TR-1 mod N(1) T=(T+MN)/R(2) IF T?N return T-N; ELSE return T其中M=(T mod R)×(N-1 mod R) mod R，且0TNR而且显然有R(R-1 mod N)+N(N-1 mod R)=1+RN(R-1 mod N)以及(N-1 mod R）可预计算，R常取2的幂一般先计算TR-1 mod N ，若R=2w，再不断左移模N 共w次可得结果/第四章 公钥密码：4.1 公钥密码常用知识和算法4.1 公钥密码常用知识和算法蒙哥马利模乘算法计算Z=XYR-1 mod M输入：X=(XNw-1 ,…, X0)r， Y=(YNw-1 ,…, Y0)r，M=(MNw-1 ,…, M0)r， M?=-(M0)-1 mod r ，其中0?X, Y ?M，2N-1?M?2N， r =2w，gcd(M, r)=1，Nw=?N/w?/第四章 公钥密码：4.2 公钥密码体制的基本概念4.2 公钥密码体制的基本概念公钥密码体制的出现在密码学史上是一个最大的而且是惟一真正的革命。为密码学发展提供了新的理论和技术基础公钥密码算法基本工具不再是代换和置换，而是数学函数以非对称的形式使用两个密钥，两个密钥的使用对必威体育官网网址性、密钥分配、认证等都有着深刻的意义。公钥密码体制的概念是在解决单钥密码体制中最难解决的两个问题时提出的，即密钥分配和数字签字/第四章 公钥密码：4.2 公钥密