数字签名体制学习笔记

1. 概述 (Overview)

数字签名（Digital Signature）是公钥密码学的核心原语，通过“私钥签名、公钥验证”的机制，模拟物理手写签名的法律效力，核心作用是保障消息的完整性（防篡改）、来源认证（防伪造）和不可否认性（防抵赖），是电子政务、电子商务、区块链等领域的安全基石。

1.1 基本模型

一个数字签名方案通常由三个算法组成 $(Gen, Sign, Verify)$：

1. 密钥生成 (Key Generation): $Gen(1^\lambda) \to (pk, sk)$。输入安全参数 $\lambda$，输出公钥 $pk$ 和私钥 $sk$。
2. 签名 (Signing): $Sign(sk, m) \to \sigma$。输入私钥 $sk$ 和消息 $m$，输出签名 $\sigma$。算法通常是概率性的。
3. 验证 (Verification): $Verify(pk, m, \sigma) \to {0, 1}$。输入公钥 $pk$、消息 $m$ 和签名 $\sigma$，输出 1 (有效) 或 0 (无效)。

1.2 安全性定义

最常用的安全定义是 EUF-CMA (Existential Unforgeability under Chosen Message Attack，选择消息攻击下的存在不可伪造性)。

安全游戏 (Security Game)

为什么要引入安全游戏？ 在现代密码学中，“安全”不能只靠直觉。安全游戏通过模拟攻击者 ($\mathcal{A}$) 与挑战者之间的交互，精确地量化了：

1. 攻击者的能力 (例如：可以请求任意消息的签名)。
2. 攻击者的目标 (例如：伪造一个从未见过的消息的签名)。
3. 成功的定义 (例如：验证通过且消息新颖)。

游戏流程如下：

1. Setup: 挑战者运行 $Gen(1^\lambda)$ 生成 $(pk, sk)$，将 $pk$ 发送给攻击者 $\mathcal{A}$。
2. Query: $\mathcal{A}$ 可以自适应地请求消息 $m_1, m_2, \dots, m_q$ 的签名。挑战者使用 $sk$ 计算 $\sigma_i = Sign(sk, m_i)$ 并返回给 $\mathcal{A}$。
3. Forgery: $\mathcal{A}$ 输出一对 $(m^, \sigma^)$。
4. Win Condition: $\mathcal{A}$ 赢得游戏当且仅当：
   • $Verify(pk, m^, \sigma^) = 1$ (签名有效)
   • $m^* \notin {m_1, \dots, m_q}$ (消息未被查询过)

若对任意多项式时间攻击者 $\mathcal{A}$，其赢得上述游戏的概率 $Pr[\mathcal{A} \text{ wins}]$ 是关于 $\lambda$ 的可忽略函数（即概率随 $\lambda$ 增大快速趋近于0），则称该数字签名方案是 EUF-CMA 安全的。

与 MAC 的区别

MAC（消息认证码）与数字签名均能提供完整性和来源认证，但核心差异在于“验证方式”和“不可否认性”，具体对比如下：

2. 经典数字签名方案

2.1 RSA 签名

基于大整数分解困难问题。

教科书式 RSA 签名 (Textbook RSA)

• 密钥：$N=pq$，$(e, d)$ 满足 $ed \equiv 1 \pmod{\phi(N)}$。$pk=(N, e), sk=d$。
• 签名：$\sigma = m^d \pmod N$。
• 验证：检查 $\sigma^e \equiv m \pmod N$。
• 缺陷：存在乘法同态性 ($\sigma(m_1)\sigma(m_2) = \sigma(m_1m_2)$)，易受伪造攻击。

RSA-PSS签名 (Probabilistic Signature Scheme)

为解决教科书式 RSA 缺陷，PKCS#1 v2.1（RFC 8017）定义了 RSA-PSS（Probabilistic Signature Scheme），引入随机盐值和掩码生成函数（MGF），是目前推荐的 RSA 签名标准。

