数字签名与消息认证码：从数学原理到安全模型

概述

在密码学中，消息完整性和来源认证是两大核心安全目标。消息认证码（Message Authentication Code, MAC）和数字签名（Digital Signature）是解决这两个问题的两类基本原语，但它们在安全保证、密钥管理和使用场景上存在根本性差异。

理解二者的区别，不仅有助于正确选择密码学工具，更是理解 TLS、IPSec、区块链等安全协议设计决策的基础。

历史演进

数字签名的诞生

1976 年，Diffie 和 Hellman 在划时代论文《New Directions in Cryptology》中首次提出了数字签名的概念——他们猜想基于陷门单向置换可以构造出一种方案，使得任何人都能验证签名的真实性，但只有私钥持有者才能生成签名。但他们并未给出具体构造。

1978 年，Rivest、Shamir 和 Adleman 发明了 RSA 算法，首次实现了数字签名方案。然而，"裸"RSA 签名（直接对消息进行模幂运算）存在密钥仅存在性伪造攻击：攻击者可以随机选取一个签名值 σ，利用公开的验证算法反推出对应的消息 m = σ^e mod N，从而构造出"合法"的 (消息, 签名) 对。

1988 年，Goldwasser、Micali 和 Rivest（GMR）在他们里程碑式的论文 *"A Digital Signature Scheme Secure Against Adaptive Chosen-Message Attacks"* 中，首次严格定义了数字签名的安全性层次结构，并提出了 GMR 签名方案——这是第一个被证明能够抵抗自适应选择消息攻击下存在性伪造的方案。这标志着数字签名从工程实践走向可证明安全的数学基础。

MAC 的演进

MAC 的历史更为悠久。1970 年代，随着分组密码（如 DES）的出现，人们自然开始探索利用分组密码构造消息认证码的方法。1996 年，Bellare、Canetti 和 Krocz提出了 CBC-MAC 的安全性证明。1997 年，Black 和 Rogaway 提出了基于哈希函数的 HMAC 构造，由 Iwata、Kurosawa 和 Standaert 在 2003 年给出了严格的安全性证明。

数学定义与形式化安全模型

数字签名的形式化定义

一个数字签名方案是由三个概率多项式时间算法组成的三元组 Π = (Gen, Sign, Verify)：

• Gen(1^n) → (pk, sk)：密钥生成算法，输入安全参数 n，输出公钥 pk 和私钥 sk
• Sign(sk, m) → σ：签名算法，输入私钥和消息 m，输出签名 σ
• Verify(pk, m, σ) → {0, 1}：验证算法，输入公钥、消息和签名，输出接受(1)或拒绝(0)

$$\Pr[\text{Verify}(pk, m, \text{Sign}(sk, m)) = 1] = 1$$

安全性定义——EUF-CMA（Existential Unforgeability under Chosen-Message Attack，自适应选择消息攻击下的存在不可伪造性）：

这是 Goldwasser、Micali 和 Rivest 于 1988 年提出的安全性概念，至今仍是数字签名安全性的黄金标准。

其安全博弈（Security Game）定义如下：

签名者                                  攻击者 A
   |                                       |
   |--- 1^n (安全参数) --→                |
   |                                       |
   |← (pk, sk) = Gen(1^n)                 |
   |--- pk --→                            |
   |                                       |
   |← 选择消息 m₁ --→                     |
   |--- σ₁ = Sign(sk, m₁) --→             |
   |                                       |
   |← 选择消息 m₂ --→                     |
   |--- σ₂ = Sign(sk, m₂) --→             |
   |           ...                         |
   |← 选择消息 m_q --→                    |
   |--- σ_q = Sign(sk, m_q) --→            |
   |                                       |
   |← (m*, σ*) ---------------------------|
   |                                       |
   |--- Verify(pk, m*, σ*) = 1? ---→      |
   |   且 m* ∉ {m₁, ..., m_q}             |

如果对于所有概率多项式时间的攻击者 A，其获胜概率可忽略（negl(n)），则称该签名方案满足 EUF-CMA 安全性。

直觉上：即使攻击者可以自适应地选择任意消息并获得其合法签名，他仍然无法为一个从未查询过的新消息构造出有效的签名。

MAC 的形式化定义

一个 MAC 方案同样是由三个算法组成的三元组 Π = (Gen, MAC, Verify)：

• Gen(1^n) → K：密钥生成算法，输出对称密钥 K
• MAC(K, m) → τ：标签生成算法，输入密钥和消息，输出认证标签 τ
• Verify(K, m, τ) → {0, 1}：验证算法

MAC 的安全性通常归约为底层函数是否为伪随机函数。但更直接的不可伪造性定义如下：

如果对于所有概率多项式时间的攻击者 A，以下概率可忽略：

