网络通信常用加密算法研究

网络通信常用加密算法研究

什么是对称加密和非对称加密

1. 什么是对称加密：
   对称加密采用了对称密码编码技术，它的特点是文件加密和解密使用相同的密钥，即加密密钥也可以用作解密密钥，这种方法在密码学中叫做对称加密算法，对称加密算法使用起来简单快捷，密钥较短，且破译困难，除了数据加密标准（DES），另一个对称密钥加密系统是国际数据加密算法（IDEA），它比DES的加密性好，而且对计算机功能要求也没有那么高。IDEA加密标准由PGP（Pretty Good Privacy）系统使用。
   对称加密算法在电子商务交易过程中存在几个问题：
   （1）要求提供一条安全的渠道使通讯双方在首次通讯时协商一个共同的密钥。直接的面对面协商可能是不现实而且难于实施的，所以双方可能需要借助于邮件和电话等其它相对不够安全的手段来进行协商；
   （2）密钥的数目难于管理。因为对于每一个合作者都需要使用不同的密钥，很难适应开放社会中大量的信息交流；
   （3）对称加密算法一般不能提供信息完整性的鉴别。它无法验证发送者和接受者的身份；
   （4）对称密钥的管理和分发工作是一件具有潜在危险的和烦琐的过程。对称加密是基于共同保守秘密来实现的，采用对称加密技术的贸易双方必须保证采用的是相同的密钥，保证彼此密钥的交换是安全可靠的，同时还要设定防止密钥泄密和更改密钥的程序。
   假设两个用户需要使用对称加密方法加密然后交换数据，则用户最少需要2个密钥并交换使用，如果企业内用户有n个，则整个企业共需要n×(n-1) 个密钥，密钥的生成和分发将成为企业信息部门的恶梦。
   常见的对称加密算法有DES、3DES、Blowfish、IDEA、RC4、RC5、RC6和AES
   注：DES加密算法原理：
   DES算法把64位的明文输入块变为64位的密文输出块,它所使用的密钥也是56位，其算法主要分为两步：
   1）初始置换
   其功能是把输入的64位数据块按位重新组合,并把输出分为L0、R0两部分,每部分各长32位,其置换规则为将输入的第58位换到第一位,第50位换到第2位……依此类推,最后一位是原来的第7位。L0、R0则是换位输出后的两部分，L0是输出的左32位,R0是右32位,例:设置换前的输入值为D1D2D3……D64,则经过初始置换后的结果为:L0=D58D50……D8;R0=D57D49……D7。
   其置换规则见下表：
   58,50,42,34,26,18,10,2,60,52,44,36,28,20,12,4,
   62,54,46,38,30,22,14,6,64,56,48,40,32,24,16,8,
   57,49,41,33,25,17,9,1,59,51,43,35,27,19,11,3,
   61,53,45,37,29,21,13,5,63,55,47,39,31,23,15,7,
   2）逆置换
   经过16次迭代运算后,得到L16、R16,将此作为输入,进行逆置换,逆置换正好是初始置换的逆运算，由此即得到密文输出。
   此算法是对称加密算法体系中的代表,在计算机网络系统中广泛使用.
2. 什么是非对称加密：
   与对称加密算法不同，非对称加密算法需要两个密钥：公开密钥（publickey）和私有密钥（privatekey）。公开密钥与私有密钥是一对，如果用公开密钥对数据进行加密，只有用对应的私有密钥才能解密；如果用私有密钥对数据进行加密，那么只有用对应的公开密钥才能解密。因为加密和解密使用的是两个不同的密钥，所以这种算法叫作非对称加密算法。
   非对称加密算法实现机密信息交换的基本过程是：甲方生成一对密钥并将其中的一把作为公用密钥向其它方公开；得到该公用密钥的乙方使用该密钥对机密信息进行加密后再发送给甲方；甲方再用自己保存的另一把专用密钥对加密后的信息进行解密。甲方只能用其专用密钥解密由其公用密钥加密后的任何信息。
   非对称加密算法的保密性比较好，它消除了最终用户交换密钥的需要，但加密和解密花费时间长、速度慢，它不适合于对文件加密而只适用于对少量数据进行加密。
   如果企业中有n个用户，企业需要生成n对密钥，并分发n个公钥。由于公钥是可以公开的，用户只要保管好自己的私钥即可(企业分发后一般保存的是私钥,用户拿的是公钥)，因此加密密钥的分发将变得十分简单。同时，由于每个用户的私钥是唯一的，其他用户除了可以可以通过信息发送者的公钥来验证信息的来源是否真实，还可以确保发送者无法否认曾发送过该信息。非对称加密的缺点是加解密速度要远远慢于对称加密，在某些极端情况下，甚至能比非对称加密慢上1000倍。
   常见的非对称加密算法有：RSA、ECC（移动设备用）、Diffie-Hellman、El Gamal、DSA（数字签名用）

