第2章密码学导论(3)

第2章密码学导论(3)公钥密码学概述,2,关键知识点,公钥密码学是为了解决电信网环境下的安全数据传递而提出的密码方法。公钥密码学可以公开部分密钥。公钥加密算法目前采用计算不可逆原理目前广泛应用的公钥加密算法是RSA算法Diffie-Hellman密钥生成算法可以解决在公共电信网环境下数据加密传递的问题,3,主要内容,公钥密码学发展动因公钥密码学基本原理RSA公钥加密算法Diffie-Hellman密钥生成算法公钥密码体系与密钥管理,4,公钥密码学历史,Diffie和Hellman于1976年首先提出公钥密码学的需求和思路,这是几千年来密码学中的真正的一次革命性的进步.这是电信时代产物.美国麻省理工学院的RonRivest,AdiShamir,LenAdleman于1978年首先提出的公共密钥加密算法RSA,RSA算法的发明使得公钥密码学得到了广泛的应用2003年5月,发明公钥加密算法的RonRivest,AdiShamir和LenAdeman获得2002度图灵奖(计算机领域的诺贝尔奖),5,WhitfieldDiffie,WhitfieldDiffie是世界著名的密码技术与安全技术专家，1991年加盟Sun公司，在Sun实验室工作。Diffie以其1975年发现公钥密码技术的概念而著名，被业界公认为信息技术安全事物的权威人士。,WhitfieldDiffie,MartinHellman,6,公钥密码学发展动因,公钥密码学发展动因来源于电信网环境下安全数据传递的应用。电信网环境数据的传递存在两类安全威胁：其一是窃取电信网上传递的数据；其二在电信网传递的数据中插入非法的数据。为了解决这个问题，可以采用密码学方法对电信网传递的数据进行加密。,7,公钥密码学发展动因(续1),在通信网环境下，传统密码学无法实现快速的密钥分发，所以，传统的密码学无法解决电信网环境的数据安全问题。,8,公钥密码学发展动因(续2),为了解决在电信网环境下任意两个互不相识的用户之间能够进行安全传递问题，M.Diffie和W.Hellman设计了两个方案：（1）采用公钥密码系统，将传统密码学的密钥分解成加密密钥PK和解密密钥VK，从PK无法推导出VK，这样，就可以公开加密密钥PK，由接收方保密自己的解密密钥VK。（2）采用“公钥分发系统”，通过公开交互的信息，可以生成只有通信双方才知道的密钥。,9,公钥密码学发展动因(续3),为了解决电信网环境下数据完整传递的问题，必须设计一种机制，使得该发送方传递的数据，除发送方之外，任何其他一方都无法修改数据。这样，才能通过电信网传递商业合同。由于传统密钥学的加密算法中发送方和接收方共用同一个密钥，则接收方接收后可以更改数据。这样，传统密码学无法解决电信网环境下数据完整传递的问题。公钥密码体系中只有一方掌握私钥VK，则发送方采用私钥加密报文摘要后传递，则其他一方无法修改报文而不被发觉。,10,公钥密码学原理,W.Diffie和M.Hellman于1976年首先给出了公钥密码系统的定义：一个公钥密码系统由一对加密算法E和解密算法D构成，该公钥密码系统采用一个密钥对集合KS=(PK,VK)，对于任何一个KS集合中的密钥对(PK,VK)与任何一个明文P，存在以下特性：（1）采用密钥对(PK,VK)中任何一个密钥对明文P执行加密算法E，都可以采用另外一个密钥对密文进行解密。,11,公钥密码学原理(续1),（2）对于掌握了密钥对(PK,VK)，则加密算法E和解密算法D都是容易计算的。（3）如果公开密钥对中的一个密钥，例如PK，则无法通过计算推导出另外一个密钥，例如VK。（4）如果只掌握了密钥对中的一个密钥PK，并且利用该密钥将明文P加密得到密文C，则无法再利用该密钥将C进行解密得到明文P。这4个特性较为完整地刻画了公钥密码系统的特征。,12,公钥密码学原理(续2),由于公钥密码学中的加密算法采用了不同的加密和解密密钥，所以，也称为不对称密钥加密算法。其原理如下图所示。,13,RSA公钥加密算法,RSA公钥加密算法是R.L.Rivest，A.Shamir和L.Adleman在1978年提出一种具体实现公钥密码系统的加密算法。该算法随后以这三位发明者姓氏的第一个英文字母组合成的缩写RSA命名，即RSA公钥加密算法，简称为RSA算法。这是迄今为止使用最为广泛的公钥加密算法，特别是在数字签名方面得到了广泛的应用。,14,RSA公开密钥算法的发明人(1978年),RonRivest,AdiShamir,LeonardAdleman,15,RSA公钥加密算法(续),RSA公钥加密算法是基于数论中的欧拉定理和费马定理设计的一种加密算法，其安全性主要是基于“大数分解”的不可解特性。RSA公钥加密算法可以分成两个部分：RSA公钥加密算法的加密和解密过程；RSA公钥加密算法的“密钥对”选择和生成过程。,16,在数论，对正整数n，欧拉函数是少于或等于n的数中与n互质的数的数目。例如(8)=4，因为1,3,5,7均和8互质。,17,RSA算法加密/解密过程,为了利用一个公钥(e,n)对一个报文M进行加密，这里e和n是一对正整数，可以采用以下过程：（1）将报文M表示成一个0到n1的整数。如果M较长，可以将M分解成多个数据块，分别进行多次加密。（2）将M进行e次乘法运算，然后对乘积取n的模，这样，就得到M的密文C。C=E(M)=Me(modn),18,RSA算法加密/解密过程(续),（3）如果需要对密文C进行解密，则只需要对C进行d次乘法运算，然后再对乘积取n的模，这样，就得到报文M。M=D(C)=Cd(modn)这里(d,n)就是与公钥(e,n)对应的私钥，这是需要该“密钥对”所有者秘密保存的密钥。这里的e，d和n是需要用户在生成“密钥对”过程中选择和生成的正整数。,19,RSA算法的密钥选择,为了使用RSA加密算法，首先需要按照以下方法选择并生成RSA公钥加密算法的“密钥对”。（1）选择两个很大的“随机”素数p和q，这两个素数的乘积就是RSA密钥中的正整数n，即n=p*q如果p和q足够大，即使公开n，则根据目前的计算能力，也无法分解出p和q。,20,RSA算法的密钥选择(续),（2）选择一个很大的随机整数d，使得该整数与(p1)*(q1)的最大公因子为1（3）从p，q和d中计算出e，e是以(p1)*(q1)为模的d的倒数，即e*d=1(mod(p1)*(q1)从以上算法过程可以看出，私钥是根据一定规则选择的，而公钥是计算得出的。,21,RSA算法的证明,按照欧拉和费马的定理可知，对于任何一个整数M（M相当于转换成为整数的报文），如果与n互质，则M(n)=1(modn)(1)这里(n)表示所有小于n的，与n互质的正整数的个数。对于任何一个素数p，(p)=p1(2)(n)=(p*q)=(p)*(q)=(p1)*(q1)(3),22,RSA算法的证明(续1),对于RSA中公钥(e,n)和私钥(d,n)中的参数，存在以下关系：e*d=1(mod(p1)*(q1),即e*d=1(mod(n)这样，取模运算的规则可知，可以找到某个整数k，使得e*d=k*(n)+1,23,RSA算法的证明(续2),以下就可以证明RSA算法。RSA算法的加密之后的解密过程可以表示为：D(E(M)=(E(M)d=(Me)d(modn)=Me*d(modn)=Mk*(n)+1(modn)(5)由于p无法整除M，这样，按照公式(1)和(2)可以得出：Mp1=1(modp)由于(p1)是(n)的因子，所以，Mk*(n)=1(modp),24,RSA算法的证明(续2),这样，就可以得到如下公式：Mk*(n)+1=M(modp)(6)同理可以得到如下公式：Mk*(n)+1=M(modq)(7)由于n=p*q，综合公式(6)和(7)，按照取模运算规则可以得出：Mk*(n)+1=M(modn)这样，就证明了RSA算法的加密和解密过程是正确的。,25,RSA算法的实现,RSA加密和解密算法。R.L.Rivest等人提出了一个计算Me的算法，它最多执行2*log2(e)次乘法和除法，具体如下：（i）设ekek-1e1e0是e的二进制数表示形式。（ii）设置变量C的初值为1。（iii）对于j=k,k1,0，重复执行(a)和(b)：(a)C=C*C(modn)(b)如果ej=1，则C=C*M(modn)（iv）输出C，C就是M的密文。,26,RSA算法的实现(续1),RSA密钥的选择要求如下：对于p和q选择的要求：其十进制位数应该不小于100，两个数的长度仅仅差别几个十进制数。另外，(p1)和(q1)应该包含很大的素数因子，而(p1)和(q1)之间的公因子应该很小。选择与(n)互质的私钥d的方法比较简单，例如任何大于max(p,q)的素数都可以作为d。为了防范攻击者猜测到私钥，d的选择集合应该足够大，不一定只局限于素数。,27,RSA算法的实现(续2),可以采用欧几里德算法，通过计算(n)与d的最大公因子选择公钥e。欧几里德计算(n)和d的最大公因子gcd(n),d)的算法可以表示为如下形式：(i)设x0=(n)，x1=d，j=1(ii)xj+1=xj-1(modxj)(iii)如果xj+10，则j=j+1，转(ii)；如果xj+1=0，则输出最大公因子xj。,28,RSA算法的实现(续3),由于(n)与d互质，所以，它们的最大公因子是1。就可以找到参数e1和e2，使得e1*(n)+e2*d=1这里的e2满足e2*d(mod(n)=1的条件，所以，e2可以作为与d对应的公钥e。如果得出的e小于log2(n)，则从安全角度考虑，需要重新选择d，重新计算e。,29,简单例子,为了说明该算法的工作过程,我们下面给出一个简单例子,显然我们在这只能取很小的数字，但是如上所述，为了保证安全，在实际应用上我们所用的数字要大的多得多。例1：选取p=3,q=5，则n=15，（p-1）*（q-1）=8。选取e=11（大于p和q的质数），通过d*11=1mod8，计算出d=3。假定明文为整数13。则密文C为C=Memodn=1311mod15=1,792,160,394,037mod15=7复原明文P为：P=Cdmodn=73mod15=343mod15=13,30,课堂练习,用RSA算法加密时，已知公钥是（e=7，n=20），私钥是（d=3，n=20），用公钥对消息M=3加密，得到的密文是：。解答n=20,d=3,e=7加密C=Memodn=37mod20=2187mod20=7解密M=Cdmodn=73mod20=343mod20=3,31,RSA算法举例,例2选择p=47，q=59，n=47*59=2773，d=157。(n)=46*58=2668，e计算如下：2668=157*16+156=157*171这样，可知e=17以下对“ITSALLGREEKTOME”进行加密。首先采用00表示空格、01表示A、26表示Z，对该句子进行编码，得到以下数据：0920190001121200071805051100201500130500,32,RSA算法举例(续),以下仅对第一个数据块进行加密，第一个数据块加密算式如下：92017=(920)2)2)2)2*920=948(mod2773)以上整个英文句子加密后的密文为：0948234210841444266323900778077402191655对第一个数据块的解密算式可以按照加密算式进行，其结果为：948157=920(mod2773)。,33,RSA算法分析,R.L.Rivest等人已经研究，攻破RSA加密算法的计算复杂度等同于分解大数n的计算复杂度。假定n=2l，则当l336（相当于100个十进制位），已有时间复杂度可以小于O(2l/8)的分解大数n的算法。1994年,一个小组利用因特网上1600台计算机,经过8个月的计算,攻破了公钥长度为129位十进制数(约428比特)的RSA(这种攻击意义不大).现在通常认为,采用1024比特密钥长度(约300位十进制数)是比较安全的.,34,RSA算法分析,在RSA密码应用中，公钥是被公开的，即e和n的数值可以被第三方窃听者得到。破解RSA密码的问题就是从已知的e和n的数值（n等于pq），想法求出d的数值，这样就可以得到私钥来破解密文。从上文中的公式：de-1(mod(p-1)(q-1)或de1(mod(p-1)(q-1)可以看出密码破解的实质问题是：从Pq的数值，去求出(p-1)和(q-1)。即只要求出p和q的值，就能求出d的值而得到私钥。当p和q是一个大素数的时候，从它们的积pq去分解因子p和q，这是一个公认的数学难题。比如当pq大到1024位时，迄今为止还没有人能够利用任何计算工具去完成分解因子的任务。因此，RSA从提出到现在30年，经历了各种攻击的考验，逐渐为人们接受，普遍认为是目前最优秀的公钥方案之一。然而，虽然RSA的安全性依赖于大数的因子分解，但并没有从理论上证明破译RSA的难度与大数分解难度等价。即RSA的重大缺陷是无法从理论上把握它的保密性能如何。,35,RSA的缺点：A)产生密钥很麻烦，受到素数产生技术的限制，因而难以做到一次一密。B)分组长度太大，为保证安全性，n至少也要600bits以上，使运算代价很高，尤其是速度较慢，较对称密码算法慢几个数量级；且随着大数分解技术的发展，这个长度还在增加，不利于数据格式的标准化。因此，使用RSA只能加密少量数据，大量的数据加密还要靠对称密码算法。,36,Diffie-Hellman密钥生成算法,这里介绍的Diffie-Hellman密钥生成算法，实际上并不是属于W.Diffie和M.Hellman提出的公钥密码体系中的算法。而且Diffie-Hellman算法生成的密钥也并不是公钥密码体系中使用的不对称密钥，而是在传统密码体系中使用的对称密钥。,37,Diffie-Hellman密钥生成算法(续),但是，一般在信息安全中，还是在讨论公钥密码体系中介绍这个密码生成算法。其原因在于：该算法部分解决了在公共网络环境下如何进行安全通信的问题；它也包含了部分公开密钥的思想。,38,Diffie-Hellman算法基本思想,如果在电信网上的一方A试图与电信网上的另外一方B进行通信，则A首先通过“电话黄页薄”获取B公布的公钥；然后，利用自己的私钥对B的公钥进行指数运算后再取模，得到密钥KA,B；最后，A利用KA,B作为密钥，利用传统加密算法（例如DES算法）加密数据后传递给B。,39,Diffie-Hellman算法基本思想(续),在电信网上的另一方B收到了A发送来的加密报文之后，则首先通过“电话黄页薄”获得A公布的公钥；然后，利用自己的私钥对A的公钥进行指数运算后再用共同的数取模，得到密钥KB,A；Diffie-Hellman算法可以保证KB,A=KA,B，这样，B就可以利用KB,A解密A采用传统加密算法生成的密文。,40,Diffie-Hellman算法基本过程,假设q是一个素数，是(1,q)范围中的一个素数，利用Diffie-Hellman密钥生成算法生成共享密钥过程如下：(i)A从1,2,q1中生成一个随机整数XA作为保密字保存好，将YA=XAmodq计算值连同A的名字和地址等信息放置在公共文件中。(ii)B从1,2,q1中生成一个随机整数XB作为保密字保存好，将YB=XBmodq计算值连同B的名字和地址等信息也放置在公共文件中。,41,Diffie-Hellman算法基本过程(续),(iii)如果A要与B进行保密通信，则A从公共文件中取出B对应的保密字指数运算值YB，利用自己保存的保密字对该数进行指数运算，得到密钥KA,B=YBXA=XBXA。(iv)同样，B也可以从公共文件中取出A对应的保密字指数运算值，利用自己保存的保密字对该数进行指数运算，得到密钥KB,A=YAXB=XAXB=XBXA=KA,B。(v)随后，A与B就可以利用双方共享的KA,B进行数据传统加密和解密的操作。,42,DH更为一般的描述,Diffie-Hellman1976年，WhitDiffie和MartinHellman共同提出了Diffie-Hellman算法（简称DH），这是一种两方密钥交换协议，用于两个