• 核心改进：通过“消息哈希+随机填充”破坏同态性，使签名具有随机性（同一消息多次签名结果不同）。
• 签名流程（简化版）： ① 哈希消息：计算 $h = H(m)$（$H$ 为安全哈希函数，如 SHA-256）； ② 生成盐值：随机选择盐值 $s$（长度与哈希输出一致）； ③ 消息编码：将 $h$、$s$ 拼接后通过 MGF 生成编码 $EM$（确保 $EM < N$）； ④ 生成签名：$\sigma = EM^d \pmod{N}$。
• 验证流程（简化版）： ① 计算 $\sigma^e \pmod{N}$ 得到 $EM’$； ② 对 $EM’$ 解码，提取盐值 $s’$ 和哈希值 $h’$； ③ 计算 $h = H(m)$，对比 $h$ 与 $h’$，一致则签名有效。
• 关键特性： ① 安全性：随机预言机模型下，可紧致归约到 RSA 困难问题； ② 实用性：支持任意长度消息，抵抗所有已知攻击； ③ 兼容性：广泛支持于 TLS、SSH、数字证书等场景。

2.2 ElGamal 签名

基于有限域上的离散对数问题 (DLP)：给定有限群 $G$、生成元 $g$ 和元素 $y = g^x$，求解 $x$ 是计算困难的。DLP 家族签名方案因“密钥短、效率高”成为主流，包括 ElGamal、Schnorr、DSA/ECDSA、EdDSA 等。

• 参数：大素数 $p$，生成元 $g$。私钥 $x \in [1, p-2]$，公钥 $y = g^x \pmod p$。
• 签名：
  1. 选择随机数 $k \in [1, p-2]$，且 $\gcd(k, p-1)=1$（确保 $k$ 存在逆元）。
  2. 计算 $r = g^k \pmod p$。
  3. 计算 $s = k^{-1}(H(m) - xr) \pmod{p-1}$（$H$ 为哈希函数，$k^{-1}$ 是 $k$ 在模 $p-1$ 下的逆元）。
  4. 签名 $\sigma = (r, s)$。
• 验证：检查 $g^{H(m)} \equiv y^r r^s \pmod p$。
• 注意：随机数 $k$ 必须保密且不可重用！若 $k$ 泄露或重复使用，攻击者可通过联立方程求解私钥 $x$。

2.3 Schnorr 签名

由 Schnorr 于1989年提出，基于“强离散对数问题”（SDLP），通过 Fiat-Shamir 变换将交互式零知识证明转化为非交互式签名，以“简洁性、高效性”著称，因专利过期后被广泛应用（如 Bitcoin Taproot）。

• 参数： 系统参数：素数阶群 $G$（阶为 $q$，$q$ 为大素数），生成元 $g \in G$； 私钥：$x \in [1, q-1]$； 公钥：$y = g^x \in G$。
• 签名：
  1. 选择随机数 $k \in [1, q-1]$，计算承诺 $R = g^k \in G$。
  2. 计算挑战 $e = H(R | m)$ (将承诺与消息拼接后哈希，绑定消息与承诺)。
  3. 计算响应 $s = k + xe \pmod q$。
  4. 签名 $\sigma = (e, s)$ 或 $\sigma = (R, s)$（两种表示等价，后者更简洁）。
• 验证：$\sigma = (e, s)$，计算 $R’ = g^s y^{-e}\pmod{p}$，检查 $H(R’ | m) \stackrel{?}{=} e$。
• 优点：
  • 线性特性：支持多重签名 (Multi-sig) 和聚合签名 (Aggregate Signature)。
  • 安全性：在随机预言机模型下证明安全。
  • 应用：Bitcoin (BIP-340, Taproot)。

3. 标准化的签名体制

3.1 DSA (Digital Signature Algorithm)

NIST 标准（FIPS 186），1991年发布，是 ElGamal 签名的优化版本，核心改进是“运算在子群上进行”，减少签名长度和运算量。

参数与结构：

• $p$：大素数，要求 $2^{L-1} < p < 2^L$，$L$ 早期标准为 $512 \leq L \leq 1024$ 且为 64 的倍数（如 512, 576, …, 1024），新标准支持更大 $L$（如 2048, 3072）。
• $q$：$p-1$ 的素因子，$q$ 是 160 位（或更高，取决于 $L$）的素数。
• $g$：生成元，$g = h^{(p-1)/q} \pmod p$，其中 $h$ 是 $[2, p-2]$ 内任取的整数，需保证 $g > 1$。
• $h$：任意 $2 \leq h \leq p-2$，使 $g$ 满足阶为 $q$。
• 私钥 $x \in [1, q-1]$，公钥 $y = g^x \pmod p$。

