四公开密钥密码阳振坤yzkicstpkueducn计算机科学技术.ppt
《四公开密钥密码阳振坤yzkicstpkueducn计算机科学技术.ppt》由会员分享,可在线阅读,更多相关《四公开密钥密码阳振坤yzkicstpkueducn计算机科学技术.ppt(76页珍藏版)》请在三一文库上搜索。
1、1,四、公开密钥密码 阳振坤 计算机科学技术研究所 http:/ 对称密钥密码 对称密钥密码应用基础 公开密钥密码 数字签名与Hash函数 公开密钥密码应用基础 密钥交换与密钥管理,内容提要,3,信息安全的基本内容,保密性(Confidentiality) 真实性(Authentication) 完整性(Integrity) 不可否认性(Nonrepudiation) ,4,公开密钥密码,基本思想 数学基础 RSA算法 基于离散对数的算法 基于椭圆曲线的算法 密钥分发 总结 ,5,基本思想,加密与解密由不同的密钥完成 加密: XY: Y = EKU(X) 解密: YX: X = DKR(Y)
2、 = DKR(EKU(X) 从解密密钥得到加密密钥在计算上是不可行的 加密与解密的顺序没有限制(不是必须的) X = DKR(EKU(X) = EKU(DKR(X) 若X=Y且映射E: XY是映上的,则成立 EKU(X) = EKU(DKR(EKU(X) 若X=Y且为有限集合(例如分组密码),则E: XY是映上的,从而成立,6,用公钥密码实现保密,用户拥有自己的密钥对(KU,KR) 公钥KU公开,私钥KR保密 AB: Y=EKUb(X) B: DKRb(Y)= DKRb(EKUb(X)=X,7,用公钥密码实现认证,条件: 加密与解密的顺序没有限制 认证: AALL: Y=DKRa(X) ALL
3、: EKUa(Y)=EKUa(DKRa(X)=X 认证+保密: AB: Z= EKUb(DKRa(X) B: EKUa(DKRb(Z)=X,8,公钥密钥的应用范畴,加密/解密 数字签名(身份认证) 密钥交换,9,公钥密钥算法必须满足的条件,密钥对的生成在计算上是可行的 用公钥加密明文在计算上是可行的 用私钥解密密文在计算上是可行的 从公钥获得私钥在计算上是不可行的 从公钥和密文来获得明文在计算上是不可行的 加密与解密的顺序没有限制(不是必须的) X = DKR(EKU(X) = EKU(DKR(X),10,One-way trapdoor function,对称密钥密码: Y = FK(X)
4、easy if X & K are known X = FK-1(Y) easy if Y & K are known X = FK-1(Y) infeasible if only Y is known 公开密钥密码: Y = FK(X) easy if X & K are known X = FK-1(Y) easy if Y & K are known Where, K and K are related keys. X = FK-1(Y) infeasible if Y & K are known but K is unknown.,11,公钥密码分析,强制破译 通过公钥得到私钥 破译公
5、钥加密的对称密钥 ,12,数学基础,素数,最大公约数(gcd),互素 模运算: a = qn + r, 0rn (a mod n) = r 同余: ab mod n iff (a mod n)=(b mod n) (a mod n)(b mod n) mod n = (ab) mod n (a mod n)(b mod n) mod n = (ab) mod n If (ab)(ac) mod n and a is relatively prime to n, then bc mod n (ab)(ac) mod n n|(ab-ac) n|(a(b-c) n|(b-c) bc mod n,1
6、3,Fermat定理,Fermat定理: p素数,a是整数且不能被p整除,则: ap-1 1 mod p 证明: 考虑集合1,2,p-1,对每个数乘以a,得到集合a mod p,2a mod p,(p-1)a mod p,对于p,后者两两不同且都在1与p-1之间,因此两个集合相同,于是: (p-1)! = 12(p-1) (a mod p)(2a mod p)(p-1)a mod p) mod p a2a(p-1)a mod p ap-1(p-1)! mod p 注意到(p-1)!与p互素,因此定理成立. 推论: p素数,a是任意整数,则: ap a mod p,14,Euler数,Euler
7、数(n)定义为小于n且与n互素的正整数个数 p是素数,(p)=p-1 若n的因子分解为n=Piai, ai0,Pi互不相同,则 (n)= Piai(1-1/Pi) 若gcd(m,n)=1,则(mn)=(m)(n),特别地,若pq且都是素数, (pq)=(p-1)(q-1) Euler定理: 若a与n为互素的正整数,则: a(n) 1 mod n,15,Euler定理,a(n) 1 mod n 证明: R=x1,x2,x(n)为所有小于n且与n互素的正整数,考虑集合 S=(ax1mod n), (ax2mod n), (ax(n) mod n) (aximod n)与n互素 (aximod n)
8、两两不等: (aximod n) = (axjmod n) ximod n = xjmod n S有(n)个元素 故S也是所有小于n且与n互素的正整数,因此S=R,从而 xi=(aximod n)(axi) mod n (a(n) xi) mod n 注意到xi 与n互素,从而得到结论.,16,Euler定理推论,推论: 若n=pq, pq都是素数, k是任意整数,则 mk(p-1)(q-1)+1 m mod n, 对任意0mn 证明:若m=0或n,结论是显然的;若m与n互素,注意到(n)=(p-1)(q-1),由Euler定理可得到结论;否则m必定是p或者q的倍数,不妨设m=sp,则0sq为
9、正整数,m与q互素,由Euler定理得到: m(q) 1 mod q (m(q)k(p) 1 mod q mk(p-1)(q-1) = tq+1 t是整数 等式两边乘以m=sp,得到: mk(p-1)(q-1)+1 = (tq+1)sp = tspq+sp m mod n,17,中国剩余定理(1),中国剩余定理: m1,m2,mk是两两互素的整数, a1,a2,ak是任意整数,M=mi,那么方程组 xai mod mi, 1im 关于模M有唯一解: x aiMi(Mi-1 mod mi) mod M , Mi=M/mi 证明: m1,m2,mk两两互素因此gcd(Mi,mi)=1 Mi-1 m
10、od mi存在 正确性: Mi定义 Mi0 mod mj, 任给ij,18,中国剩余定理(2), x aiMi(Mi-1 mod mi) mod mj ajMj(Mj-1 mod mj) mod mj aj mod mj 正确性 唯一性: 假如x,y都是解x y mod mi,对任意i mi|(x-y),对任意i (mi) |(x-y),对任意j (m1,m2,mk两两互素) M|(x-y) x y mod M 唯一性 ,19,(axi mod n)与n互素,a与n为互素的正整数,x1,x2,x(n)为所有小于n且与n互素的正整数. S=(ax1mod n), (ax2mod n), (ax(
11、n) mod n) 反证法: 若某个(aximod n)与n不互素,则存在素数p使得 p|n且p|(aximod n) 令r=(aximod n),则axi=tn+r,t是整数 p|n,p|r p|(axi) p|a或者p|xi 这说明a或者xi与n有共因子p,与假设a和xi都与n互素相矛盾. ,20,RSA算法简介,由Ron Rivest,Adi Shamir & Len Adlemen于1977年发布 属于分组密码 明文和密文在0n-1之间,n是一个正整数 应用最广泛的公钥密码算法 只在美国申请专利且已于2000年9月到期 NSA声称在60年代中期发现了公钥算法 英国的Clifford C
12、ocks在1973年发表了与RSA几乎一样的算法,21,RSA算法描述,分组大小为k, 2k n 2k+1 加密: C = Me mod n 解密: M = Cd mod n = Med mod n 公钥: KU=e,n, 私钥: KR=d,n 上述算法需要满足以下条件: 能够找到e,d,n,使得Med mod n = M, 对所有Mn 计算Me和Cd相对容易 从e和n得到d是在计算上不可行的,22,RSA密钥生成原理,令n=pq, pq都是素数,(n)=(p-1)(q-1)是n的Euler数 Euler定理推论: 若n=pq, pq都是素数, k是任意整数,则 mk(p-1)(q-1)+1
13、m mod n, 对任意0mn 只要选择e,d, 满足ed=k(n)+1,即 ed 1 mod (n) d e-1 mod (n) 公钥: KU=e,n, 私钥: KR=d,n,23,RSA密钥生成与使用,选择两个大素数p,q, pq 计算n=pq,(n)=(p-1)(q-1) 选择整数e,使得gcd(e,(n)=1 (两个随机数互素概率0.6) 计算d e-1 mod (n) 公钥: KU=e,n, 私钥: KR=d,n 加密: C = Me mod n 解密: M = Cd mod n ,24,提高RSA解密速度: 结论1,解密: M = Cd mod n需作大数的幂运算,速度慢 结论1:
14、 若pq都是素数,n=pq,则同余方程 x xp mod p x xq mod q 对模n有唯一解 x=(xp-xq)(q-1mod p)q+xq 证明: pq是素数 gcd(p,q)=1 q-1mod p存在. 唯一性由中国剩余定理保证. 验证解: 令r=q-1mod p,则r是整数, rq1 mod p x=(xp-xq)rq+xq 对于q, x=(xp-xq)r)q+xqxq mod q 对于p, x=(xp-xq)(rq)+xq(xp-xq)+xqxp mod p,25,提高RSA解密速度: 结论2,结论2: p素数,a是任意整数,则 ak (a mod p)k mod (p-1) m
15、od p, k是任意整数 证明: 若a 0 mod p, 结论是显然的.否则, 令k=t(p-1)+r, t,r是整数, r=k mod (p-1), 那么 ak = at(p-1)+r at(p-1)ar mod p ar mod p (Fermat定理: ap-1 1 mod p) (a mod p)r mod p (a mod p)k mod (p-1) mod p,26,提高RSA解密速度: 方法,解密: M = Cd mod n, n = pq, pq都是素数 假如得到了 Mp M mod p Mq M mod q 就得到了M=(Mp-Mq)(q-1mod p)q+Mq mod n
16、由于M=Cd mod n,因此 Mp=Cd mod p = (C mod p)d mod (p-1) mod p Mq=Cd mod q = (C mod q)d mod (q-1) mod q 由于C mod p与C mod q要比C小, d mod (p-1)与d mod (q-1)也比d小,故解密速度会提高(48倍).,27,提高RSA加密速度?(1),同样的方法可以用于RSA的加密 加密: C = Me mod n, n = pq, pq都是素数 假如得到了 Cp C mod p Cq C mod q 就得到了C=(Cp-Cq)(q-1mod p)q+Cq mod n 由于C=Me,从
17、而 Cp=Me mod p = (M mod p)e mod (p-1) mod p Cq=Me mod q = (M mod q)e mod (q-1) mod q 加密速度是否会提高?,28,提高RSA加密速度?(2),加密: C = Me mod n, n = pq, pq都是素数 M0,1,2,2k-10,1,2,n-1, 其中2kn2k+1 定义上,加密E: 0,1,2,n-10,1,2,n-1 实际上,加密E: 0,1,2,2k-10,1,2,n-1 解密映射的定义域总是0,1,2,n-1 M在较小的空间上,C在较大的空间上 e一般可以选择比d小 加密: Cp=Me mod p =
18、 (M mod p)e mod (p-1) mod p 解密: Mp=Cd mod p = (C mod p)d mod (p-1) mod p 同样的方法对加密速度的提高不如对解密速度的提高显著,29,RSA的安全性,强制破解 基于数学的攻击 基于运算时间的攻击 ,30,RSA加密解密计算量,加密: C = Me mod n 解密: M = Cd mod n 幂运算位数增长快 幂运算速度慢并且e,d都是很大的数 (a mod n)(b mod n) mod n = (ab) mod n 计算xm,其中m=2s,只需要计算s次,即计算: xmi,mi=2i,i=0,1,s,31,计算幂,计算d
19、=am, m=bkbk-1b0(二进制表示) d1 for ik downto 0 do d(dd) mod n if bi = 1 then d(da) mod n return d ,32,Euclid算法,gcd(a,b)=gcd(b, a+kb) a,b,k为任意整数 gcd(a,b)=gcd(b, a mod b) a0,b0 Eclid(d,f): 求最大共约数,假定df Xf, Yd if Y = 0 then return X X X mod Y XY goto 上述的循环最多进行多少次? 2log2(max(f,d),33,扩展Euclid算法,ExtEclid(d,f):求
20、最大共约数或模逆, 假定df (X1,X2,X3)(1,0,f), (Y1,Y2,Y3)(0,1,d) if Y3 = 0 then return X3, no inverse if Y3 = 1 then return 1, inverse is Y2 Q (X3/Y3)的整数部分 (X1,X2,X3)(X1-QY1, X2-QY2, X3-QY3) (X1,X2,X3) (Y1,Y2,Y3) goto fX1+dX2=X3, fY1+dY2=Y3 若Y3=1,则 fY1+dY2=1 dY2=(-Y1)f+1 dY2 1 mod f Y2 = d-1 mod f ,34,素数模的平方剩余解,
21、直接判断一个整数是否为素数是困难的 命题: 如果p是素数,则方程 x2 1 mod p 只有平凡解x 1 mod p. 证明: x2 1 mod p p|(x2-1) p|(x+1)(x-1) p|(x+1),或者p|(x-1) x+1=kp,或者x-1=jp, k,j是整数 x=kp-1,或者x=jp+1 x 1 mod p, 或者x -1 mod p,35,Miller-Rabin素数测试算法,Miller-Rabin算法用来测试一个整数是否是素数 WITNESS(a,n) 设bkbk-1b0是(n-1)的二进制表示 d1 for ik downto 0 do xd d(dd) mod n
22、 /x2 1 mod n if(d=1 & x1&xn-1) return TRUE if(bi=1) then d(da) /d=an-1 if(d1) return TRUE /Fermat定理 else return FALSE Miller-Rabin是概率测试(一次概率约0.5) ,36,素数生成,素数生成过程: 随机选择一个奇数n(如通过伪随机数发生器) 随机选择a, 使an 进行素数测试(例如用Miller-Rabin算法),若n没有通过测试,抛弃n,转到 如果通过了足够次数的测试,认为n是素数,否则转到. 素数定理: (N)N/ln(N), (N)为不超过N的素数个数. 随机整
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 公开 密钥 密码 阳振坤 yzkicstpkueducn 计算机 科学技术
链接地址:https://www.31doc.com/p-3188477.html