数字签名与认证是现代密码学的核心应用之一，为数字世界提供了身份验证、数据完整性和不可抵赖性保障。本章将深入探讨数字签名方案的数学基础、消息认证码的设计原理，以及零知识证明这一革命性的密码学工具。
学习目标：
历史回顾： 从古代的封印印鉴到现代的数字签名，人类对身份认证的需求从未停止。1976年，Diffie和Hellman首次提出了数字签名的概念。随后，Rivest、Shamir和Adleman在1978年提出了第一个实用的数字签名方案RSA。1985年，Shafi Goldwasser、Silvio Micali和Charles Rackoff提出了零知识证明的概念，开创了密码学的新纪元。
当代视角： 在区块链技术蓬勃发展的今天，数字签名成为了加密货币和智能合约的安全基石。零知识证明技术，特别是zk-SNARKs和zk-STARKs，正在隐私保护和可验证计算领域发挥重要作用。从比特币的ECDSA签名到以太坊的零知识rollup，认证技术正在重塑数字经济的信任基础。
数字签名方案在数学上可以视为一种特殊的公钥密码系统，但其目标是提供认证而非保密。形式化地，一个数字签名方案 $\Pi = (\text{KeyGen}, \text{Sign}, \text{Verify})$ 定义如下：
基本组成算法：
数学结构的深层含义：
从代数角度看，数字签名实际上是一个带有陷门的单向函数族。签名算法利用陷门信息（私钥）计算单向函数的逆，而验证算法检查这个逆是否正确。这与公钥加密的结构形成有趣的对偶关系：
\[\begin{array}{c|c} \text{公钥加密} & \text{数字签名} \\ \hline \text{公钥加密，私钥解密} & \text{私钥签名，公钥验证} \\ \text{保密性目标} & \text{认证性目标} \\ \text{Easy}(pk, m) \rightarrow c & \text{Hard}(pk, m) \rightarrow \sigma \\ \text{Hard}(c) \rightarrow m & \text{Easy}(pk, m, \sigma) \rightarrow \{0,1\} \end{array}\]正确性要求的精确表述：
对于任意由 $\text{KeyGen}(1^k)$ 生成的密钥对 $(pk, sk)$ 和任意消息 $m \in \mathcal{M}$，正确性要求：
\[\Pr[\text{Verify}(pk, m, \text{Sign}(sk, m)) = 1] = 1\]这里的概率是对算法内部随机性的，包括密钥生成和签名过程中的随机选择。
消息空间的考虑：
实际应用中，消息空间 $\mathcal{M}$ 通常需要特殊处理：
这导致了”哈希后签名”的标准范式： \(\text{Sign}(sk, m) = \text{Sign}'(sk, H(m))\)
其中 $H: {0,1}^* \rightarrow {0,1}^n$ 是密码学哈希函数，$\text{Sign}’$ 是对固定长度输入的核心签名算法。
效率考量：
数字签名的效率通常用以下指标衡量：
| 密钥大小：$ | pk | + | sk | $ 随安全参数的增长率 |
| 签名大小：$ | \sigma | $ 的期望值 |
Rule-of-thumb： 在设计数字签名方案时，安全性、效率和实用性之间需要权衡。通常，签名越短，计算开销越大；安全性越高，密钥和签名尺寸越大。
数字签名的安全性需要从多个维度进行分析。最核心的安全性质是不可伪造性（Unforgeability），它确保只有拥有私钥的实体才能产生有效签名。
安全性层次的演进：
数字签名的安全性定义经历了从弱到强的发展过程：
攻击模型的分类：
根据敌手的能力，攻击模型分为：
定义 5.1（EUF-CMA安全性）： 一个数字签名方案 $\Pi$ 是存在性不可伪造的选择消息攻击安全（EUF-CMA），如果对于任意概率多项式时间敌手 $\mathcal{A}$，以下实验中 $\mathcal{A}$ 成功的概率是可忽略的：
实验 Exp^{euf-cma}_{\Pi,\mathcal{A}}(k):
1. (pk, sk) ← KeyGen(1^k)
2. 初始化查询列表 Q = ∅
3. (m*, σ*) ← A^{Sign(sk,·)}(pk)，其中预言机查询满足：
- 对于 A 的查询 mi，返回 σi = Sign(sk, mi)
- 将 mi 添加到 Q 中
4. 如果 Verify(pk, m*, σ*) = 1 且 m* ∉ Q
则返回 1，否则返回 0
形式化地，$\mathcal{A}$ 的优势定义为： \(\text{Adv}^{\text{euf-cma}}_{\Pi,\mathcal{A}}(k) = \Pr[\text{Exp}^{\text{euf-cma}}_{\Pi,\mathcal{A}}(k) = 1]\)
如果对于所有概率多项式时间敌手 $\mathcal{A}$，存在可忽略函数 $\text{negl}(k)$ 使得： \(\text{Adv}^{\text{euf-cma}}_{\Pi,\mathcal{A}}(k) \leq \text{negl}(k)\)
则称 $\Pi$ 是EUF-CMA安全的。
强不可伪造性的扩展：
在某些应用中，需要更强的安全性定义：
定义 5.2（SUF-CMA安全性）： 强不可伪造性（Strong Unforgeability）要求敌手不能产生新的有效消息-签名对，即使对已查询的消息也不行。实验修改为：
如果 Verify(pk, m*, σ*) = 1 且 (m*, σ*) ∉ {(mi, σi) : mi ∈ Q}
则返回 1，否则返回 0
这排除了签名延展性攻击，即从有效签名 $(m, \sigma)$ 生成同一消息的不同有效签名 $(m, \sigma’)$。
安全性的直觉理解：
EUF-CMA安全性捕获了以下关键直觉：
与其他安全概念的关系：
数字签名的不可伪造性与其他密码学概念存在深刻联系：
\[\begin{array}{c} \text{单向函数} \\ \downarrow \\ \text{数字签名存在} \\ \downarrow \\ \text{单向函数存在} \end{array}\]这表明数字签名与单向函数在复杂性理论上等价，都是现代密码学的基础假设。
安全性证明的一般方法：
证明数字签名方案的EUF-CMA安全性通常采用归约方法：
Rule-of-thumb： 在实际应用中选择数字签名方案时，EUF-CMA安全性是最基本要求。对于需要防范签名延展性的应用（如区块链），应选择SUF-CMA安全的方案。
RSA签名方案基于大整数分解的困难性，是历史上第一个实用的数字签名方案。其设计思路是RSA加密的”逆向”应用：用私钥”加密”（签名），用公钥”解密”（验证）。
数学基础回顾：
RSA签名的安全性依赖于以下数学困难问题：
朴素RSA签名方案：
密钥生成 $\text{KeyGen}(1^k)$：
签名算法 $\text{Sign}(sk, m)$： 对消息 $m \in \mathbb{Z}_N^*$，计算： \(\sigma = m^d \bmod N\)
验证算法 $\text{Verify}(pk, m, \sigma)$： 检验等式： \(\sigma^e \stackrel{?}{\equiv} m \pmod{N}\)
如果等式成立则接受，否则拒绝。
正确性验证： 对于正确生成的签名，有： \((\sigma)^e = (m^d)^e = m^{de} = m^{1 + k\phi(N)} = m \cdot (m^{\phi(N)})^k \equiv m \pmod{N}\)
最后一步使用了欧拉定理：$m^{\phi(N)} \equiv 1 \pmod{N}$（当 $\gcd(m, N) = 1$ 时）。
朴素方案的严重漏洞：
朴素RSA签名方案存在多个致命安全缺陷：
1. 存在性伪造攻击： 敌手可以执行以下步骤：
这个攻击成功是因为敌手可以自由选择消息，而朴素RSA对消息没有结构限制。
2. 乘性同态攻击： RSA具有乘性同态性质： \(\text{Sign}(m_1) \cdot \text{Sign}(m_2) = m_1^d \cdot m_2^d = (m_1 \cdot m_2)^d = \text{Sign}(m_1 \cdot m_2)\)
因此，如果敌手知道 $m_1, m_2$ 的签名，就可以计算 $m_1 \cdot m_2 \bmod N$ 的签名。
3. 选择消息攻击： 敌手可以巧妙构造查询来获取目标消息的签名：
安全的RSA签名：填充方案
为了克服朴素RSA的缺陷，必须使用填充方案。最重要的是PSS（Probabilistic Signature Scheme）：
RSA-PSS构造：
签名过程：
其中 $\text{MGF}$ 是掩码生成函数，$\text{DB} = \text{PS} | 0x01 | \text{salt}$。
PSS的安全性保证：
定理 5.3： 在随机预言模型下，如果RSA问题是困难的，则RSA-PSS是EUF-CMA安全的。
证明思路依赖于PSS填充的随机性和不可逆性，使得敌手无法利用RSA的代数结构进行攻击。
参数选择的实际考虑：
模数大小：
公开指数选择：
性能特性分析：
验证效率： RSA验证只需计算 $\sigma^e \bmod N$，当 $e = 65537$ 时，只需要16次模乘运算，非常高效。
签名效率： RSA签名需要计算 $m^d \bmod N$，其中 $d$ 是大指数，通常使用中国剩余定理加速： \(\begin{aligned} \sigma_p &= m^{d_p} \bmod p \\ \sigma_q &= m^{d_q} \bmod q \\ \sigma &= \text{CRT}(\sigma_p, \sigma_q) \end{aligned}\)
这可以将签名速度提高约4倍。
与现代方案的比较：
\[\begin{array}{l|c|c|c} \text{特性} & \text{RSA-2048} & \text{ECDSA-256} & \text{Ed25519} \\ \hline \text{签名大小} & 256\text{字节} & 64\text{字节} & 64\text{字节} \\ \text{公钥大小} & 256\text{字节} & 64\text{字节} & 32\text{字节} \\ \text{验证速度} & \text{快} & \text{中} & \text{快} \\ \text{签名速度} & \text{慢} & \text{中} & \text{快} \\ \text{量子安全性} & \text{否} & \text{否} & \text{否} \end{array}\]Rule-of-thumb： RSA签名方案永远不要使用朴素构造。在需要快速验证的场景（如TLS握手）中，RSA仍有优势。但对于新设计的系统，建议考虑椭圆曲线签名或后量子签名方案。
ECDSA基于椭圆曲线离散对数问题的困难性，相比RSA具有更短的密钥长度。
域参数： 选择椭圆曲线 $E: y^2 = x^3 + ax + b \pmod{p}$ 和基点 $G$，阶为素数 $n$。
密钥生成：
签名算法： 对消息 $m$：
验证算法：
安全性特性： ECDSA的安全性基于椭圆曲线离散对数问题的困难性。关键安全要求：
Rule-of-thumb： ECDSA中随机数 $k$ 的重用或预测性是致命漏洞，曾导致PlayStation 3和Android比特币钱包的私钥泄露。
消息认证码（Message Authentication Code, MAC）是对称密码学中用于验证消息完整性和来源的工具。
定义 5.2（MAC方案）： MAC方案由三个算法组成 $\Pi = (\text{KeyGen}, \text{MAC}, \text{Verify})$：
安全性定义： MAC的安全性用存在性不可伪造性定义：
定义 5.3（EUF-CMA for MAC）： MAC方案 $\Pi$ 是EUF-CMA安全的，如果对于任意多项式时间敌手 $\mathcal{A}$：
实验 Exp^{euf-cma}_{\Pi,\mathcal{A}}(k):
1. K ← KeyGen(1^k)
2. (m*, t*) ← A^{MAC(K,·)}(1^k)
3. 如果 Verify(K, m*, t*) = 1 且 m* 从未被查询过
则返回 1，否则返回 0
成功概率是可忽略的。
HMAC（Hash-based Message Authentication Code）是最广泛使用的MAC构造之一，基于任意密码学哈希函数构建。
HMAC定义： 设 $H$ 是哈希函数，$K$ 是密钥，$m$ 是消息，则： \(\text{HMAC}_K(m) = H((K \oplus \text{opad}) \| H((K \oplus \text{ipad}) \| m))\)
其中：
设计原理： HMAC的双层哈希结构旨在抵抗以下攻击：
安全性定理：
定理 5.1： 如果底层哈希函数 $H$ 是抗碰撞的，且其压缩函数在相关密钥攻击下是伪随机函数，则HMAC是EUF-CMA安全的。
证明思路： 证明通过将HMAC的安全性归约到底层哈希函数的性质。关键观察是内外层的不同密钥使得敌手无法简单地利用哈希函数的弱点。
CBC-MAC基于分组密码的CBC模式构造MAC。
CBC-MAC算法： 设 $E$ 是分组密码，$K$ 是密钥，消息 $m = m_1 | m_2 | … | m_\ell$：
安全性限制： 朴素的CBC-MAC仅对固定长度消息安全。对于变长消息，需要以下修改之一：
Rule-of-thumb： 绝不要对不同长度的消息直接使用CBC-MAC，这会导致容易的伪造攻击。
定义 5.4（ε-AU哈希族）： 哈希函数族 $\mathcal{H} = {h: \mathcal{X} \rightarrow \mathcal{Y}}$ 是 $\varepsilon$-almost universal的，如果对于任意不同的 $x_1, x_2 \in \mathcal{X}$： \(\Pr_{h \leftarrow \mathcal{H}}[h(x_1) = h(x_2)] \leq \varepsilon\)
Carter-Wegman构造提供了一种通用的MAC构造方法：
构造： 设 $\mathcal{H}$ 是 $\varepsilon$-AU哈希族，$f$ 是伪随机函数，则： \(\text{MAC}_K(m) = f_{K_2}(h_{K_1}(m))\)
其中 $K = (K_1, K_2)$，$K_1$ 用于选择哈希函数，$K_2$ 用作PRF密钥。
安全性定理：
定理 5.2： 如果 $\mathcal{H}$ 是 $\varepsilon$-AU哈希族，$f$ 是伪随机函数，则Carter-Wegman构造是EUF-CMA安全的MAC，敌手的成功概率至多为 $q\varepsilon + \text{Adv}^{prf}(t, q)$，其中 $q$ 是查询次数。
Poly1305是一个基于多项式求值的高效AU哈希函数：
构造： 对于消息 $m = m_1 | m_2 | … | m_k$（每块128位），选择素数 $p = 2^{130} - 5$：
\[h_r(m) = \left(\sum_{i=1}^k (m_i + 2^{128}) \cdot r^{k-i+1}\right) \bmod p\]其中 $r$ 是密钥的一部分，最终输出为： \(\text{Poly1305}(m) = h_r(m) + s \bmod 2^{128}\)
$s$ 是用AES生成的随机数。
效率优势： Poly1305的设计允许高效的硬件和软件实现，特别适合高性能网络协议（如TLS 1.3中的ChaCha20-Poly1305）。
零知识证明是密码学中最深刻的概念之一，允许证明者向验证者证明某个陈述的真实性，而不泄露任何除陈述真实性之外的信息。
定义 5.5（交互式证明系统）： 交互式证明系统是一个协议，包含证明者 $P$ 和验证者 $V$，对于语言 $L$：
定义 5.6（零知识性）： 交互式证明系统具有零知识性，如果对于任意多项式时间验证者 $V^*$，存在多项式时间模拟器 $S$，使得对于任意 $x \in L$： \(\{V^*(P(w), V^*)(x)\} \stackrel{c}{\equiv} \{S(x)\}\)
其中 $w$ 是 $x$ 的证据，$\stackrel{c}{\equiv}$ 表示计算不可区分。
Schnorr协议是最经典的零知识证明例子，证明者证明知道离散对数而不泄露它。
系统参数：
| 质数 $p$，$q$ 使得 $q | (p-1)$ |
协议流程：
证明者 P 验证者 V
知道 x 使得 y = g^x
选择 r ← Z_q
a = g^r mod p ──a──→
←──c── 选择 c ← {0,1}^t
z = r + cx mod q ──z──→
验证: g^z ≟ a·y^c mod p
零知识性证明： 模拟器 $S$ 的工作方式：
由于 $c’$ 是随机选择的，模拟的交互与真实交互计算不可区分。
知识抽取： 如果恶意证明者能对同一个 $a$ 回答两个不同的挑战 $c_1, c_2$，则可以提取私钥： \(x = \frac{z_1 - z_2}{c_1 - c_2} \bmod q\)
Fiat-Shamir变换将交互式零知识证明转换为非交互式版本，通过随机预言模型实现。
变换方法： 用密码学哈希函数 $H$ 替代验证者的随机挑战： \(c = H(x, a)\)
其中 $x$ 是公共输入，$a$ 是证明者的首轮消息。
Schnorr签名： 应用Fiat-Shamir变换到Schnorr协议得到Schnorr签名：
安全性分析： 在随机预言模型下，如果底层的Schnorr协议是零知识的，则Fiat-Shamir变换保持安全性。但在标准模型下，这个变换可能不安全。
Rule-of-thumb： Fiat-Shamir变换的安全性严重依赖于哈希函数的随机性，实际应用中需要使用密码学安全的哈希函数。
zk-SNARKs（Zero-Knowledge Succinct Non-Interactive Arguments of Knowledge）是零知识证明的现代发展，具有以下特性：
通用可信设置： zk-SNARKs通常需要可信设置阶段，生成公共参考串（CRS）。这是实际部署的主要挑战。
现代零知识系统将计算表示为算术电路：
R1CS（Rank-1 Constraint System）： 约束形式为：$(A\mathbf{w}) \circ (B\mathbf{w}) = C\mathbf{w}$
其中 $\mathbf{w}$ 是见证向量，$A, B, C$ 是约束矩阵，$\circ$ 表示逐元素乘积。
实际应用：
HMAC构造： \(\text{HMAC}_K(m) = H((K \oplus \text{opad}) \| H((K \oplus \text{ipad}) \| m))\)
ECDSA签名： \(s = k^{-1}(e + dr) \bmod n\)
Carter-Wegman MAC： \(\text{MAC}_K(m) = f_{K_2}(h_{K_1}(m))\)
Schnorr协议验证： \(g^z \stackrel{?}{=} a \cdot y^c \bmod p\)
数字签名与认证技术的安全性可以分为以下层次：
问题描述： 在ECDSA和DSA中，随机数 $k$ 的重用会导致私钥泄露。
攻击方法： 如果两个签名使用相同的 $k$：
则私钥可被计算为： \(d = \frac{s_1 m_2 - s_2 m_1}{r(s_1 - s_2)} \bmod n\)
历史案例：
防护措施：
问题： 使用弱哈希函数（如MD5、SHA-1）进行签名易受碰撞攻击。
攻击场景： 攻击者构造两个不同文档具有相同哈希值，欺骗签名者签名其中一个，然后声称签名了另一个。
Rule-of-thumb： 永远使用SHA-256或更强的哈希函数进行签名。
ECDSA延展性： 给定有效签名 $(r, s)$，$(r, -s \bmod n)$ 也是有效签名。
危害： 在比特币等系统中可能导致交易ID被恶意修改。
解决方案：
攻击对象： 直接使用SHA-1、SHA-256等基于Merkle-Damgård构造的哈希函数作为MAC： \(\text{MAC}(K, m) = \text{SHA256}(K \| m)\)
攻击原理： 攻击者可以在不知道密钥 $K$ 的情况下，为消息 $m | \text{padding} | m’$ 计算有效MAC。
正确做法：
问题： MAC验证中的非常量时间比较可能泄露信息。
错误示例：
def verify_mac(computed_mac, provided_mac):
if len(computed_mac) != len(provided_mac):
return False
for i in range(len(computed_mac)):
if computed_mac[i] != provided_mac[i]:
return False # 提前返回泄露信息
return True
正确做法： 使用常量时间比较：
def constant_time_compare(a, b):
if len(a) != len(b):
return False
result = 0
for x, y in zip(a, b):
result |= x ^ y
return result == 0
攻击场景： 对于消息 $m_1$ 和 $m_2 = m_1 | (t_1 \oplus m_2’)$，其中 $t_1 = \text{CBC-MAC}(m_1)$，有： \(\text{CBC-MAC}(m_2) = \text{CBC-MAC}(m_2')\)
防护：
问题： 许多zk-SNARKs需要可信设置，如果设置参数被泄露，整个系统安全性失效。
Zcash的”烧毁仪式”： 为了增强公信力，Zcash在主网启动前进行了公开的参数销毁仪式。
新方向：
问题： 在通用零知识系统中，恶意构造的电路可能泄露见证信息。
示例： 电路中包含形如 $w_i \cdot 0 = \text{public_output}$ 的约束，会直接泄露私有输入 $w_i$。
防护：
问题： 零知识性只在诚实验证者情况下保证，恶意验证者可能提取信息。
实际影响： 在实际协议设计中，需要考虑零知识性在并发环境下的保持。
解决方案：
时序攻击： 签名和验证操作的执行时间可能泄露密钥信息。
功耗分析： 智能卡等设备的功耗变化可能泄露计算中间值。
防护措施：
熵不足： 密码学随机数生成器的熵源不足可能导致可预测的随机数。
伪随机数生成器缺陷： 使用不当的PRNG（如C语言的rand()）进行密码学操作。
最佳实践：
本章结语： 数字签名与认证技术是现代密码学应用的基石。从理论基础到实际应用，每个环节都需要严格的安全性考量。随着量子计算威胁的临近和区块链技术的发展，这一领域正在经历快速的变革。理解其数学原理和安全性分析方法，对于设计和评估安全系统至关重要。