常规数字签名体制

4.1.2　常规数字签名体制

目前的数字签名是建立在公共密钥体制基础上的，它是公用密钥加密技术的另一类应用。已经具有大量数字签名算法，如RSA数字签名体制、EIGamal数字签名算法、Fiat－Shamir数字签名算法、Guillou－Quisquarter数字签名算法、Schnorr数字签名算法、DSS数字签名体制、椭圆曲线数字签名算法（ECDSA）和有限自动机数字签名算法等。

本节将介绍应用最广泛的三种数字签名方法，即RSA数字签名体制、DSS数字签名体制和椭圆曲线数字签名算法（ECDSA）。这三种算法可单独使用，也可综合在一起使用。

1.RSA数字签名体制

用RSA算法做数字签名很简单。总的来说，就是签名者用私钥参数d加密，也就是签名；验证者用签字者的公钥参数e解密来完成认证。

（1）数字签名框图　可以用图4-2总结RSA数字签名的原理。

图4-2　RSA数字签名框图

使用发送方的私钥（d，n）对消息M的散列值加密，既具有身份辨别又有数据完整性保护的功能，也就达到了数字签名的要求。

（2）签名过程　下面描述RSA数字签名和认证的过程。

①计算消息的散列值H（M）。

②用私钥（d，n）加密散列值：s＝（H（M））^dmod n。签名结果就是s。

③发送消息和签名（M，s）。

当然，消息M很短的时候，可以直接对M用私钥加密，可以表达为

s＝Sig（M）＝M^dmod n。

总之，签名时使用私钥（d，n）。

（3）认证过程　接收方收到（M，s）之后，按照如下步骤验证签名的有效性。

①取得发送方的公钥（e，n）。

②解密签名s：h＝s^emod n。

③计算消息的散列值H（M）。

④比较，如果h＝H（M），表示签名有效；否则，签名无效。

如果消息M很短的时候，可以直接对M用公钥解密以验证签名的有效性，可以表达为

Ver（M，s）＝真〈＝〉M＝s^emod n。

在对短消息进行RSA签名的实际系统中，我们建议不要使用私钥直接加密的方式。总之，认证时使用公钥（e，n），然后通过比较来确定签名的合法性。

2.DSS数字签名体制

美国国家标准技术研究所（NIST）于1991年颁布了数字签名标准（DSS：Digital Signature Standard），该标准使用的签名算法简称为DSA（Digital Signature Algorithm）。注意区别DSS和DSA两个概念，前者是一个标准，后者是标准当中使用的算法。DSS签名标准具有较大的兼容性和适用性，已经成为网络中安全体系的基本构件之一。

DSA数字签名算法是EIGamal、Schnorr等数字签名算法的变体，该算法是由DWKravitz设计，由美国国家标准技术研究所和国家安全局共同开发的。DSA是基于离散对数的难度。

（1）DSS介绍

数字签名标准（DSS）由美国NIST于1991年8月提出，于1994年底正式成为美国联邦信息处理标准（FIPS PUB186）。其间，到1992年NIST征求了各方对DSS的意见，在1993和1996年分别做了小的修改。DSS中采用的用于签名的算法称为“数字签名算法”——DSA，DSA的安全性是基于离散对数问题的。

DSA算法设计专用作数字签名，不像RSA还可用作加密和密钥变换。

DSS方法也利用一个散列函数。散列码和一个用作这个特殊签名的随机数k作为签名函数的输入。签名函数还依赖于发方的私钥和一个对许多通信原则来说是知名的参数集。我们可以认为这个集合组成一个全局公开密钥。结果是由两个分量组成，记为s和r。

接收端将计算所收到报文的散列码，该散列码和签名将作为验证函数的输入。验证函数还依赖于全局公开密钥和发方私钥配对的发方公开密钥。如果签名是有效的，验证函数的输出值就等于签名分量r。签名函数就是这样的：只有发方用掌握的私钥才能产生有效的签名。我们可以用图4-3简明地表示DSS数字签名体制。

图4-3　DSS数字签名体制

DSA签名和RSA签名一样不存在Hash签名的局限性，因为它们都采用了公钥算法，即每个人都有两个密钥，其中一个产生签名，并秘密保存；另一个公开，用来验证签名。

图中散列函数是SHA散列函数。其中签名方在签名时，使用了随机数k，签名结果为（s，r）。验证方就是通过比较接收到的r与自己计算出来的r′，根据是否相等来判断签名的有效性。

