3.3.4
DSA

DSA的中文全称是“数字签名算法”，是美国政府1994年颁布的签名标准，它的应用范围远比RSA和ElGamal签名方案广泛。和其他签名算法一样，它包括密钥参数生成、签名和验证等几部分。下面对该算法进行简述。

DSA的密钥参数生成分为以下几个步骤：

• Step 1：找到一个长度为1024比特的素数 p 。
• Step 2：找到长度位160比特的 q ，使得 q 为素数且被 p -1整除。
• Step 3：找到集合 的本原元 α 。
• Step 4：随机选择整数 d ，使得0< d < q 。计算 β = α ^d mod p 。

上述过程中，{ p , q , α , β }为公钥， d 为私钥。

Bob签名的计算过程如下：

• Step 1：随机选择整数0< t < q 。
• Step 2：计算： r =( α ^t mod p ) mod q 以及 s =[SHA( x )+ dr ]× t ^-1 ) mod q 。

这里SHA( x )表示进行SHA-1计算，输出的是160比特的摘要信息；上述过程中，{ r , s }即为签名信息。

Alice验证的计算过程如下：

• Step 1：计算 w = s ^-1 mod q 。
• Step 2：计算 u ₁ = w ×SHA( x ) mod q ，以及 u ₂ = w × r mod q 。
• Step 3：计算 v =( α ^{u ₁} × β ^{u ₂} mod p ) mod q 。
• Step 4：进行验证，如果 v = r mod q ，则通过，否则不通过。

上述计算过程看似复杂，实际上和ElGamal加密算法的数学过程相似，其核心是Bob所选择的随机整数 t ，以及Alice所计算的辅助变量 u ₁ 和 u ₂ 满足如下关系：

t = u ₁ + du ₂ mod q 。

所以验证函数就是验证 v 和 r 是否模相等。当ElGamal签名方案选取参数 p 的长度为1024时，其签名长度也为1024。通过一些对算法的改变，DSA算法的签名长度减少为320比特。出于算法安全性的考虑，除 p 为1024比特长度外，还可以选择 p 长度为2048或3072，分别给出长度为448或512比特的签名。 RKlY0Uy3kt/LjxT5sKatUSucrmtkw8EUwe+Zq6taiD2pI+ty+c0Rhq7UoWYfLZOP