转载数字签名算法分析与Hash签名转

1、转载 数字签名算法分析与Hash签名【转】原文地址：数字签名算法分析与Hash签名【转】作者：stanley序：这篇文章我用了近一周的时间完成，其中涉及到的RSA算法已经在上一篇公钥密码体系中详细的介绍过，目前数字签名中人们使用很多的还是512位与1024位的RSA算法。摘要：数字签字和认证机构是电子商务的核心技术。数字签名作为目前Internet中电子商务重要的技术，不断地进行改进，标准化。本文从数字签名的意义出发，详细介绍了数字签名中涉及到的内容与算法，并自行结合进行改进。关键词：Internet公钥加密Hash函数电子商务加密数字签名数字签名简介我们对加解密算法已经有了一定理解,可以进一

2、步讨论数字签名(注意不要与数字认证混淆)的问题了,即如何给一个计算机文件进行签字。数字签字可以用对称算法实现，也可以用公钥算法实现。但前者除了文件签字者和文件接受者双方，还需要第三方认证，较麻烦；通过公钥加密算法的实现方法，由于用秘密密钥加密的文件，需要靠公开密钥来解密，因此这可以作为数字签名，签名者用秘密密钥加密一个签名(可以包括姓名、证件号码、短信息等信息)，接收人可以用公开的、自己的公开密钥来解密，如果成功，就能确保信息来自该公开密钥的所有人。公钥密码体制实现数字签名的基本原理很简单，假设A要发送一个电子文件给B，A、B双方只需经过下面三个步骤即可：1.A用其私钥加密文件，这便是签字过程

3、2.A将加密的文件送到B 3.B用A的公钥解开A送来的文件这样的签名方法是符合可靠性原则的。即：*签字是可以被确认的，*签字是无法被伪造的，*签字是无法重复使用的，*文件被签字以后是无法被篡改的，*签字具有无可否认性，数字签名就是通过一个单向函数对要传送的报文进行处理得到的用以认证报文来源并核实报文是否发生变化的一个字母数字串。用这几个字符串来代替书写签名或印章，起到与书写签名或印章同样的法律效用。国际社会已开始制定相应的法律、法规，把数字签名作为执法的依据。数字签名的实现方法实现数字签名有很多方法，目前数字签名采用较多的是公钥加密技术，如基于RSA Data Security公司的PKCS(

4、Public Key Cryptography Standards)、DSA(Digital Signature Algorithm)、x.509、PGP(Pretty Good Privacy)。1994年美国标准与技术协会公布了数字签名标准(DSS)而使公钥加密技术广泛应用。同时应用散列算法(Hash)也是实现数字签名的一种方法。非对称密钥密码算法进行数字签名算法的含义：非对称密钥密码算法使用两个密钥：公开密钥和私有密钥，分别用于对数据的加密和解密，即如果用公开密钥对数据进行加密，只有用对应的私有密钥才能进行解密；如果用私有密钥对数据进行加密，则只有用对应的公开密钥才能解密。使用公钥密码算

5、法进行数字签名通用的加密标准有：RSA，DSA，Diffie-Hellman等。签名和验证过程：发送方(甲)首先用公开的单向函数对报文进行一次变换，得到数字签名，然后利用私有密钥对数字签名进行加密后附在报文之后一同发出。接收方(乙)用发送方的公开密钥对数字签名进行解密交换，得到一个数字签名的明文。发送方的公钥可以由一个可信赖的技术管理机构即认证中心(CA)发布的。接收方将得到的明文通过单向函数进行计算，同样得到一个数字签名，再将两个数字签名进行对比，如果相同，则证明签名有效，否则无效。这种方法使任何拥有发送方公开密钥的人都可以验证数字签名的正确性。由于发送方私有密钥的保密性，使得接受方既可以根

6、据结果来拒收该报文，也能使其无法伪造报文签名及对报文进行修改，原因是数字签名是对整个报文进行的，是一组代表报文特征的定长代码，同一个人对不同的报文将产生不同的数字签名。这就解决了银行通过网络传送一张支票，而接收方可能对支票数额进行改动的问题，也避免了发送方逃避责任的可能性。对称密钥密码算法进行数字签名算法含义对称密钥密码算法所用的加密密钥和解密密钥通常是相同的，即使不同也可以很容易地由其中的任意一个推导出另一个。在此算法中，加、解密双方所用的密钥都要保守秘密。由于计算机速度而广泛应用于大量数据如文件的加密过程中，如RD4和DES，用IDEA作数字签名是不提倡的。使用分组密码算法数字签名通用的加

