密碼學 - DSA
數位簽章演算法（Digital Signature Algorithm, DSA）是廣泛應用的非對稱金鑰加密技術，主要用於資料的數位簽章，確保訊息的完整性、來源的真實性以及不可否認性。
本文將探討 DSA 的歷史、運作原理、優缺點、相關變形，並提供一個 Python 實作範例。
歷史背景
DSA 於 1991 年由美國國家標準暨技術研究院（NIST）發布，成為美國的聯邦資訊處理標準（FIPS）之一。 目前最新的版本為 2013 年發布的 FIPS 186-4。 此演算法是 Taher A. Elgamal 於 1984 年提出的 ElGamal 簽章方案的一種變形。
DSA 運作原理
DSA 的運作包含簽章與驗章兩個核心流程，其安全性基於在有限體中計算離散對數的困難度。
簽章流程
在生成金鑰之前，系統需要先定義一組所有使用者共享的公共參數 $(p,q,g)$：
- 選擇一個大質數 $q$，其位元長度需與雜湊函數的輸出長度相符。
- 選擇一個質數 $p$，滿足 $(p−1)$ 是 q 的倍數。$p$ 的位元長度決定了金鑰的強度 (例如：2048 位元)。
- 選擇一個產生器 $g$，其計算方式為 $g \equiv h^{(p-1)/q} \pmod{p}$，其中 $h$ 是一個隨機選擇的整數，且 $1 < h < p-1$。
這組參數 $(p,q,g)$ 是公開的，可以由一個受信任的機構產生並發布。
金鑰生成：
首先，使用者擁有一組金鑰對 $(x,Y)$，其中 $x$ 是私鑰，而公鑰 $Y$ 的計算方式為：
$$
\begin{aligned}
Y=g^{x}\pmod{p}
\end{aligned}
$$接著，為每筆簽章產生一組臨時金鑰對 $(k,R)$，其中 $k$ 為臨時私鑰，$R$ 的計算方式為：
$$
\begin{aligned}
R=g^{k}\pmod{p}
\end{aligned}
$$
雜湊計算：將要簽署的訊息（message）透過雜湊函數（hash function）運算，得到雜湊值 $H$
$$
\begin{aligned}
H \equiv \text{hash}(message) \pmod{q}
\end{aligned}
$$簽章計算：計算簽章值 $(r,s)$：
$$
\begin{aligned}
r &\equiv R \pmod{q} \\
s &\equiv (H + x \cdot r) \cdot k^{-1} \pmod{q}
\end{aligned}
$$其中 $k^{-1}$ 是 $k$ 在模 $q$ 下的乘法逆元。
輸出：最終輸出的數位簽章即為 $(r,s)$。
驗章流程
參數準備：
- 計算：
$$
\begin{aligned}
w &\equiv s^{-1} \pmod{q}
\end{aligned}
$$- 同樣對接收到的訊息進行雜湊運算，得到雜湊值 H。
中間值計算：
$$
\begin{aligned}
u_1 &\equiv H \cdot w \pmod{q}\\
u_2 &\equiv r \cdot w \pmod{q}
\end{aligned}
$$
計算驗證值 $V$：
使用收到的公鑰 $Y$ 和公共參數 $(p,q,g)$，計算出驗證值 $V$。$$
\begin{aligned}
V \equiv ((g^{u_1} \cdot Y^{u_2}) \pmod{p}) \pmod{q}\
\end{aligned}
$$$$
\begin{aligned}
V \stackrel{?}{=} r
\end{aligned}
$$
Python 實作範例
在現代程式設計中，我們強烈建議不要從頭手動實現底層的數學運算，因為這很容易出錯並產生安全漏洞。我們應該使用經過專家審核且廣泛使用的密碼學函式庫。在 Python 中，cryptography 是一個很好的選擇。
以下範例展示了如何使用 cryptography 函式庫來生成 DSA 金鑰、簽署訊息以及驗證簽章。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56from cryptography.hazmat.primitives import hashes
from cryptography.hazmat.primitives.asymmetric import dsa
from cryptography.exceptions import InvalidSignature
# --- 1. 生成 DSA 金鑰 ---
# 生成一個新的 DSA 私鑰。公鑰是私鑰的一部分。
# key_size=2048 是指質數 p 的位元長度，這是建議的最小安全長度。
private_key = dsa.generate_private_key(
key_size=2048,
)
public_key = private_key.public_key()
print("金鑰生成完畢。")
# --- 2. 準備要簽署的資料 ---
# 在真實世界中，這可能是任何你需要保護的資料，例如一份合約文件或一筆交易紀錄。
message = "這是一份需要進行數位簽章的重要文件。".encode('utf-8')
print(f"原始訊息: {message.decode('utf-8')}")
# --- 3. 使用私鑰進行簽章 ---
# 簽章過程會先對訊息進行雜湊運算 (這裡使用 SHA-256)，然後用私鑰加密雜湊值。
# 只有擁有私鑰的人才能產生有效的簽章。
signature = private_key.sign(
message,
hashes.SHA256()
)
print(f"n產生的數位簽章 (前 32 bytes): {signature[:32].hex()}...")
# --- 4. 使用公鑰進行驗章 ---
# 任何人只要有公鑰和原始訊息，都可以驗證簽章的真偽。
# 驗證過程會用公鑰解開簽章，並與訊息的雜湊值進行比對。
try:
public_key.verify(
signature,
message,
hashes.SHA256()
)
print("n[成功] 簽章驗證成功！訊息未被竄改，且來源可信。")
except InvalidSignature:
print("n[失敗] 簽章驗證失敗！訊息可能已被竄改或簽章無效。")
# --- 5. 模擬驗章失敗的情境 ---
# 讓我們試著竄改訊息，看看驗證結果會如何。
tampered_message = "這是一份被偷偷竄改過的文件。".encode('utf-8')
print(f"n竄改後的訊息: {tampered_message.decode('utf-8')}")
try:
public_key.verify(
signature, # 使用原始的簽章
tampered_message, # 但比對的是竄改後的訊息
hashes.SHA256()
)
print("n[成功] 簽章驗證成功！")
except InvalidSignature:
print("n[失敗] 簽章驗證失敗！公鑰無法驗證此簽章與竄改後訊息的配對。")
橢圓曲線數位簽章演算法（ECDSA）
ECDSA 是 DSA 利用橢圓曲線密碼學（ECC）的變體，其簽章與驗章流程與傳統 DSA 相似，但運算是在橢圓曲線的點上進行，能在提供相同安全等級的情況下，使用更短的金鑰，因此在資源受限的環境（如智慧卡、物聯網裝置）中特別受歡迎。
優缺點與安全性
優點：
- 金鑰短：相較於 RSA，DSA 在達到相同安全等級時，所需的金鑰長度較短。
- 安全性高：基於成熟的數學難題。
- 簽章速度快：產生簽章的速度通常比 RSA 快。
缺點：
- 驗章速度慢：驗證簽章的速度通常比 RSA 慢。
- 臨時金鑰 k 的風險：傳統 DSA 的安全性極度依賴臨時金鑰 k 的唯一性。
重複使用相同的 k 值會導致私鑰被輕易破解。
確定性 DSA（Deterministic DSA）
為了解決因 k 值隨機性不足而可能導致的安全漏洞，RFC 6979 提出了一種「確定性 DSA」的實現方式。它使用 HMAC 技術，根據訊息雜湊值和私鑰，以一種確定的方式生成 k 值。這不僅避免了因隨機數生成器瑕疵而導致的漏洞，也讓簽章過程更具可靠性。現代的密碼學函式庫（包括 Python 的 cryptography）在實作 DSA 時，通常都已採用了這種確定性的方法。
參考資料
- Wikipedia - Digital Signature Algorithm
- RFC 6979 - 確定性 DSA 的規範
- Cryptography.io - DSA - Python cryptography 函式庫的 DSA 實作說明