数字签名的算法研究与JAVA实现.doc

1、摘 要数字签名作为密码学的一个分支，可实现身份认证、数据完整性、不可抵赖性等重要功能;数字证书可实现公钥的统一管理，是数字签名非常重要的应用领域;SSL作为运输层的重要安全协议，吸取了对称和非对称密钥体制的优点。以上三者在实际生活中被巧妙结合并广泛应用于电子商务、电子政务、电子邮件等各个领域。本文首先概述了数字签名的基本知识，指出该领域当前的研究方向和现状。接着阐述了基于非对称密钥体制的数字签名中的三大算法RSA、DSA、ECDSA的参数生成、签名和验证过程，以及算法正确性证明，详细说明了数字证书的概念、功能、由来、格式和组织形式，简要说明了SSL的功能。最后简介java类库对消息摘要、加解密

2、、数字签名、SSL的实现，并重点介绍笔者编写的SHA、RSA、Elgamal算法的java改进实现。【关键词】 数字证书; 非对称密钥体制; 数字签名；SSLIVStudies of Algorithms and Implementation in Java of Digital SignatureAbstract:Digital Signature, as a branch of Cryptography, can implement some significant functions such as identity authentication, integrity of data,

3、and nonrepudiation; Digital Certificate can fulfill the management of public keys, it is the most critical field of application for Digital Signature; SSL, as a significant secure protocol on transport layer, holds both the advantages of Symmetric/Asymmetric Key System. In real life, the three above

4、 have been combined subtly and applied widely in many fields such as electronic business, electronic government affair, and email.This paper briefly introduces the ABC of Digital Signature and the direction and state of this field. Next, the paper elaborates on the parameter generation, signature ge

5、neration and signature verification. The proof of three signature algorithmsRSA,DSA,ECDSA is also given in addition. The paper introduces the concept, the function, the origin, the format, and the framework of digital certificate, and the function of SSL. At last, on the basis of brief introduction

6、on the implementation of message digest, encryption & decryption, digital signature, SSL in Java built-in library, the paper focuses on the improved implementation of SHA, RSA, Elgamal algorithms written by the author in Java.Keywords:Digital Certificate; Asymmetric Key System; Digital Signature; SS

7、L目录1 引言11.1 研究背景11.2 国内外研究现状21.3 本文研究思路与分析42 基于非对称密钥体制的数字签名72.1 RSA公钥密码72.1.1 参数生成72.1.2 加密过程82.1.3 解密过程82.1.4 签名过程82.1.5 验证过程82.1.6 RSA算法正确性证明82.2 DSA签名算法102.2.1 参数构成112.2.2 签名过程112.2.3 验证过程112.2.4 DSA算法正确性证明122.3 ECDSA签名算法132.3.1 椭圆曲线142.3.2 椭圆曲线上的加法162.3.3 椭圆曲线上的离散对数问题172.3.4 参数构成172.3.5 签名过程172.

8、3.6 验证过程182.3.7 ECDSA算法正确性证明183 数字证书简述203.1 功能203.2 格式213.2.1 密钥和策略信息213.2.2 主体和发行人属性213.2.3 证书路径约束223.3 组织形式224 SSL简述245 数字签名的java实现255.1 数字签名算法的现有java程序实现255.1.1 消息摘要的java实现255.1.2 非对称加解密265.1.3 数字签名的java实现275.2 数字签名算法的java改进实现295.2.1 手动编写SHA算法295.2.2 RSA算法的java改进实现305.2.3 Elgamal签名算法的java实现396 SS

9、L的java实现436.1 借助tomcat的实现436.2 不借助tomcat的实现456.2.1 服务器端466.2.2 客户端467 应用前瞻498 总结50江西财经大学本科毕业论文1 引言数字签名是密码学的一个分支，其主要用途是抵御伪造、篡改、重放、抵赖等网络攻击，确保消息的完整性、不可否认性。除少数数字签名算法是基于对称密钥体制外，绝大多数的数字签名算法是基于公钥密码体制（非对称密钥体制）的。下面对这两种体制作简要说明。对称密钥体制的加密密钥与解密密钥相同，因此也称单密钥体制。该体制分为分组密码和流密码两类。前者一次操作多位明文，后者一次操作一位明文，其实二者并无本质上的严格界限。典

