12 签名算法

签名算法是公钥密码学的“消息认证码”，它主要包括3个部分：

签名算法可以在加密算法的基础上构建。使用一个私钥，可以对一个消息产生一个值，通常是使用hash算法来生成。任何人都可以用公钥来检查这个值，计算该值是否由消息计算得到，然后将两者进行验证。和公钥加密算法一个明显的不同是，使用私钥来产生消息（这个情形下就是签名），使用公钥去解析它，这个和加密的过程是反过来的。

上面的说明是对后面很多重要细节的概述。本文将搏逗仔继续讨论一些细节。

数字签名算法（Digital Signature Algorithm DSA）是英国联邦政府的一个数字签名标准。它由NIST（National Institute of Standards and Technology）在1991年第一次提出,用来作为数字签名的标准（Digital Signature Standard DDS）。该算法由NSA的技术顾问David W.Kravitz发布。

DSA的密钥生成分为两步：第一步，选择在用户中共享的参数。第二步，为每一个用户生成一份公私钥对。

首先需要挑选一个被推荐的密码hash函数H，密钥长度L和一个素数长度N。原始的DSS中推荐L的长度为512和1024之间，现在NIST推荐密钥的长度为3072位这样密钥的安全生命周期就可以到2030年。随着L的增长，N也需要增长。

接下来选择素数q，其长度为N位。N需要小于或者等于hash输出的长度。再选择一个L位长度的素数p，使得p-1是q的倍数。

最后一部分是最容易让人困惑的。需要找到一个数字g，它的乘法序模p是q。最简单的方法是设

也可以尝试其他比2大，比p-1小的数。

一旦确定了(p,q,g),可以将其在用户中共享。

有了参数，就该来位用户计算公钥和私钥了。首先，选择随机数x (0<x<q)， 接下来计算y y=g^x(mod p).这样私钥就是x，公钥为（p,q,g,y）。

为了对消息进行签名，签名者在0-q之间挑选一个随机数k。如何挑选k是一个很敏感和相关的过程，这个在之后进行讨论。当k选定后，可以计算消息m的签名的两部分r和s:

如果两者中任意一个是0（罕见时间），再重新选择一个k。

验证签名需要一个复杂的计算。给定消息m和签名（r，s）:

如果签名是有效的，那么v就会等于r，也就是签名的第二部分。

虽然目前DSA算法自身没有什么问题，但是它却很容易出错。进一步说，DSA是非常敏感的，仅仅是一个很小的实现上的错误就可以毁掉整个机制。

特殊来看，签名参数k的选择是非常严格的。可以说是密码系统中对于随机数选择中最严格的。例如，很多算法需要一个nonce值。nonce值仅仅需要唯一，它不需要私密。它也不需要不可预测。nonce值基汪通常可以使用简单的计数器或者时钟。很多其他算法例如CBC模式，需要一个初始化向量。它不需要是唯一的，只需要是不可预测的。它也不需要是私密的：初始化向量通常和密文一起。但是DSA算法的随机数k是以上的组合：

如果没有满足这些特性，攻击者可以尝试从一定数量的签名中得到你的私钥。例如，攻击者只要知道k的一些位，和比较多的有效签名，就可以恢复出私钥。[NS00]

实际中DSA的很多实现都不能保证唯一性，愉快地重用随机数k。这就使得只需要使用简单的数学就可以恢复密钥。因为这个攻击很容易理解，应用非指缓常广泛并且可以造成非常严重的影响，本节将讨论它的细节。

假设攻击者看到了很多对于不同消息mi的签名（ri，si），它们使用了相同的k。攻击者可以挑选出两个签名（r1，s1）和（r2，s2），假设它们的原消息位m1和m2.s1和s2的是通过如下计算得到的

攻击者可以推断出r1和r2是相同的，因为

重用了相同的k，而r仅仅依赖于k，所以r是相同的。另外由于签名者使用的是同一个密钥，两个公式中的x也是相同的。

将两个s相减，得到一下的计算：

可以得到k

两个hash值H(m1)和H(m2)很容易计算。它们并没有加密，被签名的消息是公开的。签名的两个s1和s2是签名的组成部分，攻击者都可以看到。所以攻击者可以计算得到k。目前它还没有得到私钥x，然后用私钥去伪造签名。

再次看下s的计算过程，这次把k当作是已知项，x作为需要解决的变量。

所有有效的签名都满足这个等式，所以可以尝试任意一个签名。来解出x

同样的H（m）是公开的，攻击者可以计算出k。假设他们已经计算出了k，s本身就是签名的一部分。现在只需要计算r^(-1)(mod q)(也就是r相对于模q的逆元)，这个同样也可以计算出来。（更多信息可以查看附录中有关于现代数学，记住q是个素数，所以这个模的逆元是可以直接计算的）。这也就意味着攻击者，只要发现了任何签名的k，就可以得到私钥的值。

目前为止，本节中假设的是签名者一直使用的同一个随机数k。更糟的是，签名者只要在攻击者可以看到的签名中，有两个签名复用k一次。如上，k重复了，r就会重复。而r是签名的一部分，签名者的这个错误非常容易被观察到。这样即便签名者只是很罕见地重用了k（比方说随机数生成器的问题），只一次，攻击者就可以打破这个DSA系统。

简而言之，在DSA签名算法中重用参数k就意味着攻击者可以破解出私钥。

