4. RSA算法详解：密钥生成、加密、解密、数字签名与填充方案
RSA算法是1977年由Ron Rivest、Adi Shamir和Leonard Adleman提出的非对称密码体制，其安全性基于大整数分解的困难性。作为端到端加密设计中应用最广泛的公钥算法之一，RSA同时支持加密保密性和数字签名认证两大核心功能。本节将系统阐述RSA的数学原理、密钥生成流程、加解密运算、签名验证机制以及关键的填充方案。
4.1 数学基础与核心原理
RSA的安全性依赖于两个数学难题：大整数分解问题（给定大合数N，求其素因子p和q）和RSA问题（给定公钥(N, e)和密文c，求明文m使得me ≡ c mod N）。目前，当密钥长度≥2048位时，这两个问题在计算上被认为是不可行的。
| 数学概念 | 符号 | 作用 |
|---|---|---|
| 大素数 | p, q | 密钥生成的基础，长度通常为1024位或以上 |
| 模数 | N = p × q | 公钥和私钥的公共模数，长度即密钥长度 |
| 欧拉函数 | φ(N) = (p-1)(q-1) | 用于计算私钥指数d |
| 公钥指数 | e | 通常取65537（0x10001），满足1 < e < φ(N)且gcd(e, φ(N))=1 |
| 私钥指数 | d ≡ e-1 mod φ(N) | 解密和签名时使用的秘密指数 |
关键安全约束： p和q必须独立随机生成，且|p-q|不能过小；e必须与φ(N)互素；d必须保密且长度接近N的比特长度。任何一项不满足都会导致安全强度下降。
4.2 密钥生成流程
RSA密钥生成是算法安全性的第一道防线。以下步骤必须使用密码学安全的随机数生成器（CSPRNG）执行：
- 选择大素数： 随机生成两个长度相近的大素数p和q（例如各1024位，构成2048位密钥）。
- 计算模数： N = p × q。N的长度即为RSA密钥长度。
- 计算欧拉函数： φ(N) = (p-1)(q-1)。
- 选择公钥指数： 选取e，满足1 < e < φ(N)且gcd(e, φ(N)) = 1。标准推荐值为65537。
- 计算私钥指数： 使用扩展欧几里得算法计算d ≡ e-1 mod φ(N)。
- 输出密钥对： 公钥 = (N, e)，私钥 = (N, d)。
工程实践： 实际实现中，私钥通常还包含p、q、dP = d mod (p-1)、dQ = d mod (q-1)和qInv = q-1 mod p，用于通过中国剩余定理（CRT）加速解密和签名运算，速度提升约4倍。
4.3 加密与解密运算
RSA的加解密基于模幂运算。明文m必须小于N，且与N互素（概率极高）。实际使用中，m是经过填充后的消息编码。
| 操作 | 公式 | 输入 | 输出 |
|---|---|---|---|
| 加密 | c = me mod N | 明文m，公钥(N, e) | 密文c |
| 解密 | m = cd mod N | 密文c，私钥(N, d) | 明文m |
正确性证明： 由于ed ≡ 1 mod φ(N)，存在整数k使得ed = 1 + kφ(N)。根据欧拉定理，当gcd(m, N)=1时，mφ(N) ≡ 1 mod N，因此cd ≡ med ≡ m1+kφ(N) ≡ m × (mφ(N))k ≡ m mod N。
4.4 数字签名与验证
RSA数字签名本质上是“反向使用”加解密：用私钥签名，用公钥验证。这利用了RSA的对称性——加密和解密互为逆运算。
- 签名生成： 发送方对消息m的哈希值H(m)进行签名运算：s = H(m)d mod N。签名s与原始消息m一起发送。
- 签名验证： 接收方使用发送方的公钥(N, e)计算：H(m)' = se mod N。比较H(m)'与本地计算的H(m)是否相等。
安全警告： 不要直接对原始消息m进行签名！必须使用密码学哈希函数（如SHA-256）对消息摘要进行签名。直接签名容易遭受选择明文攻击和存在性伪造攻击。
4.5 填充方案：从PKCS#1到OAEP与PSS
教科书式RSA（无填充）存在严重的安全缺陷：确定性加密、小指数攻击、共模攻击等。填充方案将确定性加密转化为概率性加密，并引入结构化编码以抵御攻击。
| 填充方案 | 应用场景 | 特点 | 安全强度 |
|---|---|---|---|
| PKCS#1 v1.5 | 加密 | 兼容性好，但存在Bleichenbacher攻击风险 | 中等（需额外防护） |
| OAEP（最优非对称加密填充） | 加密 | 基于Feistel网络，提供IND-CCA2安全 | 高（推荐） |
| PKCS#1 v1.5 | 签名 | 简单，但存在哈希长度扩展风险 | 中等 |
| PSS（概率签名方案） | 签名 | 提供可证明安全性，抵抗选择消息攻击 | 高（推荐） |
4.5.1 OAEP填充（加密场景）
OAEP使用两个哈希函数G和H，通过Feistel网络结构将明文m与随机数r混合，确保相同的明文每次加密产生不同的密文。OAEP在随机预言机模型下可证明满足IND-CCA2安全。
OAEP填充过程（k0为随机数长度，k1为零填充长度）：
1. 将消息m填充至n-k0-k1位：m' = m || 0...0
2. 选择随机数r（k0位）
3. 计算：X = m' ⊕ G(r)
4. 计算：Y = r ⊕ H(X)
5. 输出：填充后的消息 = X || Y4.5.2 PSS填充（签名场景）
PSS同样引入随机数，使签名结果具有概率性。PSS在随机预言机模型下可证明抵抗适应性选择消息攻击（EUF-CMA）。
PSS签名填充过程：
1. 计算消息哈希：mHash = Hash(M)
2. 生成随机数salt（通常与哈希输出等长）
3. 构造：M' = 0x00 || 0x01 || mHash || salt
4. 计算：H = Hash(M')
5. 构造数据块：DB = 0x00...0x01 || salt
6. 计算：maskedDB = DB ⊕ MGF(H, emLen - hLen - 1)
7. 输出：填充块 = maskedDB || H || 0xBC4.6 工程实现要点
| 实现环节 | 推荐做法 | 常见错误 |
|---|---|---|
| 模幂运算 | 使用蒙哥马利模乘或滑动窗口法 | 直接使用Python内置pow()（性能差） |
| CRT加速 | 私钥操作使用中国剩余定理 | 未使用CRT导致解密速度慢4倍 |
| 侧信道防护 | 实现常数时间比较和固定窗口指数 | 未防护导致计时攻击泄露私钥 |
| 密钥存储 | 使用HSM或安全飞地（TEE） | 私钥明文存储在文件系统 |
| 随机数生成 | 使用操作系统提供的CSPRNG | 使用rand()或自建随机数 |
性能数据参考（Intel Xeon 3.0GHz，2048位RSA）：
• 公钥操作（加密/验证）：约 0.1-0.3 ms/次
• 私钥操作（解密/签名，无CRT）：约 5-10 ms/次
• 私钥操作（解密/签名，有CRT）：约 1-3 ms/次
• 密钥生成：约 0.5-2 秒（取决于素数检测算法）
• 公钥操作（加密/验证）：约 0.1-0.3 ms/次
• 私钥操作（解密/签名，无CRT）：约 5-10 ms/次
• 私钥操作（解密/签名，有CRT）：约 1-3 ms/次
• 密钥生成：约 0.5-2 秒（取决于素数检测算法）
4.7 安全强度与密钥长度演进
随着计算能力的提升和因数分解算法的进步，RSA密钥长度需要持续增长。NIST SP 800-57给出了明确的密钥强度对应关系：
| 安全强度（比特） | RSA密钥长度（位） | 等效对称密钥 | 推荐使用期限 |
|---|---|---|---|
| 80 | 1024 | 2TDEA（3DES） | 已不推荐 |
| 112 | 2048 | 3TDEA（3DES） | 至2030年 |
| 128 | 3072 | AES-128 | 至2035年 |
| 192 | 7680 | AES-192 | 长期 |
| 256 | 15360 | AES-256 | 长期 |
迁移建议： 对于新建系统，建议直接使用3072位RSA或迁移至椭圆曲线密码（ECC，如Curve25519/Ed25519），后者在同等安全强度下密钥更短、运算更快。RSA-2048在2025年后应逐步淘汰。