10、型的分组密码算法有：DES , CAST , RC5 , 3DES , SAFER , Blowfish , FEAL , IDEA, Skipjack, Rijndael等。典型的流密码算法有：A5,Rambutan,Gifford等1。公钥密钥体制与对称密钥体制相对，加密解密用不同的密钥，其中一个公开，称为公钥，另一个自己保存，称私钥。公钥密码体制的前提是：按公钥来算私钥，在计算上是不可行的。公钥密码体制一般基于以下三个数学上的难问题 10：(1) 背包问题：给定一个互不相同的数组成的集合，找出一个子集，其和为N。(2) 离散对数问题：如果p是质数，g和M是整数，找出x，使。它的另一种形式

11、：椭圆曲线上的离散对数问题。(3)因子分解问题：设N是两质数乘积，则： 分解N。 给定整数M和C，寻找d满足。 给定整数e和C，寻找M满足。 给定整数x，求解。1.1 研究背景数字签名已广泛应用到众多领域，但仍有较大的可开拓空间。目前数字签名研究的主要方向有：(1) 新数学模型和单向函数研究。如前文所述，目前公钥密码体制的数学基础仅局限于三个数学上的难问题中。随着攻击者攻击手段的改进，建立在如此狭隘的数学领域的数字签名的安全性不得不让人担忧。因此新的数学难题及单向陷门函数的寻找成为当前数字签名研究中的首要问题。(2) 针对实际应用环境的数字签名设计，尤其是智能卡上的数字签名设计。由于智能卡存储

12、空间的局限，很多早期被广泛应用的算法，如RSA、DSA等等，当其要求密钥长度达到512 bit、1024 bit时4，根本无法应用到智能卡中。目前智能卡上的数字签名一般采用椭圆曲线上的密钥体制，该体制已经发展得较为完善，相应地，针对它的攻击手段也不断翻新。当前这方面的研究方向主要集中在超椭圆曲线密钥体制上，它对空间的要求低于椭圆曲线密钥体制，也更适合智能卡这一特殊环境。但是，超椭圆曲线的数学难度远胜于椭圆曲线，同时，这个领域需要解决的问题还有很多，要真正把超椭圆曲线密钥体制投入到实际应用中，还有很长的一段路要走5。(3) 算法和程序优化、软硬件实现。优化和实现这一块的难度，说实话，是要远低于发

13、明创造的。实现DES算法的芯片数不胜数。java类库也已经把绝大多数常用的数字签名算法纳入其中，笔者在下文中作了陈述，这里不再赘述。这一方向的可提高之处主要在于效率上的进步，以及对已有算法的各种变体性地优化研究。(4) 安全性评估。目前对数字签名中重要算法的安全性衡量和比对已经做得比较完善，网上可以搜出无数张表，对RSA、DSA、ECDSA各长度密钥需要多少台计算机联解多少年，某算法各长度密钥安全性相当于另一算法多长的密钥。这一方向主要可提高之处在于对新攻击手段的研究。由于攻击者水平在不断提高，针对已有算法的攻击方式也在不断翻新，如何对某算法的安全隐患做出预测性的评估，是当前研究者需要考虑的问

14、题。1.2 国内外研究现状现代密码体制的研究成果，最重要的集中在新数学基础和新算法的不断提出，这里简要介绍几个主要算法的诞生：1976年，斯坦福大学的Diffie和Hellman提出公钥密码思想，并提出Diffie-Hellman密钥交换协议。该协议貌似简陋，实际上是离散对数问题在通信领域里程碑式的开创，目前仍广泛用于密钥交换中。1977年，IBM公司提出DES算法，并被美国国家标准局颁布。该算法是分组加解密算法中第一个成熟算法，应用十分广泛。1978年，MIT的三位科学家开发出RSA算法。RSA是这三位科学家姓氏的首字母。这二十多年来，RSA始终是非对称密钥体制中最著名，也被最广泛应用的算法

