数字签名研究的现状与发展

数字签名研究的现状与发展

作者：刘兆丽 魏仕民 李孝诚

来源：《电脑知识与技术·学术交流》2008年第12期

摘要：随着网络技术的飞速发展及网上活动的日益频繁，信息安全成为一个非常突出的问题，而数字签名技术在保证数据的完整性、可控性和不可抵赖性等方面起着极为重要的作用。在对数字签名技术宏观分析的基础上，文中主要讨论了RSA、ElGamal、DSA、ECDSA等典型签名方案，并分析了数字签名的发展前景。

关键词：数字签名；RSA；ElGamal；DSA；ECDSA

中图分类号：TN918文献标识码：A文章编号：1009-3044(2008)12-2pppp-0c

Survey and Trend of Digital Signature LIU Zhao-li1,WEI Shi-min2,LI Xiao-cheng1

(1.Institute of Mathematics Science,Huaibei Coal Teachers College,Huaibei 235000,China;

2.Institute of Computer Science & Technology,Huaibei Coal Teachers College,Huaibei 235000,China) Abstract:With the development of the network technology and the high frequency activity in the network,the secure of information have become a very important problem. Digital signature has very important function in protecting the integrity,controllability and non-repudiation of information.Based on the macro-analysis of digital signature,analyzes several digital signature,i.e. RSA、ElGamal、DSA、ECDSA etc,and the trend of digital signature are analyzed in the paper. Key words:Digital signature;RSA;ElGamal;DSA;ECDSA

20世纪70年代，公钥密码体制的诞生标志了现代密码学的形成。不久，基于PKI的数字签名技术也随之产生。自数字签名概念提出后，数字签名的基础理论和应用研究引起了世界各国的广泛重视[1]。理论研究方面，基于各种PKI体制的数字签名方案和适应某些特殊要求的数字签名方案应运而生，各种数字签名的安全性分析和攻击分析研究也日益火热；应用研究方面，数字签名标准和数字签名法案越来越完善，数字签名的应用领域越来越广。1991年8月美国NIST（National Institute of Standard and Technology）公布了数字签名标准（DSS）。2000年6月，美国通过数字签名法案。进入21世纪，数字签名技术已经广泛运用于商业、金融、军事、政府、电子购物等领域。2004年8月，我国正式颁布了《中华人民共和国电子签名

龙源期刊网 http://www.qikan.com.cn

法》，从而确立了电子签名的法律效力和地位。这部法律有力地保障和支持了我国数字签名理论和应用研究的顺利进行。

文章分为3部分：第1部分简要介绍了数字签名理论的数学基础；第2部分分类讨论了基于大素数因子分解、离散对数分解和椭圆曲线难题的重要数字签名体制；第3部分给出了结论，并对数字签名体制的发展和努力方向做了展望。

1 数字签名的数学描述

1.1 数字签名的形式化定义

数字签名，是一种基于公钥密码体制的以电子形式存储的消息签名，一般包含三个主要过程：系统的初始化过程、签名产生过程和签名验证过程。系统的初始化过程产生数字签名用到一切参数；签名产生过程中，发送方利用给定的算法对消息产生签名；签名验证过程中，接收方利用公开的验证方法对接收到的信息的数字签名进行有效验证。

定义：一个数字签名方案包括签名算法和验证算法，一般由以下部分组成[2]： (1)一个明文消息空间M：某字母表中串的集合 (2)一个签名空间S：可能的签名集合

(3)一个签名密钥空间K：用于生成签名的可能密钥集合，和一个认证密钥空间K'：用于验证签名的可能密钥集合

(4)一个有效的密钥生成算法Gen：N→K×K'，其中K和K'分别为私钥和公钥空间 (5)一个有效的签名算法Sign：M×K→S，

(6)一个有效的验证算法Verify：M×S×K'→S(True,False) 对任意的sk∈K和任意的m∈M，我们用 s←Singnsk(m) 表示签名变换。

龙源期刊网 http://www.qikan.com.cn

对于任意的私钥sk∈K，用pk表示与sk相匹配的公钥。对于m∈M和s∈S，必有

其中，概率空间包括S，M，K和 。

一个有效的数字签名方案必须经过安全性证明，并具备以下功能：

(1)保证信息的完整性，数据不被篡改。根据单向函数的性质，一旦原始信息被改动，所生成的数字摘要就会发生很大的变化，即发生雪崩效应。因此，通过此种方式，能防止原始信息被篡改；

