RSA（Rivest–Shamir–Adleman）是一种著名的非对称密钥加密算法（Asymmetric Key Cryptography），也是目前为止最常用、最重要的公钥加密算法之一。该算法由三位科学家 Rivest、Shamir 和 Adleman 在 1977 年共同提出，并以他们姓氏的首字母命名为 RSA。RSA的目标是让加密容易、解密极难(除非拥有私钥)。RSA 是现代密码学中最经典、最重要的 非对称加密算法 之一，被广泛应用于 HTTPS、安全通信、数字签名、软件验证等场景。RSA已成为现代密码学与网络安全体系的重要基石。

本文将从基础概念出发，帮助你以简单清晰的方式理解 RSA 的原理、结构和使用方式。

1. 什么是 RSA？

RSA（Rivest–Shamir–Adleman）是一种 公钥加密算法，特点是使用 不同的密钥 完成加密和解密。与传统的对称加密（如 AES、DES）不同，RSA 不要求通信双方在开始时提前共享密钥。

公钥（public key）：公开给任何人，用来加密或验证签名
私钥（private key）：由本人保管，用来解密或签名

特点：

加密和解密使用不同的密钥
安全性基于 “大整数质因数分解困难”
可用于加密和数字签名

常见用途：

应用场景	RSA 的作用
HTTPS	握手阶段用于安全交换密钥
数字证书	验证网站或用户身份
数字签名	验证消息是否被篡改
加密通信	对重要数据加密

常用的 RSA 密钥长度：

密钥长度	安全等级（2025）	还能安全用到哪年？	典型用途
1024 bit	完全死亡	2015 年已死	禁止使用
2048 bit	勉强可用（过渡期）	≈2030 年下线	部分老系统、兼容性证书
3072 bit	安全（推荐最低）	≈2040 年	当前主流
4096 bit	过度安全	2050 年后	政府、银行、根证书

2. RSA工作原理

