DSA算法：数字签名的安全之道

数字签名（Digital Signature）主要用于对数字消息进行签名，以防消息被冒名伪造或篡改，亦可以用于通信双方的身份鉴别。数字签名具有身份认证、数据完整性、不可否认性及匿名性等特点。随着计算机通信网络的迅速发展，特别是在大型网络安全通信中的密钥分配、认证及电子商务系统中，数字签名的使用越来越普遍，数字签名是防止信息欺诈行为的重要措施。

数字签名标准（Digital Signature Standard，DSS）是由美国NIST公布的联邦信息处理标准FIPS186，它是在ElGamal和Schnorr数字签名的基础上设计的。数字签名标准中的算法称为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，其中，2^511+64j＜p＜2^512+64j（j∈{0，1，…，8}）。

2）选取p-1的一个160bit的素数因子q（2¹⁵⁰＜q＜2¹⁶⁰）。

3）计算g=h^{（p−1）/q}mod p，其中1＜h＜p-1。

4）生成一个随机数x（0＜x＜q）。

5）计算y=g^xmod p。

公钥为（p，q，g，y），私钥为x。

2.签名生成

对明文m的签名算法如下：(www.xing528.com)

1）生成一个随机数k（0＜k＜q）。

2）计算r=（g^kmod p）mod q。

3）计算s=（k⁻¹（SHA−1（m）+xr））mod p，其中，SHA−1（m）是用SHA−1算法对明文m进行Hash运算。

签名为（m，r，s）。

3.签名验证

对一个签名（m′，r′，s′）的验证过程如下：

1）计算w=（s′）⁻¹。

2）计算u₁=（SHA−1（m′）w）mod q。

3）计算u₂=（r′w）mod q。

4）计算。

5）检验v是否等于r′。

只有当上述算法中v=r′时，接收的签名才被验证。