第五章 公钥密码体制

第五章公钥密码体制本章重点：公钥密码体制的性质公钥密码学的理论基础：单向陷门函数数论的部分知识公钥密码学的实例：RSA算法的原理和工作过程；ElGamal密码体制5.1公钥密码体制的基本原理公钥密码体制采用了两个不同的密钥，这对在公开的网络上进行保密通信、密钥分配、数字签名和认证有着深远的影响。5.1.1对称算法的不足密钥管理量的困难：两两分别用一个密钥时，则n个用户需要C(n,2)=n(n-1)/2个密钥，当用户量增大时，密钥空间急剧增大。如:n=100时，共4,995个；n=5000时增加到12,497,500个。密钥建立问题：对协商密钥的信道的安全性的要求比正常的传送消息的信道的安全性要高。数字签名的问题：传统加密算法无法实现抗抵赖的需求。5.1.2公钥密码体制的起源公钥密码又称为双钥密码和非对称密码，是1976年由Diffie和Hellman在其“密码学新方向”一文中提出的，见划时代的文献：W.DiffieandM.E.Hellman,NewDirectrionsinCryptography,IEEETransactiononInformationTheory,V.IT-22.No.6,Nov1976,PP.644-654RSA公钥算法是由Rivest,Shamir和Adleman在1978年提出来的,见CommunitionsoftheACM.Vol.21.No.2.Feb.1978,PP.120-1265.1.3公开密钥密码的重要特性：加密与解密由不同的密钥完成加密:X→Y:Y=EKU(X)解密:Y→X:X=DKR(Y)=DKR(EKU(X))知道加密算法,从加密密钥得到解密密钥在计算上是不可行的。（单向函数的性质）两个密钥中任何一个都可以用作加密而另一个用作解密(单向函数的交换性，不是必须的)X=DKR(EKU(X))=EKU(DKR(X))基于公开密钥的加密过程图4.1公钥密码体制的通信保密过程基于公开密钥的鉴别过程图4.2公钥密码体制的数字签名和验证签名过程公钥密钥的应用范围加密/解密数字签名(身份鉴别)密钥交换1、涉及到各方：发送方、接收方、攻击者2、涉及到数据：公钥、私钥、明文、密文3、公钥算法的条件：–产生一对密钥是计算可行的；–已知公钥和明文，产生密文是计算可行的；–接收方利用私钥来解密密文是计算可行的；–对于攻击者，利用公钥来推断私钥是计算不可行的–已知公钥和密文，恢复明文是计算不可行的；–(可选)加密和解密的顺序可交换。5.1.4公钥密码系统基本思想和要求涉及计算复杂性、近世代数等内容。严格单向函数一个单射函数f:如果下述条件成立：存在一个有效的方法，对所有的x∈X可计算f（x），但不存在一个有效的办法由y=f（x）计算x,所有的y∈Y。则称X→Y称为是严格单向函数。5.1.5部分数学基础陷门单向函数单向陷门函数是满足下列条件的函数f：(1)给定x，计算y=fk(x)是容易的；(2)给定y,计算x使x=fk-1(y)是不可行的。(3)存在k，已知k时,对给定的任何y，若相应的x存在，则计算x使fk-1(x)是容易的。背包问题大整数分解问题（TheIntegerFactorizationProblem,RSA体制）离散对数问题：有限域的乘法群上的离散对数问题(TheDiscreteLogarithmProblem,ElGamal体制）椭圆曲线上的离散对数问题（TheEllipticCurveDiscreteLogarithmProblem,类比的ElGamal体制）大整数分解问题和离散对数是构造RSA算法的重要基础5.1.6公钥密码基于的数学难题整数因子分解问题许多密码系统的安全性都依赖于整数因子分解的困难性。如RSA加密方案，RSA签名方案和Rabin公钥加密方案。定义：给定一个正整数n，找到它的素因子，即n=p1e1p2e2…pkek,这里pi是不同的素数，并且ei≥1。如：91=7×13;3600=24×32×52至今没有有效的求解方法。指数函数及其性质指数函数y=axmodp，已知x求y是一个可解问题，但其逆过程：已知y求x称为离散对数问题，所以指数函数被认为是一个单向函数。Fermat定理：p素数，a是整数且不能被p整除，则:ap-1≡1modp乘法逆元：n是整数当ax=1modn，x是a的乘法逆元。a的逆元记作a-1，根据Fermat定理，p是素数，若gcb(a,p)=1，ap-2modp是a的乘法逆元。Euclid计算公因数gcd(a，b)=gcd（b，amodb）;可以通过扩展的Euclid算法可以算:ed=kφ(n)+1知道e，d，φ(n)其中两个求另一个。因此：aed≡amodnEuler定理:若a与n为互素的正整数,则:aφ(n)≡1modn，推论:若n=pq,p≠q都是素数,k是任意整数,mkφ(n）+1≡mk(p-1)(q-1)+1≡mmodn,对任意0≤m≤n证明φ(n)=(p-1)(q-1)离散对数的计算:y≡gxmodp已知g,x,p,计算y是容易的已知y,g,p,计算x是困难的。密码学中常用的主要有三个群的离散对数1.有限域GF（p）的乘法群2.有限域GF（2n）上的乘法群3.有限域F上的椭圆曲线群利用指数函数设计一个公钥密码体制用于密钥协商：通信双方根据对方公开的信息，通过协商获得一对密钥（对称密钥），用来对以后的信息数据进行加密。5.1.7设计公钥密码体制算法：通信方A和B①双方选择素数p以及p的一个原根a②用户A选择一个随机数Xap，计算Ya=aXamodp③用户B选择一个随机数Xbp，计算Yb=aXbmodp④每一方保密X值，而将Y值交换给对方⑤用户A计算出K=YbXamodp⑥用户B计算出K=YaXbmodp⑦双方获得一个共享密钥(aXaXbmodp)素数p以及p的原根a可由一方选择后发给对方,也可以是网络中共知的信息。Diffie-Hellman密钥交换方案用户Alice和Bob想交换密钥:约定素数P=353和a=31、随机选择密钥:AchoosesxA=97,BchoosesxB=2332、计算公钥:yA=397mod353=40(Alice)yB=3233mod353=248(Bob)3、计算共享的会话密钥:KAB=yBxAmod353=24897=160(Alice)KAB=yAxBmod353=40233=160(Bob)1、是第一个公钥方案Diffie&Hellmanin1976(nowknowthatJamesEllis(UKCESG)secretlyproposedtheconceptin1970)2、密钥交换方案不能用于交换任意信息允许两个用户可以安全地建立一个秘密信息，用于后续的通讯过程该秘密信息仅为两个参与者知道3、算法的安全性依赖于有限域上计算离散对数的难度。利用指数函数的性质设计一个公钥加密系统：利用aed≡amodn，用户选定一对e和d，ed=kφ(n)+1可以将(e，n)作为公开密钥发布，而d作为私钥密钥保存；当A要发送m给B时，计算密文c=memodn；B收到c后，恢复明文m=cd=med=mmodn；算法的关键是：ed=kφ(n)+1，当知道e和φ(n)时，很容易求出d，因此d的保密性依赖于φ(n)的保密性。如何做到让所有人知道n却不能求出φ(n)，而自己可以容易求出φ(n)。这是RSA算法的关键所在。通过三个方面研究：RSA算法描述RSA的应用RSA实现中的问题对RSA的攻击方法4.2RSA算法RSA算法1977年由RonRivest、AdiShamir和LenAdleman发明，1978年公布是一种分组加密算法，明文和密文在0-（n-1）之间，n是一个正整数；应用最广泛的公钥密码算法只在美国申请专利，且已于2000年9月到期。RSA体制的安全性基于数论中的Euler定理和计算复杂性理论中的下述论断：求两个大素数的乘积是很容易计算的，但要分解两个大素数的乘积，求出它们的素因子则是非常困难的，它属于NP-完全类。5.2.1RSA算法描述1、密钥生成（1）随机选取两个大素数p、q，令N=pq，随机选取两个整数e和d。使得e,d与(N)互素，且（2）公开N,e，作为E，记为E=(N,e)（3）保密p,q,d与(N)，作为D，记为D=(p,q,d,(N)))(mod1Ned2、加密过程（1）在公开密钥数据库中，查得用户U的公钥：E(N,e)；（2）将明文分组，使得每个≤N,i=1,2…r（3）对每一组明文作加密变换（4)将密文传送给用户U。rxxxxx2ixryyyy21NxxEyeiiimod)(3、解密过程（1）先对每一组明文做解密变换：（2）合并分组得到明文NyyDxdiiimod)(思考：RSA算法中如何体现安全性？讨论RSA算法的安全性：在算法中，e和N作为公开密钥，任何人都可以用来加密消息；而p、q、d和是保密的，用来解密密文，只有秘密钥拥有者知道，也就是只有接收者知道。由于N为两个大素数的乘积，又N=pq，那么可以得到Φ(N)=(p-1)(q-1)。发信者并不知道N的两个素因子p和q，就无法计算Φ(N)。又由于ed≡1modΦ(N)，d是通过此式计算出来的，因此无法计算d，所以就无法进行解密。这样，只有秘密钥拥有者才可以进行密文的解密，其他任何人都不能。)(N因式分解的计算量证明解密过程的正确性：ix)(mod1Ned∴存在某个整数k，使得设与N互素，即NyyDdiimod)(NxedimodNxNkimod1)(NxxNkiimod)(ix1),gcd(Nxi1)(Nked若Bob选择了p=101和q＝1131.计算，n=11413,φ(n)=100×112＝11200；2.假设Bob选择了e=3533，那么用Euclidean算法将求得：d=e-1(mod11200)=6597,于是Bob的解密密钥d=6597.RSA算法举例：5.Bob在一个目录中公开n=11413和e=3533作为Bob的公钥。6.现假设Alice想发送明文9726给Bob，她计算：97263533(mod11413)=5761，且在一个信道上发送密文5761。7.当Bob接收到密文5761时，他用他的秘密解密指数（私钥）d＝6597进行解密：57616597（mod11413)=9726设p=43，q=59，取e=13。利用RSA算法加密明文publickeyencryption。练习：解：p=43,q=59,n=pq=43×59=2539φ(N)=42×58=2436,取e=13,解方程de≡1(mod2436)2436=13×187+5,13=2×5+3,5=3+2,3=2+11=3-2,2=5-3,3=13-2×5,5=2436-13×1871=3-2=3-(5-3)=2×3-5=2(13-2×5)-5=2×13-5×5=2×13-5(2436-13×187)=937×13-5×2436即：937×13≡1（mod2436）取e=13,d=937明文：publickeyencryption先将明文分块为：publickeyencptions利用英文字母表的顺序：即a为00，b为01，c为02，…y为24，z为25,将明文数字化得：1520011108021004240413021724151908141418利用其加密得密文：00951648141012991365137923332132175112895.2.2RSA系统的应用1、数据加密：设B欲秘密传递明文m给A，则B首先由公开档案找到A的公开密钥接着执行加密：将密文c传送给A。A收到后，利用私钥执行解密操作：AdAeNmcmEAmod)(AdNcmcDAmod)()(,AANe2、数字签名A欲将文件m签名，则A利用其秘密密钥，对m加以签名得到签名文S：并将m与签名文S一起送给B。B收到m与S后，利用A的公开密钥，进行验证：AdAd