15、。在网络上、银行系统、军事情报等等许多领域都能见到它的身影。1985年，Koblitz和Miller提出ECDSA算法。该算法开曲线上实现密码算法之先河，为此后圆锥曲线密钥体制和超椭圆曲线密钥体制的建立奠定了坚实的基础。1985年，ElGamal提出ElGamal算法。该算法为基于离散对数的数字签名，已被纳入ANSI X9.30-199X标准。1989年，Schnorr提出Schnorr签名算法。该算法是ElGamal签名算法的变体，安全性低于ElGamal算法，但空间需求和时间需求低于Elgamal算法，可用于某些特定环境。1991年，NIST开发出DSA算法。该算法是ElGamal签名算法

16、和Schnorr签名算法的变体，从产生至今，它一直饱受争议，但客观地说，它确实是目前基于离散对数问题的数字签名算法中用得最广泛，评价也最高的。1993年，NIST和NSA共同设计了SHA算法， 并于1995年修订为SHA-1。SHA算法脱胎于MD4算法，并且从其产生至今，它的成就一直压倒MD系列算法，成为消息摘要算法的首选。同期，欧共体开发出了RIPE-MD算法及其改进型:RIPEMD-160算法。该算法同样取材于MD4算法，但它的运算远比SHA算法复杂，也远不如SHA算法应用得广泛。下文给出一个数字签名算法简表，囊括了绝大多数数字签名领域中里程碑式的算法，如表1-1所示：表1-1数字签名算法

17、简表算法名称对称/非对称数学基础能否用于加解密Lamport-Diffie对称能Rabin概率对称能RSA非对称因子分解能ElGamal非对称离散对数能Schnorr非对称离散对数能DSA非对称离散对数否ECDSA非对称椭圆曲线上的离散对数否Shamir非对称背包否Rabin非对称因子分解能GOST非对称离散对数否OSS非对称模n多项式能FA非对称FA可逆性能ESIGN非对称因子分解否Okamoto非对称离散对数否GQ非对称零知识证明否McEliece非对称Goppa码能Xinmei非对称大矩阵分解能1.3 本文研究思路与分析在或粗或细地看完多个数字签名算法之后，笔者断然放弃了从(1)着手的念

18、头。毫不夸张地说，笔者整理的数字签名算法简表中的算法，每个都是几十年的数学基础，几年甚至十几年辛勤耕耘的结晶。如果笔者有能力在几个月时间内，在这张表的最后一行附上一个自己创造的自成一体的算法的话，恐怕笔者的人生轨迹也会发生重大变化了。退而求其次，想到了从(2)着手。超椭圆曲线密钥体制业已建立，但还有不少算法未平移到超椭圆曲线密钥体制中，将已有算法作平移的工作量要远远小于自创一个全新的算法。但几个月的努力之后，发现(2)同样远远超出了笔者的能力范围。笔者很想做RSA算法在超椭圆曲线密钥体制上的实现：想先吃透椭圆曲线上RSA算法的资料，再参照几部超椭圆曲线密钥体制的文献，然后自己写出来。着手做的时

19、候，才发觉困难重重：目前绝大多数关于椭圆曲线密钥体制的文献是写ECDSA的，也就是基于域上的椭圆曲线;而椭圆曲线上RSA算法，即ECRSA，是基于环上的椭圆曲线的。这方面的资料可以用寥若晨星来形容。笔者能找到的所有超椭圆曲线密钥体制的文献都是基于域上的超椭圆曲线，而环上的超椭圆曲线根本找不出一个字的资料。笔者也试图自己建立环上的超椭圆曲线密钥体制，但困难重重，最后选择了放弃(2)。退而求其再次，从(3)和(4)着手。Java类库确实提供了绝大多数数字签名算法的实现，但用过以后就知道，它在效率上并不能令人满意。在 2.4GHz，512MB的机子上运行最简单的java类库进行RSA算法加解密的程序