签名流程：

1. 选随机 $k \in [1, q-1]$。
2. 计算 $r = (g^k \pmod p) \pmod q$。
3. 计算 $s = k^{-1}(H(m) + x r) \pmod q$，$H$ 为安全哈希函数（如 SHA-1/SHA-2）。
4. 签名为 $(r, s)$。

验证流程：

1. 计算 $w = s^{-1} \pmod q$。
2. 计算 $u_1 = H(m) w \pmod q$，$u_2 = r w \pmod q$。
3. 计算 $v = ((g^{u_1} y^{u_2}) \pmod p) \pmod q$。
4. 验证 $v \stackrel{?}{=} r$。

补充说明：

• $p, q, g$ 的选取保证了安全性和运算效率。
• $g$ 的生成方式确保其在模 $p$ 的阶为 $q$ 的子群中。
• $k$ 必须随机且不可重用，否则私钥易泄露。
• $H$ 通常为 SHA-1（老标准）或 SHA-2（新标准）。
• 早期标准 $L \in [512, 1024]$，新标准推荐 $L=2048, q=224/256$。
• DSA 设计初衷是避开当时的 RSA 专利，兼顾安全与性能。

3.2 ECDSA (Elliptic Curve DSA)

DSA 在椭圆曲线群上的变体（FIPS 186-5），核心优势是“相同安全强度下，密钥和签名长度远短于 RSA/DSA”，是移动设备、区块链、TLS 等场景的主流方案。

• 优势：相比 RSA/DSA，在相同安全强度下密钥和签名更短。

• 风险：对随机数 $k$ 极其敏感。

  • 若 $k$ 重复使用或可预测，攻击者可通过以下方式求解私钥 $x$： 已知 $(r, s_1)$（$m_1$ 的签名）和 $(r, s_2)$（$m_2$ 的签名），联立 $s_1 = k^{-1}(H(m_1) + xr)$ 和 $s_2 = k^{-1}(H(m_2) + xr)$，消去 $k$ 得 $x = (s_2H(m_1) - s_1H(m_2)) \cdot (s_1r - s_2r)^{-1} \pmod{q}$。
  • 典型案例：Sony PS3 因 ECDSA 随机数 $k$ 固定，导致私钥泄露。

• 改进 (RFC 6979)：为了避免随机数生成器 (RNG) 故障带来的灾难性后果，现代实现通常使用确定性 ECDSA。即 $k = HMAC(sk, m)$，确保对同一消息始终生成相同的 $k$，且 $k$ 对攻击者不可预测。

• 应用：Bitcoin（secp256k1 曲线）、Ethereum、TLS 1.3、iOS/Android 密钥存储。

3.3 EdDSA (Edwards-curve DSA)

基于扭曲爱德华曲线 (Twisted Edwards Curve)，如 Ed25519。

• 特点：
  • 确定性签名：随机数 $k$ 由 $H(sk, m)$ 确定性生成，消除了随机数发生器故障导致的风险。
  • 高性能：Ed25519 签名和验证速度极快，且公钥很短 (32 字节)。
  • 侧信道安全：设计上避免了分支和秘密相关的内存访问。
  • 变体:
    • PureEdDSA: 直接对消息 $m$ 签名。
    • HashEdDSA (Ed25519ph): 先对消息 $m$ 进行哈希，再签名。适用于硬件受限无法一次性处理长消息的场景。

3.4 SM2 数字签名算法

中国国家密码标准（GM/T 0003-2012），基于椭圆曲线离散对数问题（ECDLP），专为中文场景设计，具备自主可控的安全特性。

• 核心特色：引入“用户身份绑定”机制，签名时需将用户身份 $ID$、椭圆曲线参数、公钥等信息拼接后哈希，得到 $Z_A = H(ID | a | b | x_G | y_G | x_A | y_A)$，再计算 $e = H(Z_A | m)$，确保签名与用户身份强绑定，防止身份伪造。
• 流程特点：签名/验证流程类似 Schnorr 与 ECDSA 的混合体，安全性可证明，且抗已知攻击。
• 应用场景：电子政务、金融行业、国内区块链项目（如联盟链）、电子发票。

4. 特殊性质的签名 (Advanced Signatures)

4.1 盲签名 (Blind Signature)

