数字签名算法

此條目可参照英語維基百科相應條目来扩充。 若您熟悉来源语言和主题，请协助参考外语维基百科扩充条目。请勿直接提交机械翻译，也不要翻译不可靠、低品质内容。依版权协议，译文需在编辑摘要注明来源，或于讨论页顶部标记{{Translated page}}标签。

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

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

DSA的椭圆曲线密码学版本是ECDSA。

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