摘 要：计算机网络的发展突飞猛进，与此同时产生了公钥密码体制，本文重点介绍了当前公钥密码体制的几种常见的算法以及公钥密码体制的未来发展趋势。
关键词 公钥密码体制 RSA DSA ECDSA SHA-1 数字签名 身份认证
1 引言
公开密钥密码体制的概念是1976年由美国密码学专家狄匪(Diffie)和赫尔曼(Hellman)[1]提出的，有两个重要的原则：第一，要求在加密算法和公钥都公开的前提下，其加密的密文必须是安全的；第二，要求所有加密的人和掌握私人秘密密钥的解密人，他们的计算或处理都应比较简单，但对其他不掌握秘密密钥的人，破译应是极困难的。随着计算机网络的发展，信息保密性要求的日益提高，公钥密码算法体现出了对称密钥加密算法不可替代的优越性。近年来，公钥密码加密体制和PKI、数字签名、电子商务等技术相结合，保证网上数据传输的机密性、完整性、有效性、不可否认性，在网络安全及信息安全方面发挥了巨大的作用。本文详细介绍了公钥密码体制常用的算法及其所支持的服务。
2 公钥密码算法
公钥密码算法中的密钥依性质划分，可分为公钥和私钥两种。用户或系统产生一对密钥，将其中的一个公开，称为公钥；另一个自己保留，称为私钥。任何获悉用户公钥的人都可用用户的公钥对信息进行加密与用户实现安全信息交互。由于公钥与私钥之间存在的依存关系，只有用户本身才能解密该信息，任何未受授权用户甚至信息的发送者都无法将此信息解密。在近代公钥密码系统的研究中, 其安全性都是基于难解的可计算问题的。 如:
(1)大数分解问题；(2)计算有限域的离散对数问题；(3)平方剩余问题；(4)椭圆曲线的对数问题等。
基于这些问题, 于是就有了各种公钥密码体制。关于公钥密码有众多的研究, 主要集中在以下的几个方面:
(1)RSA 公钥体制的研究；(2)椭圆曲线密码体制的研究；(3)各种公钥密码体制的研究；(4)数字签名研究。
公钥加密体制具有以下优点:
(1)密钥分配简单；(2)密钥的保存量少；(3)可以满足互不相识的人之间进行私人谈话时的保密性要求；(4)可以完成数字签名和数字鉴别。
2.1 RSA算法
RSA算法[2]是Ron Rivest, Adi Shamir和Len Adleman 在1978年提出的，是一种公认十分安全的公钥密码算法。RSA算法是目前网络上进行保密通信和数字签名的最有效安全算法。RSA算法的安全性基于数论中大素数分解的困难性。所以，RSA需采用足够大的整数。因子分解越困难，密码就越难以破译，加密强度就越高。其公开密钥和私人密钥是一对大素数的函数。从一个公开密钥和密文中恢复出明文的难度等价于分解两个大素数之积。因式分解理论的研究现状表明：所使用的RSA密钥至少需要1024比特，才能保证有足够的中长期安全。
为了产生两个密钥，选取两个大素数p和q。为了获得最大程度的安全性，两数的长度一样。计算乘积：N=pq，然后随机选取加密密钥e，使e和（p-1）（q-1）互素。最后用欧几里得扩展算法计算解密密钥d，以满足：ed=1mod（p-1）（q-1）则 d=e-1mod（p-1）（q-1）注意：d和n也互素。e和n是公开密钥，d是私人密钥。两个素数p和q不再需要，可以舍弃，但绝不能泄漏。
加密消息m时，首先将它分成比n份小的数据分组。加密后的密文c，将由相同长度的分组ci组成。加密公式可表示为：ci=mie ×(mod n) 解密消息时，取每一个加密后的分组ci并计算：mi= cdi ×(mod n)。
由于：cdi= (mei ) d= medi = mi k (p - 1) (q- 1) + 1= m i×m i k (p - 1) (q- 1)= m i×1= m i (mod n)这个公式能恢复出全部明文。公开密钥 n：两个素数p和q的乘积（p和q必须保密）；e：与（p-1）（q-1）互素。私人密钥 d：与n互素。加密 c=me×(mod n)；解密 m=cd×(mod n)。
2.2 ECDSA算法
椭圆曲线数字签名算法(ECDSA) [5]设计的数学原理是基于椭圆曲线离散对数问题的难解性。EC点上离散对数的研究现状表明:所使用的ECDSA密钥至少需要192比特,才能保证有足够的中长期安全。椭圆曲线是指由韦尔斯特拉斯(Weierstrass)方程：
y2+a1xy+a3y=x3+a2x2+a4x+a6
所确定的平面曲线。定义F为一个域，其中ai∈F，i＝1,2，…6。F可为有理解域、实数域、复数域，也可为有限域GF(q)。在椭圆曲线密码体制中，F一般为有限域。由有限域椭圆曲线上的所有点外加无穷远点组成的集合，连同按照“弦切法”所定义的加法运算构成一个有限Abel群。在此有限Abel群上，定义标量乘法(Scalar Multiplication)为：mP＝P+P+…P(m个P相加)；若mP＝Q，定义： m＝logpQ为椭圆曲线点群上的离散对数问题，此问题无多项式时间内的求解算法。ECDSA的设计正是基于这一问题的难解性。
在此，我们讨论定义在有限域GF(2m)上的椭圆曲线数字签名算法。今定义椭圆曲线方程为：y2+xy＝x3+ax2+b a,b∈GF(2m)；则椭圆曲线的域参数为 D(m,f(x),a,b,P,n)
其中,f(x)为GF(2m)的多项式基表示的不可约多项式。P表示椭圆曲线上的一个基点，n为素数且为点G的阶。
ECDSA算法密钥对的生成过程为：在区间[1，n-1]上选择一个随机数d，计算Q＝dP，则Q为公钥，d为私钥。
ECDSA算法的签名生成过程可简述如下：若签名的消息为e，则在区间[1，n-1]上选择一个随机数k，计算 kG＝(xl，y1)； r＝xl mod n；s＝k-1(e+dr) mod n。如果r或s为零，则重新计算，否则生成的签名信息为(r，s)。
ECDSA算法的签名验证过程可简述如下：若公钥为Q，签名的消息为e计算： w＝s-1 mod n ；u1＝ew mod n ；u2＝rw mod n ；X＝u1P + u2Q＝(xl，y1)。如果X为无穷远点，则拒绝签名，否则计算：v＝xl mod n；如果v＝r，则接受签名，否则拒绝签名。
2.3 SHA-1算法
SHA-1杂凑算法[4]起初是针对DSA算法而设计的，其设计原理与Ron Rivest提出的MD2，MD4，尤其是MD5杂凑函数的设计原理类似。当输入长度<264bit的消息时，输出160bit的摘要，其算法分为5步：
(1)填充消息使其长度为512的倍数减去64，填充的方法是添一个“1”在消息后，然后添加“0”直至达到要求的长度，要求至少1位，至多512位填充位；
(2)完成第1步后，在新得到的消息后附加上64bit填充前的消息长度值；
(3)初始化缓存，SHA-1用5字的缓存，每个字均是32bit；
(4)进入消息处理主循环，一次循环处理512bit，主循环有4轮，每轮20次操作；
(5)循环结束后，得到的输出值即为所求。
3 公钥密码的服务
3.1 数据加密
一般说来，公钥密码中的计算是很慢的，以至于在很多情况下是不可行的。可以用一个两步过程来代替。
(1)用随机生成的对称密钥来加密数据。
(2)用授权接收者的公钥来加密这个对称密钥。
当授权接收者收到加过密的数据后，也采取一个类似的两步过程：
(1)授权接收者用自己的私钥来解出对称密钥。
(2)接着用对称密钥进行解密获得原始数据。
3.2 数字签名
数字签名在公钥密码体制下是很容易获得的一种服务，但在对称密码体制下很难获得。数字签名从根本上说是依靠密钥对的概念。发送方必须拥有一个只有自己知道的私钥，这样当他签名一些数据时，这些数据唯一而又明确地和他联系在一起，同时，应该有一个或更多实体都知道的公钥，以便大家验证，并确认签名是发送方的。因此，可以把数字签名操作看作是在数据上的私钥操作。整个签名操作就是一个两步过程：
(1)签名者通过杂凑函数把数据变成固定大小。
(2)签名者把杂凑后的结果用于私钥操作。
验证操作也是一个类似的两步过程：
(1)验证者通过杂凑函数把数据变成固定大小。
(2)验证者检查杂凑后的结果，传输来的签名，如果传输来的签名用公钥解密后的结果和验证者计算的杂凑结果相匹配，签名就被验证，否则，验证失败。
从而，数字签名不仅提供了数据起源认证服务，还有数据完整性及不可否认性的服务。
3.3 密钥的建立
公钥密码体制也可以用来实现两个实体间的密钥建立的功能（即密钥交换），也就是说，一个协议用到公钥和私钥，协议的结果是两个实体共享一个对称密钥，而这个密钥不为其他的实体所知。密钥的建立可以通过以下两种途径：
(1)密钥传递：一个实体产生一个对称密钥送给其他的实体，公钥密码体制可以用来保证传送的机密性。如发送方用接收方的公钥来加密对称密钥，使得只有接收方才能得到。
(2)密钥协定：两个实体共同来完成对称密钥的产生，公钥密码体制把这个过程变得相对简单。如Diffie-Hellman [6]体制是第一个利用公钥密码的特点来选取双方共同约定的对称密码体制中密钥的方案。
其具体方法如下: 假设Alice和Bob 两个用户打算选取一个高阶有限域Zp 中某一个数作为会话密钥。设P是一个质数, g是P 的一个本原元: 0< a< P, 当k= 1,2,…,P-1 时gKmod P 的值, 可以使1,2,…,P-1 中的每一状态都出现一次。选定g 和P,由网络中的所有用户和主机共享。Alice和Bob可以通过如下的交换过程建立相同的密钥:
(1) Alice 随机选取整数a (1<a<P-1) 予以保密, 并计算Qa=gamod P∈Zp；
(2) Bob 随机选取整数b (1<b<p-1) 予以保密, 并计算Qb=gbmod P∈Zp；
(3) Alice 将Qa传送给Bob, 而Bob 将Qb传送Alice；
(4) Alice 收到Qb后, 计算K=Qbamod P∈Zp；Bob 收到Qa后, 计算K=Qabmod P∈Zp；
则K∈Zp 就可作为Alice 和Bob所使用对称密码体制中的密钥。
3.4 身份标识和认证
在对称密码环境下，通信双方的身份认证是十分困难的，这就成了推动公钥密码体制发展的巨大动力之一。通信或交易时，应该保证信息的接收方和发送方能够被唯一地标识出来，让通信双方都能够知道信息从哪里来或者到哪里去。我们也将这种安全保障简称为真实性。按照被验证对象可以将真实性问题分成三种，一种是设备真实性，其二是人的真实性，其三是信息的真实性。通过主机地址，主机名称，拥有者的口令等都在一定的程度上保证了对设备的验证，但都不能很好地满足安全的要求。非对称算法或数字签名是人员、设备或信息验证的一种好方法。原理上说，没有人能够假冒数字签名。基于公钥体制的身份认证主要利用数字签名和hash 函数实现。设A 对信息M 的hash 值H(M) 的签名为SigSA(H(M)) ,其中SA 为A 的私钥. A 将M 及SigSA (H(M)) 发送给用户B。B 通过A 的公钥PA进行解密：
PA（SigSA(H(M))= M。确认信息是由A 所发出的并且计算hash 值还可对信息M 的完整性进行鉴别。在信息需要保密的情况下，A 和B 应通过密钥分配中心(KDC) 获得一个会话密钥KAB , A 将信息签名和加密后再传送给B，由于只有A 和B拥有KAB ，因此B 同样可以确信信息来源的可靠性和完整性。
对于那些需要使用密钥对中的公钥来获得基本安全服务的实体来说，公钥总是能很方便地得到。然而，没有完整性保护措施就分发公钥会削弱这些安全服务。需要有一种数据完整性机制来保证公钥及其相关信息不被篡改，即一种把公钥和它的声称者绑定的机制。公私证书可以满足上述要求，使得证书使用者能得到以下保证：
(1)公钥（以及其他相关信息）的完整性得到保障。
(2)公钥（以及其他相关信息）以一种可信的方式和它的声称者绑定在一起。
公私证书机制很好的解决了通信双方相互确定身份的问题。
4 结束语
公钥密码体制是非常重要的一种技术，它实现了数字签名的概念，提供了对称密钥协定的切实可行的机制，使安全通信成为可能。密钥对的思想也实现了其他的服务和协议，包括：机密性、数据完整性、安全伪随机数发生器和零知识证明等。目前，公钥密码的重点研究方向,理论方面[7]:
(1)用于设计公钥密码的新的数学模型和陷门单向函数的研究；
(2)公钥密码的安全性评估问题，特别是椭圆曲线公钥密码的安全性评估问题。
应用方面:
(1)针对实际应用环境的快速实现的公钥密码设计；
(2)公钥密码在当今热点技术如网络安全、电子商务、PKI、信息及身份认证等中的应用，这方面还将是持续研究热点。
参考文献
[1] Diffie, W.and M.Hellman. New directions in Cryptography. IEEE Transactions on Information Theory 22(1976):644-654.
[2] Rivest R , Shamir A , Adleman L. A method for obtaining digital signatures and public-key cryptosystems[J]. Communications of the ACM,1976 ,21(2) :120-126.
[3] 谭凯军,诸鸿文,顾尚杰. 基于数字签名方案DSS/DSA 的几种应用方案[J].计算机研究与发展.1999,36(5):632-638.
[4] 吴世忠，祝世雄等.应用密码学-协议、算法与C源程序[M].机械工业出版社,2000.
[5] M J B Robshaw, Yiqun Lisa Yin. Elliptic Curve Cryptosystems. An RSA laboratories Technical Note, Revised,1997: URL-http://www.ras.com/rsalabs.ecc/elliptic_curve.html.
[6] 庞南,戴英侠,李镇江.因特网密钥交换协议研究[J].计算机工程,2002,28(5):67-70.
[7] 冯登国.国内外密码学研究现状及发展趋势[J].通信学报,2002,23(5):18-27.
[8] 冯登国等译. 公开密钥基础设施—— 概念、标准和实施[M].北京：人民邮电出版社,2001.
作者简介：毕仁平（1962.5——）男，汉族，湖南石门人，长江大学教育技术与服务中心，