代数在网络安全中的应用培训课件

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,2016/12/12,#,代数在网络安全中的应用,20131989,应用数学,2,班童钞,概述,现有的公钥密码体制大多是建立在交换代数的基础上,例如著名的,RSA,密码体制、,Diffie,Hellman,密钥交换,协议和,ELGamal,密码体制都,基于整数环,而概率公钥算法,NTRU,则,基于多项式环交换代数结构的优点在于有丰富的理论、容易理解的结构并且易于实现但是,由于计算能力的持续增强,为保证预期安全水平所需要的密钥长度也不断增长,这就使得基于交换代数的公钥密码遭遇了计算瓶颈因此有必要寻找基于更加复杂的代数结构的密码技术,近年出现的一种具有强大竞争力的椭圆曲线密码学（,ECC,）对,RSA,提出了挑战在关于公钥密码学的,IEEEP1363,中,已经考虑了,ECC,在公钥密码学中使用椭圆曲线是,Neal,Koblitz,和,Victor,Miller,于,1985,年各自独立地提出的与,RSA,相比, ECC,的主要诱人之处在于它可以用比,RSA,短得多的密钥得到相同的安全性,因此可以减少处理负荷,近年来,基于（超奇异）椭圆曲线上双线性对的密码体制的研究十分活跃,解决了构造三方一轮,Diffie,Hellman,密钥协议、短签名方案和基于身份加密算法等长期悬而未决的公开问题但是,正如,Barreto,Lynn,Scott,所指出,（超奇异）椭圆曲线上,Weil,对与,Tate,对的运算成本经常使它成为基于双线性对密码系统的瓶颈寻找安全高效的双线性对已成为基于双线性对密码学的首要问题,目前,已经出现了一些使用非交换代数的公钥密码系统,尤其是辫子群密码学吸引了大量的研究,1999,年,Anshel-Anshel-Goldfeld,基于,辫子群中的共轭问题构建了密钥交换协议,2000,年, KoLee,等,人利用,辫子群,的子,群间的交换关系构建了基于广义共轭问题的,Diffie,Hellman,密钥交换协议,以及一个类似于,ELGamal,体制,的加密算法,但是,由于非交换群中没有像整数环中加法那样与共轭运算相容的运算,这使得基于非交换群的,签名方案,的设计变得困难直到,2002,年,Ko-Choi-Cho-Lee,才,基于共轭问题的计算形式和判定形式之间的,鸿沟（,Gap,）设计了第一个辫子群签名方案,目录,基于椭圆曲线的密码算法,循环矩阵在网络安全中的应用,DES,算法,基于双线性对的密码学,基于辫子群的密码体制,AES,算法,RSA,算法,SHA-1,算法,离散对数密码体制,椭圆曲线在网络安全中的应用,椭圆曲线的定义及点的加法运算,有限域上的椭圆曲线,椭圆曲线的离散对数问题,椭圆曲线密码体制的概念,椭圆曲线密码体制是属于公钥密码体制中的一种，它主要的数学理论基础是源于数论的相关知识，它是通过有限域中椭圆曲线上的点构成的,Aebel,加法群，在,Aebel,群中计算椭圆对数,。,现在国际上比较流行的密码体制都是以三种难解的理论为依据而设计的，其中一种是基于大整数因子分解问题设计的比如,RSA,公钥密码体制，还有一种是基于离散对数的难解问题而设计的比如,ELGamal,公钥密码体制，最后一种就是同样基于离散对数问题设计的椭圆曲线密码体制。,构造椭圆曲线,ElGamal,算法,ElGamal,算法，是一种较为常见的加密算法，它是基于,1984,年提出的公钥密码体制和椭圆曲线加密体系。既能用于数据加密也能用于数字签名，其安全性依赖于计算有限域上离散对数这一难题。在加密过程中，生成的密文长度是明文的两倍，且每次加密后都会在密文中生成一个随机数,K,，在密码中主要应用离散对数问题的几个性质：求解离散对数（可能）是困难的，而其逆运算指数运算可以应用平方,-,乘的方法有效地计算。也就是说，在适当的群,G,中，指数函数是单向函数。,椭圆曲面密码体制的应用背景及优势,我们现在快速的生活节奏和便捷的生活方式都是显而易见的，足不出户的我们就能够通过计算机完成许多的事情，比如工作、购物等，由于需求的增加导致计算机也不断的改进提高，尤其是计算机速度的提高，同时也就需要更好更完善的加密方案。由于现在普遍使用的是经典的公钥密码体制,RSA,，但在密钥长度为,512,比特的情况下却逐渐变得不安全，通过加长密钥长度虽然可以提高密码的安全性能，但是加密解密的效率也会变得越来越低，所以最好的方式就是设计一种新的密码体制替代原本使用的,4,。,椭圆曲线密码体制就是在这样的背景下开始逐渐受到重视的，是一种以椭圆曲线相关数学知识为基础的公钥密码体制,4,。在公钥密码体制中与其它算法相比较，椭圆曲线密码体制具有密钥短和计算效率高等典型优点，而其本身的算法及其数学理论都是非常深奥难懂的。椭圆曲线密码体制应用在实际中的主要优势有：,安全性能较高，速度快，计算量小、效率高,对于所有的密码体制而言，它的安全性能毫无疑问的成为了核心的问题，对于椭圆曲线密码体制来说它的数学原理是对它安全性能最有利的左证。该体制的核心是有限域上的离散对数问题,4,，而这个问题是不能在多项式时间内使用所有的已知算法来求解的，由此可见该体制的抗攻击性能与其它体制相比是占有绝对优势的。下面通过一个表格可以更直观的感受椭圆曲线密码体制的这点优势,由表格可以看出，将,160,位的,ECC,算法和,1024,位的,RSA,算法作为比较它们的安全强度相差不多，并且在同等的条件下安全强度要求越高的话,ECC,算法的短密钥优势也就显现的更为明显。所以，,ECC,算法与,RSA,算法相比较在每一比特都是拥有更高的安全性能的，也正是由于拥有这样的特点，才能广泛的应用于移动的电子商务以及计算机网络安全和软件注册的相关领域。,公开密钥的生成速度主要取决于其中的大数算术运算而它的运算速度自然和它的大小规模息息相关，在一个相同的计算条件下，椭圆曲线密码体制（,ECC,）的实现可以选择比基于大合数因子分解困难性的公开密钥密码体制（,RSA,）小很多的大数，这也就保证了实现的速度和效率。同样可以通过下面表格中的数据来说明,通过上表就可以明显的看出,ECC,在密钥对的生成速度、签名速度和认证方面的速度都快得多，计算量小且计算速度快，尤其是在存储容量不大运算能力比较低的情况下是具有显著优势的。,所需存储的空间比较小，带宽要求较低,椭圆曲线密码体制的密钥长度与基于大合数因子分解困难性的公开密钥密码体制相比就要小很多，这一点也可以从表,1,中看出来，比如,RSA,需要,512,位元元而,ECC,只需要,106,位即可，这也就表明了,ECC,对存储空间的需求要较小，在计算上的开销也很小，所以,ECC,会广泛的应用在类似这些存储空间有限制的设备中。,同样也是由于这样的优势决定了,ECC,可以广泛的使用在移动通信设备和智能卡等存储空间小计算能力相对较差的设备上。,带宽即频带宽度是指可以有效通过某信道的信号最大频带宽度。因为椭圆曲线密码体制和其它加密算法相比具有密钥短的特点，所以在传输中要求的带宽也更低，当对一个长的数据信息进行加密时,ECC,和,RSA,密码系统有同样的带宽要求,8,，但是应用在较短的数据信息中,ECC,的带宽要求却低很多，这也是,ECC,能够广泛的应用于无线网络中的重要原因。,ECC,的使用可以减少一定的带宽开销所以使得通信的效率也大幅提高，并且在,Web,服务器上使用带宽的费用是十分高昂的，,ECC,的出现既解决了需要节省计算时间的要求又节约了因带宽需要的花费。在,3G,网络中针对计算效率低、带宽资源有限的限制，基于椭圆曲线密码体制而涉及安全的支付流程是可以实现端对端的安全数据信息传送。,在对系统初始化以及设置系统参数时椭圆曲线密码体制也有不同于其它密码体制的优势，比如与,RSA,算法相比，,RSA,需要选取两个素数才能初始化，而,ECC,则需要选择一个素数并在有限域上选取不同的椭圆曲线，因为选择椭圆曲线时有很多的选择所以初始化的选择空间就很大。,基于以上的这些优点，椭圆曲线密码体制在实际中的应用十分广泛，比如虚拟专用网络,VPN,安全隧道方面由于要考虑到计算机存储和资源方面对嵌入式应用的局限性，依据,ECC,加密解密速度较快、节省带宽和节省所需要的存储资源的特点可以选择使用椭圆曲线密码体制设计应用于身份鉴别中，在网络的通信中必须要高效率的对数据信息进行加密，而,ECC,的快速处理速度可以使通信不再受限于存储的容量大小和计算能力的高低。除此之外，椭圆曲线密码体制在数字签名等需要高加密速度的方面也能快速实现安全高效的加密、签名。,指纹加密与椭圆曲线,随着近几年科技的发展，尤其是生物特征识别技术的逐步成熟，通过利用生物体本身具有唯一稳定不变性的特征将其运用到确保信息安全的领域，指纹加密技术就是生物识别技术与信息安全融洽结合的最好体现。由于生物特征的唯一性就可以保证使用指纹信息进行身份验证会比其他方案有更高的安全性、准确性。,指纹采集端和指纹认证端是分开工作的，它们之间通过网络传输数据信息，这也是指纹识别认证系统中的一个特点。首先是采集指纹信息的过程，用户通过提取指纹的仪器完成该步骤，然后再将指纹信息的数字图像传送给计算机。之后计算机完成指纹特征的采集工作，并将指纹的数字图像转换成即将进行加密操作的特征序列。此时就可以将加密后的信息传送到指纹认证的终端了，在终端完成对应的解密操作、指纹特征的对比操作，最后将对比的结果返回，也就是完成了一次通过网络对指纹身份的识别认证操作。该方案与上文中介绍的,EIGamal,方案的原理基本相同，具体如下,方案的优缺点,该方案的优点主要体现在指纹的唯一性决定了较高的安全性，也就是说其他的加密方式也能够达到同样安全的效果。换言之，这个方案的安全性并不取决于加密算法的复杂程度，而是取决于加密的数据信息的安全强度。但是，与其他的加密方式相比椭圆曲线使用较少、较小的参数完成过程，尤其与,RSA,算法相比计算过程更不易出错，所以使用椭圆曲线密码体制进行加密还是比较高效的。,椭圆曲线密码体制与,RSA,密码体制在实际应用中的比较,椭圆曲线密码算法和,RSA,算法相比最大的优点就是不需要计算椭圆曲线有理点群的离散对数问题的子指数算法，也就是说当在同等安全的条件下，椭圆曲线密码算法可以选择比,RSA,算法更小的参数进行加密解密操作。同时椭圆曲线密码算法将实数域中乘法的运算和指数的运算映像成了椭圆曲线上加法的运算。综上所述，椭圆曲线密码体制更实用、更容易、更安全，同时成本也更低。,将两种算法作比较可以发现，,RSA,算法的过程不仅复杂还必须严格保密，对于素数的产生和检测的计算过程容易产生错误；而椭圆曲线密码算法虽然生成的参数复杂但是不需要保密甚至还可以对外公布，不过虽然保密的密钥生成复杂但是计算公钥很容易。,椭圆曲线密码体制具有椭圆曲线丰富、不易被破解、不需要大量的参数参与计算及不占用大量存储空间的优势。比如在数字签名中完成各部分的效率方面进行比较，,RSA,算法是几乎不会受到密钥位数变化的影响，一直都可以保持着很快的验证速度，相反地，,ECC,算法受到的影响很剧烈，与,RSA,算法受影响程度相比有很大的差距。在使用超过一定的密钥位数的范围中，随着密钥位数逐渐地增大,ECC,算法就会越优于,RSA,算法。,对于相同使用量的参数，椭圆曲线密码体制在每一比特的加密解密过程中都拥有更大的强度，并且所需要的参数规模也较小，这在实际的应用中是具有很大优势的。椭圆曲线虽然子在一个有限域中只有有限的几个乘法子群，但是却有很高的安全性能，所以成为公钥密码学中应用广泛的新体制。,二,、循环矩阵在网络安全中的应用,多变量密码学中的循环矩阵,等价的多项式定义了相同密码体制，因此等价的多项式产生的密码体制也有相同的密钥空间和加,/,解密映射的集合。一个等价类的势,(cardinality),相当于选取不同的仿射变换对所产生的加密映射的个数,.,这就引出了找到产生相同加密映射的仿射变换的个数问题,.,例如,:,对于一个给定的多变量公钥密码体制，找到其等价密钥的个数。在一个等价类中的不同多项式方程组的个数代表可以选择的不同密钥的个数。等价密钥的存在可以缩小密钥空间，这对于多变量公钥密码学的密码分析是很有帮助的。,多项式同构引出多项式方程组的等价关系,.,因此多项式方程组的集合可以被划分为不同的等价类。多项式同构的计数问题则包含以下,3,个方而,:,1),对不同等价类的计数,;,2),对每一个等价类的势进行计数,;,3),确定所有的等价类的代表元,.,基于循环矩阵的,ElGamal,密码体制,离散对数问题是公钥密码学中应用最广泛的一个密码原语。其应用之一是最经典的,ElGamal,密码系统。众所周知，,ElGamal,密码系统的安全性依赖于有限域上的离散对数问题。为了能够提出更安全的密码系统，人们开始将有限域上的离散对数问题推广到非交换群上的离散对数问题，并在此上提出了,MOR,密码系统，可以说,MOR,密码系统是,ElGamal,密码系统在非交换群上的推广。而这个非交换群是循环矩阵群的自同构群。，循环矩阵群提供了一个有限域上的同样大小的安全，且它有一半的计算成本。循环矩阵的另一个有趣的事实是：其能提供一个安全的域的实现大小。循环矩阵的算法是在有限域上进行运算，这与椭圆曲线的情况极为相似。在循环的情况下，该域的大小甚至可以小于一个用于椭圆曲线的大小。总之，循环矩阵的优点是，它使用较小的域而且运算速度更快。在该文献中，所有矩阵是非奇异循环矩阵,C(,d,q,),和特殊循环矩阵，即循环矩阵的行列式,1,，记为,SC(,d,q,),。,ElGamal,密码体制在,SC(,d,q,),的实现,在,SC(d, q),的,ElGamal,密码系统中，需要进行十二次的逆操作，这是很容易计算的。自公钥密码学概念提出以来，许多优秀的公钥密码体制相继被提出并得到完善。目前，大多数未被攻破的公钥密码体制都是基于交换代数结构的困难问题，如大整数分解问题、有限域上的离散对数问题等。然而，由于量子计算的最新研究成果，许多基于交换代数结构的难题假设不再困难。迄今为止，人们已经提出了许多基于非交换代数结构的公钥密码体制，特别是辫群密码体制吸引了大量的研究。经过本文的探究，我们可以知道，循环矩阵是数学研究中非常重要的一个数学计算手段，它本身具有很多特殊性质。本文针对循环矩阵的特殊性质，研究了其在密码学中的公钥密码加密解密的过程中的应用。随着电子科技的发展，以及电子通信的普及，密码学得到了前所未有的发展机遇。我们从数学工具，数学算法的角度出发，进行创造性思维，使其在密码学中发挥作用，相信对密码学的研究会越来越成熟。,DES,算法,DES,是一种分组密码协议，有两个基本指导思想扩散（,Diffusion,）和混乱（,Confusion,）,以保证密码算法能满足要求，所以,DES,的具体实现是依赖于多次迭代进行乘积密码加密变换。,这个算法的核心是,Feistel,密码，由于其设计的巧妙，加密解密都用一个函数。它的算法是对称的，既可用于加密又可用于解密,。,DES,使用一个,56,位的密钥以及附加的,8,位奇偶校验位，产生最大,64,位的分组大小。这是一个迭代的分组密码，使用称为,Feistel,的技术，其中将加密的文本块分成两半。使用子密钥对其中一半应用循环功能，然后将输出与另一半进行“异或”运算；接着交换这两半，这一过程会继续下去，但 最后一个循环不交换。,DES,使用,16,个循环，使用异或，置换，代换，移位操作四种基本运算。,DES,的流程基本是执行,16,轮下面的运算：,1,初始变换,Initial Permutation,2,右边,32,位,f,函数,2.1 E,置换,2.2,与轮密钥,XOR,2.3 S,盒替换,2.4 P,置换,2.5,和左边,32,位,XOR,3,左右交换，最终变换,final permutation,需要特别注意的是，最后一轮是不需要做左右交换这一部的,。,从,具体实现看,DES,有几个已知的方面存在脆弱性：,1,，加密协议半公开化,2,，密钥太短,3,，软件的实现的性能较低。随着计算机的处理能力的提高，只有,56,位密钥的,DES,算法不再被认为是安全性的，故现在一般的方案是三重,DES,，既,3DES,。,AES,算法,AES,（,The Advanced Encryption Standard,）是一种非,Feistel,的对称分组密码体制，和,DES,的基本指导思想一样都是多次混淆，所不同的是非线性层的由,16,个,S,盒进行并置混淆。,AES,具有安全可靠、效率高等优点。,AES,加密过程是在一个,44,的字节矩阵上运作，这个矩阵又称为,“,状态（,state,）,”,，其初值就是一个明文区块（矩阵中一个元素大小就是明文区块中的一个,Byte,）。（,Rijndael,加密法因支持更大的区块，其矩阵行数可视情况增加）加密时，各轮,AES,加密循环（除最后一轮外）均包含,4,个步骤：,1. AddRoundKey ,矩阵中的每一个字节都与该次轮秘钥（,round key,）做,XOR,运算；每个子密钥由密钥生成方案产生。,2. SubBytes ,通过个非线性的替换函数，用查找表的方式把每个字节替换成对应的字节。,3. ShiftRows ,将矩阵中的每个横列进行循环式移位。,4. MixColumns ,为了充分混合矩阵中各个直行的操作。这个步骤使用线性转换来混合每列的四个字节。,AddRoundKey,步骤,在,AddRoundKey,步骤中，将每个状态中的字节与该回合密钥做,异或,（）。,AddRoundKey,步骤，回合密钥将会与原矩阵合并。在每次的加密循环中，都会由主密钥产生一把回合密钥（通过,Rijndael密钥生成方案,产生），这把密钥大小会跟原矩阵一样，以与原矩阵中每个对应的字节作,异或,（）加法。,SubBytes,步骤,在,SubBytes,步骤中，矩阵中各字节被固定的,8,位查找表中对应的特定字节所替换,S;bij=S,（,aij,）,.,在,SubBytes,步骤中，矩阵中的各字节通过一个,8,位的,S-box,进行转换。这个步骤提供了,加密法,非线性的变换能力。,S-box,与,GF,（,28,）上的乘法,反元素,有关，已知具有良好的,非线性,特性。为了避免简单代数性质的攻击，,S-box,结合了乘法反元素及一个可逆的,仿射变换,矩阵建构而成。此外在建构,S-box,时，刻意避开了,固定点,与,反固定点,，即以,S-box,替换字节的结果会相当于错排的结果。,ShiftRows,步骤,在,ShiftRows,步骤中，矩阵中每一行的各个字节循环向左方位移。位移量则随着行数递增而递增。,ShiftRows,描述矩阵的行操作。在此步骤中，每一行都向左循环位移某个,偏移量,。在,AES,中（区块大小,128,位），第一行维持不变，第二行里的每个字节都向左循环移动一格。同理，第三行及第四行向左循环位移的偏移量就分别是,2,和,3,。,128,位和,192,比特的区块在此步骤的循环位移的模式相同。经过,ShiftRows,之后，矩阵中每一竖列，都是由输入矩阵中的每个不同列中的元素组成。,Rijndael,算法的版本中，偏移量和,AES,有少许不同；对于长度,256,比特的区块，第一行仍然维持不变，第二行、第三行、第四行的偏移量分别是,1,字节、,3,字节、,4,位组。除此之外，,ShiftRows,操作步骤在,Rijndael,和,AES,中完全相同。,MixColumns,步骤,在,MixColumns,步骤中，每个直行都在,modulo,之下，和一个固定多项式,c(x),作乘法。,在,MixColumns,步骤，每一列的四个字节通过,线性变换,互相结合。每一列的四个元素分别当作,的系数，合并即为,GF,（,28,）中的一个多项式，接着将此多项式和一个固定的,多项式,在,modulo,下,相乘。此步骤亦可视为,Rijndael有限域,之下的矩阵乘法。,MixColumns,函数接受,4,个字节的输入，输出,4,个字节，每一个输入的字节都会对输出的四个字节造成影响。因此,ShiftRows,和,MixColumns,两步骤为这个密码系统提供了,扩散性,。,大致说来，,AES,加密算法的核心有四个操作。,AddRoundKey,使用从种子密钥值中生成的轮密钥代替,4,组字节。,SubBytes,替换用一个代替表 替换单个字节。,ShiftRows,通过旋转,4,字节行 的,4,组字节进行序列置换。,MixColumns,用域加和域乘的组合来替换字节。,正如你所看到的，,AES,加密算法使用相当简单明了的技术来代替和置换，除,MixColumns,例程以外。,MixColumns,使,用特殊的加法和乘法。,AES,所用,的加法和乘法是基于,数学的,域论。尤其是,AES,基于有限域,GF(28),。,GF(28),由一组从,0x00,到,0xff,的,256,个值组成，加上加法和乘法，因此是,(28),。,GF,代表伽罗瓦域，以发明这一理论的数学家的名字命名。,GF(28),的一个特性是一个加法或乘法的操作的结果必须是在,0x00 . 0xff,这组数中。虽然域论是相当深奥的，但,GF(28),加法的最终结果却很简单。,GF(28),加法就是异或（,XOR,）操作。,在,GF(28),中用,0x01,的乘法是特殊的；它相当于普通算术中用,1,做乘法并且结果也同样任何值乘,0x01,等于其自身。,现在让我们看看用,0x02,做乘法。和加法的情况相同，理论是深奥的，但最终结果十分简单。只要被乘的值小于,0x80,，这时乘法的结果就是该值左移,1,比特位。如果被乘的值大于或等于,0x80,，这时乘法的结果就是左移,1,比特位再用值,0x1b,异或。它防止了“域溢出”并保持乘法的乘积在范围以内。,一旦你在,GF(28),中用,0x02,建立了加法和乘法，你就可以用任何常量去定义乘法。用,0x03,做乘法时，你可以将,0x03,分解为,2,的幂之和。为了用,0x03,乘以任意字节,b,， 因为,0x03 = 0x02 + 0x01,，因此：,b * 0x03 = b * (0x02 + 0x01) = (b * 0x02) + (b * 0x01),这是可以行得通的，因为你知道如何用,0x02,和,0x01,相乘和相加，用,0x0d,去乘以任意字节,b,可以这样做：,b * 0x0d = b * (0x08 + 0x04 + 0x01) = (b * 0x08) + (b * 0x04) + (b * 0x01) = (b * 0x02 * 0x02 * 0x02) + (b * 0x02 * 0x02) + (b * 0x01),在加解密算法中，,AES MixColumns,例程的其它乘法遵循大体相同的模式，如下所示：,b * 0x09 = b * (0x08 + 0x01) = (b * 0x02 * 0x02 * 0x02) + (b * 0x01) b * 0x0b = b * (0x08 + 0x02 + 0x01) = (b * 0x02 * 0x02 * 0x02) + (b * 0x02) + (b * 0x01) b * 0x0e = b * (0x08 + 0x04 + 0x02) = (b * 0x02 * 0x02 * 0x02) + (b * 0x02 * 0x02) + (b * 0x02),总之，在,GF(28),中，加法是异或操作。其乘法将分解成加法和用,0x02,做的乘法，而用,0x02,做的乘法是一个有条件的左移,1,比特位。,AES,规范中包括大量 有关,GF(28),操作的附加信息。,有限域,GF(28),的加法和乘法,类似,DES,，,AES,等算法中双方都使用相同的密钥进行加密解密，我们把这种加解密都使用同一个密钥的密码体制称为对称密码体制。使用相同的密钥进行加密解密，密钥的传输是一个重要的问题。所以，在公开的计算机网络上安全地传送和保管密钥是一个严峻的问题。,于是，密码学家们构想了一个不一样的的密码体制来解决这一问题,-,公钥加密算法。公钥加密算法也称非对称密钥算法，用两对密钥：一个公共密钥和一个专用密钥。用户要保障专用密钥的安全；公共密钥则可以发布出去。公共密钥与专用密钥是有紧密关系的，用公共密钥加密的信息只能用专用密钥解密，反之亦然。由于公钥算法不需要联机密钥服务器，密钥分配协议简单，所以极大简化了密钥管理。除加密功能外，公钥系统还可以提供数字签名。,RSA,是其中的一种有效实现。,RSA,的基本指导思想是设计有效的单向陷门函数，来使得正向加密计算容易、没有密钥下的反向计算几乎不可能。,RSA,的安全性是建立在大整数分解的困难性上的。,RSA,算法,假设,Alice,想要通过一个不可靠的媒体接收,Bob,的一条私人讯息。她可以用以下的方式来产生一个,公钥,和一个,私钥,：,随意选择两个大的,质数,p,和,q,，,p,不等于,q,，计算,N,=,pq,。,根据,欧拉函数,，求得,r = (,p,-1)(,q,-1),选择一个小于,r,的整数,e,，求得,e,关于模,r,的,模反元素,，命名为,d,。（模反元素存在，当且仅当,e,与,r,互质）,将,p,和,q,的记录销毁。,(N,e),是公钥，,(N,d),是私钥。,Alice,将她的公钥,(N,e),传给,Bob,，而将她的私钥,(N,d),藏起来。,公钥与密钥的产生,假设,Bob,想给,Alice,送一个消息,m,，他知道,Alice,产生的,N,和,e,。他使用起先与,Alice,约好的格式将,m,转换为一个小于,N,的整数,n,，比如他可以将每一个字转换为这个字的,Unicode,码，然后将这些数字连在一起组成一个数字。假如他的信息非常长的话，他可以将这个信息分为几段，然后将每一段转换为,n,。用下面这个公式他可以将,n,加密为,c,：,ne c (mod N),计算,c,并不复杂。,Bob,算出,c,后就可以将它传递给,Alice,。,加密消息,Alice,得到,Bob,的消息,c,后就可以利用她的密钥,d,来解码。她可以用以下这个公式来将,c,转换为,n,：,cd n (mod N),得到,n,后，她可以将原来的信息,m,重新复原。,解码的原理是：,cd ned(mod N),以及,ed, 1 (mod,p,-1),和,ed, 1 (mod,q,-1),。由,费马小定理,可证明（因为,p,和,q,是质数）,ned n (mod p),和,ned n (mod q),这说明（因为,p,和,q,是,不同,的质数，所以,p,和,q,互质）,ned n (mod pq),解密消息,RSA,也可以用来为一个消息署名。假如甲想给乙传递一个署名的消息的话，那么她可以为她的消息计算一个,散列值,(Message digest),，然后用她的密钥,(private key),加密这个散列值并将这个,“,署名,”,加在消息的后面。这个消息只有用她的公钥才能被解密。乙获得这个消息后可以用甲的公钥解密这个散列值，然后将这个数据与他自己为这个消息计算的散列值相比较。假如两者相符的话，那么他就可以知道发信人持有甲的密钥，以及这个消息在传播路径上没有被篡改过。,签名消息,当,p,和,q,是一个大素数的时候，从它们的积,pq,去分解因子,p,和,q,，这是一个公认的数学难题。然而，虽然,RSA,的安全性依赖于大数的因子分解，但并没有从理论上证明破译,RSA,的难度与大数分解难度等价。,1994,年,彼得秀尔,（,Peter Shor,）证明一台,量子计算机,可以在多项式时间内进行因数分解。假如量子计算机有朝一日可以成为一种可行的技术的话，那么秀尔的算法可以淘汰,RSA,和相关的衍生算法。（即依赖于分解大整数困难性的加密算法）,另外，假如,N,的长度小于或等于,256,位,，那么用一台个人电脑在几个小时内就可以分解它的因子了。,1999,年，数百台电脑合作分解了一个,512,位长的,N,。,1997,年后开发的系统，用户应使用,1024,位密钥，证书认证机构应用,2048,位或以上。,RSA,加密算法的安全性,虽然,RSA,加密算法作为目前最优秀的公钥方案之一，在发表三十多年的时间里，经历了各种攻击的考验，逐渐为人们接受。但是，也不是说,RSA,没有任何缺点。由于没有从理论上证明破译,RSA,的难度与大数分解难度的等价性。所以，,RSA,的重大缺陷是无法从理论上把握它的保密性能如何。在实践上，,RSA,也有一些缺点：,产生密钥很麻烦，受到素数产生技术的限制，因而难以做到一次一密；,分组长度太大，为保证安全性，,n,至少也要,600 bits,以上，使运算代价很高，尤其是速度较慢，。,RSA,加密算法的缺点,SHA-1,算法,与其他算法不一样的是，,SHA-1,设计的出发点是用于数字签名，其本质是一种散列函数（,HASH,）。哈希（,Hash,）是将目标文本转换成具有相同长度的、不可逆的杂凑字符串（或叫做消息摘要）,由于哈希算法的定义域是一个无限集合，而值域是一个有限集合，将无限集合映射到有限集合，根据,“,鸽笼原理,(Pigeonhole principle)”,，每个哈希结果都存在无数个可能的目标文本，因此哈希不是一一映射，是不可逆的。,离散对数密码体制,1976,年,Diffie,和,Hellman,首次提出了密钥协商协议，自此之后直到,1984,年,EIGamal,才提出了基于离散对数难解问题的公钥加密方案和公钥签名方案,4,。从此之后还有很多的学者提出了许多相关的密钥方案，但大多数都是基于离散对数问题的公开密钥密码方案的变形。下面将要简单的介绍一下最基本的,ELGamal,公钥加密方案以及数字签名算法,DAS,。在基于离散对数问题的密码体制中密钥和公开的参数,对,是,息息相关的，,其中,P,是素数，,q,是,p-1,的素因子。,g,的阶是,q,也就是说,t=q,是满足,的最小正整数。私钥是从,区间,内,随机选择的一个整数，其相应的公钥就是,。,对于已经确定的,参数,和,y,想要得,到,x,的数值就是离散对数问题（,DLP,，,Discrete logarithm,problem,）。,DL,密钥生成机制,总结,密码,编码学主要研究对信息进行变换，以保护信息在传递过程中不被敌方窃取、解读和利用的方法,。除了,密码分析学之外，密码编码学主要致力于信息加密、信息认证、数字签名和密钥管理方面的研究。信息加密的目的在于将可读信息转变为无法识别的内容，使得截获这些信息的人无法阅读，同时信息的接收人能够验证接收到的信息是否被敌方篡改或替换过；数字签名就是信息的接收人能够确定接收到的信息是否确实是由所希望的发信人发出的；密钥管理是信息加密中最难的部分，因为信息加密的安全性在于密钥。数字签名大致包含两个算法：一个是签署，使用私密密钥处理信息或信息的杂凑值而产生签章；另一个是验证，使用公开钥匙验证签章的真实性,。密码学,的应用更是广泛渗透到各个,领域,。,谢谢,