20、大概需要700ms左右，如果拿到配置更差的机子上，也许无法排除超过1s的可能性，这样就与实际应用的要求相去甚远了。于是笔者想到自己手动实现RSA算法。目前网上java手动实现RSA算法的程序有很多，但存在不少问题，归纳了一下，在安全性和功能性上各有三条缺陷：(1) 安全性缺陷： 普遍使用long或int作为p,q,n,e,d的数据类型 普遍硬指定或手工输入参数，而不是通过随机生成 未考虑任何攻击抵御(2) 功能缺陷： 未考虑消息分组，极有可能加解密失败 采用效率最低的素性判断函数 只能对字符串进行操作针对这些缺陷，笔者写出了MyRSA类，时间性能上要优于java类库提供的RSA算法。java类

21、库中未提供Elgamal算法的实现，网上也找不到任何用java手动实现Elgamal算法的程序。于是，在发现9中存在的重大安全隐患，并对其提出自己的改进方法之后，笔者动手编写了MyElgamal类。应该来说，该类不如MyRSA类那样有价值，而且效率上存在重大瓶颈，但毕竟是对这一空白的一个小小的填补，留待今后大方之家斧正吧。在研究过程中，用了一定的时间在数字证书的概念以及SSL的java实现上。在阅读过2、3、8、11的相应章节之后，借用java类库实现了SSL。在做这个毕业设计时，重点是在算法的学习和证明上，这里主要是以10为提纲，并查阅了大量数学资料。因为计算机系本科生所学的数学知识是远远达

22、不到密码学领域的要求的，几乎每一种数字签名算法都要求数学系本科生乃至研究生的数学基础才能勉强看懂，正如每一种算法的发明都需要极深的数学功底一样。下文中对花时间最久，也是在数字签名领域最重要的三个算法作了较为详尽，较为浅显的介绍，并给出了相应证明过程。如果读者对数学完全没兴趣，可以跳过这一段。不过笔者是希望能跟着证明步骤一步步走一遍，否则无法深入体味算法的妙处和乐趣。本文第三部分RSA算法的介绍引用了张先红(2003)(RSA数字签名体制的介绍)数字签名原理及技术，(北京: 机械工业出版社)中的相关介绍内容;第六部分网络各层的安全技术引用了胡道元，闵京华(2002)(OSI七层中各层安全技术)网

23、络安全，(北京: 清华大学出版社)中的观点;第六部分SSL的介绍引用了张友纯(2006)(SSL的组成部分、步骤及功能)计算机网络安全，(武汉: 华中科技大学出版社)中的相关介绍内容。512 基于非对称密钥体制的数字签名早期人们不确定非对称密钥体制的安全性时，曾开发过对称密钥数字签名。由于对称密钥体制要求通信双方持有相同的密钥，所以通信时必然涉及密钥本身的传输，带来安全方面的隐患（如密钥被窃听、篡改等等）。其主要解决方法是：使用多个私钥，每次泄露其中的一半。典型的算法有Lamport-Diffie和Rabin概率签名。它们共同的缺点是：(1)签名太长；(2)每次使用时要更换密钥（由于前一次的密

24、钥已经泄露了一半，再使用将很危险）。尽管可以通过压缩函数解决(1)，但(2)的问题始终无法很好地解决，造成计算量十分庞大，于是有了基于非对称密钥体制的数字签名。在此着重阐述公钥密码体制中的三个数字签名算法：RSA、DSA和ECDSA。2.1 RSA公钥密码1978年，Ron Rivest, Adi Shamir和Leonard Adleman三人发明了世界上第一个既能用于加密也能用于数字签名的算法，并以他们自己姓氏的首字母组合将其命名为RSA算法6。这二十多年来，RSA始终是非对称密钥体制中最著名，也被最广泛应用的算法。在网络上、银行系统、军事情报等等许多领域都能见到它的身影。RSA算法是基于

