双钥加密算法

　　双钥密码体制的加密密钥和解密密钥不相同，它们的值不等，属性也不同，一个是可公开的公钥，另一个则是需要保密的私钥。双钥密码体制的特点是加密能力和解密能力是分开的，即加密与解密的密钥不同，或从一个难以推出另一个。它可以实现多个用户用公钥加密的消息只能由一个用户用私钥解读，或反过来，由一个用户用私钥加密的消息可被多个用户用公钥解读。其中前一种方式可用于在公共网络中实现保密通信；后一种方式可用于在认证系统中对消息进行数字签名。
　　双钥加密算法的主要特点如下：
　　1）用加密密钥PK对明文m加密后得到密文，再用解密密钥SK对密文解密，即可恢复出明文m，即
　　　　　　　　　　　　　　　DSK(EPK(m))＝m
　　2）加密密钥不能用来解密，即：
　　　　　　　　　　　　　　　DPK(EPK(m))≠m ；DSK(ESK(m))≠m
　　3）用SK加密的信息只能用PK解密；用PK加密的信息只能用SK解密。
　　4）从已知的PK不可能推导出SK。
　　5）加密和解密的运算可对调，即
　　　　　　　　　　　　　　　EPK(DSK(m))＝m
　　双钥密码体制大大简化了复杂的密钥分配管理问题，但公钥算法要比私钥算法慢得多(约1000倍)。因此，在实际通信中，双钥密码体制主要用于认证（比如数字签名、身份识别等）和密钥管理等，而消息加密仍利用私钥密码体制。下面介绍双钥密码体制的杰出代表――RSA加密算法。
　　1．RSA算法
　　RSA体制是由R.L.Rivest、A.Shamir和L.Adleman设计的用数论构造双钥的方法，它既可用于加密，也可用于数字签名。RSA得到了世界上的最广泛应用，ISO在1992年颁布的国际标准X.509中，将RSA算法正式纳入国际标准。1999年，美国参议院已经通过了立法，规定电子数字签名与手写签名的文件、邮件在美国具有同等的法律效力。在Internet中广泛使用的电子邮件和文件加密软件PGP(Pretty Good Privacy)也将RSA作为传送会话密钥和数字签名的标准算法。RSA算法的安全性建立在数论中“大数分解和素数检测”的理论基础上。
　　（1）大数分解
　　双钥密码体制算法按由公钥推算出密钥的途径可分为两类：一类是基于素数因子分解问题的(如RSA算法)，它的安全性基于100位十进制数以上的所谓“大数”的素数因子分解的难题，这是一个至今没有有效快速算法的数学难题。另一类是基于离散对数问题的(如EIGamal算法)，其安全性基于计算离散对数的困难性。离散对数问题是指模指数运算的逆问题，即找出一个数的离散对数。一般地，计算离散对数是非常困难的。
　　RSA算法运用了数论中的Euler同余定理：即a、r是两个互质的自然数，则a^z=1 (mod r),其中z为与r互质的且不大于r的自然数，称z为r的Euler指标函数。
　　（2）RSA算法表述
　　假定用户A欲送消息m给用户B，则RSA算法的加／解密过程为：
　　1）首先用户B产生两个大素数p和q(p、q是保密的)。
　　2）用户B计算n=pq和φ(n)=(p-1)(q-1)(φ(n)是保密的)。
　　3）用户B选择一个随机数e(0　　4）用户B通过计算得出d，使得d*e mod φ(n)=1(即在与n互素的数中选取与φ(n)互素的数，可以通过Euclidean算法得出。d是用户B自留且保密的，用作解密密钥)。
　　5）用户B将n及e作为公钥公开。
　　6）用户A通过公开渠道查到n和e。
　　7）对m施行加密变换，即EB(m)=m^e mod n=c。
　　8）用户B收到密文c后，施行解密变换
　　　　　　　DB(c)=c^d mod n=(m^e mod n)^d mod n=m^ed mod n=m mod n
　　下面举一个简单的例子用于说明这个过程：令26个英文字母对应于0到25的整数，即a-00，b-01，…，y-24，z-25。设，m=inclub，则m的十进制数编码为：m=08 13 02 11 20 01。设n=3×11=33,p=3,q=11, φ(n)=2×10=20。取e=3，则d=7将n=33和e=3公开，保留d=7。
　　用户A查到n和e后，将消息m加密：
　　EB(i)=08³ mod 33= 17,
　　EB(n)=13³ mod 33= 19,
　　EB(c)=02³ mod 33= 8,
　　EB(l)=11³ mod 33= 11,
　　EB(u)=20³ mod 33= 14,
　　EB(b)=01³ mod 33= 1,
则 c= EB(m) = 17 19 08 11 14 01,它对应的密文为
　　c=rtilob
　　当用户B接到密文c后施行解密变换：
　　DB(r) = 17⁷ mod 33= 8，即明文i，
　　DB(t) = 19⁷ mod 33= 13，即明文n，
　　DB(i) = 08⁷ mod 33= 2，即明文c，
　　DB(l) = 11⁷ mod 33= 11，即明文l
　　DB(o) = 14⁷ mod 33= 20，即明文u,
　　DB(b) = 01⁷ mod 33= 1，即明文b。
　　（3）RSA安全性分析
　　RSA的保密性基于一个数学假设：对一个很大的合数进行质因数分解是不可能的！若RSA用到的两个质数足够大，可以保证使用目前的计算机无法分解。即RSA公开密钥密码体制的安全性取决于从公开密钥（n，e）计算出秘密密钥（n，d）的困难程度。想要从公开密钥（n，e）算出d，只能分解整数n的因子，即从n找出它的两个质因数p和q，但大数分解是一个十分困难的问题。RSA的安全性取决于模n分解的困难性，但数学上至今还未证明分解模就是攻击RSA的最佳方法。尽管如此，人们还是从消息破译、密钥空间选择等角度提出了针对RSA的其他攻击方法，如迭代攻击法、选择明文攻击法、公用模攻击、低加密指数攻击、定时攻击法等，但其攻击成功的概率微乎其微。
　　出于安全考虑，在RSA中，建议使用1024bit的n，对于重要场合n应该使用2048位。
　　2．ElGamal算法
　　RSA算法是基于素数因子分解的双钥密码，而ElGamal算法则是基于离散对数问题的另一种类型的双钥密钥，它既可用于加密，也可用于签名。
　　（1）ElGamal算法方案
　　1985年，ELGamal第一次在有限域上基于离散对数问题设计了原始的ElGamal数字签名方案。
　　令p是使在GF（p）域计算离散对数在多项式时间内是不可行的大素数。引进集合Zp ={0,1,2,…，p}及其子集Zp*={0,1,2,…，p-1}。令g∈Zp*，是本原元，定义：密钥集K={（p,g,x,y）:y=g^x  mod p}，这里p,g,y是公钥，x是用户选择的私钥，x∈Zp*且gcd(x,p-1)=1。即产生密钥对时，首先选择一个素数p，两个Zp*中的随机数g和x, 计算 y = g^x mod p ，则其公钥为 y, g 和p。私钥是x。g和p可由一组用户共享。
　　（2）ElGamal加、解密及其安全性
　　选择随机数k∈zp-1，且(k，p-1)=1，计算：y1=g^kmod p(随机数k被加密)，y2=my^k mod p，这里，m是发送明文组。密文则由y1和y2级连构成，即密文C=y1‖y2。这种加密方式的特点是，密文由明文和所选随机数k来决定，因而是非确定性加密，一般称之为随机化加密，对同一明文由于不同时刻的随机数k不同而给出不同的密文，这样做的代价是使数据扩展1倍。
　　在收到密文组C后，ElGamal的解密是通过下列计算得到明文的：
　　　　　　　　　　　　　　

　　ElGamal算法的安全性是基于zP^*中有限群上的离散对数的困难性的。研究表明，mod p生成的离散对数密码可能存在陷门，这会造成有些“弱”素数p下的离散对数较容易求解，但密码学家也发现可以较容易地找到这类陷门以避免选用可能产生脆弱性的这些素数。
　　3．双钥算法小结
　　双钥密钥体制的密钥管理和分配较简单，尤其可方便地用于数字签名和认证。虽然其算法都较复杂，运算量巨大，但其仍不失为一种非常有前途的加密体制，它的出现是密码学发展史上的划时代事件。上面我们分析了双钥密码体制的典型代表RSA算法和ElGamal算法，还有其他一些有意义的算法，如LUC密码、Rabin密码，以及DSA密码等。
　　对于RSA体制，可以将其推广为有多个密钥的双钥体制，即在多个密钥中选用一部分密钥作为加密密钥，而另一些作为解密密钥。同样地，RSA还可以推广为多签名体制，如有k1、k2和k3三个密钥，可将k1作为A的签名私密钥，k2作为B的签名私密钥，k3作为公开的验证签名用密钥，实现这种多签名体制，需要一个可信赖中心对A和B分配秘密签名密钥。