选两个大素数 p 和 q（保密！）
计算 n = p × q（公开）
计算 φ(n) = (p−1)(q−1)（保密）
选一个 e（通常是 65537），满足和 φ(n) 互质
计算 d，使得 d × e ≡ 1 (mod φ(n)）→ 这就是私钥
公开 (n, e)，保密 (n, d)

加密：密文 = 明文ᵉ mod n

解密：明文 = 密文ᵈ mod n

举例：

p = 61, q = 53 → n = 61×53 = 3233
φ(n) = 60×52 = 3120
选 e = 17（常用）
算出 d = 2753（因为 17×2753 = 1 mod 3120）

公钥：(3233, 17)
私钥：(3233, 2753)

明文 123 加密：
123¹⁷ mod 3233 = 855  → 密文

解密：
855²⁷⁵³ mod 3233 = 123  → 回到原文

3. RSA数学理论基础

RSA 的核心理论依赖以下数学基础：

欧拉函数（Euler’s Totient Function）

对于一个正整数 n，其欧拉函数 φ(n) 表示：

1 ≤ x ≤ n 中与 n 互质的整数个数

若 n = p × q（p, q 为质数）：

φ(n) = (p - 1)(q - 1)

模幂运算（Modular Exponentiation）

RSA 涉及计算：

c = m^e mod n
m = c^d mod n

使用快速幂算法（Binary Exponentiation / Montgomery Ladder）可在 O(log e) 时间内求解。

模逆元（Modular Inverse）

RSA 私钥 d 需要满足：

d × e ≡ 1 (mod φ(n))

可用扩展欧几里得算法（Extended Euclidean Algorithm）求得。

RSA 正确性证明

证明 RSA 解密确实能恢复原文 m。

已知：

c = m^e mod n
m = c^d mod n = (m^e)^d mod n = m^(ed) mod n

若：

ed ≡ 1 (mod φ(n))

即：

ed = 1 + k φ(n)

则：

m^(ed) = m^(1 + k φ(n)) = m × (m^φ(n))^k

由于欧拉定理：

m^φ(n) ≡ 1 (mod n)

可得：

m^(ed) ≡ m mod n

因此 RSA 解密总能得到原文。

4. RSA 安全性的数学来源

RSA 的安全性并未严格证明，而是依赖以下难题的“经验性难解性”：

大整数质因数分解问题（Integer Factorization Problem）

给定：

n = p × q

在 p、q 为 1000+ 位质数时，当前算法无法在可接受时间内分解 n。

RSA 假设（RSA Assumption）

给定：

c = m^e mod n

即使知道 (n, e)，求 m 依然困难。

5. 填充、编码与标准规范

裸 RSA（raw RSA）是极不安全的，原因：

可被选择密文攻击（CCA）
存在可预测结构
同样的明文加密结果一致

因此必须使用安全填充。

5.1 现代常用填充

填充模式	用途	标准	是否推荐	理由
PKCS#1 v1.5 Padding	签名/历史用途	RFC 2313	禁止	易受 Bleichenbacher、亿次攻击
OAEP (Optimal Asymmetric Encryption Padding)	加密	RFC 8017	强烈推荐	抗选择密文攻击（IND-CCA2）
PSS (Probabilistic Signature Scheme)	数字签名	RFC 8017	唯一推荐签名方式	抗存在性伪造
RSA-KEM		ISO 18033-2	推荐（新协议）	更现代、更安全

5.2 为什么 OAEP 安全？

OAEP 使用：

随机种子 r
两层 hash 函数
异或掩码扩展（mask generation function）

确保：

加密结果不可预测
防止数学结构漏洞
满足 IND-CCA2 安全

注意：所有新系统必须使用 OAEP + PSS，禁止 v1.5 填充。

6. 性能优化与工程实现

RSA 并非直接使用高精度整数进行全量运算，而要使用优化技术：

6.1 快速模幂：蒙哥马利乘法（Montgomery Multiplication）

现代 RSA 使用：

Montgomery reduction
Barrett reduction

实现 O(log n) 高效模幂运算。

6.2 CRT 优化（中国剩余定理）

私钥解密可使用：

m1 = c^(d mod (p-1)) mod p
m2 = c^(d mod (q-1)) mod q

再合并：

m = CRT(m1, m2)

速度提升约 3–4 倍。

6.3 常见实现库

OpenSSL（最广泛）
BoringSSL（Chrome 使用）
libsodium
mbedTLS

6.4 RSA在线工具

RSA在线加密解密工具：RSA加密解密

7. 常见攻击与脆弱性分析

7.1 数学攻击

低指数攻击

当 e = 3 且消息过短时：

c = m^3

可能在整数域直接开立方根得到 m。

Hastad’s Broadcast Attack

相同明文用相同 e 发送给 k ≥ e 个接收者时，可通过 CRT 解出原文。

分解 n 的改进算法

算法	复杂度	状态
ECM	exp(√log n log log n)	有效
NFS	sub-exponential	当前最强攻击

7.2 实现攻击

定时攻击（Timing attack）
功耗分析（Power Analysis）
Cache side-channel（例如 Spectre/L1TF）
故障注入攻击（Fault Attack）

7.3 填充攻击

最著名：Bleichenbacher Attack（1998） 针对 PKCS#1 v1.5，导致大量 TLS 服务器被攻破。

7.4 历年最著名 RSA 因式分解记录

年份	位数	名称	耗时/成本	方法
1999	512 bit	RSA-155	几千台 PC，7 个月	GNFS
2010	768 bit	RSA-768	2 年级算力	GNFS
2020	829 bit	RSA-250	~2700 CPU·年	GNFS
2024	847 bit	RSA-260	约 3500 CPU·年	CADO-NFS
预计	1024 bit	—	2030 前后可能被分解	经典算法
预计	2048 bit	—	2035–2042（数千万美元级）	经典算法

7.5 实际攻击情况

攻击类型	目标密钥长度	是否实用（2025）	备注
因式分解（GNFS/CADO）	≤ 847 bit	已全破	1024 bit 理论可行但成本极高
小私钥指数攻击	d < N⁰.²⁹²	常见低危漏洞	OpenSSL 曾有此问题
共模攻击	多个证书共用 p/q	曾大面积爆发	ROCA 漏洞影响 Infineon 芯片
侧信道（功率、缓存、故障注入）	任意长度	物理访问即破	智能卡、TPM 最怕
Padding Oracle（PKCS#1 v1.5）	任意长度	极高危	Bleichenbacher 攻击
Quantum Shor 算法	任意长度无关	2035 年前不可能	一旦实用，所有 RSA/ECC 瞬间死亡

8. RSA 应用场景

8.1 HTTPS 握手

TLS 1.2 及以前使用：

RSA 加密交换对称密钥
RSA 签名验证服务器身份

TLS 1.3 已废弃 RSA 加密握手只保留 RSA-PSS 用于签名。

8.2 数字证书

证书链验证使用：

RSA 签名（PSS 或 PKCS#1 v1.5）
SHA 系列摘要

8.3 软件签名

Windows Update
Linux 包管理器（APT/RPM）
Apple App 签名

8.4 主流系统RSA使用现状

系统 / 协议	当前 RSA 长度	填充方式	迁移状态
TLS 1.3	3072–4096	OAEP/PSS	已强制禁用 RSA 密钥交换（只剩签名）
OpenSSH	3072+	PSS	推荐 ed25519
OpenVPN	4096	OAEP	正在迁移 P-256 / Kyber
Windows Code Signing	3072–4096	PSS	2026 强制 SHA-384 + PSS
Apple iOS / macOS	3072–4096	PSS	已支持 post-quantum 混合证书
中国金融 SM2 证书	256 bit 等价	SM2 签名	完全替代 RSA

9. 量子计算时代的 RSA

量子算法：

Shor’s Algorithm（1994）

可在多项式时间分解大整数 → 完全破解 RSA。

但现实状况：

需要数百万逻辑量子比特
远未达到工程实现

RSA 面临的未来风险

密钥长度	量子下安全性
1024 bit	即刻失效
2048 bit	理论上可破解
4096 bit	延缓被破解时间

未来方向： 后量子密码学（PQC）如：CRYSTALS-Kyber、Dilithium、NTRU、Falcon，这些算法已被 NIST 标准化，将替代 RSA。

迁移线路图：

年份区间	推荐方案	备注
2025–2027	继续使用 3072/4096 RSA + 引入混合证书（RSA + Kyber-768）	兼容性最佳
2027–2030	新证书默认 Kyber-768 + Dilithium 或纯 PQ	Chrome/Apple 已宣布
2030–2035	完全禁用 RSA 密钥交换，仅保留签名过渡	NIST 预计时间线
2035 以后	RSA 彻底退役	只剩考古价值

10. 总结与展望

RSA 作为现代密码学的里程碑：

基于稳固的数学假设
理论简单、工程成熟
在 TLS、数字签名、证书体系中发挥核心作用

但与此同时：

质因数分解算法不断进步
量子计算对其构成潜在威胁
PKCS#1 v1.5 等旧标准仍导致安全事故

RSA 正在被谁取代？

新算法	密钥长度	性能	安全性	现状
ECC（椭圆曲线）	256–384 bit	快 5–10 倍	等同或更高	主流推荐（Ed25519、P-256）
SM2	256 bit	快	等同 ECC	中国国密强制
格密码（Kyber）	768–1024 字节	稍慢	抗量子	2025–2030 过渡期，部分已上线

常见问题（FAQ）

Q：RSA 会被量子计算机秒破吗？

A：是的！量子计算机的 Shor 算法可以直接分解大整数，所有传统 RSA、ECC 都会瞬间死亡。但 2025 年实用量子计算机还很远。

Q：现在还敢用 RSA 吗？

A：敢！在 2035 年前，3072/4096 bit RSA 仍然安全。但新系统建议直接上抗量子算法（Kyber + Dilithium）。

Q：RSA 加密大文件行不行？

A：不行！RSA 只能加密很小数据（< 密钥长度）。大文件必须用“混合加密”：RSA 换对称密钥 + AES 加密正文。

RSA 深度解析:原理、数学基础、编码与安全性

目录