$$\Pr[K \leftarrow \text{Gen}(1^n), (m^*, \tau^*) \leftarrow A^{\text{MAC}(K, \cdot)}(1^n) : m^* \notin Q \land \text{Verify}(K, m^*, \tau^*) = 1] < \text{negl}(n)$$

其中 Q 表示攻击者查询 MAC 预言机时使用的消息集合。

关键区别：MAC 的安全模型中，攻击者只能查询 MAC 预言机（获取标签），但无法验证——因为他不知道密钥，也无法自行验证一个标签是否正确。而数字签名的攻击者则可以自行运行验证算法检查签名是否有效。

安全性层次结构

数字签名的攻击层次（Goldwasser-Micali-Rivest 1988）

按照攻击者能力的递进：

MAC 的安全层次

核心差异对比

密钥模型

数字签名（非对称）：
  签名者: sk（私钥，保密）
  验证者: pk（公钥，公开）
  
  → 任何人都能验证，只有签名者能生成
  → 天然支持第三方仲裁

MAC（对称）：
  通信双方: K（共享密钥，双方保密）
  
  → 能验证的人也能生成
  → 无法区分"谁发了这条消息"
  → 无法向第三方证明消息来源

安全保证差异

为什么 MAC 无法提供不可否认性

MAC 的验证和生成使用同一把密钥。如果 Alice 和 Bob 共享密钥 K，当 Bob 收到一条带有有效 MAC 标签的消息时，他只能确认：持有 K 的某个人生成了这条消息。但他无法区分是 Alice 还是 Alice 自己生成的。

数字签名则不同：私钥仅由签名者持有，验证只需要公钥。因此，一个有效的签名唯一地指向了私钥持有者，提供了密码学意义上的不可否认性。

典型构造方案

数字签名的典型构造

基于 RSA 的签名（RSA-PSS）：

RSA-PSS (Probabilistic Signature Scheme) 是目前推荐的 RSA 签名标准（PKCS#1 v2.2 / RFC 8017）。与"裸"RSA 不同，PSS 引入了随机盐值（salt）使签名具有随机性：

$$\text{Sign}(sk, m) = \text{EMSA-PSS-ENCODE}(m, salt)^d \bmod N$$

其安全性可归约到 RSA 难题的困难性，在随机预言机模型下可证明 EUF-CMA 安全。

基于椭圆曲线的签名（ECDSA / SM2）：

ECDSA 和 SM2 签名都基于椭圆曲线上的离散对数问题（ECDLP）。签名过程涉及生成随机数 k，计算 (x, y) = k·G，然后输出 (r, s) 对。

两者的区别在于哈希函数和消息处理方式：

• ECDSA：使用 SHA-256 系列哈希
• SM2：使用 SM3 哈希，且消息处理中包含用户 ID 等额外信息（Z 值计算）

NIST PQC 标准化进程中选定的数字签名方案：

• CRYSTALS-Dilithium：基于格上 MLWE/MSIS 问题，签名小、速度快
• SPHINCS+：基于哈希函数，安全性仅依赖哈希的抗碰撞性（最保守假设），但签名较大
• Falcon：基于格上短整数解问题（SIS），签名最小但实现复杂

MAC 的典型构造

HMAC（Hash-based MAC）：

HMAC 由 Bellare、Canetti 和 Krocz于 1996 年提出，构造如下：

$$\text{HMAC}(K, m) = H\left((K' \oplus \text{opad}) \| H((K' \oplus \text{ipad}) \| m)\right)$$

其中：

• K' = H(K) 如果 K 长于哈希块长度，否则 K' = K 补零
• ipad = 0x36 重复块长度次数
• opad = 0x5C 重复块长度次数
• H 为底层哈希函数（如 SHA-256 或 SM3）

CMAC（Cipher-based MAC）：

基于分组密码的 MAC 构造（如 AES-CMAC），使用分组密码的 CBC 模式变体，最后一步应用子密钥异或以防止长度扩展攻击。

Poly1305：

基于通用哈希函数（Universal Hashing）的 MAC，与 AES 组合使用（Poly1305-AES）。特点是极快的单消息处理速度，广泛用于 ChaCha20-Poly1305 等 AEAD 方案。

国密算法中的实现

SM2 数字签名（GM/T 0003.2-2012）

SM2 签名算法是我国自主设计的椭圆曲线数字签名算法，基于 256 位素数域上的椭圆曲线。

签名流程：

• 计算 Z_A = SM3(ENTL_A || ID_A || a || b || x_G || y_G || x_A || y_A)
• 计算 e = SM3(Z_A || M)
• 生成随机数 k ∈ [1, n-1]
• 计算 (x₁, y₁) = k·G
• 计算 r = (e + x₁) mod n
• 计算 s = (1 + d_A)⁻¹ · (k - r · d_A) mod n
• 输出签名 (r, s)

