ElGamal、Schnorr、DSA 签名方案对比分析

实验目的

深入理解基于离散对数问题（DLP）的非对称数字签名核心原理，掌握ElGamal、Schnorr、DSA三种经典签名方案的数学模型；
从计算量、通信开销、安全性、实用性等维度对比分析三种签名方案的优劣；
编程实现三种签名方案的签名生成与验证功能，通过实验数据验证理论分析结果；
掌握密码学算法实现中的核心技术（大素数生成、模逆计算、哈希函数应用），提升密码学工程实践能力。

实验原理

核心数学基础

三种签名方案均基于离散对数问题（DLP） 的难解性：给定大素数$p$、原根$g$和$y = g^x \mod p$，求解$x$在计算上不可行。核心操作包括：

模幂运算：$a^b \mod m$，是签名生成/验证的核心计算；
模逆运算：求解$a^{-1} \mod m$（扩展欧几里得算法）；
素性检测：米勒-拉宾算法生成安全的大素数。

三种签名方案核心逻辑

方案	签名生成核心步骤	验证核心步骤
ElGamal	1. 随机数$k$满足$\gcd(k,p-1)=1$ 2. $r = g^k \mod p$ 3. $s = (h - xr)k^{-1} \mod (p-1)$	验证$g^h \equiv y^r \cdot r^s \mod p$
Schnorr	1. 随机数$k$，计算$r = g^k \mod p$ 2. $e = H(r\	m) \mod q$ 3. $s = (k - xe) \mod q$	计算$r’ = g^s \cdot y^e \mod p$，验证$e = H(r’\	m) \mod q$
DSA	1. 随机数$k$满足$\gcd(k,q)=1$ 2. $r = (g^k \mod p) \mod q$ 3. $s = k^{-1}(h + xr) \mod q$	计算$w = s^{-1} \mod q$，$u_1 = hw \mod q$，$u_2 = rw \mod q$，验证$(g^{u_1}y^{u_2} \mod p) \mod q = r$

理论维度对比

对比维度	ElGamal	Schnorr	DSA
计算量	签名：2次模幂+1次模乘验证：3次模幂+1次模乘	签名：1次模幂+2次模乘验证：2次模幂+1次模乘	签名：1次模幂+2次模乘+1次哈希验证：2次模幂+2次模乘+1次哈希
通信开销	签名长度=2×模数长度（如256位模数→512位签名）	签名长度=模数长度+哈希长度	签名长度=2×160位（固定长度，与模数无关）
安全性	依赖DLP，随机数$k$泄露则私钥泄露	依赖DLP，抗伪造性优于ElGamal，交互性强	依赖ELP/DLP，NIST标准，抗碰撞性强
实用性	理论价值高，实际应用少（签名过长）	轻量级，适合物联网/区块链	工业标准，适合金融/政务场景

实验环境

硬件环境

CPU：Intel Core i5-13500H @ 2.60GHz
内存：16GB DDR4
硬盘：512GB SSD

软件环境

操作系统：Windows 11 64位
编程语言：Python 3.12.4
开发工具：VsCode 1.107.0
依赖库：Python内置random（通过secrets模块使用）、hashlib、math、time库（无额外依赖）

实验步骤

实验参数设置

为了保证对比的公平性，实验采用了符合密码学标准的参数配置（模拟 RFC 5114 标准）：

模数 $P$ (Prime Modulus)：1024-bit (所有算法共用，定义了运算的有限域大小)。
子群阶 $Q$ (Subgroup Order)：160-bit (仅 DSA 和 Schnorr 使用，ElGamal 使用 $P-1$)。
生成元 $G$：
- 对于 ElGamal：使用全群生成元。
- 对于 DSA/Schnorr：使用阶为 $Q$ 的子群生成元（满足 $G^Q \equiv 1 \bmod P$）。
测试样本：对同一消息进行 100 次循环测试，取平均时间以消除系统抖动影响。

算法实现步骤

ElGamal 签名方案实现

密钥生成：
- 选择私钥 $x \in [1, P-2]$
- 计算公钥 $y = G^x \bmod P$
签名生成：
- 生成随机数 $k$，满足 $\gcd(k, P-1) = 1$
- 计算 $r = G^k \bmod P$
- 计算消息哈希 $h = H(m)$
- 计算 $s = k^{-1}(h - xr) \bmod (P-1)$
- 签名为 $(r, s)$
签名验证：
- 验证 $0 < r < P$ 和 $0 < s < P-1$
- 计算 $v_1 = G^h \bmod P$
- 计算 $v_2 = y^r \cdot r^s \bmod P$
- 若 $v_1 = v_2$，则签名有效

