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

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,遵义师范学院,网络安全,第,2,章 密 码 技 术,2.4,公钥（非对称）密码体制,在对称密钥密码体制中，加密运算与解密运算使用同样的密钥。,在公共的计算机网络上安全地传送和保管密钥是一个严峻的问题,。,公开密钥加密（,Public-key cryptography,），也称为非对称,(,密钥,),加密，该思想最早由雷夫,莫寇（,Ralph C.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,的一个映射，如果对任意的,x,1,x,2,，,x,1,x,2,A,，有,y,1,y,2,y,1,y,2,B,，则称,f,是从,A,到,B,的单射，或,11,映射，或可逆的函数，记为,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=log,b,y,中要计算,x,是非常困难的。,如,b,=2,，,p,=2,100,，给定,x,求,y,，只需作,100,次乘法，利用高速计算机可在,0.1ms,内完成。而给定,y,求,x,，所需计算量为,1600,年,。可见，有限域,GF(,p,),中的指数函数,f,(,x,)=,b,x,是一个单向函数。,x,=log,b,y,2.4,公钥（非对称）,密码体制,2.4.2,公钥密码体制的原理,公钥密码体制的基本数学方法和基本原理如下所述。,2,用于构造公钥密码的常用单向函数,1,）多项式求根,有限域,GF(,p,),上的一个多项式,当给定多项式的系数和,x,、,p,以后，利用,Honer,算法，最多进行,n,次乘法，,n,-1,次加法，就可以求得,y,的值。但已知多项式的系数,a,和,y,、,p,以后，要求,x,，就需要对高次方程求根，至少要进行不小于,n,2,(lb,p,),2,的整数次乘法，当,n,、,p,很大时很难求解。,2.4,公钥（非对称）,密码体制,2.4.2,公钥密码体制的原理,公钥密码体制的基本数学方法和基本原理如下所述。,2,用于构造公钥密码的常用单向函数,）离散对数,如果,p,是一个足够大的素数，,a,是,0,1,2,p,-1,中与,p,互素的数,则已知,p,、,a,、,x,的值，计算,f,(,x,)=,a,x,mod,p,并不困难；若已知,p,、,a,、,y,的值，则计算,x,=log,b,y mod,p,（是一个离散对数问题）就很困难了。若,p,=512,，则计算乘法次数为,10,77,。,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,使得,C,d,M,mod,n,；,（,3,）给定整数,k,、,C,，求,M,使得,M,k,C,mod,n,；,（,4,）给定整数,x,、,C,，决定是否存在,y,使得,x,y,2,mod,n,（二次剩余问题）。,2.4,公钥（非对称）,密码体制,2.4.2,公钥密码体制的原理,公钥密码体制的基本数学方法和基本原理如下所述。,2,用于构造公钥密码的常用单向函数,）迪菲,-,赫尔曼（,Diffie-Hellman,）问题,给定素数,p,，可构造一乘群,Z,*,p,，令,为,Z,*,p,的生成元，若已知,a,、,b,，求,ab,的问题即为菲,-,赫尔曼问题。,）二次剩余问题,给定一个奇合数,n,和整数,a,，决定,a,是否为,mod,n,平方剩余问题就称为二次剩余问题。,2.4,公钥（非对称）,密码体制,2.4.2,公钥密码体制的原理,公钥密码体制的基本数学方法和基本原理如下所述。,3.,公钥密码体制的原理,若用户,A,有一个加密密钥,k,a,，同时还有一个解密密钥,k,a,，可将加密密钥,k,a,公开，而解密密钥,k,a,保密。若用户,B,要向,A,传送信息的明文为,m,，可查,A,的公开密钥,k,a,，若用,A,的公开密钥,k,a,加密得到密文,c=Ek,a,（,m,）,则,A,收到密文,c,以后，用只有自己才知道的解密密钥,k,a,对,c,进行解密得,m=Dk,a,（,c,）,图,2.14,公钥密码体系模型,2.4,公钥（非对称）,密码体制,2.4.3 RSA,算法,1978,年，美国麻省理工学院,(,MIT),的研究小组成员：李维斯特,(,Rivest),、,沙米尔,(,Shamir),、,艾德曼,(,Adleman),提出了一种基于公钥密码体制的优秀加密算法,RSA,算法。,RSA,的取名就是来自于这三位发明者的姓的第一个字母，后来，他们在,1982,年创办了以,RSA,命名的公司,RSA Data Security Inc.,和,RSA,实验室，该公司和实验室在公开密钥密码系统的研究和商业应用推广方面具有举足轻重的地位。,RSA,密码系统的安全是,基于大整数分解因子的难度,，其公开密钥,(,现在一般是,1024,位甚至更长,),和私人密钥是,一对大素数,的函数。一般来说，,求一对大素数的乘积相对比较容易，但要对这个乘积进行因式分解则非常困难,。因此，可以把一对大素数的乘积作为公开密钥公布，而把素数作为私钥，从而从一个公开密钥和密文中恢复出明文的难度等价于分解两个大素数之积。,2.4,公钥（非对称）,密码体制,2.4.3 RSA,算法,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,，,