• SM2 的消息哈希包含用户 ID（Z 值），天然抵抗密钥替换攻击
• SM2 使用 SM3 而非 SHA-256
• SM2 的 s 值计算方式不同，不需要随机数的逆元
• SM2 签名具有强不可区分性：同一消息的不同签名之间无法关联

SM3-HMAC（GM/T 0004-2012）

SM3 是我国自主设计的密码杂凑算法，输出长度 256 位，安全性相当于 SHA-256。其结构采用 Merkle-Damgård 迭代框架：

SM3 压缩函数结构：
  V₀ = IV (初始值)
  Vᵢ = CF(Vᵢ₋₁, Bᵢ₋₁)  for i = 1, ..., n
  BN = Vₙ

其中 CF 包含 64 轮压缩：
  SS1 ← ((A <<< 12) + E + (Tᵢ <<< i)) <<< 7
  SS2 ← SS1 ⊕ (A <<< 12)
  TT1 ← FFᵢ(A, B, C) + D + SS2 + W'ᵢ
  TT2 ← GGᵢ(E, F, G) + H + SS1 + Wᵢ
  D ← C
  C ← B <<< 9
  B ← A
  A ← TT1
  H ← G
  G ← F <<< 19
  F ← E
  E ← P₀(TT2)

SM3-HMAC 的构造方式与国际标准 HMAC-SHA256 完全一致，仅将底层哈希替换为 SM3。GM/T 0004 标准明确规定了 SM3 在 HMAC 模式下的使用方式。

GM/T 0009-2023《SM2 密码算法使用规范》

该标准（2023 年发布）规定了 SM2 算法在实际系统中的使用要求，包括：

• 密钥生成与验证
• 签名与验签的数据格式
• 消息摘要的计算方法
• 用户标识（ID）的编码规则

应用场景分析

何时选择数字签名

• 需要不可否认性的场景：电子合同、金融交易、软件发布
• 多方验证场景：证书链验证、区块链交易
• 无需预先共享密钥的场景：首次通信、公开宣告

何时选择 MAC

• 双方已共享密钥的场景：TLS 已建立会话后的数据传输、IPSec SA
• 性能敏感场景：高频消息认证、嵌入式设备
• 不需要第三方仲裁的场景：内部系统间通信

组合使用：认证加密（AEAD）

现代协议通常将 MAC 与加密组合为 AEAD（Authenticated Encryption with Associated Data）方案：

常见设计陷阱

1. 签名方案选择错误

❌ 使用"裸"RSA 签名（无哈希、无填充） ✅ 使用 RSA-PSS 或 RSA-PKCS#1 v1.5（兼容性场景）

2. MAC 密钥与加密密钥混用

❌ 用同一把密钥做加密和 MAC ✅ 使用 KDF 从主密钥派生出独立的加密密钥和 MAC 密钥

3. MAC 不验证长度

❌ 某些 MAC 构造存在长度扩展攻击（如 SHA-256 without HMAC） ✅ 使用 HMAC 或 SHA-3（天然抵抗长度扩展）

4. 签名随机数重用

❌ ECDSA/SM2 中随机数 k 被重用 → 私钥直接泄露 ✅ 使用 RFC 6979 确定性随机数生成，或确保高质量熵源

参考来源

• Goldwasser, S., Micali, S., Rivest, R.L. (1988). "A Digital Signature Scheme Secure Against Adaptive Chosen-Message Attacks." *SIAM Journal on Computing*, 17(2), 281-308.
• Bellare, M., Canetti, R., Krawczyk, H. (1996). "Keying Hash Functions for Message Authentication." *CRYPTO '96, LNCS 1109, 1-15.
• Iwata, T., Kurosawa, K., Standaert, F.X. (2003). "OMAC: One-Key CBC MAC." *FSE 2003, LNCS 2887, 129-153.
• GM/T 0003.2-2012. SM2 第 2 部分：数字签名算法.
• GM/T 0004-2012. SM3 密码杂凑算法.
• GM/T 0009-2023. SM2 密码算法使用规范.
• GB/T 32918.2-2016. SM2 第 2 部分：数字签名算法.
• NIST FIPS 180-4. Secure Hash Standard (SHS).
• NIST FIPS 198-1. The Keyed-Hash Message Authentication Code (HMAC).
• RFC 8017. PKCS #1: RSA Cryptography Specifications Version 2.2.
• ISO/IEC 9797-1:2011. Security techniques — Message Authentication Codes (MACs) — Part 1: Mechanisms using a block cipher.

相关实践

• 如需了解 SM2 签名在 TLS 中的完整部署流程，请参阅《SM2 国密算法实战：从密钥生成到 TLS 完整部署》
• 如需了解国密 HTTPS 部署过程中的常见问题，请参阅《国密 HTTPS 踩坑实录：从开发到上线的 12 个坑》
• 如需了解 SM3 哈希算法的实际应用，请参阅《SM3 国密哈希算法实战：HMAC-SM3、PBKDF2-SM3 与性能调优》