第四章公钥密码 内容提要 ●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 { ⚫ xd; d(dd) mod n; (此时d刚好是x的平方) ⚫ if d=1 and x1 and xn-1 then return False; ⚫ if bi=1 then d(da) mod n;} ⚫ if d1 then return False; ⚫ Return True; ⚫ 循环结束后有d=a n-1mod n，若d1，则n不是素数。x1 and xn-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 TN 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 公钥密码常用知识和算法