签名者对消息“盲化后签名”，无法获取消息内容；用户去盲后得到有效签名，签名者无法将签名与原始消息关联（盲性+不可链接性）。

• 性质：
  • 盲性 (Blindness): 签名者无法看到 $m$。
  • 不可链接性 (Unlinkability): 签名者无法将签名后的结果与之前的签名请求对应起来。
• Chaum 盲签名 (RSA based):
  1. 用户选择随机因子 $r$，计算盲化消息 $m’ = m \cdot r^e \pmod N$ 发送给签名者。
  2. 签名者计算 $\sigma’ = (m’)^d \pmod N$ 发回。
  3. 用户去盲：$\sigma = \sigma’ \cdot r^{-1} \pmod N = m^d \pmod N$。
• 应用：电子现金 (E-Cash)，电子投票。

4.2 群签名 (Group Signature)

允许群成员代表整个群体签名，验证者只能验证是群体成员签的，但不知道具体是谁。

• 角色：群成员，群管理员 (Group Manager)。
• 性质：
  • 匿名性：对公众匿名。
  • 可追踪性：群管理员在争议时可以打开签名，揭示真实签名者身份。
• 应用：企业授权（员工代表企业签名）、车联网（V2X 通信匿名认证）、分布式系统节点认证。

4.3 环签名 (Ring Signature)

一种简化的群签名，但没有群管理员，完全匿名。

• 机制：签名者利用自己的私钥和其他 $n-1$ 个成员的公钥生成签名。
• 性质：
  • 无条件匿名：无法追踪真实签名者。
  • 自发性：无需其他成员配合，只要有公钥即可成环。
• 应用：匿名举报、隐私货币（如 Monero 的 RingCT 协议）、匿名通信。

4.4 不可否认签名 (Undeniable Signature)

验证签名的有效性需要签名者的配合（通过交互式“确认协议”验证有效性）。

• 目的：防止签名被随意验证和传播（保护签名者隐私），但在法律纠纷时签名者无法否认（通过“否认协议”证明伪造签名无效）。
• 组成：签名算法 + 确认协议 (Confirmation Protocol) + 否认协议 (Disavowal Protocol)。
• 应用场景：版权保护、电子合同（需双方确认）、敏感信息签名。

4.5 门限签名 (Threshold Signature)

需要 $n$ 个参与者中的至少 $t$ 个合作才能生成有效签名。

• 机制：私钥被秘密共享 (Secret Sharing) 为 $n$ 份。
• 应用：多方计算 (MPC) 钱包，高安全级密钥管理。

4.6 BLS 签名 (Boneh-Lynn-Shacham)

基于双线性配对 (Bilinear Pairing) 的签名方案。

• 原理：利用配对函数 $e: G_1 \times G_2 \to G_T$ 的“双线性特性”（$e(g^a, h^b) = e(g, h)^{ab}$），将签名验证转化为配对运算。

• 签名：

  • 密钥：私钥 $x$，公钥 $y = g^x \in G_2$；
  • 签名：$\sigma = H(m)^x \in G_1$（仅需群中一个元素，签名极短）；
  • 验证：检查 $e(\sigma, g) \stackrel{?}{=} e(H(m), y)$。

• 特性：

  • 短签名：签名只是群中的一个点，非常短。
  • 非交互式聚合 (Non-interactive Aggregation)：可以将多个用户对不同消息的签名聚合成一个签名，且验证成本极低。

• 应用：Ethereum 2.0 (信标链验证者签名聚合), Zcash, Filecoin。

5. 工程实践与常见陷阱 (Engineering Best Practices)

理论安全不等于实际安全，大多数漏洞都源于实现细节。

5.1 随机数生成 (RNG)

• 陷阱: 使用弱随机数生成器（如 C 语言 rand()、JavaScript Math.random()）、种子可预测、随机数 $k$ 重复/泄露。
• 后果: 对于 DSA/ECDSA/Schnorr，只要随机数 $k$ 泄露、预测或重复，私钥就会立即暴露。
• 最佳实践:
  • 使用密码学安全的随机数生成器 (CSPRNG)，如 /dev/urandom, CryptGenRandom。
  • 优先选择确定性签名方案 (如 RFC 6979 ECDSA, Ed25519)，完全消除对 RNG 的运行时依赖。

