数字签名算法

数字签名算法（DSA）是用于数字签名的联邦信息处理标准之一，基于模算数和离散对数的复杂度。DSA是Schnorr和ElGamal签名方案的变体。

美国国家标准技术研究所（NIST）于1991年提出将DSA用于其数字签名标准（DSS），并于1994年将其作为FIPS 186采用。[2]已对初始规范进行了四次修订。DSA已获得专利，但NIST已将此专利在全球范围内买断式授权。

概述

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

操作

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

密钥生成

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

参数选择

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

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

用户密钥

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

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

其中 $x$ 是私钥、 $y$ 是公钥。

密钥分发

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

签名流程

消息 $m$ 签名流程如下：

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

签名为 $(r,s)$ 组合

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