7、密标准有：DES，Tripl-DES,RC2,RC4,CAST等。签名和验证过程Lamport发明了称为Lamport-Diffle的对称算法：利用一组长度是报文的比特数(n)两倍的密钥A，来产生对签名的验证信息，即随机选择2n个数B，由签名密钥对这2n个数B进行一次加密交换，得到另一组2n个数C。发送方从报文分组M的第一位开始，依次检查M的第I位，若为0时，取密钥A的第i位，若为1则取密钥A的第i+1位；直至报文全部检查完毕。所选取的n个密钥位形成了最后的签名。接受方对签名进行验证时，也是首先从第一位开始依次检查报文M，如果M的第i位为0时，它就认为签名中的第i组信息是密钥A的第i位，若为1

8、则为密钥A的第i+1位；直至报文全部验证完毕后，就得到了n个密钥，由于接受方具有发送方的验证信息C，所以可以利用得到的n个密钥检验验证信息，从而确认报文是否是由发送方所发送。这种方法由于它是逐位进行签名的，只有有一位被改动过，接受方就得不到正确的数字签名，因此其安全性较好，其缺点是：签名太长(对报文先进行压缩再签名，可以减少签名的长度)；签名密钥及相应的验证信息不能重复使用，否则极不安全。结合对称与非对称算法的改进对称算法与非对称算法各有利弊，所以结合各自的优缺点进行改进，可以用下面的模块进行说明：Hash算法进行数字签名Hash算法也称作散列算法或报文摘要，Hash算法将在数字签名算法中详细

9、说明。Hash算法数字签字通用的加密标准有：SHA-1，MD5等。数字签名算法数字签名的算法很多,应用最为广泛的三种是：Hash签名、DSS签名、RSA签名。这三种算法可单独使用，也可综合在一起使用。数字签名是通过密码算法对数据进行加、解密变换实现的，常用的HASH算法有MD2、MD5、SHA-1，用DES算法、RSA算法都可实现数字签名。但或多或少都有缺陷，或者没有成熟的标准。Hash签名Hash签名是最主要的数字签名方法，也称之为数字摘要法(digital digest)、数字指纹法(digital finger print)。它与RSA数字签名是单独的签名不同，该数字签名方法是将数字签名

10、与要发送的信息紧密联系在一起，它更适合于电子商务活动。将一个商务合同的个体内容与签名结合在一起，比合同和签名分开传递，更增加了可信度和安全性。下面我们将详细介绍Hash签名中的函数与算法。单向函数单向函数的概念是公开密钥密码的核心。尽管它本身并不是一个协议，但对大多数协议来说却是一个基本结构模块。单向函数的概念是计算起来相对容易，但求逆却非常困难。也就是说，已知x，我们很容易计算f(x)。但已知f(x)，却难于计算出x。在这里，难定义成：即使世界上所有的计算机都用来计算，从f(x)计算出x也要花费数百万年的时间。打碎盘子就是一个很好的单向函数的例子。把盘子打碎成数千片碎片是很容易的事情，然而，

11、要把所有这些碎片再拼成为一个完整的盘子，却是非常困难的事情。这听起来很好，但事实上却不能证实它的真实性。如果严格地按数学定义，我们不能证明单向函数的存在性，同时也还没有实际的证据能够构造出单向函数。即使这样，还是有很多函数看起来和感觉像单向函数：我们能够有效地计算它们，且至今还不知道有什么办法能容易地求出它们的逆。例如，在有限域中x2是很容易计算的，但计算x1/2却难得多。所以我们假定也尽量构造单向函数存在。陷门单向函数是有一个秘密陷门的一类特殊单向函数。它在一个方向上易于计算而反方向却难于计算。但是，如果你知道那个秘密，你也能很容易在另一个方向计算这个函数。也就是说，已知x，易于计算f(x)