25、因数分解问题的，包括以下几个过程：2.1.1 参数生成(1) 选两个大质数p、q；(2) 计算n=p*q；(3) 随机选e，满足，公钥为(e,n)；(4) 计算d，满足，私钥为(d,n)；(5) 销毁p、q、。注：gcd为求最大公约数运算,为小于n且与n互质的正整数个数。此处=(p-1)(q-1)79。加解密时，发送方用接收方的公钥来加密，接收方用自己的私钥来解密，这样确保密文在传输过程中不被破译，因为只有接收方才拥有接收方私钥。2.1.2 加密过程(1) 把消息m分组为mi，i=1,2, |mi|= |n|-1；(|a|表示a的二进制形式的长度)(2) 加密每个分组mi：；(3) 连接ci，

26、得密文c。2.1.3 解密过程(1) 将c分组为ci，i=1,2, |ci|= |n|-1；(2) 解密每个分组ci：；(3) 连接mi，得到明文m。签名时，发送方用自己的私钥来处理消息散列值（散列函数概念类似上文中的压缩函数，它能起到类似指纹的效果）。接收方用发送方公钥来验证。这样能保证签名不被伪造，因为只有发送方拥有发送方私钥，接收方用发送方公钥验证其他私钥的签名将肯定失败。RSA数字签名过程如下：2.1.4 签名过程(1) 计算消息散列值H(M)；(2) 用私钥处理散列值s=(H(M)d mod n；(3) 发送消息和签名(M,s)。2.1.5 验证过程(1) 验证签名s: h=se m

27、od n；(2) 计算消息散列值 H(M)；(3) 比较h和H(M)，相等则通过，否则验证失败。2.1.6 RSA算法正确性证明(1) 命题：(a mod n)(b mod n) mod n= (ab) mod n. (2.1.1)证明：设，则右边=(cn+d)(en+f) mod n=(cen2+cfn+den+df) mod n=(df) mod n=左边(2.1.1)式说明，取模之下，任意两数的积可以把取模符任意地内置或外提，这个等式将在后文中大量应用。(2) 命题：若ac=bc mod t ，且gcd(c,t)=1，则a=b mod t. (2.1.2)证明：若ac=bc mod t，

28、则ac-bc必为t的倍数，设ac-bc=dt，即(a-b)c=dt又gcd(c,t)=1，即等式左侧t的因子完全由a-b提供，即a-b是t的倍数，设a-b=et所以a=b mod t得证。(2.1.2)式说明，两取模下相等数，可以消去与模数互质的一个因子，仍然保持相等。(3) Euler定理：gcd(a,m)=1,则 mod m. (2.1.3)证明：设，令0r1,r2,r3rkm且均与m互质则ar1,ar2,ar3ark这k个数均不含m的因子，即均与m互质;且这k个数两两模m不同余。假设ij且ari=arj mod m ，则由(1.3)可知ri=rj mod m，也就是ri=rj，这与ij矛

29、盾。因此ari(1ik)这k个数两两模m不同余。令集合A=r1,r2rk,B=ar1 mod m, ar2 mod m,ark mod m明显，A与B中的元素一一对应，即A=B.则，r1r2rk=akr1r2rk mod m因r1r2rk与m互质，由(1.3)得ak=1 mod m，即=1 mod m所以Euler定理得证。(4) 命题： mod n （n=pq,且p、q为质数，0mn）. (2.1.4)证明：(i)若gcd(m,n)=1，则 mod n，两边乘m，即得证(ii)若gcd(m,n)1，则由n=pq可知，p|m或q|m。设m=kp(0kq).由gcd(m,q)=1可得 mod q

30、，两边作次方，得 mod q，即 mod q设=rq+1，得明显， mod n当m为q的倍数时，同理可证。故原等式得证。(5) 命题： mod n（n=pq,且p、q为质数，0mn）. (2.1.5)证明： mod n= ( mod n)k) mod n=mk mod n则n|(- mk)，设- mk=bn，即(i)若gcd(m,n)=1，则n|()。设=cn，则=1 mod n，得 mod n(ii)若gcd(m,n)1，则p|m或q|m。设m=cp(0cq),则q|()。设=dq，得=dqm+m=cdpq+m=cdn+m所以=m mod n。当m为q的倍数时，同理可证。所以原等式得证。(6

31、) RSA算法正确性证明：m=cd mod n=(me mod n)d mod n=med mod n= mod n(因为ed mod =1)=mRSA算法得证。2.2 DSA签名算法基于离散对数问题的数字签名算法有很多，如ElGamal , Schnorr , DSA , GOST , Okamoto等等。下面仅介绍DSA。DSA算法是ElGamal签名算法和Schnorr签名算法的变体10。它从产生起一直倍受争议，但至今还未发现该算法大的弱点。2.2.1 参数构成(1) 全局参数(所有用户公用参数)p:大质数，其字长L的范围是，按64 bit的幅度递增。q:(p-1)的素因子，字长为160

