數位簽章演算法

數字簽名算法（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$ 求得。