12、，而已知f(x)，却难于计算x。然而，有一些秘密信息y，一旦给出f(x)和y，就很容易计算x。拆开表是很好的单向陷门函数的例子。很容易把表拆成数百片小片，把这些小片组装成能够工作的表是非常困难的。然而，通过秘密信息(表的装配指令)，就很容易把表还原。单向Hash函数单向Hash函数有很多名字：压缩函数、缩短函数、消息摘要、指纹、密码校验和、信息完整性检验(DIC)、操作检验码(MDC)。不管你怎么叫，它是现代密码学的中心。单向Hash函数是许多协议的另一个结构模块。Hash函数长期以来一直在计算机科学中使用，无论从数学上或别的角度看，Hash函数就是把可变输入长度串(叫做预映射，Pre-ima

13、ge)转换成固定长度(经常更短)输出串(叫做hash值)的一种函数。简单的Hash函数就是对预映射的处理，并且返回由所有输入字节异或组成的一字节。这儿的关键就是采集预映射的指纹：产生一个值，这个值能够指出候选预映射是否与真实的预映射有相同的值。因为Hash函数是典型的多到一的函数，我们不能用它们来确定两个串一定相同，但我们可用它来得到准确性的合理保证。单向Hash函数是在一个方向上工作的Hash函数，从预映射的值很容易计算其Hash值，但要产生一个预映射的值使其Hash值等于一个特殊值却是很难的。好的hash函数也是无冲突的：难于产生两个预映射的值，使他们的hash值相同。Hash函数是公开的

14、，对处理过程不用保密。单向hash函数的安全性是它的单向性。无论怎么看，输出不依赖于输入。预映射单个比特的改变，平均而言，将引起hash值中一半的比特改变。已知一个hash值，要找到预映射的值，使它的hash值等于已知的hash值在计算上是不可行的。哈希函数，即对于任意长度的信息m，经过哈希函数运算后，压缩后固定长度的数，比如64比特HASH函数的特殊要求是：1.已知哈希函数的输出，要求它的输入是困难的，即已知c=Hash(m)，求m是困难的。这表现了函数的单向性。2.已知m，计算Hash(m)是容易的。这表现了函数的快速性。3.已知，构造m2使Hash(m2)=c1是困难的。这是函数的抗碰撞

15、性。4.c=Hash(m)，c的每一比特都与m的每一比特有关，并有高度敏感性。即每改变m的一比特，都将对c产生明显影响。这就是函数的雪崩性。5.作为一种数字签名，还要求哈希函数除了信息m自身之外，应该基于发信方的秘密信息对信息m进行确认。6.接受的输入m数据没有长度限制；对输入任何长度的m数据能够生成该输入报文固定长度的输出；曾有数家统计计算结果表明，如hash(m)的长度为128位(bit)时，则任意两个分别为M1.M2的输入报文具有完全相同的h(m)的概率为10-24，即近于零的重复概率。它较人类指纹的重复概率10-19还要小5个数量级。而当我们取hash(m)为384(bit)乃至102

16、4(bit)时，则更是不大可能重复了。另外，如输入报文M1与输入报文M2全等,则有h(m1)与h(m2)全等，如只将M2或M1中的某任意一位(bit)改变了，其结果将导致h(m1)与h(m2)中有一半左右对应的位(bit)的值都不相同了。这种发散特性使电子数字签名很容易发现(验证签名)输入报文的关键位的值被人篡改了。数字摘要(digitaldigest)加密方法亦称安全Hash编码法(SHA：SecureHashAlgorithm)或MD5(MDstandardforMessageDigest)，由RonRivest设计。该编码法采用单向Hash函数将需加密的明文摘要成一串128bit的密文，

17、这一串密文亦称为数字指纹(FingerPrint)，它有固定的长度，且不同的明文摘要必定一致。这样这串摘要使可成为验证明文是否是真身的指纹了。Hash签名不属于强计算密集型算法，应用较广泛。很多少量现金付款系统，如DEC的Millicent和CyberCash的CyberCoin等都使用Hash签名。使用较快的算法,可以降低服务器资源的消耗,减轻中央服务器的负荷。Hash的主要局限是接收方必须持有用户密钥的副本以检验签名,因为双方都知道生成签名的密钥，较容易攻破，存在伪造签名的可能。如果中央或用户计算机中有一个被攻破,那么其安全性就受到了威胁。DSS和RSA签名DSS和RSA采用了公钥算法。D

