3.4 数字签名技术
3.4.1 DSA算法
数字签名（Digital Signature）主要用于对数字消息进行签名，以防消息的冒名伪造或篡改，也可以用于通信双方的身份鉴别。数字签名具有身份认证、数据完整性、不可否认性及匿名性等方面的特点。随着计算机通信网络的迅速发展，特别是在大型网络安全通信中的密钥分配、认证及电子商务系统中，数字签名的使用越来越普遍，数字签名是防止信息欺诈行为的重要措施。
数字签名标准（Digital Signature Standard，DSS）是由美国NIST公布的联邦信息处理标准FIPS 186，它是在ElGamal和Schnorr数字签名的基础上设计的。DSS中的算法称为DSA（Digital Signature Algorithm），其安全性基于离散对数问题的困难性。DSS最初提出于1991年，1993年根据公众对于其安全性的反馈意见进行了一些修改，1996年又稍做修改。2000年发布了该标准的扩充版，即FIPS 186-2，该版本还包括基于RSA和ECDSA的数字签名算法。
DSA是美国NIST公布的数字签名方案，1994年12月1日正式被采纳为美国联邦信息处理标准算法。DSA是Schnorr和ElGamal签名算法的变形，它的安全性基于计算有限域上离散对数问题的困难性。
1.密钥生成
密钥生成算法如下：
1）选取一个素数p，其中，2511+64j＜p＜2512+64j（j∈{0,1,…,8}）。
2）选取p-1的一个160bit的素数因子q（2150＜q＜2160）。
3）计算g=h（p-1）/qmod p，其中1＜h＜p-1。
4）生成一个随机数x（0＜x＜q）。
5）计算y=gxmod p。
公钥为（p, q, g, y），私钥为x。
2.签名生成
对明文m的签名算法如下：
1）生成一个随机数k（0＜k＜q）。
2）计算r=（gkmod p）mod q。
3）计算s=（k-1（SHA-1（m）+xr））mod p，其中，SHA-1（m）是用SHA-1算法对明文m进行Hash运算。
签名为（m, r, s）。
3.签名验证
对一个签名（m′,r′,s′）的验证过程如下：
1）计算w=（ s′）-1。
2）计算u1=（SHA-1（ m′）w）mod q。
3）计算u2=（ r′w）mod q。
4）计算
。
5）检验v是否等于r′。
只有当上述算法中v=r′时，接收的签名才被验证。
3.4.2 ECDSA算法
ECDSA是基于椭圆曲线的数字签名算法，目前已经被标准化，并在IEEE P1363和ANSI X9.62中被采纳，未来几年很可能取代DSA而成为新的数字加密标准。ECDSA是一种不带消息恢复功能的签名方案，其安全性基于计算椭圆曲线离散对数问题的困难性。
椭圆曲线的参数为（E（GF（q））, a, b, G, n, h）。其中G为选择的基点，n为G的阶，h=E（GF（q））/n。
1.密钥生成
ECDSA的密钥对生成很简单。首先，选取一个随机数d∈[1,n-1]作为私钥；然后，计算Q=dG，作为公钥。
2.签名生成
对明文m的签名算法如下：
1）选取一个随机数k，1≤k≤n-1；
2）计算kG=（x1,y1），r≡x1modn。若r=0，则转1）。
3）计算k-1modn。
4）计算e=Hash（m）。
5）计算s≡k-1（e+dr）modn。若s=0，则转1）。
签名为（m, r, s）。
3.签名验证
对一个签名（m′,r′,s′）的验证过程如下：
1）验证r′和s′是（1,n-1）间的整数。
2）计算e=Hash（ m′）。
3）计算w≡s′-1modn。
4）计算u1≡ewmodn，u2≡r′wmodn。
5）计算X=u1G+u2Q=（x1,y1）,令v≡x1modn。
如果r′=v，则接受签名，否则拒绝。