（2）数字签名算法（DSA）

①DSA算法参数说明

DSA算法中应用了下述参数：

P：Lbit长的素数。L是64的倍数，范围是512～1 024；

Q：p－1的160bit的素因子；

G：g＝h^{（p－1）/q}mod p，h满足1＜h＜p－1，h^{（p－1）/q}mod p＞1；

X：1＜x＜q，x为私钥；

Y：y＝g^xmod p，（p，q，g，y）为公钥；

H（x）：单向Hash函数。在DSS中选用安全散列算法（Secure Hash Algorithm，SHA）。

p，q，g：可由一组用户共享，但在实际应用中，使用公开模数可能会带来一定的威胁。

②签名及验证协议

签名及验证协议如下：

（i）p产生随机数k，k＜q。

（ii）p计算r＝（g^kmod p）modq和s＝（k^－1（H（m）＋xr））modq。签名结果是（m，r，s）。

（iii）验证时，计算

w＝s^－1mod q　　　　　

u₁＝（H（m）·w）mod q

u₂＝（r·w）mod q　　

若v＝r，则认为签名有效。

DSA是基于整数有限域离散对数难题的，其安全性与RSA差不多。DSA的一个重要特点是两个素数公开，这样，当使用别人的p和q时，即使不知道私钥，也能确认它们是否是随机产生的。而RSA算法确做不到。图4-4描述了DSS的签名和验证函数。

图4-4　DSS签名和验证

3.椭圆曲线数字签名算法（ECDSA）

椭圆曲线加密系统是一种运用RSA和DSA来实施的数字签名方法。基于椭圆曲线的数字签名具有与RSA数字签名和DSA数字签名基本上相同的功能，但实施起来更有效，因为椭圆曲线数字签名在生成签名和进行验证时要比RSA和DSA快。椭圆曲线数字签名还可以用在一些较小、对资源有一定限制的设备（如智能卡，即含有微处理器芯片的塑料片）中。

椭圆曲线加密系统和DSA都属于利用离散对数问题进行加密方法的变体。DSA是一种由一系列以质数p为模的整数所组成的乘法组中解决离散对数问题的算法。利用不同的有线组可以获得这一算法的变体，而椭圆曲线是产生这些组的基础。在不同的组中寻找像DSA这样的算法的变体的原因是因为离散对数问题在有些组中要比其他组更困难。椭圆曲线就是比较困难的一种，这意味着可以用椭圆曲线来设计出一种比用以p为模的整数来加密的系统所需要的密钥长度更小、而加密强度却更大的系统。使用椭圆曲线系统，所要处理的数字更小，因而运行结果趋向更好。

从DSA演变出来的基于椭圆曲线变体的标准称为椭圆曲线数字签名算法（ECDSA），这是由电气和电子工程师协会IEEE和美国国家标准局ANSI有关金融服务的X9委员会联合开发的。

（1）ECDSA的签名算法

签名的时候，自然有待签署的消息m；全局参数D＝（q，FR，a，b，G，n，h），还有签名者的公钥私钥对（Q，d）。

签名的算法步骤描述如下：

①选择一个随机数k，k∈［1，n－1］；

②计算kG＝（x₁，y₁）；

③计算r＝x₁mod n；如果r＝0，则回到步骤①；

④计算k^－1mod n；

⑤计算e＝SHA1（m）；

⑥计算s＝k^－1（e＋dr）mod n，如果s＝0，则回到步骤①；

⑦对消息的签名为（r，s）；

最后签名者就可以把消息m和签名（r，s）发送给接收者。

（2）ECDSA的认证算法

当接收者收到消息m和签名（r，s）之后，验证对消息签名的有效性，需要取得这些参数：全局参数D＝（q，FR，a，b，G，n，h），发送者的公钥Q。我们建议接收者利用前面的合法性检查算法，也对参数D和Q的合法性进行检验。

认证算法可以描述如下：

①检查r、s，要求r、s∈［1，n－1］；

②计算e＝SHA1（m）；

③计算w＝s^－1mod n；

④计算u₁＝ewmod n；u₂＝rwmod n；

⑤计算X＝u₁G十u₂Q；

⑥如果X＝O，表示签名无效；否则，X＝（x₁，y₁），计算v＝x₁mod n；

⑦如果v＝r，表示签名有效；否则表示签名无效。

到此为止，我们全面介绍了ECDSA算法的实现过程。可以说，ECDSA算法就是在椭圆曲线上实现了DSA算法。