18、igital Signature Algorithm(DSA)是Schnorr和ElGamal签名算法的变种，被美国NIST作为DSS(Digital SignatureStandard)数字签名标准。DSS是由美国国家标准化研究院和国家安全局共同开发的。由于它是由美国政府颁布实施的，主要用于与美国政府做生意的公司，其他公司则较少使用，它只是一个签名系统，而且美国政府不提倡使用任何削弱政府窃听能力的加密软件，认为这才符合美国的国家利益。算法中应用了下述参数：*p：L bits长的素数。L是64的倍数，范围是512到1024；*q：是p-1的160bits的素因子；*g：g=h(p-1)/q)m

19、od p，h满足h p-1,h(p-1)/q)mod p1；*x：秘密密钥，正整数，x q；*y：y=gx mod p，(p,q,g,y)为公钥；*k为随机数，0kq；*H(x)：One-Way Hash函数。DSS中选用SHA(Secure Hash Algorithm)。p,q,g可由一组用户共享，但在实际应用中，使用公共模数可能会带来一定的威胁。签名过程如下：1.P产生随机数k，k q；2.P计算r=(gk mod p)mod qs=(k(-1)(H(m)+xr)mod q验证过程：签名结果是(m,r,s)。3.验证时计算w=s(-1)mod qu1=(H(m)*w)mod qu2=(r

20、*w)mod qv=(gu1*yu2)mod p)mod q若v=r，则认为签名有效。DSA位数仅为160位，没有太大的意义，也存在系统平台不兼容的问题，而且DSA是基于整数有限域离散对数难题的，安全强度和速度均低于RSA算法。DSA的一个重要特点是两个素数公开，这样，当使用别人的p和q时，即使不知道私钥，你也能确认它们是否是随机产生的，还是作了手脚。RSA算法却作不到。DSA算法的安全性也依赖于有限域上的离散对数问题，其优点是不涉及专利问题。其中H(x)可选择美国推荐的标准算法SHA或MD5等安全散列算法。其中MD5算法在本论坛中已有介绍。RSA是最流行的一种加密标准，许多产品的内核中都有R

21、SA的软件和类库,早在Web飞速发展之前,RSA数据安全公司就负责数字签名软件与Macintosh操作系统的集成,在Apple的协作软件PowerTalk上还增加了签名拖放功能,用户只要把需要加密的数据拖到相应的图标上,就完成了电子形式的数字签名。RSA与Microsoft、IBM、Sun和Digital都签订了许可协议,使在其生产线上加入了类似的签名特性。与DSS不同,RSA既可以用来加密数据,也可以用于身份认证。和Hash签名相比，在公钥系统中,由于生成签名的密钥只存储于用户的计算机中,安全系数大一些。用RSA或其它公开密匙密码算法进行数字签名的最大方便是没有密匙分配问题(网络越复杂、网络

22、用户越多，其优点越明显)。因为公开密匙加密使用两个不同的密匙，其中有一个是公开的，另一个是保密的。公开密匙可以保存在系统目录内、未加密的电子邮件信息中、电话黄页(商业电话)上或公告牌里，网上的任何用户都可获得公开密匙。而保密密匙是用户专用的，由用户本身持有，它可以对由公开密匙加密信息进行解密。RSA算法中数字签名技术实际上是通过一个哈希函数来实现的。数字签名的特点是它代表了文件的特征，文件如果发生改变，数字签名的值也将发生变化。不同的文件将得到不同的数字签名。一个最简单的哈希函数是把文件的二进制码相累加，取最后的若干位。哈希函数对发送数据的双方都是公开的。我们认为RSA算法是目前比较好的密码算

23、法，它不仅可以作为加密算法使用，而且可以用作数字签名和密钥分配与管理，而DSA只适合作签名，且安全强度和速度都不如RSA，椭圆曲线上的公开密钥密码系统安全强度依赖于曲线的选择和体制，我们相信它会有更高的安全强度，目前200比特长的椭圆曲线密码体制已经有相当高的安全强度。数字签名的保密性数字签名的保密性很大程度上依赖于公开密钥。数字签名的加密解密过程和秘密密钥的加密解密过程虽然都使用公开密钥体系，但实现的过程正好相反，使用的密钥对也不同。数字签名使用的是发送方的密钥对，发送方用自己的私有密钥进行加密，接收方用发送方的公开密钥进行解密。这是一个一对多的关系：任何拥有发送方公开窃钥的人都可以验证数字