32、 bit。g:g=h(p-1)/q mod p,其中1h 1。(2) 私钥x:选取的一个随机数，0xq.(3) 公钥y:y=gx mod p.DSA签名算法包括以下过程：2.2.2 签名过程(1) 生成随机数k,0k=160 bit的比特串seedE(可选项，用于合法性检查)；(3) 方程系数a,b 用于y2=x3+ax+b(基于Fp)或y2+xy=x3+ax2+b(基于)；(4) xG、yG，定义点G，要求G的阶为质数；(5) G的阶n,n2160且；(6) h=#E(Fq)/n.私钥与公钥的选取：(1) 选取随机整数d,要求；(2) 求Q=dG；(3) 则私钥为d,公钥为Q；2.3.5 签

33、名过程(1) 选择随机数k,要求；(2) 求kG=(x1,y1) ；注：kG不是整数k乘以G，而是k个G连加，下文中也类似。(3) 求r=x1 mod n，若r=0，回到(1)；(4) 求k-1 mod n；(5) 求e=SHA1(m)；(6) 求s=k-1(e+dr) mod n，若s=0，回到(1)；(7) 将消息m和签名(r,s)发送。从以上过程可以看出：ECDSA算法同样不可用于加解密。因为发送方只有对方的公钥，而此处须用到私钥。2.3.6 验证过程(1) 检查r和s，要求；(2) 求e=SHA1(m)；(3) 求w=s-1 mod n；(4) 求u1=ew mod n, u2=rw

34、mod n；(5) 求X=u1G+u2Q；(6) 若X=O，则验证失败，否则,设X=(x1,y1),计算v=x1 mod n；(7) 若v=r，则验证通过，否则失败。2.3.7 ECDSA算法正确性证明s=k-1(e+dr) mod n，则ks mod n=(k mod n)* (k-1(e+dr) mod n) mod n=(kk-1(e+dr) mod n =( (kk-1) mod n )* (e+dr) mod n) mod n =(e+dr) mod n (2.3.1)k=k mod n= (kss-1) mod n =(ks mod n) * (s-1 mod n) mod n =

35、(e+dr)mod n) *(w mod n) mod n =(e+dr)w) mod n=(ew+drw) mod n=(ew) mod n +(drw) mod n) mod n=(u1+(d mod n) *( (rw) mod n) mod n) mod n =(u1+du2 mod n) mod n=(u1+u2d) mod n (2.3.2)X=u1G+u2Q=u1G+u2dG=(u1+u2d)G设u1+u2d=jn+k (3.2),则X=(jn+k)G=jnG+kG=kG(因为n是G的阶，所以nG=O)所以X的横坐标x1与kG的横坐标x1相等，故v=x1 mod n=x1 mod n=r所以ECDSA算法得证。3 数字证书简述数字证书是一种权威性的电子文档。它提供了一种在Internet上验证身份的方式，其作用类似于司机的驾驶执照或日常生活中的身份证。它是由权威机构认证中心发行的。数字证书是认证中心(Certificate Authority，简称CA)颁发并进行数字签名的数字凭证。数字证书又简称证书或电子证书，分属性证书、公钥证书等类型。一般未注明时，证书即公钥证书。数字证书和认证中心是数字签名技术最重要的应用领域。目前的数字证书类型主要包括：个人数字证书、单位数字证书、单