代数在网络安全中的应用

代数在网络安全中的应用20131989应用数学2班童钞概述•现有的公钥密码体制大多是建立在交换代数的基础上,例如著名的RSA密码体制、Diffie－Hellman密钥交换协议和ELGamal密码体制都基于整数环,而概率公钥算法NTRU则基于多项式环．交换代数结构的优点在于有丰富的理论、容易理解的结构并且易于实现．但是,由于计算能力的持续增强,为保证预期安全水平所需要的密钥长度也不断增长,这就使得基于交换代数的公钥密码遭遇了计算瓶颈．因此有必要寻找基于更加复杂的代数结构的密码技术．•近年出现的一种具有强大竞争力的椭圆曲线密码学（ECC）对RSA提出了挑战．在关于公钥密码学的IEEEP1363中,已经考虑了ECC．在公钥密码学中使用椭圆曲线是NealKoblitz和VictorMiller于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算法•离散对数密码体制椭圆曲线在网络安全中的应用•椭圆曲线的定义及点的加法运算椭圆曲线其实并不是椭圆形状，只是因为椭圆曲线的方程和计算椭圆周长的方程类似，所以称它为椭圆曲线，椭圆曲线的方程是：23213246yaxyayxaxaxa其中,,,,,()123456aaaaaaFF是一个域，而F域既可以是一个有理数域也可以是一个复数域还可以是有限域()GFp，通常将满足上述方程的数(,)xy称为F域中椭圆曲线E上的点[4]。假设P点和Q是点椭圆曲线上的两个点并在椭圆曲线上定义加法运算+PQR，R表示通过连接P点和Q点的直线与椭圆曲线E相交，交点关于x轴对称的点称为R点。如图3-1。特别地，如果P点和Q点是重合的，R就表示P点的切线与椭圆曲线E的交点关于x轴对称的点，即2PQPPPR。这里定义的加法运算需要引进一个零元素，将0定义为一个无穷点即0（，），那么0+0=000（，）（，）并且0,+=0,PPP（）（x,y）（x,y）+（）（x,y），假设(,)11Pxy和(,)22Qxy是解点，如果,1212xxyy就有(,)+Q(,)=01122Pxyxy，当(,)11Pxy和(,)22Qxy不相等的时候就有(,)+Q(,)=(,)112233PxyxyRxy，其中2312xxx，()3131yxxy，()/()2121yyxx，如果P点和Q点是重合的，那么2231xx，()3131yxxy，2(3)/(2)11xay。由此可知椭圆曲线E在有限域F上的加法运算，构成了加法交换群并且加法单位元为0[4]。有限域上的椭圆曲线对有理数、实数、复数等常见的数系和它们基本特征的抽象称为域，是由一个集合和加法乘法两种运算来组成的[4]。一个集合域，域中除0以外的数位如果满足以下的特性：1、域对加法封闭，并对加法运算构成加法交换群；2、域对乘法封闭，并对乘法运算构成乘法交换群；3、使分配律成立，对域中任意的数字,,abc都有()abcacbc成立，并且这个集合是有限集合，那就称这个域为有限域。有限域中含有元素的个数被称为这个有限域的阶。如果在有限域F上定义出一条椭圆曲线E，那么椭圆曲线E的个数就称为在有限域F上椭圆曲线E的阶。椭圆曲线的离散对数问题椭圆曲线离散对数问题就是指在有限域F上定义出一条椭圆曲线E，在E上给定一个基点P并计算出阶N即0NP。然后在椭圆曲线E上寻找任意一点Q，在[0,1]N的范围内找一个正整数k使=QkP成立，这时将正整数k称为点Q对点P的椭圆离散对数即将k表示为logkQp。已知椭圆曲线E的离散对数k和E上的一个基点P可以比较容易将点Q计算出来，但是如果已知点Q和E上的一个基点P想要计算出离散对数k是十分难的，以至于迄今为止都没有有效的方法来计算，同时也正是因为有这样难解的问题存在，Koblitz和Miller就在这个基础上建立了椭圆曲线密码体制ECC而这也正是椭圆曲线密码的加密原理。椭圆曲线密码体制的概念•椭圆曲线密码体制是属于公钥密码体制中的一种，它主要的数学理论基础是源于数论的相关知识，它是通过有限域中椭圆曲线上的点构成的Aebel加法群，在Aebel群中计算椭圆对数。•现在国际上比较流行的密码体制都是以三种难解的理论为依据而设计的，其中一种是基于大整数因子分解问题设计的比如RSA公钥密码体制，还有一种是基于离散对数的难解问题而设计的比如ELGamal公钥密码体制，最后一种就是同样基于离散对数问题设计的椭圆曲线密码体制。下面简述一下椭圆曲线的离散对数问题，首先我们在有限域Fp上选取一条椭圆曲线E，p是()EFp上的点，p是素数n，那么集合,,2,3,,(1)PPPPnP是利用P生成的椭圆曲线循环子群，其中的素数p，椭圆曲线E，点p和阶n构成一个公开的参数组[4]。在区间[1,1]n内随机地选取一个正整数d作为算法中的私钥，相对应的公钥就是QdP。构造椭圆曲线在二进制域2mF上：输入：一个正整数m和1比特杂凑函数[4]H。输出：种子2,,mSabF，定义一条椭圆曲线[4]232:Eyxyxaxb。1．令(1)/sml，lms。2.S选取一个随机的二进制串，其长度g1bit。3.计算()hHS，令0b是h的最右边比特所得长度为的二进制串。4.令zS是与二进制表示相等的整数。5.对i从1到s，执行：5.1令is为整数()mod2gzi的g位二进制表示。5.2计算()iibHs。6.令010||||||||bbbb。7.若0b，则跳至步骤2。8.选择任意的2maF。9.返回(,,)Sab。ElGamal算法•ElGamal算法，是一种较为常见的加密算法，它是基于1984年提出的公钥密码体制和椭圆曲线加密体系。既能用于数据加密也能用于数字签名，其安全性依赖于计算有限域上离散对数这一难题。在加密过程中，生成的密文长度是明文的两倍，且每次加密后都会在密文中生成一个随机数K，在密码中主要应用离散对数问题的几个性质：求解离散对数（可能）是困难的，而其逆运算指数运算可以应用平方-乘的方法有效地计算。也就是说，在适当的群G中，指数函数是单向函数。椭圆曲面密码体制的应用背景及优势•我们现在快速的生活节奏和便捷的生活方式都是显而易见的，足不出户的我们就能够通过计算机完成许多的事情，比如工作、购物等，由于需求的增加导致计算机也不断的改进提高，尤其是计算机速度的提高，同时也就需要更好更完善的加密方案。由于现在普遍使用的是经典的公钥密码体制RSA，但在密钥长度为512比特的情况下却逐渐变得不安全，通过加长密钥长度虽然可以提高密码的安全性能，但是加密解密的效率也会变得越来越低，所以最好的方式就是设计一种新的密码体制替代原本使用的[4]。•椭圆曲线密码体制就是在这样的背景下开始逐渐受到重视的，是一种以椭圆曲线相关数学知识为基础的公钥密码体制[4]。在公钥密码体制中与其它算法相比较，椭圆曲线密码体制具有密钥短和计算效率高等典型优点，而其本身的算法及其数学理论都是非常深奥难懂的。椭圆曲线密码体制应用在实际中的主要优势有：安全性能较高，速度快，计算量小、效率高•对于所有的密码体制而言，它的安全性能毫无疑问的成为了核心的问题，对于椭圆曲线密码体制来说它的数学原理是对它安全性能最有利的左证。该体制的核心是有限域上的离散对数问题[4]，而这个问题是不能在多项式时间内使用所有的已知算法来求解的，由此可见该体制的抗攻击性能与其它体制相比是占有绝对优势的。下面通过一个表格可以更直观的感受椭圆曲线密码体制的这点优势•由表格可以看出，将160位的ECC算法和1024位的RSA算法作为比较它们的安全强度相差不多，并且在同等的条件下安全强度要求越高的话ECC算法的短密钥优势也就显现的更为明显。所以，ECC算法与RSA算法相比较在每一比特都是拥有更高的安全性能的，也正是由于拥有这样的特点，才能广泛的应用于移动的电子商务以及计算机网络安全和软件注册的相关领域。•公开密钥的生成速度主要取决于其中的大数算术运算而它的运算速度自然和它的大小规模息息相关，在一个相同的计算条件下，椭圆曲线密码体制（ECC）的实现可以选择比基于大合数因子分解困难性的公开密钥密码体制（RSA）小很多的大数，这也就保证了实现的速度和效率。同样可以通过下面表格中的数据来说明表5-2ECC与RSA密码软件实现的速度的比较功能163ECCms位的（）1023RSAms位的（）密钥对的生成3.84708.3签名3.0228.4认证10.712.7•通过上表就可以明显的看出ECC在密钥对的生成速度、签名速度和认证方面的速度都快得多，计算量小且计算速度快，尤其是在存储容量不大运算能力比较低的情况下是具有显著优势的。所需存储的空间比较小，带宽要求较低椭圆曲线密码体制的密钥长度与基于大合数因子分解困难性的公开密钥密码体制相比就要小很多，这一点也可以从表1中看出来，比如RSA需要512位元元而ECC只需要106位即可，这也就表明了ECC对存储空间的需求要较小，在计算上的开销也很小，所以ECC会广泛的应用在类似这些存储空间有限制的设备中。同样也是由于这样的优势决定了ECC可以广泛的使用在移动通信设备和智能卡等存储空间小计算能力相对较差的设备上。带宽即频带宽度是指可以有效通过某信道的信号最大频带宽度。因为椭圆曲线密码体制和其它加密算法相比具有密钥短的特点，所以在传输中要求的带宽也更低，当对一个长的数据信息进行加密时ECC和RSA密码系统有同样的带宽要求[8]，但是应用在较短的数据信息中ECC的带宽要求却低很多，这也是ECC能够广泛的应用于无线网络中的重要原因。ECC的使用可以减少一定的带宽开销所以使得通信的效率也大幅提高，并且在Web服务器上使用带宽的费用是十分高昂的，ECC的出现既解决了需要节省计算时间的要求又节约了因带宽需要的花费。在3G网络中针对计算效率低、带宽资源有限的限制，基于椭圆曲线密码体制而涉及安全的支付流程是可以实现端对端的安全数据信息传送。•在对系统初始化以及设置系统参数时椭圆曲线密码体制也有不同于其它密码体制的优势，比如与RSA算法相比，RSA需要选取两个素数才能初始化，而ECC则需要选择一个素数并在有限域上选取不同的椭圆曲线，因为选择椭圆曲线时有很多的选择所以初始化的选择空间就很大。•基于以上的这些优点，椭圆曲线密码体制在实际中的应用十分广泛，比如虚拟专用网络VPN安全隧道方面由于要考虑到计算机存储和资源方面对嵌入式应用的局限性，依据ECC加密解密速度较快、节省带宽和节省所需要的存储资源的特点可以选择