1,四、公开密钥密码阳振坤yzkicst.pku.edu.cn计算机科学技术研究所http:/www.icst.pku.edu.cn/cryptocourse/,密码算法与应用基础,2,信息安全引论对称密钥密码对称密钥密码应用基础公开密钥密码数字签名与Hash函数公开密钥密码应用基础密钥交换与密钥管理,内容提要,3,信息安全的基本内容,保密性(Confidentiality)真实性(Authentication)完整性(Integrity)不可否认性(Nonrepudiation),4,公开密钥密码,基本思想 数学基础 RSA算法 基于离散对数的算法 基于椭圆曲线的算法 密钥分发 总结 ,5,基本思想,加密与解密由不同的密钥完成加密: XY: Y = EKU(X)解密: YX: X = DKR(Y) = 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: 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)easy if X & K are knownX = FK-1(Y)easy if Y & K are knownX = FK-1(Y)infeasible if only Y is known公开密钥密码:Y = FK(X)easy if X & K are knownX = FK-1(Y)easy if Y & K are knownWhere, K and K are related keys.X = FK-1(Y)infeasible if Y & K are known but K is unknown.,11,公钥密码分析,强制破译通过公钥得到私钥破译公钥加密的对称密钥,12,数学基础,素数,最大公约数(gcd),互素模运算: a = qn + r, 0r0,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)两两不等: (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为正整数,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 mod 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,对任意imi|(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(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 Cocks在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 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: 若pq都是素数,n=pq,则同余方程x xp mod px 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 px=(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) mod 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解密速度: 方法,