TODO：

和一般的DSA相同，k的选择是极为严格的。攻击者可以使用几千个签名，这些签名的nonce仅仅有一些位泄漏，攻击者便可以破解出签名的私钥。

本章描述的签名算法有一个特点被称为：不可抵赖性。简单说，它意味着不可以否认自己就是签名消息的发送者。任何人都可以验证你用私钥签署的签名。但是签名只有你可以做。

这通常并不是一个有用的特性，只有少数接受者可以验证签名可能更加谨慎。这种算法通常需要只有接受者才可以计算出这个特殊的值。

这些消息是可以拒绝的，例如一种通常被称为“可以否认的消息认证”。一个发送者认证一条消息给接收者，发送者之后可以否认它发送了这条消息。接收者也无法向任何人证明发送者给他发送了特定的消息。

简洞碧镇单地说,所谓数字签名就是附加在数据单元上的一些数据,或是对数据单元所作的密码变换。这种数据或变换允许数据单元的接收者用以确认数据单元的来源和数据单元的完整性并保护数据,防止被人(例如接收者)进行伪造。它是对电子形式的消息进行签名的一种方法,一个签名消息能在一个通信网络中传输。基于公钥密码体制和私钥密码体制都可以获得数字签名,目前主要是基于公钥密码体制的数字签名。包括普通数字签名和特殊数字签名。普通数字签名算法有RSA、ElGamal、Fiat-Shamir、Guillou- Quisquarter、Schnorr、Ong-Schnorr-Shamir数字签名算法、Des/DSA,椭圆纳粗曲线数字签名算法和有限自动机数字签名算法等。特殊慧祥数字签名有盲签名、代理签名、群签名、不可否认签名、公平盲签名、门限签名、具有消息恢复功能的签名等,它与具体应用环境密切相关。显然,数字签名的应用涉及到法律问题,美国联邦政府基于有限域上的离散对数问题制定了自己的数字签名标准(DSS)。

关于如何申请数字签名，请参考这个网站：http://llloo.cn/archives/1132.html

数字签名

所谓"数字签名"就是通过某种密码运算生成一系列符号及代码组成电子密码进行签名，来代替书写签名或印章，对于这种电子式的签名还可进行技术验证，其验证的准确度是一般手工签名和图章的验证而无法比拟的。"数字签名"是目前电子商务、电子政务中应用最普遍、技术最成熟的、可 *** 作性最强的一种电子签名方法。它采用了规范化的程序和科学化的方法，用于鉴定签名人的身份以及对一项电子数据内容的认可。它还能验证出文件的原文在传输过程中有无变动，确保传输电子文件的完整性、真实性和不可抵赖性。

数字签名在ISO7498-2标准中定义为："附加在数唤春据单元上的一些数据，或是对数据单元所作的密码变换，这种数据和变换允许数据单元的接收者用以确认数据单元来源和数据单元的完腔高整性，并保护数据，防止被人（例如接收者）进行伪造"。美国电子签名标准（DSS，FIPS186-2）对数字签名作了如下解释："利用一套规则和一个参数对数据计算所得的结果，用此结果能够确认签名者的身份和数据的完整性"。按上述定义PKI（Public Key Infrastructino 公钥基础设施）提供可以提供数据单元的密码变换，并能使接收者判断数据来源及对数据进行验证。

PKI的核心执行机构是电子认证服务提供者，即通称为认证机构CA（Certificate Authority），PKI签名的核心元素是由CA签发的数字证书。它所提供的PKI服务就是认证、数据完整性、数据保密性和不伍链尺可否认性。它的作法就是利用证书公钥和与之对应的私钥进行加/解密，并产生对数字电文的签名及验证签名。数字签名是利用公钥密码技术和其他密码算法生成一系列符号及代码组成电子密码进行签名，来代替书写签名和印章；这种电子式的签名还可进行技术验证，其验证的准确度是在物理世界中对手工签名和图章的验证是无法比拟的。这种签名方法可在很大的可信PKI域人群中进行认证，或在多个可信的PKI域中进行交*认证，它特别适用于互联网和广域网上的安全认证和传输。

“数字签名”与普通文本签名的最大区别在于，它可以使用个性鲜明的图形文件，你只要利用扫描仪或作图工具将你的个性签名、印章甚至相片等，制作成BMP文件，就可以当做“数字签名”的素材。

目前可以提供“数字签名”功能的软件很多，用法和原理都大同小异，其中比较常用的有“ OnSign”。安装“OnSign”后，在Word、Outlook等程序的工具栏上，就会出现，“OnSign”的快捷按钮，每次使用时，需输入自己的密码，以确保他人无法盗用。

对于使用了“OnSign”寄出的文件，收件人也需要安装“OnSign”或“OnSign Viewer”，这样才具备了识别“数字签名”的功能。根据“OnSign”的设计，任何文件内容的窜改与拦截，都会让签名失效。因此当对方识别出你的“数字签名”，就能确定这份文件是由你本人所发出的，并且中途没有被窜改或拦截过。当然如果收件人还不放心，也可以单击“数字签名”上的蓝色问号，“OnSign”就会再次自动检查，如果文件有问题，“数字签名”上就会出现红色的警告标志。

在电子邮件使用频繁的网络时代，使用好“数字签名”，就像传统信件中的“挂号信”，无疑为网络传输文件的安全又增加了一道保护屏障。

---