RSA 公钥密码算法原理详解

概述

RSA 密码系统是三位 MIT 研究人员 Rivest、Shamir 和 Adleman 于 1977 年发明的公钥密码算法。作为最早且最广泛部署的公钥基础设施组件，RSA 至今仍是数字证书、密钥交换、数字签名等应用的主力军。其安全性基于大整数分解问题：已知素数乘积 n = p × q，在不知 p 和 q 的情况下，计算 φ(n) = (p-1)(q-1) 和私钥 d 在计算上不可行。

核心数学关系

密钥生成：
  n = p × q                (模数)
  φ(n) = (p-1)(q-1)        (欧拉函数)
  e 满足 1 < e < φ(n) 且 gcd(e, φ(n)) = 1     (公钥指数)
  d ≡ e⁻¹ mod φ(n)         (私钥指数)

密钥对：
  公钥：(n, e)
  私钥：(n, d, p, q, dp, dq, qinv)   [含 CRT 参数]

标准体系

RSA 相关的国际标准构成了完整的规范体系，涵盖密钥格式、算法操作、签名方案和填充模式：

公钥指数选择

公钥指数 e 对性能有显著影响：

• e = 65537 (F₄)：工业默认值，兼顾安全性与加密效率，65537 = 2¹⁶ + 1，仅需 17 次模乘（16 次平方 + 1 次乘法）即可
• e = 3：加密仅需一次乘法，但易受低指数广播攻击（Hastad 攻击）和使用 CRT 时的故障攻击
• 随机大 e：无性能优势，与私钥 d 安全性等价于 d 不能过小（Wiener 攻击）

算法过程

密钥生成

安全遵循 FIPS 186-5 第 5.3 节：

1. 使用 CSPRNG 生成随机素数 p, q
   - 长度要求：n ≥ 2048 位（推荐 3072+）
   - 使用 Miller-Rabin 和 Lucas 素性测试
   - |p-q| > 2^(nLen/2-100) 防止 Fermat 因式分解

2. 计算模数 n = p × q
   - 满足 nLen = ⌈log₂(n)⌉（密钥长度表示）

3. 选择公钥指数 e
   - 标准值：65537 (0x010001)
   - 或使用随机大 e 但确保 gcd(e, φ(n)) = 1

4. 计算私钥指数 d = e⁻¹ mod φ(n)
   - 使用扩展欧几里得算法
   - 验证 d > 2^(nLen/2) 防止 Wiener 攻击

5. 计算 CRT 参数（解密加速 3-4 倍）：
   - dp = d mod (p-1)
   - dq = d mod (q-1)
   - qinv = q⁻¹ mod p

加密操作

RSAEP（RSA Encryption Algorithm）：

加密：c = m^e mod n    （m 为填充后的明文块）
解密：m = c^d mod n

CRT 优化解密步骤：
1. m₁ = c^dp mod p
2. m₂ = c^dq mod q
3. h = qinv × (m₁ - m₂) mod p
4. m = m₂ + h × q

块大小限制：

• 使用 OAEP+SHA-256：最大明文 = nLen/8 - 2×32 - 2 = nLen/8 - 66 字节
• 使用 PKCS#1 v1.5：最大明文 = nLen/8 - 11 字节

签名操作

RSASSA（RSA Signature Algorithm）包含两个主要方案：

RSASSA-PKCS1-v1_5：

EM = 0x00 0x01 [Padding(FF...FF)] 0x00 DER(Hash(M)) 0x00...
签名：s = EM^d mod n
验证：EM' = s^e mod n，比较 EM' == EM

• 确定性签名，无随机性
• 遗留方案，仍广泛使用但不再是首选