DSA 签名方案实现

密钥生成：
- 选择私钥 $x \in [1, Q-1]$
- 计算公钥 $y = G^x \bmod P$
签名生成：
- 生成随机数 $k \in [1, Q-1]$
- 计算 $r = (G^k \bmod P) \bmod Q$
- 若 $r = 0$，重新选择 $k$
- 计算 $s = k^{-1}(H(m) + xr) \bmod Q$
- 若 $s = 0$，重新选择 $k$
- 签名为 $(r, s)$
签名验证：
- 验证 $0 < r < Q$ 和 $0 < s < Q$
- 计算 $w = s^{-1} \bmod Q$
- 计算 $u_1 = H(m) \cdot w \bmod Q$
- 计算 $u_2 = r \cdot w \bmod Q$
- 计算 $v = ((G^{u_1} \cdot y^{u_2}) \bmod P) \bmod Q$
- 若 $v = r$，则签名有效

Schnorr 签名方案实现

密钥生成：
- 选择私钥 $x \in [1, Q-1]$
- 计算公钥 $y = G^x \bmod P$
签名生成：
- 生成随机数 $k \in [1, Q-1]$
- 计算 $R = G^k \bmod P$
- 计算 $e = H(R | m) \bmod Q$
- 计算 $s = (k - xe) \bmod Q$
- 签名为 $(e, s)$
签名验证：
- 验证 $0 < s < Q$
- 计算 $R’ = G^s \cdot y^e \bmod P$
- 计算 $e’ = H(R’ | m) \bmod Q$
- 若 $e = e’$，则签名有效

性能测试步骤

分别对三种签名方案执行100次测试
测量并记录各阶段的执行时间：
- 密钥生成时间
- 签名生成时间
- 签名验证时间
统计签名长度
验证签名正确性

数据收集与分析

收集每种方案在各阶段的平均执行时间
比较不同方案的签名长度
分析计算复杂度和通信开销
验证实验结果与理论分析的一致性

实验结果展示

根据代码运行结果，三种签名方案的性能数据如下表所示：

性能指标 (平均值)	ElGamal	DSA	Schnorr
密钥生成 (KeyGen)	3.2736 ms	0.5033 ms	0.5661 ms
签名生成 (Sign)	3.6480 ms	0.5667 ms	0.5739 ms
签名验证 (Verify)	7.1386 ms	1.3576 ms	0.9754 ms
签名长度 (Size)	~2045 bits	~318 bits	~317 bits
验证结果	Pass	Pass	Pass

(注：ElGamal 签名长度约为 2048 bits，实验值 2045 bits 为数据统计时的轻微浮动，属正常现象)

实验结果分析

计算开销分析 (Computational Cost)

ElGamal 效率最低：
- 现象：ElGamal 的各项耗时均大幅高于 DSA 和 Schnorr（慢约 6-7 倍）。
- 原因：ElGamal 的指数运算是在模 $P$（1024-bit）上进行的，指数本身也是 1024-bit 量级；而 DSA 和 Schnorr 虽然底数和模数也是 1024-bit，但利用了子群特性，其指数运算的指数仅为 160-bit ($Q$ 的大小)。根据模幂运算复杂度 $O(\log(\text{exponent}))$，计算量呈线性倍数下降。
Schnorr 验证速度最快 (Highlight)：
- 现象：在签名生成阶段，DSA (0.57ms) 与 Schnorr (0.57ms) 几乎持平；但在验证阶段，Schnorr (0.98ms) 明显快于 DSA (1.36ms)，速度提升约 28%。
- 原因：
  - DSA 验证需要先计算模逆元 $w = s^{-1} \bmod q$，然后计算两个指数幂 $u1, u2$。
  - Schnorr 验证直接计算 $R’ = g^s y^e \bmod p$，虽然同样是双指数运算，但省去了模逆元计算步骤，且结构更适合线性优化。这验证了 Schnorr 在验证效率上的理论优势。

通信开销分析 (Communication Overhead)