(2)具有不可否认性。既然只有发送者可以生成消息的一个数字签名，并可以被任何人所验证，所以就很容易处理关于是谁生成了该签名的纠纷，即不可否认性；

(3)具有抗伪性。伪造一个数字签名在计算上不可行，无论是通过以后的数字签名来构造新的消息，还是对给定的消息构造一个虚假的数字签名。 1.2 数字签名方案的数学基础

数字签名是基于各种公钥密码体制的，因此其安全性也依赖于单向陷门函数的安全性。绝大多数的数字签名方案都是基于以下三个数学难题： 1.2.1 大素数因子分解难题

已知两个大素数p和q，要求n=pq，非常简单，只需要1次乘法。但是，若知道n，求p和q则是几千年来数论学者的研究难题，当n很大时，则异常困难。这就是所谓的大素数因子分解问题。目前，对于大于110位的整数，数域筛选法是最快的算法，其分解时间为T(n)=O(exp(1.92+0(1))(ln n)1/3(lnlnn2/3))。 1.2.2 素数域上的离散对数难题

设 是一个素数，g∈F*p是其生成元，已知x∈F*p，求y=gxmodp，非常简单。但是，若已知y，通过y=gxmodp求x，则非常困难。这就是所谓的离散对数问题（DLP）。目前，其最快的求解时间复杂度为lzl02.tif 。 1.2.3 椭圆曲线难题

龙源期刊网 http://www.qikan.com.cn

设p是一个素数，?P,Q∈E(GF(p))，若存在某整数k，使得Q=kP，称k为点Q的椭圆曲线离散对数（ECDL）。由P,Q，求k的问题就称为E上的椭圆曲线离散对数问题（ECDLP）。目前为止，还没有出现较好的低于指数级时间的求解算法。

除了上述三个难题之外，还有多项式求根问题、背包问题、二次剩余问题等都可以作为数字签名方案的数学基础。

2 经典数字签名方案的探讨

