重要
RSA安全性基于质因数分解困难性：p × q = N 容易，但 N → p, q 极难。
核心：欧拉定理保证解密有效，模反元素保证加解密互逆。
变量速查
| 变量 | 说明 | 公开性 |
|---|---|---|
| p, q | 两个大质数 | 私密 |
| N | N = p × q（模数） | 公开 |
| T | T = (p-1)×(q-1)（欧拉函数φ(N)） | 私密 |
| E | 公钥指数（与T互质） | 公开 |
| D | 私钥指数（D×E ≡ 1 mod T） | 私密 |
密钥对： 公钥(E, N)，私钥(D, N)
核心洞察（记忆锚点）
真相一句话
RSA 用同一个 T 把欧拉函数、模反元素、欧拉定理串成闭环：φ(N) 算出 T，模反用 T 当模数得 D，欧拉定理用 T 当指数得 1，三个 T 必须同源，加密才能被解密；而 T 又依赖 p、q，不分解 N 就拿不到 T，安全性由此成立。
T 的几何含义： T 正是指数运算的循环区间，指数每隔 T，结果都对 N 同余（即 明文^(指数+T) ≡ 明文^指数 (mod N)）。所有"指数加减 T 不影响结果"的推导，根源都在这。
三个概念围绕 T 的分工
承接 T 的循环周期身份，三个概念各司其职：
- 欧拉函数 φ：算出 T 的具体数值（T = (p-1)(q-1)）
- 欧拉定理：声明"指数每隔 T 循环一次"（明文^T ≡ 1 mod N）
- 模反元素：在循环规则下，构造出 E×D 恰好落在 1 上的 D（D×E ≡ 1 mod T）
| 概念 | 角色 | 核心式子 |
|---|---|---|
| 欧拉函数 φ(n) | 给出 T | T = φ(N) = (p-1)(q-1) |
| 欧拉定理 | 给出循环规则 | a^T ≡ 1 (mod N) |
| 模反元素 | 给出落点 | D×E ≡ 1 (mod T) |
关键观察： T 的双重身份（欧拉定理的指数 + 模反方程的模数）不是巧合，而是硬约束——欧拉定理只在指数为 T 的整数倍时给出 ≡ 1，要让 E×D 在指数上等价于 1，模反方程的模数就必须等于 T，否则两边接不上，证明断链。
点击展开：T 如何串联欧拉定理 + 模反元素（推导细节）
前置工具： 同余的同次幂性质 —— 若 a ≡ b (mod N)，则 a^k ≡ b^k (mod N)，这是把"加密+解密"合并成单一指数的代数基础。
完整推导：
┌─ 第1步：加密同余式 ────────────────────────────────────┐ │ 密文 = 明文^E mod N ⇔ 密文 ≡ 明文^E (mod N) │ ├─ 第2步：两边 D 次方（同次幂性质）─────────────────────┤ │ 密文^D ≡ (明文^E)^D ≡ 明文^(E×D) (mod N) │ │ ⇒ 终极命题：明文^(E×D) ≡ 明文 (mod N) 待证 │ ├─ 第3步：T 第一次出场（模反元素：T 当模数）───────────┤ │ D×E ≡ 1 (mod T) ⇒ E×D = k×T + 1 │ │ 代入指数：明文^(E×D) = (明文^T)^k × 明文 │ ├─ 第4步：T 第二次出场（欧拉定理：T 当指数）───────────┤ │ 明文^T ≡ 1 (mod N) │ │ ⇒ 明文^(E×D) ≡ 1^k × 明文 ≡ 明文 (mod N) ✓ │ └────────────────────────────────────────────────────────┘
T 的串联作用：
模反元素 欧拉定理
(T 当模数) (T 当指数)
│ │
E×D ─────────────→ E×D = k×T + 1 ──────→ 明文^(k×T+1)
│
= (明文^T)^k × 明文
│
= 1^k × 明文
│
= 明文 ✓模反元素把 T 塞进指数（E×D = k×T + 1），欧拉定理再把含 T 的指数项 明文^T 消成 1。两次都是同一个 T，证明才能接上。
数值验证移到 §4.2，本节专注概念串联。
点击展开：反例 - 如果 T 不同源会怎样
假设步骤 1、2 用了正确的 T = φ(N) = 20，但步骤 3 错误地使用另一个数 T’ = 18 来套欧拉定理。
正常情况（T 同源 = 20）：
| |
错误情况（T’ = 18，与模反方程的 T 不一致）：
| |
结论： T 必须是 φ(N)，且必须在"模反元素的模数"和"欧拉定理的指数"两处同时使用，缺一不可。这就是为什么 RSA 的私钥 D 一旦泄露 T（或 p、q），整个系统立即破防。
1.数学基础
1.1 质数与余数
质数： 只能被1和自身整除的数（2, 3, 5, 7, 11…）
余数与模运算：
| |
模运算示例：
| |
1.2 欧拉函数
定义： φ(n) = [1, n] 范围内与 n 互质的元素个数
简要解释： [1, n]中不与n互质的数只有p的倍数和q的倍数，排除后剩余个数正好是(p-1)×(q-1)
关键性质： 当 n = p × q（p、q都是质数）时
| |
点击展开：为什么 φ(p×q) = (p-1)×(q-1)
详细推导：
在 [1, p×q] 范围内，不与 p×q 互质的数有哪些？
p的倍数：p, 2p, 3p, …, (q-1)p, qp
- 共 q 个
q的倍数：q, 2q, 3q, …, (p-1)q, pq
- 共 p 个
p×q 被计算了两次，需要减回来
所以：
| |
示例验证：
| |
1.3 欧拉定理
如果 a 与 n 互质，则：
| |
示例：
| |
这是RSA解密正确性的理论基础。
2.密钥生成
步骤 计算过程
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
[步骤1] 选择两个质数
p = 3, q = 11
└───┐ │
[步骤2] 计算N和T ↓ ↓
N = p × q = 3 × 11 = 33 ──────────┐
T = (p-1) × (q-1) = 2 × 10 = 20 │
│ │
(T：用于选E算D) ────────────────────────────┘ │
| │ │
[步骤3] 选择公钥指数E ↓ │ │
(满足: 1<E<T 且互质) │ │
E = 7 ────────────────────┐ │ │
验证: 1 < 7 < 20 ✓ │ │ │
gcd(7, 20) = 1 ✓ │ │ │
│ │ │
(E：用于算D) ────────────────────────────┘ │ │
| ┌──────────────┘ │
[步骤4] 计算私钥指数D ↓ ↓ │
(D是E在模T下的模反元素) D × E ≡ 1 (mod T) ──┐ │
D × 7 ≡ 1 (mod 20) │ │
试算: 7×1=7 ❌ │ │
7×2=14 ❌ │ │
7×3=21≡1 ✓ │ │
↓ │ │
┌──────────────────── D = 3 │ │
(组成私钥)│ (组成公钥) ┌─┘ │
[结果] 密钥对生成完成 ↓ ↓ │
私钥: (D, N) = (3, 33), 公钥: (E, N) = (7, 33) │
↑ ↑ │
└───────────────────────────────────────────┘关键点：
- p、q → 计算 N 和 T（两个质数是基础）
- T → 用于选择 E 和计算 D（欧拉函数是桥梁）
- E、T → 计算 D（模反元素关系）
- N → 同时出现在公钥和私钥中（模数）
点击展开：D的计算方法
D 的计算： 找到 D 使得 D×E mod T = 1
| |
实际应用中使用扩展欧几里得算法计算D，可以高效找到模反元素。
3.加密解密
加密公式： 密文 = 明文^E mod N
解密公式： 明文 = 密文^D mod N
3.1 加密流程
步骤 计算过程
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
[输入] 明文与公钥
明文 = 2
公钥 (E, N) = (7, 33)
┌─┘ │
[公式] 应用加密公式 ↓ ↓
密文 = 明文^E mod N
│ ┌─┘ ┌─┘
[计算] 代入数值 ↓ ↓ ↓
密文 = 2^7 mod 33
(先计算幂) ──────────────────┤
= 128 mod 33
(再取模) ────────────────────────┤
= 29
┌───┘
[输出] 密文 ↓
密文 = 293.2 解密流程
步骤 计算过程
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
[输入] 密文与私钥
密文 = 29 (来自加密输出)
私钥 (D, N) = (3, 33)
┌──┘ │
[公式] 应用解密公式 ↓ ↓
明文 = 密文^D mod N
│ ┌─┘ ┌─┘
[计算] 代入数值 ↓ ↓ ↓
明文 = 29^3 mod 33
(先计算幂) ───────────────────┤
= 24389 mod 33
(再取模) ─────────────────────────┤
= 2
┌──────┘
[输出] 明文 ↓
明文 = 2 ✓ 与原始明文一致关键观察：
- 加密的输出（密文29）= 解密的输入
- 解密的输出（明文2）= 加密的输入
- 公钥E和私钥D是互逆的
4.解密正确性证明
4.1 已知条件
证明前需要的数学工具：
条件1：欧拉函数公式
| |
条件2：欧拉定理
| |
条件3：模反元素定义（D和E的关系）
| |
条件4：加密解密公式
| |
点击展开：同余等式的关键性质（推导前置工具）
证明用到 3 个同余性质，这里先列出来，证明时直接引用。
性质1：同余的定义
| |
两种写法表达同一件事：a 除以 N 余 b。
性质2：同次幂保持同余（关键）
| |
通俗说：两个数模 N 同余，它们的同次幂也模 N 同余。这条性质让我们可以"两边同时取幂"而不破坏同余关系。
示例：
| |
性质3：指数运算法则（与同余无关，普通幂运算）
| |
把嵌套的幂展平成单个指数，是把"加密再解密"合并成 明文^(E×D) 的代数基础。
为什么 RSA 必须用同余视角而不是普通等式？
走"加 k×N"的普通等式路线：
| |
走同余路线：
| |
后者一步到位，这就是 RSA 证明全程使用同余记号的原因。
4.2 证明过程
承接： 由加密公式 密文 ≡ 明文^E (mod N)，两边 D 次方得 密文^D ≡ 明文^(E×D) (mod N)（用到性质 2）。解密做的就是 密文^D mod N，所以"解密回到明文"等价于证明：
需要证明： 明文^(E×D) ≡ 明文 (mod N)
证明：
由 D×E ≡ 1 (mod T)，可写成 D×E = k×T + 1
| |
根据欧拉定理：明文^T ≡ 1 (mod N)（因为 T = φ(N)）
所以：
| |
最终：
| |
本节是 §核心洞察 折叠推导块的展开版：前者用紧凑符号串联 4 步；本节给出严谨语言论证 + 完整数值代入。
数值验证（E=7, D=3, T=20, N=33, 明文=2）：
| |
5.安全性
5.1 破解难度
已知： N, E（公开）
要破解： 求出 D
破解路径：
| |
困难点： 质因数分解
当N是2048位时，分解需要300万亿年（当前计算能力）。
5.2 密钥长度
| 长度 | 安全级别 | 说明 |
|---|---|---|
| 1024位 | 低 | 已不推荐 |
| 2048位 | 中 | 当前标准 |
| 4096位 | 高 | 高安全场景 |
6.实际应用
6.1 HTTPS中的RSA
RSA在HTTPS中主要承担两个角色：
| 用途 | 说明 |
|---|---|
| 密钥交换 | 客户端用服务器RSA公钥加密预主密钥，仅服务器私钥可解 |
| 数字签名 | CA用RSA私钥签名服务器证书，客户端用CA公钥验证 |
完整TLS握手流程、证书链验证、会话密钥派生等内容，参考：Https流程说明
6.2 RSA vs ECDHE
| 特性 | RSA | ECDHE |
|---|---|---|
| 性能 | 慢 | 快 |
| 密钥长度 | 2048位 | 256位 |
| 前向保密 | ❌ | ✅ |
| TLS 1.3 | 仅签名 | 密钥交换 |
6.3 为什么不直接用RSA加密数据？
- 性能差： RSA比AES慢1000倍
- 长度限制： 一次只能加密少量数据
实际方案： RSA协商密钥 + AES加密数据
7.总结
| |
Reference
RSA算法原理（一）
RSA算法原理（二）
RFC 8017 - PKCS #1: RSA Cryptography Specifications
