数字签名算法

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

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

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

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

操作
DSA 演算法包含了四種操作：金鑰生成、金鑰分發、簽章、驗證

金鑰生成
金鑰生成包含兩個階段。第一階段是演算法參數的選擇，可以在系統的不同使用者之間共享，而第二階段則為每個使用者計算獨立的金鑰組合。

參數選擇
 選擇經核可的 密碼雜湊函式 ，在原版的 DSS（Digital Signature Standard）中， 總是使用 SHA-1，而目前的 DSS 已核可更為安全的 SHA-2 作為雜湊函式。 假如長度  大於模數長度 ，則雜湊函式的輸出只有最左邊的  位元會被使用。
 選擇金鑰長度 ，原版的 DSS 限制  必須為 512 到 1024 之間 64 的倍數，NIST 800-57 建議使用長度為 2048 的金鑰。
 選擇模數長度  使得  且 ，FIPS 186-4 規定  必須為 (1024, 160)、(2048, 224)、(2048, 256) 或 (3072, 256) 其中一種。
 選擇長度為  位元的質數 。
 選擇長度為  位元的質數  使得  為  的倍數。
 從  隨機選擇 。
 計算 ，當  時需要重新產生不同的 ，通常會使用 ，即使數值很大時仍然可以非常有效率的計算這個 模幂。
演算法參數為 (, , )，可被不同的使用者共享。

使用者金鑰
給定一套演算法參數後，第二階段會為每位使用者計算獨立金鑰組合：
 從  選擇隨機整數 
 計算 
其中  是私鑰、 是公鑰。

金鑰分發
簽章者需要透過可信任的管道發佈公鑰 ，並且安全地保護  不被其他人知道。

簽章流程
訊息  簽名流程如下：
 從  隨機選擇整數 
 計算 ，當出現  狀況時重新選擇隨機數 
 計算 ，當出現  狀況時重新選擇隨機數 
簽章為  組合

計算  和  旨在為不同訊息建立獨立的金鑰，計算  的模幂是這個演算法中最耗資源的部分，但這可在不知道訊息的前提下進行計算。
第二耗運算資源的部分是計算  模反元素，同樣也能在不知道訊息的前提下進行計算，這可以用擴展歐幾里得演算法或費馬小定理  求得。

驗證簽章
透過以下步驟可以驗證  是訊息  的有效簽章：
 驗證  且 
 計算 
 計算 
 計算 
 計算 
只有在  時代表簽章是有效的

實作
下列密碼學函式庫有提供 DSA 的支援：
 OpenSSL
 GnuTLS
 wolfCrypt
 Crypto++

相關條目
 模運算
 RSA
 ECDSA

參考文獻

1991年面世
数字签名方案