`自从1979年，G.J.Simmons将数字签名应用于美苏两国的禁止核试验条约的验证工作中以来，数字签名技术引起了学术界尤其是密码学界和计算机界的广泛重视，特别是随着网络的飞速发展，出现了许多签名算法。根据其基于数学难题的不同，可以分为基于大素数因子分解难题的数字签名方案、基于离散对数难题的数字签名方案、基于椭圆曲线难题的数字签名方案和基于离散对数和大素数因子分解难题结合的数字签名方案等。

2.1 基于大素数因子分解难题的数字签名方案

基于大素数因子分解难题的数字签名体制的典型代表是RSA签名体制。此外，还有Rbani签名方案、Fiat一Shamir签名方案和Guillou一Quisquater签名方案等。

RSA算法是当前最著名、应用最广泛的公钥体制。它是美国麻省理工学院的Rivest, Shamir和Adleman在1978年提出的一种非对称加密算法。RSA算法也是第一个既能用于数字加密，又能用于数字签名的算法。RSA数字签名体制是采用RSA算法来实现数字签名的。当用于数字签名时，签名者使用自己的私钥来完成签名，验证者使用签名者的公钥来完成认证。RSA算法已经经过各界多年的深入分析，到目前为止仍然认为是安全的，且是最为广泛采用的一种密码体制。

RSA数字签名体制的缺点主要有：(1)产生密钥很麻烦，受到素数产生技术的限制，因而难以做到一次一密。(2)分组长度太大，为保证安全性，至少也要600 bits以上，目前通常都采用1024bits，使运算代价很高，尤其是速度较慢，较对称密码算法慢几个数量级，且随着大数分解技术的发展，这个长度还在增加，不利于数据格式的标准化。 2.2 基于离散对数难题的数字签名方案

龙源期刊网 http://www.qikan.com.cn

由于离散对数计算的复杂性，且其指数运算的化简和处理比其他运算相对简单，很容易构造不同的方案，因此基于离散对数难题的数字签名方案应用特别广泛、资源也相当丰富。现在的大部分方案如ElGamal数字签名方案、广义ElGamal数字签名方案、Schnorr数字签名方案、DSA方案、Neberg一Rueppel签名方案、Okamoto签名方案、Miyaji签名方案等都是基于这个难题进行设计的。 2.2.1 ElGamal数字签名方案

ElGamal数字签名方案是ElGamal于1985年基于离散对数难题提出的。ElGamal数字签名方案包含系统初始化、签名过程和验证过程。 (1)系统初始化过程

设p是一个素数，g∈Zp*是一个生成元，?x(1 (2)签名过程

对于待签消息m，签名方A任意选取一个随机数k( (3)验证过程

接收方B收到消息m和签名(r,s)后，验证gm=yrrs mod p是否成立？如成立，则接收签名。否则，拒绝签名。

易见，lzl03.tif。正确性得证。

ElGamal数字签名方案提出后，关于ElGamal数字签名方案的改进和推广不断出现。1994年，Harn等人对ElGamal数字签名方案及其类似方案进行总结，列出了18个安全可行的方案[3]，得到了广义ElGamal数字签名方案。Horster又对之做了继续推广。我国李继红[4]等学者亦对之做了深入研究，取得了一定成果。ElGamal数字签名方案容易受到同态攻击和代换攻击，因此在实际应用中，要对明文消息进行Hash函数处理。 2.2.2 DSA数字签名方案

DSA数字签名方案是1991年8月美国NIST公布的数字签名标准（DSS）中采用的数字签名算法。DSA只能签名，不能用作加密。DSA签名算法是ElGamal签名算法和Schnorr签名算法的变种，具有较大的兼容性和适用性，成为网络安全体系的基本构件之一。

龙源期刊网 http://www.qikan.com.cn

DSA的签名和验证过程中，需要用到比较计算模幂或求逆元的计算，需要耗费大量的时间，为了加快运算速度，一般采用预处理的方法。Yen和Laih从尽可能避免求逆运算的角度对DSA签名方案进行了改进。

2.3 基于椭圆曲线难题的数字签名方案

椭圆曲线研究开始于19世纪，至今已有150多年的历史了。1985年Miller和Kobilitz分别提出将椭圆曲线理论用于公钥密码学，从而形成了椭圆曲线密码体制（Elliptic Curve Cryptogram，ECC）。基于椭圆曲线的数字签名体制通过ECC公开密钥加密技术和报文分解函数实现。签名方把被签名文件通过Hash函数处理后进入签名函数，在签名函数中使用签名方的私钥对文件签名，并将产生的签名与文件原文一同发送给接收方。接收方收到签名后，文件原文使用相同的散列函数进行处理，在验证函数中接收方使用签名方的公钥对文件的签名进行验证，从而确认文件是否为伪造的，是否在传输过程中被篡改[5]。基于椭圆曲线的数字签名具有密钥短、运算快和安全性高等优点，因此在密码学中占有十分重要的地位，应用领域不断扩大，而且基于大素数因子分解、离散对数等数学难题的签名方案理论上几乎都可以椭圆曲线密码体制中来。基于椭圆曲线问题的数字签名大有取代已有签名体制之趋势。

ECDSA是Scott vanstone于1992年提出的，在椭圆曲线上实现了的DSA算法。该签名方案包括系统初始化、签名过程和验证过程。 2.3.1 系统初始化

ECDSA全局参数为(q,FR,a,b,G,n,h))，其中q为有限域的大小，FR为GF(q)中的一个元素；a,b∈GF(q)且椭圆曲线为y2=x3+ax+b或y2+xy=x3+ax2+b；G=(xG,yG)为基点，G的阶为素数n,n>2160 ,n>2?q；h=#E(GF(q))/n。随机选取d∈[1,n-1]为私钥，则Q=dG为相应公钥。 2.3.2 签名过程

(1)对于待签明文消息m，用HASH－1函数计算e=H(m)，并转化为一个160位的整数； (2)任意选取一个随机整数k∈[1,n-1]，计算kG=(x1,y1)； (3)计算r=x1 mod n，如果r为0，则返回（2）重新选择k； (4)计算s=k-1(e+dr) mod m，如果s为0，则返回（2）； (5)得到消息m的签名为(r,s)。 2.3.3 验证过程

龙源期刊网 http://www.qikan.com.cn

(1)判断(r,s)是否属于[1,n-1]，否则签名无效； (2)计算e=H(m)； (3)计算w=s-1 mod n；

(4)计算u1=ew mod n,u2=rw mod n；

(5)计算X=u1G+u2Q如果X＝0，表示签名无效；否则x=(x1,y1)，计算v=x1 mod n； (6)如果v=r则签名有效；否则无效。

由于X=u1G+u2Q=(u1+u2d)G=kG,r=x(kG)modn，所以v=x1 mod n=x(X)mod n =r，ECDSA的正确性得证。

ECDSA具有安全性高、密钥长度短、存储空间小、带宽要求低、算法灵活和算法速度快等优点[6]。经过不断发展，不同的国际组织基于ECDSA，制定了有关标准，以推进密码技术的广泛使用和不同操作环境的互操作性。1998年，国际标准化组织ISO制定15014888一3标准；1999年，美国国家标准化组织ANSI出台ANSI X9.62标准；2000年，电气和电子工程师协会IEEE制定了IEEE1363-2000参考标准；2000年，美国国家标准技术研究所(NIST)制定了联邦信息处理标准[7]FIPS186-2，推荐美国政府使用的15个不同安全级别的椭圆曲线，分为三类：①素域Fp上的随机椭圆曲线5条（素域的阶p分别为：P192,P224,P256,P384,P521）；②二进制域F2m上的随机椭圆曲线5条（二进制域扩展次数m分别为:163，233，283，409，571）；③二进制域F2m上的Koblitz椭圆曲线5条(二进制域扩展次数m分别为:163，233，283，409，571)。(5)密码标准化组织(SECG)是企业间为解决密码标准的互操作性而成立的联盟。其SECI规定了ECDSA、ECIES、ECDH和ECMQV，并尝试与ANSI、NIST、IEEE及ISO/IEC椭圆曲线标准兼容。在SEC2中推荐了包括15个NIST椭圆曲线在内的一些特殊的椭圆曲线。这些标准的制定将为ECDSA进一步发展提供一个良好的平台。

2.4 其他签名方案

除了以上几种常用的签名体制外，研究者们还提出了一些特殊用途的数字签名方案[1]，如代理签名(Proxy Signature)、群签名(Group Signature)、盲签名(Blind Signature)、多重签名等等。这几类签名体制在电子商务、公共资源的管理、军事命令的签发、金融合同的签署等方面有着广泛的应用前景。

龙源期刊网 http://www.qikan.com.cn

3 结论

目前，基于PKI的数字签名体制己经广泛应用于商业、金融、军事等领域，尤其是在网络通信、电子邮件、电子商务、电子政务方面。数字签名还可以应用到访问控制、软件验证、病毒检测等不同领域。文中较为全面地介绍了目前国际上较为流行的几种数字签名方案，特别是基于椭圆曲线问题的数字签名方案。当然，由于篇幅所限，还有一些没有涉及到，比如MR(message recovery)签名方案[8]等。

由于数字签名技术广泛应用仍需解决的一些局限性，如不能充分实现数字签名具有的特殊鉴别作用，软件的普及性还不高，被剥夺了相应权限后原先的数字签名的认证问题等[9]，。特别是，我们国家还没有自己的ECC标准。因此改进数字签名在内的安全技术措施、确定CA认证权的归属和标准制定等问题依然十分关键。相信随着Internet的快速发展及其算法的不断改进和完善，数字签名的发展前景一定会越来越广阔。

参考文献：

[1]赵泽茂.数字签名理论[M].北京:科学出版社,2007.

[2][英]Webo Mao著.王继林,伍前红,等.译.现代密码学理论与实践[M].北京:电子工业出版社,2006.

[3]Harn L,Xu Y,Perersen H. Design of ElGamal type digital scheme based on discrete logarithm[J].Electronics letters,1994,31(24):2025-2026.

[4]李继红.ElGamal数字签名方案及其应用研究[D].西安:西安电子科技大学,1999. [5][加]Douglas R.Stinson,著.冯登国,译.密码学原理与实践[M].北京:电子工业出版社,2003. [6]D.Johanson,A.Menezes,S.Vanstone.The elliptic curve digital signature algorithm (ECDSA).Internatinal Journal on Information Security,2001,1:36-63.

[7]Koblitz N. Elliptic curve cryptosystems[J].Mathematics of Computation,1987,48(5):203-209. [8]Nyberg K,Rueppel RA.Messege recovery for signature schems based on the discrete logarithm[C].Advances in Cryptology-Eurocrypt'94,Berlin:Springer-Verlag,1994.175-190. [9]断云所,魏仕民,唐礼勇,等.信息安全概论.北京:高等教育出版社,2003.