5.2 侧信道攻击 (Side-Channel Attacks)

• 陷阱: 算法执行时间或功耗与私钥相关。例如，模幂运算中的分支判断。
• 最佳实践:
  • 恒定时间实现 (Constant-time): 确保核心运算的时间不依赖于密钥数据。
  • 盲化 (Blinding): 在 RSA 运算前对密文进行随机盲化，防止计时攻击。

5.3 消息编码与哈希

• 陷阱: 直接对短消息签名而不哈希，或者哈希函数存在碰撞。
• 最佳实践:
  • Hash-then-Sign: 始终先对消息进行哈希。
  • 域分离 (Domain Separation): 在哈希输入中加入特定的前缀字符串 (如 Hash("MyApp-v1" || m)), 防止不同协议间的签名重放攻击。

5.4 密钥管理

• 陷阱: 私钥硬编码（如写死在代码中）、存储在不安全内存中、未加密存储。
• 最佳实践:
  • 使用硬件安全模块 (HSM) 或可信执行环境 (TEE/Enclave)。
  • 使用密钥派生函数 (KDF) 保护存储的私钥。
  • 定期轮换密钥。

6. 总结与对比

7. 理解与记忆心法 (Mnemonics)

建立一个**“家族谱系” + “演化故事”**的思维导图，避免死记硬背。

7.1 第一层：核心逻辑（一句话心法）

所有数字签名都在做同一件事：用私钥对“消息的指纹（哈希）”盖章，公钥用来验章。

• 目的：防篡改（完整性）、你是你（认证）、赖不掉（不可否认）。

7.2 第二层：两大门派（按数学难题分）

1. 大整数分解派（RSA 家族）

• 代表：RSA。
• 记忆钩子：“简单粗暴的幂运算”。
• 核心逻辑：签名就是解密（$s = m^d$），验证就是加密（$m = s^e$）。
• 演化：
  • 教科书 RSA：太简单，容易被利用数学性质攻击（乘法同态）。
  • RSA-PSS：为了安全，加了“盐”（随机填充），把消息打乱再签名。

2. 离散对数派（DLP 家族）

这是人丁兴旺的一派，包括 ElGamal, DSA, Schnorr, ECDSA, EdDSA, SM2, BLS。

• 记忆钩子：“随机数 $k$ 的诅咒”。这一派几乎所有算法在签名时都要选一个随机数 $k$。
• 演化故事线：
  1. ElGamal：老祖宗。开创了用随机数 $k$ 保护私钥 $x$ 的先河。缺点是签名太长（两个大数）。
  2. Schnorr：“完美的极简主义者”。把 ElGamal 优化了，签名短、速度快、还能把多个签名加在一起（线性特性）。因为专利原因被雪藏了很久，现在比特币（Taproot）把它请回来了。
  3. DSA：“政府版 ElGamal”。NIST 当年为了避开 RSA 专利搞的标准。它是 ElGamal 的变体，专门优化了签名长度。
  4. ECDSA：“DSA 的椭圆曲线版”。把 DSA 搬到了椭圆曲线上。好处是钥匙短（256位 vs RSA 3072位），手机、区块链最爱用。坏处是随机数 $k$ 极其脆弱（$k$ 重复 = 私钥丢）。
  5. EdDSA (Ed25519)：“工程学的胜利”。为了解决 ECDSA 容易因为随机数 $k$ 写不好而出事的问题，它直接取消了随机数（用哈希确定性生成 $k$），又快又安全。
  6. SM2：“国货之光”。结构类似 ECDSA/Schnorr，但加了个特色：把用户身份 ID 也卷进哈希里签了。
  7. BLS：“来自未来的魔法”。利用双线性配对，签名极短且支持无限聚合，是以太坊 2.0 的基石。

记忆钩子：“DLP 看 $k$，漏了就完蛋；要快要稳用 Ed，聚合签名用 BLS”。

7.3 第三层：特殊技能（按场景记忆）

把高级签名想象成拥有“超能力”的变种，对应现实故事：

7.4 总结记忆口诀

1. RSA 看填充（PSS才安全）。
2. DLP 看随机数（$k$ 漏了就完蛋）。
3. 比特币用两代（老 ECDSA，新 Schnorr）。
4. 要快要稳用 Ed（Ed25519）。
5. 聚合签名用 BLS。
6. 想匿名用环/群，想隐私用盲签。

