第09-12讲 公钥密码体制

第4章非对称密码体制学习要点：–了解非对称密码体制的提出背景、基本思想–了解非对称密码体制的基本应用方向–掌握三种典型的公钥密码体制DH密钥交换算法RSAECC§4-1概述问题的提出：密钥管理困难–传统密钥管理两两分别用一对密钥时，则n个用户需要C(n,2)=n(n-1)/2个密钥，当用户量增大时密钥空间急剧增大。如:–n=100时C(100,2)=4,995–n=5000时C(5000,2)=12,497,500陌生人间的保密通信问题数字签名的问题–传统加密算法无法实现抗抵赖的需求020000400006000080000100000120000140000用户数密钥量50040030020010050图6－1　用户数与密钥量的对应关系公钥密码体制公钥密码又称为双钥密码、非对称密码公钥密码体制提出的标志性文献：–W.DiffieandM.E.Hellman,NewDirectionsinCryptography,IEEETransactiononInformationTheory,V.IT-22.No.6,Nov1976,PP.644-654对公钥密码体制的要求（1）参与方B容易通过计算产生一对密钥(公钥PK和私钥SK）。（2）在知道公开密钥和待加密报文M的情况下，对于发送方A，很容易通过计算产生对应的密文：C＝EPKB(M)（3）接收方B使用私有密钥容易通过计算解密所得的密文以便恢复原来的报文：M＝DSKB(C)＝DSKB(EPKB(M))（4）敌对方即使知道公开密钥PKB，要确定私有密钥SKB在计算上是不可行的。（5）敌对方即使知道公开密钥PKB和密文C，要想恢复原来的报文M在计算上也是不可行的。（6）加密和解密函数可以以两个次序中的任何一个来使用:M＝DPK(ESK(M))M=ESK(DPK(M))注：1*.仅满足(1)、(2)两条的称为单向函数；第(3)条称为陷门性，δ称为陷门信息。2*.当用陷门函数f作为加密函数时，可将f公开，这相当于公开加密密钥。此时加密密钥便称为公开密钥，记为Pk。f函数的设计者将δ保密，用作解密密钥，此时δ称为秘密密钥，记为Sk。由于加密函数是公开的，任何人都可以将信息x加密成y=f(x)，然后送给函数的设计者（当然可以通过不安全信道传送）；由于设计者拥有Sk，他自然可以解出x=f-1(y)。3*.单向陷门函数的第(2)条性质表明窃听者由截获的密文y=f(x)推测x是不可行的。是满足下列条件的函数f：(1)给定x，计算y=f(x)是容易的(2)给定y,计算x使y=f(x)是困难的(3)存在δ，已知δ时，对给定的任何y，若相应的x存在，则计算x使y=f(x)是容易的陷门单向函数公钥密码系统的应用类型加密/解密数字签名会话密钥交换简单数字签名安全数字签名认证+加密接收方：C=EPKB[ESKA[M]]发送方：C=EPKB[ESKA[M]]m=DPKA[DSKB[c]]会话密钥交换（加密）会话密钥交换（解密）•密钥穷举攻击•如果密钥太短，公钥密码体制也易受到穷搜索攻击。因此密钥必须足够长才能抗击穷搜索攻击。•由于公钥密码体制所使用的可逆函数的计算复杂性与密钥长度常常不是呈线性关系，而是增大得更快。密钥长度太大又会使得加解密运算太慢而不实用•公钥密码体制目前主要用于密钥管理和数字签字•寻找从公开钥计算秘密钥的方法•目前为止，对常用公钥算法还都未能够证明这种攻击是不可行的对公钥密码体制的攻击对公钥密码体制的攻击•可能字攻击•例如对56比特的DES密钥用公钥密码算法加密后发送，敌手用算法的公钥对所有可能的DES密钥加密后与截获的密文相比较。如果一样，则相应的明文即DES密钥就被找出。因此不管公钥算法的密钥多长，这种攻击的本质是对56比特DES密钥的穷搜索攻击。抵抗方法是在欲发送的明文消息后添加一些随机比特。一个素数p和一个整数a（均公开），a是p的一个原根用户A选择一个随机数XAp，并计算类似地，用户B选择一个随机数XBp,并计算每一方都对X的值保密存放而使得Y的值对于另一方可以公开得到用户A计算密钥：用户B计算密钥：双方以K作为加、解密密钥，以对称密钥算法进行保密通信modAXAYapmodBXBYap()modAXBKYp()modBXAKYp§4－2Diffie-Hellman密钥交换算法Diffie-Hellman密钥交换DH例子素数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=75mod97§4-3RSA由Rivest、Shamir、Adleman于1978年首次发表；最容易理解和实现的公钥算法;经受住了多年深入的攻击;其理论基础是一种特殊的可逆模幂运算，其安全性基于分解大整数的困难性；RSA既可用于加密，又可用于数字签名，已得到广泛采用；RSA已被许多标准化组织(如ISO、ITU、IETF和SWIFT等)接纳；目前许多国家标准仍采用RSA或它的变型明文空间P＝密文空间C=Zn密钥的生成–选择互异素数p,q，计算n=p×q,(n)=(p-1)(q-1),选择整数e使((n),e)=1,1e(n),计算d,使d=e-1mod(n)–公钥PK={e,n}–私钥SK={d,n}加密(用e,n)–明文：Mn密文：C=Me(modn)解密(用d,n)–密文：C明文：M=Cd（modn)RSA密码体制描述由加密过程知c≡memodn，所以cdmodn≡medmodn≡m1modφ(n)modn≡mkφ(n)+1modn下面分两种情况：①m与n互素，则由Euler定理得mφ(n)≡1modn,mkφ(n)≡1modn,mkφ(n)+1≡mmodn即cdmodn≡m。②gcd(m,n)≠1，先看gcd(m,n)=1的含义，由于n=pq，所以gcd(m,n)=1意味着m不是p的倍数也不是q的倍数。因此gcd(m,n)≠1意味着m是p的倍数或q的倍数，不妨设m=cp，其中c为一正整数。此时必有gcd(m,q)=1，否则m也是q的倍数，从而是pq的倍数，与mn=pq矛盾。由gcd(m,q)=1及Euler定理得mφ(q)≡1modq，所以mkφ(q)≡1modq,［mkφ(q)］φ(p)≡1modq,mkφ(n)≡1modq因此存在一整数r，使得mkφ(n)=1+rq，两边同乘以m=cp得mkφ(n)+1=m+rcpq=m+rcn即mkφ(n)+1≡mmodn，所以cdmodn≡m。RSA密码解密原理若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的例子步骤：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体制的关键点在于如何分解n。若分解成功使n=pq，则可以算出φ(n)＝(p-1)(q-1)，然后由公开的e，解出秘密的d。RSA密码体制描述若使RSA安全，p与q必为足够大的素数，使分析者没有办法在有效时间内将n分解出来。建议选择p和q大约是100位的十进制素数。模n的长度要求至少是512比特。为了抵抗现有的整数分解算法，对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倍以上。RSA密钥的生成例：取p=47,q=61时,n=2867,(n)=(47-1)(61-1)=2760，可取SK=167，PK=1223QX1X2X3Y1Y2Y310276001167ExtendedEuclid(f,d)（设fd）(X1,X2,X3)←(1,0,f);(Y1,Y2,Y3)←(0,1,d);:loopifY3=0thenreturngcd(f,d)=0;ifY3=1thenreturngcd(f,d)=1；Y2=d-1modf;Q=X3/Y3；(T1,T2,T3)←(X1-QY1,X2-QY2,X3-QY3);(X1,X2,X3)←(Y1,Y2,Y3);(Y1,Y2,Y3)←(T1,T2,T3);gotoloop例：取p=47,q=61时,n=2867,(n)=(47-1)(61-1)=2760，可取SK=167，PK=1223QX1X2X3Y1Y2Y31027600116716011671-1688ExtendedEuclid(f,d)（设fd）(X1,X2,X3)←(1,0,f);(Y1,Y2,Y3)←(0,1,d);:loopifY3=0thenreturngcd(f,d)=0;ifY3=1thenreturngcd(f,d)=1；Y2=d-1modf;Q=X3/Y3；(T1,T2,T3)←(X1-QY1,X2-QY2,X3-QY3);(X1,X2,X3)←(Y1,Y2,Y3);(Y1,Y2,Y3)←(T1,T2,T3);gotoloop例：取p=47,q=61时,n=2867,(n)=(47-1)(61-1)=2760，可取SK=167，PK=1223QX1X2X3Y1Y2Y31027600116716011671-168811-1688-11779ExtendedEuclid(f,d)（设fd）(X1,X2,X3)←(1,0,f);(Y1,Y2,Y3)←(0,1,d);:loopifY3=0thenreturngcd(f,d)=0;ifY3=1thenreturngcd(f,d)=1；Y2=d-1modf;Q=X3/Y3；(T1,T2,T3)←(X1-QY1,X2-QY2,X3-QY3);(X1,X2,X3)←(Y1,Y2,Y3);(Y1,Y2,Y3)←(T1,T2,T3);gotoloop例：取p=47,q=61时,n=2867,(n)=(47-1)(61-1)=2760，可取SK=167，PK=1223QX1X2X3Y1Y2Y31027600116716011671-168811-1688-117791-117792-339ExtendedEuclid(f,d)（设fd）(X1,X2,X3)←(1,0,f);(Y1,Y2,Y3)←(0,1,d);:loopifY3=0thenreturngcd(f,d)=0;ifY3=1thenreturngcd(f,d)=1；Y2=d-1modf;Q=X3/Y3；(T1,T2,T3)←(X1-QY1,X2-QY2,X3-QY3);(X1,X2,X3)←(Y1,Y2,Y3);(Y1,Y2,Y3)←(T1,T2,T3);gotoloop例：取p=47,q=61时,n=2867,(n)=(47-1)(61-1)=2760，可取SK=167，PK=1223QX1X2X3Y1Y2Y31027600116716011671-168811-1688-117791-117792-33982-339-172817ExtendedEuclid(f,d)（设fd）(X1,X2,X3)←(1,0,f);(Y1,Y2,Y3)←(0,1,d);:loopif