數(shù)字簽名算法（Digital?Signature?Algorithm，DSA）是用于驗證信息身份的非對稱加密算法，并保證信息的完整性（未被篡改），其基本流程如下：

（1）發(fā)送方生成消息摘要M1。

（2）發(fā)送方使用DSA和私鑰Pk加密M1，生成簽名S。

（3）接收方根據(jù)消息，生成摘要M2。

（4）接收方使用DSA、S、M2和公鑰Hk，驗證S的合法性。

最后的輸出是S合法與否。

1??算法描述

DSA算法使用一個私鑰x、一個公鑰y、一個一次秘密數(shù)k、一組參數(shù)和一個摘要函數(shù)計算簽名。參數(shù)包括：

（1）p：大素數(shù)模，長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、秘密數(shù)k為小于q的隨機正整數(shù)，公鑰y為g^x?mod?p。參數(shù)L、N有幾個固定的取值，包括L=1024，N=160、L=2048，N=224、L=2048，N=256、L=3072，N=256。

簽名生成如下所述：

（1）生成r，有

（2）生成N位消息摘要z（將其視為一個N位整數(shù)）。

（3）得出數(shù)s，有

注意k^(-1)是GF(p)上k的模q逆元，最后的簽名是有序?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。設(shè)L為8，N為6，p為227，q為113，g為13。設(shè)消息摘要z為34，隨機數(shù)k為7，有k^(-1)為97，隨機數(shù)私鑰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，簽名有效。