-公钥密码体制精讲

1第6章非对称密码体制2学习要点：了解非对称密码体制的提出背景、基本思想了解非对称密码体制的基本应用方向了解三种典型的公钥密码体制DH密钥交换算法RSA3§6－1概述问题的提出：密钥管理困难传统密钥管理两两分别用一对密钥时，则n个用户需要C(n,2)=n(n-1)/2个密钥，当用户量增大时密钥空间急剧增大。如:n=100时C(100,2)=4,995n=5000时C(5000,2)=12,497,500陌生人间的保密通信问题数字签名的问题传统加密算法无法实现抗抵赖的需求4020000400006000080000100000120000140000用户数密钥量50040030020010050图6－1　用户数与密钥量的对应关系56.1.1公钥密码体制公钥密码又称为双钥密码、非对称密码公钥密码体制提出的标志性文献：W.DiffieandM.E.Hellman,NewDirectionsinCryptography,IEEETransactiononInformationTheory,V.IT-22.No.6,Nov1976,PP.644-654676.1.2对公钥密码体制的要求（1）参与方B容易通过计算产生一对密钥（公开密钥KUb和私有密钥KRb）。（2）在知道公开密钥和待加密报文M的情况下，对于发送方A，很容易通过计算产生对应的密文：C＝EKUb（M）（3）接收方B使用私有密钥容易通过计算解密所得的密文以便恢复原来的报文：M＝DKRb（C）＝DKRb（EKUb（M））8（4）敌对方即使知道公开密钥KUb，要确定私有密钥KRb在计算上是不可行的。（5）敌对方即使知道公开密钥KUb和密文C，要想恢复原来的报文M在计算上也是不可行的。（6）加密和解密函数可以以两个次序中的任何一个来使用:(这条不是所有公开密钥体系都适用，如DSA只用于数字签名)M=DKRb（EKUb（M））M=EKUb（DKRb（M））96.1.3单向陷门函数满足公钥密码体制，要设计一单向陷门函数单向陷门函数是满足下列条件的函数f：(1)给定x，计算y=fpk(x)是容易的(2)给定y,计算x使x=f-1sk（y）是困难的(3)知道密钥Sk的情况下，反向计算是容易的x=f-1sk（y）注：[1]仅满足(1)、(2)两条的称为单向函数；第(3)条称为陷门性，Sk称为陷门信息。[2]当用陷门函数f作为加密函数时，可将加密密钥pk公开。f函数的设计者将Sk保密，用作解密密钥。由于加密函数是公开的，任何人都可以将信息X加密成y=fpk(x)，然后送给函数的设计者（当然可以通过不安全信道传送）；由于设计者拥有Sk，他自然可以解出x=f-1sk（y）。[3]单向陷门函数的第(2)条性质表明窃听者由截获的密文y=fpk(x)推测x是不可行的。1112生活中的例子将挤出的牙膏弄回管子里比把牙膏挤出来困难得多；燃烧一张纸要比使它从灰烬中再生容易得多把盘子打碎成数千片碎片很容易，把所有这些碎片再拼成为一个完整的盘子则很难。13数学上(有很多函数看起来和感觉像单向函数，能够有效地计算它们，但我们至今未找到有效的求逆算法。)将许多大素数相乘要比将其乘积因式分解容易得多。我们把离散对数函数、RSA函数作为单向函数来使用，但是，目前还没有严格的数学证明表明所谓这些单向函数真正难以求逆，即单向函数是否存在还是未知的14单向函数不能用作加密。因为用单向函数加密的信息是无人能解开它的。但我们可以利用具有陷门信息的单向函数构造公开密钥密码。156.1.4公开密钥密码系统的分析方法强行攻击(对密钥)。公开密钥算法本身可能被攻破。可能报文攻击(对报文本身的强行攻击)。166.1.5公钥密码系统的应用加密/解密数字签名会话密钥交换171819§6-2Diffie-Hellman密钥交换算法Diffie-Hellman密钥交换算法的有效性依赖于计算有限域中离散对数的困难性。本原元离散对数20本原元（原根）对于一个素数q，如果数值：，……，是各不相同的整数，并且以某种排列方式组成了从1到q-1的所有整数则称整数a是素数q的一个本原元qamodqamod2qaqmod121离散对数对于一个整数b和素数q的一个本原元a，可以找到一个唯一的指数i，使得：b=aimodq(0≤i≤q-1)成立，则指数i称为b的以a为底数的模q的离散对数。2223一个素数q和一个整数a（均公开），a是q的一个原根用户A选择一个随机数XAq，计算用户B选择一个随机数XBq，计算每一方都对X的值保密存放而使得Y的值对于另一方可以公开得到用户A计算密钥：用户B计算密钥：双方以K作为加、解密密钥，以对称密钥算法进行保密通信qaYAXAmodqaYBXBmodqYKAXBmod)(qYKBXAmod)(Diffie-Hellman密钥交换算法24DH例子素数q=97,它的一个本原元a=5A和B分别选择随机数Xa=36和Xb=58A计算公开密钥：Ya=536mod97=50mod97B计算公开密钥：Yb=558mod97=44mod97A计算会话密钥：K=4436mod97=75mod97B计算会话密钥：K=5058mod97=75mod9725§6－3RSA由Rivest,Shamir和Adleman在1978年提出来的数学基础:Euler定理，并建立在大整数因子分解的困难性之上26明文空间P＝密文空间C=Zn(剩余类集合)密钥的生成为了产生两个密钥，选取两个大素数，p和q。为了获得最大程度的安全性，两数的长度一样。计算乘积：n=pqRSA密码体制描述27然后随机选取加密密钥e，使e和(p-1)(q-1)互素。最后用欧几里德扩展算法计算解密密钥d，以满足：ed≡1mod(p-1)(q-1)则d=e-1mod((p-1)(q-1))注意：e和n是公开的，公钥KU={e,n}p和q不再需要，但不可泄露私钥KR={d,n}28加密(用e,n)明文：Mn密文：C=Me(modn)解密(用d,n)密文：C明文：M=Cd(modn)29RSA加密/解密公开密钥n:两素数p和q的乘积(p和q必须保密)e:与(p-1)(q-1)互素私人密钥d:e-1(mod(p-1)(q-1))加密C=Memodn解密M=Cdmodn30算法分析密钥生成时，要求n很大，攻击者要将其成功的分解为p*q是困难的。(大因子分解困难性)RSA的加密函数C=Memodn是一个单向函数接收方，拥有私钥，解密容易证明：M’=Cdmodn=(Memodn)dmodn=M在ed=1mod((n))条件下成立M’=Cdmodn=(Memodn)dmodn=Medmodn=M1+k(n)modn=[M·(M(n))k]modn=[M·(M(n)modn)k]modn(根据欧拉定理注[5])=[M·1k]modn=M(∵Mn)∵ed=1mod(n),k为整数ed-1=k(n)∴ed=k(n)+131若Bob选择了p=7和q＝17则n=119,(n)=6×16＝96＝25×3，一个正整数e能用作加密指数，当且仅当e不能被2，3所整除假设Bob选择e=5，那么用辗转相除法将求得：d=e-177(mod96)Bob的解密密钥d={77,119}，公开｛5,119｝现假设Alice想发送明文19给BobRSA的例子32Alice能否直接发送1234给Bob?例2：p=47,q=61,(n)=(47-1)(61-1)=2760时，SK=167是否为秘密密钥的候选者？用欧氏算法计算：gcd(2760,167)=1即可证明。QX1X2X3Y1Y2Y3－1027600116716011671－168811－1688－117791－117792－33982－339－1728171－17281719－3142319－3142－7412231用RSA算法加密与解密的过程：例：明文=“RSAALGORITHM”(1)明文用数字表示空白=00，A=01,B=02,…,Z=26(两位十进制数表示)1819010001120715180920081300(2)利用加密变换公式C=mPKmodr,即C=18191223mod2867=2756PK=1223=10011000111=210+27+26+22+21+20=1024+128+64+4+2+1C=18191223(mod2867)=18191024·1819128·181964·18194·18192·18191(mod2867)=2756275620010542066923470408181535步骤：Bob为实现者Bob寻找出两个大素数p和qBob计算出n=pq和(n)=(p-1)(q-1).Bob选择一个随机数e(0e(n))，满足（e，(n)）＝1Bob使用辗转相除法计算d=e-1(mod(n))Bob在目录中公开n和e作为她的公开密钥RSA密码体制描述36密码分析者攻击RSA体制的关键点在于如何分解n。若分解成功使n=pq，则可以算出φ(n)＝（p-1)(q-1)，然后由公开的e，解出秘密的d。37要求：若使RSA安全，p与q必为足够大的素数，使分析者没有办法在有效时间内将n分解出来。建议选择p和q大约是100位的十进制素数。模n的长度要求至少是512比特。38为了抵抗现有的整数分解算法，对RSA模n的素因子p和q还有如下要求：(1)|p-q|很大，通常p和q的长度相同；(2)p-1和q-1分别含有大素因子p1和q1(3)gcd(p1-1,q1-1)应该很小。为了提高加密速度，通常取e为特定的小整数，如EDI国际标准中规定e＝216＋1，ISO/IEC9796中甚至允许取e＝3。这时加密速度一般比解密速度快10倍以上。3940选择两个大素数p和q，通常要求每个均大于10100。计算n＝pｘq和φ(n)＝(p－1)(q－1)。选择一与φ(n)互素的数、令其为d。找到一个e满足e×d＝1(modφ(n))。选好这些参数后，将明文划分成块，使得每个明文报文P长度m满足0mn。加密P时，计算C＝Pe(modn)，解密C时计算P＝Cd(modn)。由于模运算的对称性，可以证明，在确定的范围内，加密和解密函数是互逆的。为实现加密，需要公开(e,n)，为实现解密需要(d,n)。RSA算法归纳41RSA的速度硬件实现时，RSA比DES慢大约1000倍。软件实现时，DES比RSA快大约100倍。聪明地选择一个e值，RSA加密速度将快得多42如何计算abmodn？如何判定一个给定的整数是素数？如何找到足够大的素数p和q?问题……43要点1：(a×b)modn=[(amodn)×(bmodn)]modn]执行乘法操作之前先用模的方法降阶要点2：m的二进制表示为bkbk-1…b0,则计算ammodnammodn=[a(2i)]modn=[a(2i)modn]bi0bi0ikiibm20如何计算abmodn？44快速取模指数算法计算abmodnc0;d1forikdownto0doc2×cd(d×d)modnifbi=1thencc+1d(d×a)modnreturnd45快速取模指数算法：例子i9876543210bi1000110000c=01248173570140280560d=17491575261602412981666717560mod561=1a=7,n=561,m=560=(1000110000)2MillerandRabin,WITNESS算法WITNESS(a,n)判定n是否为素数，a是某个小于n的整数1.令bkbk-1…b0为(n-1)的二进制表示，2.d13.forikdownto04.doxd5.d(dd)modn6.ifd=1andx1andxn-17.thenreturnTRUE8.ifbi=19.