24、签名的正确性，而秘密密钥的加密解密则使用的是接收方的密切对，这是多对一的关系：任何知道接收方公开密钥的人都可以向接收方发送加密信息，只有唯一拥有接收方私有密钥的人才能对信息解密。这是一个复杂但又很有趣的过程。在实用过程中，通常一个用户拥有两个密钥对一一一个密钥对用来对数字签名进行加密解密，一个密钥对用来对秘密密钥进行加密解密。这种方式提供了更高的安全性。又由于加密钥匙是公开的，密钥的分配和管理就很简单，而且能够很容易地实现数字签名。因此，最适合于电子商务应用需要。在实际应用中，公开密钥加密系统并没有完全取代秘密钥匙加密系统，这是因为公开密钥加密系统是基于尖端的数学难题，计算非常复杂，它的速度远

25、赶不秘密钥匙加密系统。因此，在实际应用中可利用二者的各自优点，采用秘密钥匙加密系统加密文件，采用公开密钥加密系统加密加密文件的密钥，这就是混合加密系统，它较好地解决了运算速度问题和密钥分配管理问题。数字签名中的问题与改进以上数字签字的方法是相当简单和理想化的，具体应用中还是有一些问题需要解决的。1.签字后的文件可能被接收方重复使用。如果签字后的文件是一张支票，接收方很容易多次用该电子支票兑换现金，为此发送方需要在文件中加上一些该支票的特有的凭证，如时间戳timestamp(但时间戳会有一个时间是否同步的问题)等，以防止上述情况发生。2.数字签名应用很多的RSA算法是基于大数的因子分解难题，由于

26、计算水平的提高，人们逐渐可以用计算机分解更大的数。因此RSA算法的密钥也就越来越长，诸位使用PGP时至少要选择700比特以上的密钥。在电子商务的SET协议中，规定用户使用1024比特的RSA密钥，认证中心CA使用2048比特的RSA密钥。长密钥带来两个问题，一是运算速度较慢，另一个是密钥存储和管理问题。如果用16位的IC卡实现电子钱包，使用1024比特的RSA算法速度就很慢，要以秒计算。而固化RSA算法的IC卡或32位的IC卡价格则较贵。3.公钥算法的效率是相当低的，不易用于长文件的加密，为此我们采用Hash函数，将原文件P通过一个单向(one-way)的Hash函数作用，生成相当短的(仅几十

27、或几百bits)的输出H，即Hash(P)=H，这里由P可以很快生成H，但由于H几乎不可能生成P，然后再将公钥算法作用在H上生成签字S，记为Ek1(H)=S，k1为A的公钥，A将(P，S)传给B，B收到(P，S)后，需要验证S是A的签字。若我们有H1=H2，即Dk2(S)=Hash(P)，我们才能认为S就是A的签字。4.如果在Hash签名使用一个密钥k，让只有知道此密钥k的人才能使用hash，即用H(m，k)代替H(m)，则可以增强Hash加密的安全性。以上方法实际上就是把签字过程从对原文件转移到一个很短的hash值上，大大地提高了效率，可以在现代的电子商务中被广泛的使用。数字签名的发展方向2

28、000年1月举行的第六届国际密码学会议对应用于公开钥密码系统的加密算法，推荐了两种：基于大整数因子分解难题的RSA算法和基于椭圆曲线上离散对数计算难题的ECC算法。所以基于RSA算法的数字签名还有一定的发展。对于未来的加密、生成和验证数字签名的工具需要完善,只有用SSL(安全套接层)建立安全链接的Web浏览器,才会频繁使用数字签名,公司要对其雇员在网络上的行为进行规范，就要建立广泛协作机制来支持数字签名,支持数字签名是Web发展的目标,确保数据保密性、数据完整性和不可否认性才能保证在线商业的安全交易。和数字签名有关的复杂认证能力就像现在操作、应用环境中的口令保护一样直接做进操作系统环境、应用、远程访问产品、信息传递系统及Int