ElGamal 空间利用率低：
- 签名由 $(r, s)$ 组成，两者均在 $[1, P-1]$ 范围内。对于 1024-bit 的 $P$，签名总长约 $1024 \times 2 = 2048$ bits。这导致了极大的带宽浪费。
DSA 与 Schnorr 极其紧凑：
- 两者均利用子群阶 $Q$ (160-bit) 限制签名数值大小。
- DSA 签名 $(r, s)$ 均为 160-bit 整数，总长约 320 bits。
- Schnorr 签名 $(e, s)$ 中 $s$ 为 160-bit，$e$ 为哈希值（通常截断或取模后也适配群阶），总长同样约 320 bits。
- 结论：在存储和传输效率上，DSA 和 Schnorr 优于 ElGamal 一个数量级。

实验中遇到的问题与解决 (Troubleshooting)

在实验初期，DSA 和 Schnorr 方案出现了 “Verification Failed” 的情况。

问题定位：最初使用的生成元 $G$ 是全群 $Z_p^*$ 的生成元，其阶为 $P-1$。而 DSA/Schnorr 算法数学上要求 $G$ 必须位于阶为 $Q$ 的子群中。
解决方案：通过公式 $G = h^{(P-1)/Q} \bmod P$ 重新计算了生成元，并增加了断言 assert pow(G, Q, P) == 1。
启示：这一过程深刻体现了群参数选取在公钥密码体制中的决定性作用，错误的群参数会导致算法在数学逻辑上崩塌。

实验结论

本实验通过编程实测，验证了数字签名领域的以下理论观点：

子群技术的必要性：DSA 和 Schnorr 通过引入小素数阶子群，在不降低安全强度（基于离散对数困难性）的前提下，将计算速度和通信效率提升了数倍。
ElGamal 的历史局限性：由于其巨大的签名长度和低下的验证效率，ElGamal 签名已不再适合现代网络应用。
Schnorr 的优越性：
- 实验数据显示，Schnorr 是综合性能最优的方案。它保持了与 DSA 同级的通信开销，但在验证速度上更快。
- 结合理论知识，Schnorr 还具有可证明安全性（在随机预言机模型下）和线性特性（支持多重签名聚合），这解释了为什么比特币（Taproot升级）和许多现代隐私币转向使用 Schnorr 签名体系。

附录：实验代码

import secrets
import hashlib
import time
from math import gcd

# ==================== 数学工具函数 ====================