盐值 r ←$ {0,1}^sLen
M' = (0x)00 00 00 00 00 00 00 00 || H(M) || r
DB = Padding || 0x01 || r
dbMask = MGF(H(M'), maskedDBLen)
maskedDB = DB ⊕ dbMask
EM = maskedDB || H(M') || 0xBC
签名：s = EM^d mod n

• 概率性签名，每次签名值不同
• 可证明安全（随机预言机模型下）
• FIPS 186-5 推荐方案

填充模式原理

PKCS#1 v1.5（遗留填充）

加密时使用 0x00 0x02 + 非零随机填充 + 0x00 + 明文的结构。Bleichenbacher 在 1998 年利用错误消息反馈攻击恢复明文，后续变体（Manger 2001）仍未完全修复。当前部署要求服务器侧错误处理不分块。

OAEP（Optimal Asymmetric Encryption Padding）

OAEP 来自 Bellare 和 Rogaway 1994 年论文，通过 Feistel 结构引入不可预测性：

OAEP 编码（以 MGF1-SHA256 为例）：
1. 生成种子 seed ←$ HashLen (=32) bytes
2. lHash = Hash(L) (L = label, 通常为空)
3. PS = 0x00...0x00 (填充到 k-HashLen-1)
4. DB = lHash || PS || 0x01 || M
5. dbMask = MGF(seed, k-HashLen-1)
6. maskedDB = DB ⊕ dbMask
7. seedMask = MGF(maskedDB, HashLen)
8. maskedSeed = seed ⊕ seedMask
9. EM = 0x00 || maskedSeed || maskedDB

安全证明：若哈希函数为随机预言机，OAEP 在 IND-CCA2 模型下归约于 RSA 问题的不可解性。

PSS（Probabilistic Signature Scheme）

与 OAEP 类似结构，但操作方向相反（掩码作用于对消息的哈希值）：

PSS 编码参数：
- Hash: 默认 SHA-256
- MGF: 默认 MGF1-SHA-256
- sLen: 通常等于 HashLen (32)
- TrailerField: 常量 0xBC

安全优势：
- 每次签名盐值随机变化，签名值不可关联
- 抵御已知签名碰撞攻击
- 可证明安全

安全性分析

因式分解算法演进

实际安全评估：

• RSA-2048：截至 2026 年仍为商业安全最低要求
• RSA-3072：2030 年后推荐安全级别
• RSA-4096：高安全级别，非必要场景不建议使用

侧信道攻击

定时攻击（Kocher 1996）：

攻击原理：
- 测量 c^d mod n 的解密时间
- 推断 d 的比特位：若 decrypt(c × 2^e) 时间显著不同，说明 d 当前位为 1

缓解措施：
- 恒定时间解密（Barrett 约简）
- 盲化（blinding）：r ←$ ℤₙ*, c' = c·rᵉ, m' = (c')ᵈ, m = m'·r⁻¹

故障攻击（Boneh/DeMillo/Lipton 1997）：

攻击原理：
- 诱导计算 m₁ = c^dp mod p 或 m₂ = c^dq mod q
- 若 m₁ 错误而 m₂ 正确，则 gcd(m - m', n) = p

缓解措施：
- 验证签名/解密结果
- RSA 签名后 Verify(s^e == M)

其他攻击：

• Manger 攻击（针对 PKCS#1 v1.5 解密）
• 错误消息分析（Bardouin 2024 年 TLS 利用）
• ROCA / Minerva（弱密钥生成的硬件漏洞）

量子计算威胁

Shor 算法可在量子计算机上以多项式时间分解大整数，RSA-2048 面对实用量子计算机完全失效。根据 NIST SP 800-208 和业界路线图（Google 2029 Q-Day），RSA 需在量子计算机实用化前迁移到后量子密钥封装（KEM）方案。

RSA 与 SM2 对比

国密合规背景

在国密合规审查（密评）场景下：

• 非国密信息系统：RSA-2048 仍可接受
• 国密改造系统：SM2 为强制要求
• 混合证书策略：国际业务用 RSA/ECDSA，国内业务用 SM2
• 过渡方案：双证书体系（SM2/RSA 同时部署）

部署建议

加密应用

• 推荐：RSA-OAEP-SHA256（RFC 8017 §7.1）
• 密钥封装：RSA-KEM（NIST SP 800-56B Rev.2）
• 混合加密：RSA 加密临时对称密钥 + AES-256-GCM 加密数据
• 不推荐：裸 RSA（无填充），PKCS#1 v1.5 加密（遗留兼容除外）

签名应用

• 推荐：RSASSA-PSS-SHA256，盐长度 32 字节
• 遗留兼容：RSASSA-PKCS1-v1_5-SHA256（TLS 1.3 遗留支持）
• 证书签名：RSA-PSS-SHA256 为首选，CA/B 论坛已接受

密钥长度选择指南

当前（2026 年）：
  - 普通业务：RSA-2048（过渡方案）
  - 边界网关：RSA-3072
  - 数字证书：RSA-2048（2030 年前有效）
  - 长期签名：RSA-3072 + PSS

高合规场景：
  - 优先使用 SM2（国密强制要求）
  - 过渡期使用 RSA-3072
  - 同步规划 PQC 迁移

实现安全要求

• 恒定时间：所有核心操作必须恒定时间
• 盲化解密：每次解密前乘以随机 rᵉ
• 结果验证：解密后验证填充结构完整性
• 故障检测：签名生成后执行 1-2 次验证
• CSPRNG：使用经过验证的随机数生成器
• HSM 保护：生产场景使用硬件安全模块

总结

RSA 算法经过数十年工程验证，仍是当前公钥基础设施的支柱。掌握其数学原理、填充方案和安全边界，是密码工程师的基本功。面对国密合规和后量子技术演进，推荐策略为：

• 短期：RSA-3072-PSS-SHA256 作为兜底
• 中期：SM2 国密替代 + 混合过渡
• 长期：后量子密钥封装 (ML-KEM) 迁移

参考来源

• PKCS#1 v2.2: RSA Cryptography Specifications (RFC 8017, 2016) https://tools.ietf.org/html/rfc8017
• FIPS 186-5: Digital Signature Standard (DSS) (NIST, 2023)
• NIST SP 800-56B Rev. 2: Recommendation for Pair-Wise Key Establishment Using Integer Factorization Cryptography (2019)
• ISO/IEC 18033-2:2006 Information technology — Security techniques — Encryption algorithms — Part 2: Asymmetric ciphers
• Bleichenbacher, D. "Chosen Ciphertext Attacks Against Protocols Based on the RSA Encryption Standard PKCS #1" (CRYPTO 1998)
• Manger, J. "A Chosen Ciphertext Attack on RSA Optimal Asymmetric Encryption Padding (OAEP) as Standardized in PKCS #1 v2.0" (2001)

相关实践

• 国密 SM2 国密算法实战：从编译国密 OpenSSL 到生产级 TLS 部署全流程
• 国密 HTTPS 踩坑实录：从编译到上线的 12 个血泪教训

本文内容遵循 FIPS 186-5 和 RFC 8017 规范，代码示例建议使用 Python cryptography ≥ 42.0 和 pycryptodome ≥ 3.19。