8. 练习题 (Practice Exercises)

通过手动计算小数值示例，是记忆算法流程的最好方式。

8.1 基础计算题

练习 1: RSA 签名

假设 RSA 参数为 $p=3, q=11$。

1. 计算 $N$ 和 $\phi(N)$。
2. 若公钥 $e=3$，计算私钥 $d$。
3. 对消息 $m=5$ 进行签名，计算 $\sigma$。
4. 验证签名：计算 $\sigma^e \pmod N$ 是否等于 $m$。

练习 2: ElGamal 签名

假设素数 $p=11$，生成元 $g=2$。

1. 私钥 $x=3$，计算公钥 $y$。
2. 对消息 $m=5$ 签名：
   • 选择随机数 $k=9$ (检查 $\gcd(k, p-1)=1$)。
   • 计算 $r = g^k \pmod p$。
   • 计算 $s = k^{-1}(m - xr) \pmod{p-1}$。
3. 验证签名：检查 $g^m \equiv y^r r^s \pmod p$。

练习 3: Schnorr 签名 (严谨版)

为了演示真实的 Schnorr 签名，我们需要在一个素数阶子群上运算。 参数：$p=23$ (模数), $q=11$ (子群阶), $g=4$ (生成元，阶为 11)。

1. 密钥生成: 私钥 $x=3$。计算公钥 $y = g^x \pmod p$。
2. 签名: 对消息 $m$ 签名。
   • 选择随机数 $k=2$。计算承诺 $R = g^k \pmod p$。
   • 假设哈希输出挑战 $e = 4$。
   • 计算响应 $s = k + xe \pmod q$。
3. 验证: 计算 $R’ = g^s y^{-e} \pmod p$，并检查是否等于 $R$。

8.2 概念辨析题

练习 4: 连线题

将下列特性与对应的签名体制连接起来： A. 签名长度最短，且支持聚合 B. 必须使用确定性随机数以防侧信道攻击 C. 验证时需要检查填充格式 (Padding) D. 签名由 $(r, s)$ 组成，且 $s$ 的计算涉及 $k^{-1}$

1. RSA-PSS
2. Schnorr
3. ECDSA
4. EdDSA
5. BLS

练习 5: 安全分析

在 ECDSA 签名中，Alice 对两个不同的消息 $m_1, m_2$ 签名时，不小心使用了相同的随机数 $k$。 已知签名分别为 $(r, s_1)$ 和 $(r, s_2)$。 请问攻击者如何利用这两个签名计算出 Alice 的私钥 $x$？(提示：列出 $s_1, s_2$​ 的方程并相减)

练习 6: 核心原理简答题

1. 简述数字签名 EUF-CMA 安全定义的核心思想，为何该定义是实用中最严格的安全标准？
2. 对比 RSA-PSS 与 Ed25519 的核心差异，说明在 Web 应用中优先选择 Ed25519 的原因。
3. 为什么 ECDSA 对随机数 $k$ 的安全性要求极高，而 Ed25519 可以消除对随机数生成器的依赖？
4. 什么是盲签名的“盲性”与“不可链接性”，请结合电子投票场景说明其作用。

8.3 参考答案

练习 1 (RSA):

1. $N=33, \phi(N)=20$。
2. $3d \equiv 1 \pmod{20} \Rightarrow d=7$。
3. $\sigma = 5^7 \pmod{33}$。$5^2=25, 5^4=625\equiv 31\equiv -2, 5^7 = 5 \cdot 25 \cdot (-2) = -250 \equiv 14$。所以 $\sigma=14$。
4. $14^3 = 2744$。$2744 / 33 = 83 \dots 5$。验证通过。

练习 2 (ElGamal):

1. $y = 2^3 \pmod{11} = 8$。
2. $r = 2^9 \pmod{11} = 512 \equiv 6$。 $k=9$，在模 10 下 $9^{-1}=9$ (因 $9 \times 9 = 81 \equiv 1$)。 $s = 9(5 - 3 \cdot 6) \pmod{10} = 9(5 - 18) = 9(-13) = 9(7) = 63 \equiv 3$。 签名为 $(6, 3)$。
3. 左边 $2^5 = 32 \equiv 10$。 右边 $8^6 \cdot 6^3 \pmod{11}$。$8 \equiv -3 \Rightarrow (-3)^6 = 3^6 = 729 \equiv 3$。$6^3 = 216 \equiv 7$。$3 \cdot 7 = 21 \equiv 10$。验证通过。