介绍两种非对称加密算法

• RSA加密
  原理：
  （1）互质关系
  如果两个正整数，除了1以外，没有其他公因子，我们就称这两个数是互质关系（coprime）。比如，15和32没有公因子，所以它们是互质关系。这说明，不是质数也可以构成互质关系。
  （2）欧拉函数
  任意给定正整数n，请问在小于等于n的正整数之中，有多少个与n构成互质关系？（比如，在1到8之中，有多少个数与8构成互质关系？）
  φ函数的值 通式：φ(x)=x(1-1/p1)(1-1/p2)(1-1/p3)(1-1/p4)…..(1-1/pn),其中p1, p2……pn为x的所有质因数，x是不为0的整数。φ(1)=1（唯一和1互质的数(小于等于1)就是1本身）。 (注意：每种质因数只一个。比如12=2*2*3那么φ（12）=12*（1-1/2）*(1-1/3)=4
  若n是质数p的k次幂，φ(n)=p^k-p^(k-1)=(p-1)p^(k-1)，因为除了p的倍数外，其他数都跟n互质。
  设n为正整数，以 φ(n)表示不超过n且与n互
  素的正整数的个数，称为n的欧拉函数值，这里函数
  φ：N→N，n→φ(n)称为欧拉函数。
  欧拉函数是积性函数——若m,n互质，φ(mn)=φ(m)φ(n)。
  特殊性质：当n为奇数时，φ(2n)=φ(n), 证明与上述类似。
  若n为质数则φ(n)=n-1。
  （3）欧拉定理
  在数论中，欧拉定理,（也称费马-欧拉定理）是一个关于同余的性质。欧拉定理表明，若n,a为正整数，且n,a互质，则:

  
  费马小定理:
  a是不能被质数p整除的正整数，则有a^(p-1) ≡ 1 (mod p)
  证明这个定理非常简单，由于p是质数，所以有φ(p) = p-1，代入欧拉定理即可证明。推论：对于任意正整数a，有a^p ≡ a (mod p)，因为a能被p整除时结论显然成立。
  秘钥的生成步骤：
  
  假设爱丽丝要与鲍勃进行加密通信，她该怎么生成公钥和私钥呢？
  第一步，随机选择两个不相等的质数p和q。
  爱丽丝选择了61和53。（实际应用中，这两个质数越大，就越难破解。）
  第二步，计算p和q的乘积n。
  爱丽丝就把61和53相乘。
  　　n = 61×53 = 3233
  n的长度就是密钥长度。3233写成二进制是110010100001，一共有12位，所以这个密钥就是12位。实际应用中，RSA密钥一般是1024位，重要场合则为2048位。
  第三步，计算n的欧拉函数φ(n)。
  根据公式：
  　　φ(n) = (p-1)(q-1)
  爱丽丝算出φ(3233)等于60×52，即3120。
  第四步，随机选择一个整数e，条件是1< e < φ(n)，且e与φ(n) 互质。
  爱丽丝就在1到3120之间，随机选择了17。（实际应用中，常常选择65537。）
  第五步，计算e对于φ(n)的模反元素d。
  所谓”模反元素”就是指有一个整数d，可以使得ed被φ(n)除的余数为1。
  　　ed ≡ 1 (mod φ(n))
  这个式子等价于
  　　ed - 1 = kφ(n)
  于是，找到模反元素d，实质上就是对下面这个二元一次方程求解。
  　　ex + φ(n)y = 1
  已知 e=17, φ(n)=3120，
  　　17x + 3120y = 1
  这个方程可以用”扩展欧几里得算法”求解，此处省略具体过程。总之，爱丽丝算出一组整数解为 (x,y)=(2753,-15)，即 d=2753。
  第六步，将n和e封装成公钥，n和d封装成私钥。
  在爱丽丝的例子中，n=3233，e=17，d=2753，所以公钥就是 (3233,17)，私钥就是（3233, 2753）。
  实际应用中，公钥和私钥的数据都采用ASN.1格式表达（实例）。此所有计算完成。
  加密和解密：
  （1）加密要用公钥 (n,e)：
  假设鲍勃要向爱丽丝发送加密信息m，他就要用爱丽丝的公钥 (n,e) 对m进行加密。这里需要注意，m必须是整数（字符串可以取ascii值或unicode值），且m必须小于n。
  所谓”加密”，就是算出下式的c：
  　　me ≡ c (mod n)
  爱丽丝的公钥是 (3233, 17)，鲍勃的m假设是65，那么可以算出下面的等式：
  　　6517 ≡ 2790 (mod 3233)
  于是，c等于2790，鲍勃就把2790发给了爱丽丝。
  （2）解密要用私钥(n,d)
  爱丽丝拿到鲍勃发来的2790以后，就用自己的私钥(3233, 2753) 进行解密。可以证明，下面的等式一定成立：
  　　cd ≡ m (mod n)
  也就是说，c的d次方除以n的余数为m。现在，c等于2790，私钥是(3233, 2753)，那么，爱丽丝算出
  　　27902753 ≡ 65 (mod 3233)
  因此，爱丽丝知道了鲍勃加密前的原文就是65。
  至此，”加密–解密”的整个过程全部完成。
  我们可以看到，如果不知道d，就没有办法从c求出m。而前面已经说过，要知道d就必须分解n，这是极难做到的，所以RSA算法保证了通信安全。
  你可能会问，公钥(n,e) 只能加密小于n的整数m，那么如果要加密大于n的整数，该怎么办？有两种解决方法：一种是把长信息分割成若干段短消息，每段分别加密；另一种是先选择一种”对称性加密算法”（比如DES），用这种算法的密钥加密信息，再用RSA公钥加密DES密钥。

• EEC加密原理简述
  椭圆曲线密码体制来源于对椭圆曲线的研究，所谓椭圆曲线指的是由韦尔斯特拉斯（Weierstrass）方程：
  y2+a1xy+a3y=x3+a2x2+a4x+a6 (1)
  所确定的平面曲线。其中系数ai(I=1,2,…,6)定义在某个域上，可以是有理数域、实数域、复数域，还可以是有限域GF（pr），椭圆曲线密码体制中用到的椭圆曲线都是定义在有限域上的。
  椭圆曲线上所有的点外加一个叫做无穷远点的特殊点构成的集合连同一个定义的加法运算构成一个Abel群。在等式
  mP=P+P+…+P=Q (2)
  中，已知m和点P求点Q比较容易，反之已知点Q和点P求m却是相当困难的，这个问题称为椭圆曲线上点群的离散对数问题。椭圆曲线密码体制正是利用这个困难问题设计而来。椭圆曲线应用到密码学上最早是由Neal Koblitz 和Victor Miller在1985年分别独立提出的。
  椭圆曲线密码体制是目前已知的公钥体制中，对每比特所提供加密强度最高的一种体制。解椭圆曲线上的离散对数问题的最好算法是Pollard rho方法，其时间复杂度为，是完全指数阶的。其中n为等式(2)中m的二进制表示的位数。当n=234, 约为2117，需要1.6x1023 MIPS 年的时间。而我们熟知的RSA所利用的是大整数分解的困难问题，目前对于一般情况下的因数分解的最好算法的时间复杂度是子指数阶的，当n=2048时，需要2x1020MIPS年的时间。也就是说当RSA的密钥使用2048位时，ECC的密钥使用234位所获得的安全强度还高出许多。它们之间的密钥长度却相差达9倍，当ECC的密钥更大时它们之间差距将更大。更ECC密钥短的优点是非常明显的，随加密强度的提高，密钥长度变化不大。