数字签名算法（Digital Signature Algorithm，DSA）是用于验证信息身份的非对称加密算法，并保证信息的完整性（未被篡改），其基本流程如下：

（1）发送方生成消息摘要M1。

（2）发送方使用DSA和私钥Pk加密M1，生成签名S。

（3）接收方根据消息，生成摘要M2。

（4）接收方使用DSA、S、M2和公钥Hk，验证S的合法性。

最后的输出是S合法与否。

1  算法描述

DSA算法使用一个私钥x、一个公钥y、一个一次秘密数k、一组参数和一个摘要函数计算签名。参数包括：

（1）p：大素数模，长L位，即2^(L-1)<p<2^L。

（2）q：（p-1）的素因子，长N位，即2^(N-1)<q<2^N。

（3）g：GF（p）上乘法群的q阶子群的生成元，有1<g<p。

定义私钥x、秘密数k为小于q的随机正整数，公钥y为g^x mod p。参数L、N有几个固定的取值，包括L=1024，N=160、L=2048，N=224、L=2048，N=256、L=3072，N=256。

签名生成如下所述：

（1）生成r，有

（2）生成N位消息摘要z（将其视为一个N位整数）。

（3）得出数s，有

注意k^(-1)是GF(p)上k的模q逆元，最后的签名是有序对(r, s)。

 

拿到签名（r`, s`）后，签名验证如下所述：

（1）首先验证是否有0<r`<q、0<s`<q，如否则签名肯定不正确。

（2）计算w，有

（3）计算消息摘要z`。

（4）计算u1、u2，有

（5）计算v，有

如v=r`，则签名合法。

2  举例分析

为了简化例子，这里用了很小的L、N。设L为8，N为6，p为227，q为113，g为13。设消息摘要z为34，随机数k为7，有k^(-1)为97，随机数私钥x为19，有：

y=13**19 % 227=22

r=(13 ** 7) % 227 % 113=42

s=(97*(34+19*42))%113=22

 

(r,s) = (r`,s`)=(42,22)

 

s`^(-1)=36

w=36

z`=34

u1=(34*36)%113=94

u2=(42*36)%113=43

v=((((13)**94) * (22**43)) % 227)%113=42

有v=r，签名有效。