练习 3 (Schnorr):

1. 公钥: $y = 4^3 = 64 = 2 \times 23 + 18 \equiv 18 \pmod{23}$。
2. 签名:
   • $R = 4^2 = 16 \pmod{23}$。
   • $s = 2 + 3 \cdot 4 = 14 \equiv 3 \pmod{11}$。
   • 签名为 $(R=16, s=3)$。
3. 验证:
   • 我们需要验证 $g^s y^{-e} \stackrel{?}{=} R \pmod p$。
   • $g^s = 4^3 = 64 \equiv 18 \pmod{23}$。
   • $y^e = 18^4 \pmod{23}$。$18 \equiv -5$。$(-5)^4 = 625 = 27 \times 23 + 4 \equiv 4$。
   • $y^{-e} = 4^{-1} \pmod{23}$。因为 $4 \times 6 = 24 \equiv 1$，所以逆元是 6。
   • $g^s y^{-e} = 18 \times 6 = 108$。
   • $108 = 4 \times 23 + 16 \equiv 16 \pmod{23}$。
   • 结果等于 $R$ (16)，验证通过。

练习 4 (连线): 1-C, 2-A (部分特性), 3-D, 4-B, 5-A (最强聚合) (注：Schnorr 支持线性聚合，BLS 支持非交互式聚合且签名更短)

练习 5 (安全分析): $s_1 = k^{-1}(H(m_1) + xr)$ $s_2 = k^{-1}(H(m_2) + xr)$ 两式相减：$s_1 - s_2 = k^{-1}(H(m_1) - H(m_2))$ 所以 $k = (H(m_1) - H(m_2)) \cdot (s_1 - s_2)^{-1} \pmod q$。 求出 $k$ 后，代回任意一式即可求出私钥 $x$​。 练习 6(原理简答):

1. 核心思想：攻击者可自适应请求任意消息的签名，若无法伪造出“未请求过的消息”的有效签名（且伪造概率可忽略），则方案满足EUF-CMA安全。该定义是最严格实用标准的原因：覆盖了现实中攻击者的最强能力（主动获取签名、自适应选择消息），能抵御绝大多数实际攻击场景。
2. 核心差异：① 数学基础：RSA-PSS基于大整数分解，Ed25519基于椭圆曲线离散对数；② 效率：Ed25519签名/验证速度远快于RSA-PSS；③ 随机数依赖：RSA-PSS依赖盐值随机，Ed25519为确定性签名；④ 密钥长度：Ed25519公钥32字节，RSA-PSS（2048位）公钥256字节。Web应用优先选Ed25519的原因：效率高、密钥短（传输存储成本低）、无随机数依赖（降低实现漏洞风险）。
3. ECDSA对$k$要求高的原因：$k$重复/可预测时，攻击者可通过联立签名方程求解私钥；Ed25519消除RNG依赖的原因：通过哈希函数$H(sk, m)$确定性生成$k$，$k$与私钥、消息强绑定，无需外部随机数，从根源避免$k$泄露风险。
4. 盲性：签名者对盲化后的消息签名，无法知晓原始消息内容；不可链接性：签名者无法将最终有效签名与原始盲化消息关联。电子投票场景中，盲性确保签名者（投票站）无法获取选民投票内容，不可链接性确保签名者无法追溯某张选票的具体投票人，从而保障选民隐私与投票公正性。

9. 参考文献与扩展阅读 (References)

1. RSA-PSS: RFC 8017 - PKCS #1: RSA Cryptography Specifications Version 2.2
2. ECDSA: FIPS 186-5 - Digital Signature Standard (DSS)
3. Deterministic ECDSA: RFC 6979
4. EdDSA: RFC 8032 - Edwards-Curve Digital Signature Algorithm (EdDSA)
5. Schnorr: BIP-340 - Schnorr Signatures for secp256k1
6. BLS: IETF Draft - BLS Signatures
7. SM2: GB/T 32918.2-2016 - SM2椭圆曲线公钥密码算法 第2部分：数字签名算法