《网络安全》第5-6讲(2.4)

《《网络安全》第5-6讲(2.4)》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

第2章密码技术2.4公钥（非对称）密码体制在对称密钥密码体制中，加密运算与解密运算使用同样的密钥。在公共的计算机网络上安全地传送和保管密钥是一个严峻的问题。公开密钥加密（Public-keycryptography），也称为非对称(密钥)加密，该思想最早由雷夫·莫寇（RalphC.Merkle）在1974年提出，之后在1976年，狄菲（Diffie）与赫尔曼（Hellman）两位学者发表了著名论文《密码学的新方向》，提出了建立“公开密钥密码体制”，为发讯与收讯的两方建立密钥。这两个密钥是数学相关，用某用户加密密钥加密后所得的信息，只能用该用户的解密密钥才能解密。如果知道了其中一个，并不能计算出另外一个。因此如果公开了一对密钥中的一个，并不会危害到另外一个的秘密性质，称公开的密钥为公钥。 2.4公钥（非对称）密码体制2.4.1公钥密码体制的基本概念公钥体制下，一个用户可以将自己设计的加密公钥和加密算法对外公布，而只保留解密用的私钥。任何人都可以获取这个用户的加密公钥和加密算法，并向该用户发送加密过的信息，该用户接收后可以使用私钥还原消息。在这个公钥加解密的过程中，会涉及到公私密钥对、数字证书以及电子签证机关等主要内容。 2.4公钥（非对称）密码体制2.4.1公钥密码体制的基本概念1.密钥对在基于公钥体系的安全加密系统中，密钥生成过程每次都产生一个公钥和一个私钥，形成加密和解密的密钥对。在实际应用中，私钥由用户私人保存，而公钥则通过某种手段对外公布。公钥体系的基础问题是公钥的分发与管理，这是电子商务等业务系统能够广泛应用的基础。一个集体如果成员之间可以互信，比如A和B两人形成小集体，他们之间完全互信并直接交换公钥，在互联网上进行保密通信，不存在密钥和身份安全问题。这个集体再稍微扩大一点，成员之间有基本的信任关系，虽然从法律角度讲这种信任有一定风险，但通常也可以完成安全通信。如果在开放环境下，如互联网环境下，通信双方缺乏基本的信任关系，并且存在大量的恶意用户，密钥和身份的信任问题就成了一个大问题。 2.4公钥（非对称）密码体制2.4.1公钥密码体制的基本概念2.数字证书公开密钥体系需要在开放环境下使用，公钥加密体系采取将公钥和公钥的主人名字联系在一起的方法，再请一个有信誉的公正权威机构对每个公钥和所有者身份进行确认，确认后的公钥信息加上这个权威机构的签名，就形成了数字证书，也称为证书。由于证书上有权威机构的签字，因此人们公认证书上的内容是可信任的；又由于证书上有主人的名字等身份信息，别人就能很容易地知道公钥的主人是谁。有了数字证书之后，互联网上的庞大用户群之间可以通过权威机构建立起基本的信任关系，使得彼此都不能轻易信任的用户之间可以完成通信。证书就是用户在网上的电子个人身份证，在电子商务中的作用同日常生活中使用的个人身份证作用一样。 2.4公钥（非对称）密码体制2.4.1公钥密码体制的基本概念3.电子签证机关电子签证机关（即CA）是负责颁发数字证书的权威机构。CA自身拥有密钥对，可以使用私钥完成对其他证书的数字签名，同时也拥有一个对外开放的证书（内含公钥）。网上的公众用户通过验证CA的数字签名建立信任，任何人都可以得到CA的证书（含公钥），用以验证它所签发的其他证书。如果用户想建立自己的证书，首先要向CA提出申请证书的请求。在CA判明申请者的身份后，便为他分配一个密钥对，并且CA将申请者的公钥与身份信息绑在一起，在为之完成数字签名后，便形成证书发给那个用户（申请者）。如果一个用户想鉴别数字证书是否为假冒的，可以用证书发证机构CA的公钥对该证书上的数字签名进行验证，数字签名验证的过程是使用CA公钥解密的过程，验证通过的证书就被认为是有效的。CA在公开密码体系中非常重要，负责签发证书以及证书和密钥的管理等必要工作。CA相当于网上公安机构，专门发放、验证电子身份证。 2.4公钥（非对称）密码体制2.4.1公钥密码体制的基本概念4、公钥加密体制具有以下优点（1）密钥分配相对简单，不需要复杂的流程；（2）密钥的保存量少，且私钥和公钥分别存储；（3）可以实现互不相识的人之间进行私人通信时的保密性要求（4）可以完成通信双方的数字签名和数字身份鉴别。当然，由于公钥加密体制依赖的算法基础是难解问题，并不是真正的无解问题，若计算机达到足够的计算能力，花费足够的时间的话，还是有可能被破解的，只要花费的代价足够大就可以保证信息在一定时间内的安全性。 2.4公钥（非对称）密码体制2.4.2公钥密码体制的原理公钥密码体系中由于公钥与私钥之间存在依存关系，因此，信息使用公钥加密后，只有私钥拥有者本人才能解密该信息，任何未授权用户甚至信息的发送者都无法将此信息解密。近代公钥密码系统的研究主要基于难解的可计算问题，该方法保证了整个体系和算法的安全性。常用的难解可计算问题包括：（1）大数分解问题；（2）计算有限域的离散对数问题；（3）平方剩余问题；（4）椭圆曲线的对数问题等。 2.4公钥（非对称）密码体制2.4.2公钥密码体制的原理公钥密码体制的基本数学方法和基本原理如下所述。1．可逆函数和单向函数1）可逆函数令f是集A到集B的一个映射，如果对任意的x1≠x2，x1,x2∈A，有y1≠y2,y1,y2∈B，则称f是从A到B的单射，或1—1映射，或可逆的函数，记为y=f(x)。2）单向函数一个可逆函数y=f(x)如果满足以下两条就称为一个单向函数：对于给定的所有x∈A，能方便地计算出f(x)；对于给定的所有y，求x是困难的，以至于实际是做不到的。 2.4公钥（非对称）密码体制2.4.2公钥密码体制的原理公钥密码体制的基本数学方法和基本原理如下所述。1．可逆函数和单向函数例2.1有限域GF(p)中的指数函数，其中p是素数，即也就是x为满足0≤x＜p-1的整数。其逆运算是求离散对数，即给定x求y是容易的，但是当p很大时，从x=logby中要计算x是非常困难的。如b=2，p=2100，给定x求y，只需作100次乘法，利用高速计算机可在0.1ms内完成。而给定y求x，所需计算量为1600年。可见，有限域GF(p)中的指数函数f(x)=bx是一个单向函数。x=logby 2.4公钥（非对称）密码体制2.4.2公钥密码体制的原理公钥密码体制的基本数学方法和基本原理如下所述。2．用于构造公钥密码的常用单向函数1）多项式求根有限域GF(p)上的一个多项式当给定多项式的系数和x、p以后，利用Honer算法，最多进行n次乘法，n-1次加法，就可以求得y的值。但已知多项式的系数a和y、p以后，要求x，就需要对高次方程求根，至少要进行不小于n2(lbp)2的整数次乘法，当n、p很大时很难求解。 2.4公钥（非对称）密码体制2.4.2公钥密码体制的原理公钥密码体制的基本数学方法和基本原理如下所述。2．用于构造公钥密码的常用单向函数２）离散对数如果p是一个足够大的素数，a是{0,1,2,…,p-1}中与p互素的数,则已知p、a、x的值，计算f(x)=axmodp并不困难；若已知p、a、y的值，则计算x=logbymodp（是一个离散对数问题）就很困难了。若p=512，则计算乘法次数为1077。 2.4公钥（非对称）密码体制2.4.2公钥密码体制的原理公钥密码体制的基本数学方法和基本原理如下所述。2．用于构造公钥密码的常用单向函数3）大整数分解若已知两个大素数p、q，求n=p×q仅需一次乘法，但已知n求p、q则是几千年来数论专家的一道难题。已知的各种算法有：试除法、二次筛、数域筛、椭圆曲线。其中RSA问题是FAC问题的特例。n是两个素数p、q之积，给定n以后求p、q的问题称为RSA问题。求n=p×q分解问题有以下几种形式：（1）分解整数n为p、q；（2）给定整数M、C，求d使得Cd≡Mmodn；（3）给定整数k、C，求M使得Mk≡Cmodn；（4）给定整数x、C，决定是否存在y使得x≡y2modn（二次剩余问题）。 2.4公钥（非对称）密码体制2.4.2公钥密码体制的原理公钥密码体制的基本数学方法和基本原理如下所述。2．用于构造公钥密码的常用单向函数４）迪菲-赫尔曼（Diffie-Hellman）问题给定素数p，可构造一乘群Z*p，令α为Z*p的生成元，若已知αa、αb，求αab的问题即为菲-赫尔曼问题。５）二次剩余问题给定一个奇合数n和整数a，决定a是否为modn平方剩余问题就称为二次剩余问题。 2.4公钥（非对称）密码体制2.4.2公钥密码体制的原理公钥密码体制的基本数学方法和基本原理如下所述。3.公钥密码体制的原理若用户A有一个加密密钥ka，同时还有一个解密密钥k′a，可将加密密钥ka公开，而解密密钥k′a保密。若用户B要向A传送信息的明文为m，可查A的公开密钥ka，若用A的公开密钥ka加密得到密文c=Eka（m）则A收到密文c以后，用只有自己才知道的解密密钥k′a对c进行解密得m=Dk′a（c）图2.14公钥密码体系模型 2.4公钥（非对称）密码体制2.4.3RSA算法1978年，美国麻省理工学院(MIT)的研究小组成员：李维斯特(Rivest)、沙米尔(Shamir)、艾德曼(Adleman)提出了一种基于公钥密码体制的优秀加密算法——RSA算法。RSA的取名就是来自于这三位发明者的姓的第一个字母，后来，他们在1982年创办了以RSA命名的公司RSADataSecurityInc.和RSA实验室，该公司和实验室在公开密钥密码系统的研究和商业应用推广方面具有举足轻重的地位。RSA密码系统的安全是基于大整数分解因子的难度，其公开密钥(现在一般是1024位甚至更长)和私人密钥是一对大素数的函数。一般来说，求一对大素数的乘积相对比较容易，但要对这个乘积进行因式分解则非常困难。因此，可以把一对大素数的乘积作为公开密钥公布，而把素数作为私钥，从而从一个公开密钥和密文中恢复出明文的难度等价于分解两个大素数之积。 2.4公钥（非对称）密码体制2.4.3RSA算法1.RSA密钥的产生RSA密钥的产生过程如下：（1）选择两个大素数p、q，选择的素数要保密。（2）计算乘积n＝pq和Ф(n)＝(p－1)(q－1)。（3）随机选择加密密钥e，要求e和φ(n)互质。（4）利用Euclid算法计算解密密钥d，应满足d×e≡1modφ(n)，其中n和d也要互素。数(n，e)是公钥，(n，d)是私钥。两个素数p、q不再需要，应该丢弃，不要让任何人知道。 2.4公钥（非对称）密码体制2.4.3RSA算法1.RSA密钥的产生例2.2已知解方程d×e≡1mod2436:即937×13≡1mod2436。取e=13，d=937。2436=13×187+513=5×2+35=3+23=2+11=3-2,2=5-3,3=13-5×2，5=2436-13×187 2.4公钥（非对称）密码体制2.4.3RSA算法2.RSA加密（1）加密信息为m（二进制表示）时，首先把m分成等长数据块m1，m2，…，mi，块长s，其中2s≤n，s要尽可能的大。（2）对应的密文是：3.RSA解密对加密消息进行解密计算时，计算ci≡miemodn 2.4公钥（非对称）密码体制2.4.3RSA算法2.RSA加密例2.2续：若取明文：publickeyencryptions。先将明文按两个一组进行分块，再将明文数字化，如按英文字母表的顺序得pu=1520，bl=0111，ic=0802，ke=1004，ye=2404，nc=1302，ry=1724，pt=1519，io=0814，ns=1318。再利用加密密钥(2537，13)进行加密得密文：pu=0095，bl=1648，ic=1410，ke=1299，ye=1365，nc=1379，ry=2333，pt=2132，io=1751，ns=1324。使用解密密钥(2537，937)可将密文恢复成明文。 2.4公钥（非对称）密码体制2.4.4RSA算法中的计算问题RSA算法中首先遇到的问题就是如何选取大的素数。数百年来，人们对素数的研究一直有很大兴趣，是否有一个简单的公式可以产生素数？从目前的研究结果来看，答案是否定的。曾有人猜想若n|2n-2(2n-2能被2整除)，则n为素数。n=3,3|23-2，n<341时这一猜想是正确的，但n=341时，此猜想是错误的。 2.4公钥（非对称）密码体制2.4.4RSA算法中的计算问题1.概率测试素数法概率测试素数法有Solovay-Strassen测试法、Lehman测试法、Miller-Rabin测试法等。它们都是利用数论理论构造一种算法。对于一个给定的大正整数，进行一次测试，是素数的概率为1/2，若进行了r次测试，则第n步是素数的概率为ε=2-r，n为素数的概率为1-ε，若r足够大，如r=100，则几乎可以认为n是素数。若概率测试法得到的准素数是合数（出现的概率很小），也不会造成太大的问题，因为该结果在RSA体制的加解密时会出现异常，我们可以丢弃该结果重新产生。 2.4公钥（非对称）密码体制2.4.4RSA算法中的计算问题2．确定性验证素数法确定性验证素数法是RSA体制实用化研究的基础问题之一。定理2-1令pi+1=hipi+1，若满足下述条件，则pi+1必为素数： 2.4公钥（非对称）密码体制2.4.4RSA算法中的计算问题2．确定性验证素数法1）安全素数幂剩余函数具有特殊的周期性，反复运算M=Cemodn若干次后，将还原为最初的M。例如：p=17,q=11,n=pq=187,e=7,m=123。可以验证，m经过4次RSA连续变换，可得m4=m。过程如下： 2.4公钥（非对称）密码体制2.4.4RSA算法中的计算问题2．确定性验证素数法1）安全素数早期的RSA算法就曾被人用这种方法破译。所以在生成密钥时，应采用“安全素数”。所谓安全素数p，应满足：（1）p是一个位数足够大的随机素数；（2）p-1含有一个大的素数因子r；（3）p+1含有一个大的素数因子；（4）r-1含有一个大的素数因子t。 2.4公钥（非对称）密码体制2.4.4RSA算法中的计算问题2．确定性验证素数法2）安全素数的获得（1）选择两个指定长度的奇数a,b。（2）在a附近产生随机素数s，在b附近产生随机素数t。（3）由t产生素数r:①r=1+2t;②若r非素数，则r=r+2直到r是素数。（4）由r、s生成p:①p=(sr-1-rs-1)mod(rs)；　②若p为偶数，则p=p+rs；③p=p+2rs直到p为素数。 2.4公钥（非对称）密码体制2.4.4RSA算法中的计算问题2．确定性验证素数法3）高次幂的求模算法C=MemodpRSA加、解密变换都要进行高次幂的求模运算。求C=Memodp可通过对指数e的二进制化来实现。例如，求117mod17，计算如下：7=(111)2即7=22+21+20，117mod17=(11)22×112×11(mod17)具体步骤如下：将e用二进制表示为e=klkl-1…k0,ki∈{0,1},0≤i≤lC=1fori=l~0C=C2modp若ki=1，则C=C(Mmodp)。 2.4公钥（非对称）密码体制2.4.5RSA算法的安全性RSA算法之所以具有安全性，是基于数论中的一个事实：将两个大的素数合成一个大数很容易，而逆过程则非常困难，即若n=pq被分解，则RSA便被攻击。若p、q已知，则φ(n)=(p-1)(q-1)便可算出，解密密钥d和e满足d×e≡1modφ(n)，故d便求出。 2.4公钥（非对称）密码体制2.4.5RSA算法的安全性攻击者通常会考虑通过已知的公钥推算私钥，但是这要将模数因式分解成组成它的质数，计算的难度很大。算法可以采用足够长的密钥，使其在现有的计算水平下基本不可能实现。RSA实验室给出了不同应用场合的密钥长度建议：普通公司使用的密钥长度应为1024bit，对于极其重要的资料，使用双倍长度即2048bit。对于普通用户,使用768bit的密钥长度已足够，因为使用当前技术和计算能力无法轻易破解。 2.4公钥（非对称）密码体制2.4.5RSA算法的安全性由此可见，RSA的安全性依赖于大数分解。目前，进行大数分解速度最快的方法，其时间复杂度为exp(sqrt(ln(n)lnln(n)))由时间复杂度可见，RSA的安全性是依赖于作为公钥的大数n的位数长度的。为保证足够的安全性，三位数学家建议取p、q为100位的十进制数，这样大数n为200位十进制数，即使采用每秒107次运算的超高速电子计算机，至少也要计算108年，但在实际应用中，一般认为现在的个人应用可以采用512bit的公钥，公司需要用1024bit的公钥，极其重要的场合必须使用2048bit的公钥。 2.4公钥（非对称）密码体制2.4.5RSA算法的安全性RSA算法的重大问题是无法从理论上证明其保密性能。RSA的安全性依赖于大数因子分解，而密码学界多数人士倾向于因子分解不是NPC问题，普遍认为从一个密钥和密文推断出明文的难度等同于分解两个大素数的积，但这一假设并没有从理论上得到证明。目前，RSA的一些变种算法已被证明等价于大数分解。不管怎样，分解n是最直接的攻击方法。人们已经分解的最新纪录是129位十进制的大素数，因此，公钥的大数n必须选择得足够大。加密算法的应用不仅要考虑保密强度，还要考虑算法的运算效率。密钥越长安全性越高，其加解密所耗的时间也越长，因此，加密密钥的长度需要根据所保护信息的敏感程度、攻击者破解所要花的代价以及系统所要求的反应时间来综合考虑决定，尤其对于商业信息领域更是如此。 2.4公钥（非对称）密码体制2.4.6RSA算法的实用性及数字签名1．RSA的实际应用选用RSA算法作为公开密钥加密系统的主要算法的原因是该算法安全性好。在模N足够长时，每lnN个整数中就有一个大小接近于N的素数。在模长为1024bit时，可以认为RSA密码系统的可选密钥个数足够多，可以得到随机、安全的密钥对。目前，RSA算法已经广泛应用于安全通信，在互联网的许多领域也得到了采用，例如在安全接口层（SSL）标准中选择了RSA算法来保证网络浏览器建立安全的互联网连接。RSA加密系统也大量应用于智能IC卡和网络安全产品中。 2.4公钥（非对称）密码体制2.4.6RSA算法的实用性及数字签名1．RSA的实际应用公开密钥密码体制与对称密钥密码体制相比较，确实有非常明显的优点，但它的运算量远大于后者，常常是几百倍、几千倍甚至上万倍，计算复杂度过高。公开密钥密码体制传送机密信息的代价较高，因此通常只用来传送数据加密的密钥，大规模的数据使用传送的密钥进行对称加密，以提高工作效率。在传送机密信息的网络用户双方，如果使用某个对称密钥密码体制(例如DES)，同时使用RSA不对称密钥密码体制来传送DES的密钥，就可以综合发挥两种密码体制的优点，即DES的高速简便性和RSA密钥管理的方便和安全性。 2.4公钥（非对称）密码体制2.4.6RSA算法的实用性及数字签名2．RSA用于数字签名RSA公钥体系在应用中还可以实现对信息进行数字签名。数字签名是指信息发送者从所传报文中提取出特征数据（或称数字指纹），使用其个人私钥对特征数据进行RSA算法解密运算，得到发信者对该数字指纹的签名消息。数字签名的运算过程使用签名函数H(m)，从技术上标识了发信者对该电文的数字指纹的责任。发信者的私钥只有其本人才拥有，所以传递的信息一旦添加了签名，便保证了发信者无法抵赖曾发过该信息（即不可抵赖性）。 2.4公钥（非对称）密码体制2.4.6RSA算法的实用性及数字签名2．RSA用于数字签名当信息接收者收到报文后，就可以用发信者的公钥对数字签名进行反运算，得到发信者提供的消息数字指纹，在本地采用相同方法重新计算数字指纹，通过对比收到的报文和本地计算的内容是否一致，就可以验证签名的真实性和报文完整性。数字签名的有效性已经被众多组织和企业所接受，并逐渐具有一定的法律效力。美国参议院对此已通过了立法，现在在美国，数字签名与手书签名的文件具有同等的法律效力。 习题1.已知p＝11，q＝13，p和q的乘积为n＝p×q＝143，选取加密密钥e＝7，求解密密钥d，并加密明文m＝85。2.在RSA公开密钥密码体制中：(1)如果p＝13，q＝31，d＝7，求e。(2)已知p＝5，q＝11，d＝27，求e并加密“abcdefghi”。