def extended_gcd(a, b):
    if a == 0:
        return b, 0, 1
    else:
        g, y, x = extended_gcd(b % a, a)
        return g, x - (b // a) * y, y

def modinv(a, m):
    g, x, y = extended_gcd(a, m)
    if g != 1:
        raise Exception('Modular inverse does not exist')
    else:
        return x % m

def fast_pow(base, power, mod):
    return pow(base, power, mod)

def sha256_int(message_bytes):
    h = hashlib.sha256(message_bytes).hexdigest()
    return int(h, 16)

# ==================== 参数设置 ====================

p_hex = "B10B8F96A080E01DDE92DE5EAE5D54EC52C99FBCFB06A3C69A6A9DCA52D23B616073E28675A23D189838EF1E2EE652C013ECB4AEA906112324975C3CD49B83BFACCBDD7D90C4BD7098488E9C219A73724EFFD6FAE5644738FAA31A4FF55BCCC0A151AF5F0DC8B4BD45BF37DF365C1A65E68CFDA76D4DA708DF1FB2BC2E4A4371"
q_hex = "F518AA8781A8DF278ABA4E7D64B7CB9D49462353"

P = int(p_hex, 16)
Q = int(q_hex, 16)

h = 2 
exponent = (P - 1) // Q
G = pow(h, exponent, P)

# 验证 G 的阶是否正确 (实验中应当输出 1)
assert pow(G, Q, P) == 1, "G 的阶不是 Q，参数生成错误！"
print(f"Parameter Check: G^Q mod P == {pow(G, Q, P)} (Correct)")

# 消息
TEST_MSG = b"Hello, comparative analysis of crypto signatures!"
# ==================== 1. ElGamal 实现 ====================
class ElGamal:
    def keygen(self):
        # ElGamal 原生通常使用生成元 g 覆盖整个 Zp*，这里为对比方便沿用参数，但注意私钥范围
        # 严格的ElGamal私钥 x 在 [1, P-2]
        x = secrets.randbelow(P - 2) + 1
        y = fast_pow(G, x, P)
        return x, y

    def sign(self, x, message):
        h_m = sha256_int(message)
        while True:
            # 随机数 k 必须与 P-1 互质
            k = secrets.randbelow(P - 2) + 1
            if gcd(k, P - 1) == 1:
                break
        r = fast_pow(G, k, P)
        # s = k^(-1) * (H(m) - x*r) mod (P-1)
        k_inv = modinv(k, P - 1)
        s = (k_inv * (h_m - x * r)) % (P - 1)
        return r, s

    def verify(self, y, message, r, s):
        if not (0 < r < P and 0 < s < P - 1): return False
        h_m = sha256_int(message)
        # v1 = g^H(m)
        v1 = fast_pow(G, h_m, P)
        # v2 = y^r * r^s
        v2 = (fast_pow(y, r, P) * fast_pow(r, s, P)) % P
        return v1 == v2

# ==================== 2. DSA 实现 ====================
class DSA:
    def keygen(self):
        # x 在 [1, Q-1]
        x = secrets.randbelow(Q - 1) + 1
        y = fast_pow(G, x, P)
        return x, y

    def sign(self, x, message):
        h_m = sha256_int(message)
        while True:
            k = secrets.randbelow(Q - 1) + 1
            r = fast_pow(G, k, P) % Q
            if r == 0: continue
            k_inv = modinv(k, Q)
            s = (k_inv * (h_m + x * r)) % Q
            if s != 0: break
        return r, s

    def verify(self, y, message, r, s):
        if not (0 < r < Q and 0 < s < Q): return False
        h_m = sha256_int(message)
        w = modinv(s, Q)
        u1 = (h_m * w) % Q
        u2 = (r * w) % Q
        v = (fast_pow(G, u1, P) * fast_pow(y, u2, P)) % P % Q
        return v == r

# ==================== 3. Schnorr 实现 ====================
class Schnorr:
    def keygen(self):
        x = secrets.randbelow(Q - 1) + 1
        y = fast_pow(G, x, P)
        return x, y

    def sign(self, x, message):
        # 1. 选择随机数 k
        k = secrets.randbelow(Q - 1) + 1
        # 2. 计算 R = g^k mod p
        R = fast_pow(G, k, P)
        # 3. 计算 e = Hash(R || m)
        # 这里为了简化，将 R 转换为字节串连接
        R_bytes = R.to_bytes((P.bit_length() + 7) // 8, 'big')
        e_val = sha256_int(R_bytes + message) % Q
        # 4. 计算 s = k - x*e mod q (有些变种是 k + x*e，验证对应调整)
        s = (k - x * e_val) % Q
        return e_val, s

    def verify(self, y, message, e, s):
        if not (0 < s < Q): return False
        # R_prime = g^s * y^e mod p
        term1 = fast_pow(G, s, P)
        term2 = fast_pow(y, e, P)
        R_prime = (term1 * term2) % P
        
        R_bytes = R_prime.to_bytes((P.bit_length() + 7) // 8, 'big')
        e_prime = sha256_int(R_bytes + message) % Q
        return e_prime == e

# ==================== 性能测试台 ====================
def benchmark(scheme, name, rounds=100):
    print(f"--- Testing {name} ({rounds} rounds) ---")
    
    # KeyGen
    start = time.time()
    for _ in range(rounds):
        sk, pk = scheme.keygen()
    print(f"KeyGen Avg Time: {(time.time() - start)/rounds * 1000:.4f} ms")
    
    # Sign
    sk, pk = scheme.keygen()
    start = time.time()
    for _ in range(rounds):
        sig = scheme.sign(sk, TEST_MSG)
    print(f"Sign   Avg Time: {(time.time() - start)/rounds * 1000:.4f} ms")
    
    # Verify
    sig = scheme.sign(sk, TEST_MSG)
    start = time.time()
    for _ in range(rounds):
        res = scheme.verify(pk, TEST_MSG, *sig)
        if not res: print("Verification Failed!")
    print(f"Verify Avg Time: {(time.time() - start)/rounds * 1000:.4f} ms")
    
    # Size check
    sig_size = 0
    for comp in sig:
        sig_size += comp.bit_length()
    print(f"Signature Size : ~{sig_size} bits\n")

if __name__ == "__main__":
    benchmark(ElGamal(), "ElGamal")
    benchmark(DSA(), "DSA")
    benchmark(Schnorr(), "Schnorr")