西安电子科技大学：《现代密码学》课程教学资源（PPT课件讲稿）第四章 公钥密码（主讲：董庆宽）

第四章公钥密码 内容提要 ●41公钥密码常用知识和算法 ●4.2公钥密码体制的基本概念 ●43RSA算法 44 Rabin体制 45背包体制 ●4.6NTRU公钥密码系统 4.7 EIGamal密码体制与DH密钥交换 48椭圆曲线密码体制 ●49基于身份的密码体制 4.10公钥密码体制的可证明安全性 历忠毛孑技*字

内容提要  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公钥密码体制的可证明安全性 2/ 第四章 公钥密码

第四章公钥密码:4.1公钥密码常用知识和算法 4.1公钥密码常用知识和算法 ●一、基本数学知识 ●群、环、域、素数 ≥欧几里得算法、扩展欧几里 ●模运算 德算法 ●费尔马定理 求最大公约数和乘法的逆元 pl=1modp,p是素数 ●中国剩余定理 欧拉函数 求一次同余方程组的解 p(n):小于m的且与n互素的正整 数个数 ●离散对数,本原根 ap(n=1 mod n 平方剩余 ●素性检验 ●计算复杂性 1爱拉托斯散筛法( Eratosthenes 依次删去小于m素数的倍数 2. Miller- Rabin概率检测法 3.AKS 历忠毛孑技*字

4.1 公钥密码常用知识和算法  一、基本数学知识  群、环、域、素数  模运算  费尔马定理 ⚫ a p-1=1 mod p ，p是素数  欧拉函数 ⚫ (n)：小于n的且与n互素的正整 数个数 ⚫ a (n)=1 mod n  素性检验 ⚫ 1.爱拉托斯散筛法(Eratosthenes) ⚫ 依次删去小于 素数的倍数 ⚫ 2. Miller-Rabin概率检测法 ⚫ 3.AKS 3/ 第四章 公钥密码：4.1 公钥密码常用知识和算法  欧几里得算法、扩展欧几里 德算法 ⚫ 求最大公约数和乘法的逆元  中国剩余定理 ⚫ 求一次同余方程组的解  离散对数，本原根  平方剩余  计算复杂性 n

第四章公钥密码:4.1公钥密码常用知识和算法 4.1公钥密码常用知识和算法 ●二、扩展欧几里得算法,有限域上求逆元 计算 d mod f的逆元 1.(X1,X2,X3)←(1,0,0);(Y1,Y2,3)←(0,1,4); 2. if y3=, then return X3=gcd(, d) ∥此时无逆元 3 if Y3=l, then return Y=gcd(, d; Y2=d-I modf X3 5.T1, T2, T3)(X1QY1,X2Q123X3-Qr3); 6.(X1,X2,X3)(Y1,Y,Y3) 7.(Y1,Y2,Y3)←(T1,T2,T3) e8. goto 2 历忠毛孑技*字

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 f ⚫ 4. 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/ 第四章 公钥密码：4.1 公钥密码常用知识和算法

第四章公钥密码:4.1公钥密码常用知识和算法 4.1公钥密码常用知识和算法 ●三、 Miller-Rabint概率检测法,找大素数 原理:若是大于2的素数,则x2=1modp只有1和1两个解,所以如 果方程x2=1modp有一解x{-1,1},那么p不为素数 算法:(ax<n是随机选择的一个数,m是待检验的数,返回Fase则一 定不是素数,返回True则不一定是素数) 令1;n1的二进制表示为bb1…b for i=k downton do i x<-;d-( dxd)mod n;(此时刚好是x的平方) fd=1andx≠ I and x≠hn- I then return false; if bF=l then d(dxa)mod n; 3 o if dfl then return False; Return True 循环结束后有′mn-1modn,若d≠1,则n不是素数。x≠ I andx≠n-1 意指x2=1modp有不在1,1}中的根 该测试如果进行s次,如果都是真T,则n是素数的概率最小为1-23 历毛孑拌技大字

4.1 公钥密码常用知识和算法  三、Miller-Rabin概率检测法，找大素数 ⚫ 原理：若p是大于2的素数，则x 2=1 mod p只有1和-1两个解，所以如 果方程x 2=1 mod p有一解x0{-1, 1}，那么p不为素数 ⚫ 算法：(a<n是随机选择的一个数，n是待检验的数，返回False则一 定不是素数，返回True则不一定是素数） ⚫ 令d=1；n-1的二进制表示为bkbk-1…b0 ⚫ for 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=a n-1mod n，若d1，则n不是素数。x1 and xn-1 意指x 2=1 mod p有不在{-1, 1}中的根 ⚫ 该测试如果进行s次，如果都是真T，则n是素数的概率最小为1-2 -s 5/ 第四章 公钥密码：4.1 公钥密码常用知识和算法

第四章公钥密码:4.1公钥密码常用知识和算法 4.1公钥密码常用知识和算法 ●四、蒙哥马利算法,避免求模运算中的除法 避免求模过程中复杂耗时的除法( P L. Montgomery,1985年提出) 计算 TR-ImodM (1)=(T+MN/R (2 )IF T2N return T-N; ELSE return T 其中M=( Tmod r)X( N-I mod r)modR,且0<TNR ●而且显然有R(R1modN)+N( v-I mod r)=1+RN (R1mdN以及( N-l modR)可预计算,R常取的幂 般先计算 TR-I mod M,若R=",再不断左移模N共w次可得结 果 历忠毛孑技*字

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=(Tmod R)×(N-1 mod R) mod R，且0<T<NR ⚫ 而且显然有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次可得结 果 6/ 第四章 公钥密码：4.1 公钥密码常用知识和算法

第四章公钥密码:4.1公钥密码常用知识和算法 4.1公钥密码常用知识和算法 蒙哥马利模乘算法计算z= XYR-I mod M 输入:X=(XNm1,,X,F(Y Nw-15··· Yor, M=(M, N-1·· M=(Mo)modr,其中0≤x,Y≤M,2l≤M≤2N,r=",gcd(M,r)=1, NwHN/w Output: Z=XYr- nu mod M 1:Z÷0 2: fori=0 to nu-1 do 3:Z÷z+XY 4:qM÷( Z mod r) M mod r 5:Z÷(2+qMM/r 6: end for 7: ifz>M then 8:Z÷Z-M 9: end if 10: Retun Z 历忠毛孑技*字

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，2 N-1M2 N ， r =2 w ，gcd(M, r)=1， Nw=N/w 7/ 第四章 公钥密码：4.1 公钥密码常用知识和算法

第四章公钥密码:4.2公钥密码体制的基本概念 4.2公钥密码体制的基本概念 公钥密码体制的出现在密码学史上是一个最大的 而且是惟一真正的革命。为密码学发展提供了新 的理论和技术基础 公钥密码算法基本工具不再是代换和置换,而是数学 函数 以非对称的形式使用两个密钥,两个密钥的使用对保 密性、密钥分配、认证等都有着深刻的意义。 公钥密码体制的概念是在解决单钥密码体制中最 难解决的两个问题时提出的,即密钥分配和数字 签字 历忠毛孑技*字

4.2 公钥密码体制的基本概念  公钥密码体制的出现在密码学史上是一个最大的 而且是惟一真正的革命。为密码学发展提供了新 的理论和技术基础 ⚫ 公钥密码算法基本工具不再是代换和置换，而是数学 函数 ⚫ 以非对称的形式使用两个密钥，两个密钥的使用对保 密性、密钥分配、认证等都有着深刻的意义。  公钥密码体制的概念是在解决单钥密码体制中最 难解决的两个问题时提出的，即密钥分配和数字 签字 8/ 第四章 公钥密码：4.2 公钥密码体制的基本概念

第四章公钥密码:4.2公钥密码体制的基本概念 4.2公钥密码体制的基本概念 ●对称密码算法的缺陷 密钥分配问题:通信双方加密通信前要通过秘密的安 全信道协商加密密钥,这种安全信道可能很难实现; 对这个信道安全性的要求比正常传送消息信道的安全 性要高 密钥管理问题:在多用户网络中,任何两个用户之间 都需要有共享的秘密钥,n个用户需要Cn2=m(m-1)2个 密钥,n=5000时,C2=12,497,500,系统开销非常大 没有签名功能:当主体A收到主体B的电子文挡时, 无法向第三方证明此电子文档确实来源于B,传统单 钥加密算法无法实现抗抵赖的需求 历忠毛孑技*字

4.2 公钥密码体制的基本概念  对称密码算法的缺陷 ⚫ 密钥分配问题： 通信双方加密通信前要通过秘密的安 全信道协商加密密钥，这种安全信道可能很难实现； 对这个信道安全性的要求比正常传送消息信道的安全 性要高 ⚫ 密钥管理问题： 在多用户网络中，任何两个用户之间 都需要有共享的秘密钥，n个用户需要Cn 2=n(n-1)/2个 密钥，n=5000时，Cn 2=12,497,500，系统开销非常大 ⚫ 没有签名功能： 当主体A收到主体B的电子文挡时， 无法向第三方证明此电子文档确实来源于B，传统单 钥加密算法无法实现抗抵赖的需求 9/ 第四章 公钥密码：4.2 公钥密码体制的基本概念

第四章公钥密码:4.2公钥密码体制的基本概念 4.2公钥密码体制的基本概念 ●公钥密码的主要作用 ●公钥加密 用于加密任何消息,象分组密码一样使用 任何人可以用公钥加密消息,私钥的拥有者可以解密消息 数字签名 Digital Signature) 用于生成对某消息的数字签名 私钥的拥有者生成数字签名,任何人可以用公钥验证签名 签名时可将公钥加密算法逆用来实现,也可单独设计公钥签名算法 ≥基于公钥的密钥分配 Key Distribution) 用于交换秘密信息,常用于协商对称加密算法的密钥 可采用公钥加密的算法实现密钥分配 也可使用单独设计的密钥交换算法,如DH密钥交换协议实现密钥分配 ●参考资料: Arto salomaa《公钥密码学》芬兰,等 历毛孑拌技大字 10

4.2 公钥密码体制的基本概念  公钥密码的主要作用  公钥加密 ⚫ 用于加密任何消息，象分组密码一样使用 ⚫ 任何人可以用公钥加密消息，私钥的拥有者可以解密消息  数字签名 (Digital Signature) ⚫ 用于生成对某消息的数字签名 ⚫ 私钥的拥有者生成数字签名，任何人可以用公钥验证签名 ⚫ 签名时可将公钥加密算法逆用来实现，也可单独设计公钥签名算法  基于公钥的密钥分配(Key Distribution) ⚫ 用于交换秘密信息，常用于协商对称加密算法的密钥 ⚫ 可采用公钥加密的算法实现密钥分配 ⚫ 也可使用单独设计的密钥交换算法，如DH密钥交换协议实现密钥分配  参考资料：Arto Salomaa《公钥密码学》芬兰，等 10/ 第四章 公钥密码：4.2 公钥密码体制的基本概念

第四章公钥密码:4.2公钥密码体制的基本概念 4.2公钥密码体制的基本概念 ●公钥密码算法的最大特点是采用两个相关密钥将加密和解 密能力分开 一个密钥是公开的,称为公开密钥,简称公开钥,用 于加密、验证签名,可以被任何人知道 另一个密钥是为用户专用,因而是保密的,只能被消 息的接收者或签名者知道,称为秘密密钥,简称秘密 钥,用于解密、产生签名 因此公钥密码体制也称为双钥密码体制 ●算法有以下重要特性:已知密码算法和加密密钥,求解 密密钥在计算上是不可行的 因此加密和签名的验证者不能解密和生成签名 历忠毛孑技*字

4.2 公钥密码体制的基本概念  公钥密码算法的最大特点是采用两个相关密钥将加密和解 密能力分开 ⚫ 一个密钥是公开的，称为公开密钥，简称公开钥，用 于加密、验证签名，可以被任何人知道 ⚫ 另一个密钥是为用户专用，因而是保密的，只能被消 息的接收者或签名者知道，称为秘密密钥，简称秘密 钥，用于解密、产生签名 ⚫ 因此公钥密码体制也称为双钥密码体制  算法有以下重要特性： 已知密码算法和加密密钥，求解 密密钥在计算上是不可行的 ⚫ 因此加密和签名的验证者不能解密和生成签名 11/ 第四章 公钥密码：4.2 公钥密码体制的基本概念