数字签名算法

DSA算法工作在框架公钥加密、模算数和离散对数问题，这被认为是难解问题。该算法使用由公钥和私钥组成的密钥对。私钥用于生成消息的数字签名，并且可以通过使用签名者的相应公钥来验证这种签名。数字签名提供信息鉴定（接收者可以验证消息的来源），完整性（接收方可以验证消息自签名以来未被修改）和不可否认性（发送方不能错误地声称它们没有签署消息）。

DSA 算法包含了四种操作：密钥生成、密钥分发、签名、验证

密钥生成

密钥生成包含两个阶段。第一阶段是算法参数的选择，可以在系统的不同用户之间共享，而第二阶段则为每个用户计算独立的密钥组合。

参数选择

• 选择经核可的 密码散列函数 ${\displaystyle H}$ ，在原版的 DSS（Digital Signature Standard）中，${\displaystyle H}$  总是使用 SHA-1，而目前的 DSS 已核可更为安全的 SHA-2 作为散列函数。^[1][2] 假如长度 ${\displaystyle |H|}$  大于模数长度 ${\displaystyle N}$ ，则散列函数的输出只有最左边的 ${\displaystyle N}$  比特会被使用。
• 选择密钥长度 ${\displaystyle L}$ ，原版的 DSS 限制 ${\displaystyle L}$  必须为 512 到 1024 之间 64 的倍数，NIST 800-57 建议使用长度为 2048 的密钥。^[3]
• 选择模数长度 ${\displaystyle N}$  使得 ${\displaystyle N<L}$  且 ${\displaystyle N\leq |H|}$ ，FIPS 186-4 规定 ${\displaystyle (L,N)}$  必须为 (1024, 160)、(2048, 224)、(2048, 256) 或 (3072, 256) 其中一种。^[1]
• 选择长度为 ${\displaystyle N}$  比特的质数 ${\displaystyle q}$ 。
• 选择长度为 ${\displaystyle L}$  比特的质数 ${\displaystyle p}$  使得 ${\displaystyle p-1}$  为 ${\displaystyle q}$  的倍数。
• 从 ${\displaystyle \{2\ldots p-2\}}$  随机选择 ${\displaystyle h}$ 。
• 计算 ${\displaystyle g:=h^{(p-1)/q}\mod p}$ ，当 ${\displaystyle g=1}$  时需要重新产生不同的 ${\displaystyle h}$ ，通常会使用 ${\displaystyle h=2}$ ，即使数值很大时仍然可以非常有效率的计算这个 模幂。

算法参数为 (${\displaystyle p}$ , ${\displaystyle q}$ , ${\displaystyle g}$ )，可被不同的用户共享。

用户密钥

给定一套算法参数后，第二阶段会为每位用户计算独立密钥组合：

• 从 ${\displaystyle \{1\ldots q-1\}}$  选择随机整数 ${\displaystyle x}$ 
• 计算 ${\displaystyle y:=g^{x}\mod p}$ 

其中 ${\displaystyle x}$  是私钥、${\displaystyle y}$  是公钥。

密钥分发

签名者需要透过可信任的管道发布公钥 ${\displaystyle y}$ ，并且安全地保护 ${\displaystyle x}$  不被其他人知道。

签名流程

消息 ${\displaystyle m}$  签名流程如下：

• 从 ${\displaystyle \{1\ldots q-1\}}$  随机选择整数 ${\displaystyle k}$ 
• 计算 ${\displaystyle r:=\left(g^{k}{\bmod {\,}}p\right){\bmod {\,}}q}$ ，当出现 ${\displaystyle r=0}$  状况时重新选择随机数 ${\displaystyle k}$ 
• 计算 ${\displaystyle s:=\left(k^{-1}\left(H(m)+xr\right)\right){\bmod {\,}}q}$ ，当出现 ${\displaystyle s=0}$  状况时重新选择随机数 ${\displaystyle k}$ 

签名为 ${\displaystyle (r,s)}$  组合

计算 ${\displaystyle k}$  和 ${\displaystyle r}$  旨在为不同消息创建独立的密钥，计算 ${\displaystyle r}$  的 模幂 是这个算法中最耗资源的部分，但这可在不知道消息的前提下进行计算。 第二耗运算资源的部分是计算 ${\displaystyle k^{-1}{\bmod {\,}}q}$  模反元素，同样也能在不知道消息的前提下进行计算，这可以用 扩展欧几里得算法 或 费马小定理 ${\displaystyle k^{q-2}{\bmod {\,}}q}$  求得。

验证签名

透过以下步骤可以验证 ${\displaystyle \left(r,s\right)}$  是消息 ${\displaystyle m}$  的有效签名：

• 验证 ${\displaystyle 0<r<q}$  且 ${\displaystyle 0<s<q}$ 
• 计算 ${\displaystyle w:=s^{-1}{\bmod {\,}}q}$ 
• 计算 ${\displaystyle u_{1}:=H(m)\cdot w\,{\bmod {\,}}q}$ 
• 计算 ${\displaystyle u_{2}:=r\cdot w\,{\bmod {\,}}q}$ 
• 计算 ${\displaystyle v:=\left(g^{u_{1}}y^{u_{2}}{\bmod {\,}}p\right){\bmod {\,}}q}$ 

只有在 ${\displaystyle v=r}$  时代表签名是有效的

下列密码学库有提供 DSA 的支持：

• OpenSSL
• GnuTLS
• wolfCrypt
• Crypto++
• cryptlib（英语：cryptlib）
• Botan（英语：Botan (programming library)）
• Bouncy Castle（英语：Bouncy Castle (cryptography)）
• libgcrypt（英语：libgcrypt）
• Nettle（英语：Nettle (cryptographic library)）

• 模运算
• RSA
• ECDSA