密码学是个很枯燥的学科，如果看到某一个地方卡住了，欢迎回来重新读，或者直接在评论区提问

为什么需要 RSA？

想象你和一个朋友要在网络上说悄悄话。
你们可以用同一把钥匙（密码）把消息锁起来、再解开——这叫做对称加密。
但问题来了：这同一把钥匙，你们俩怎么安全地互相传递？ 如果一开始就能安全传钥匙，那直接传秘密消息不就行了？

1977 年，Rivest、Shamir 和 Adleman 三个人提出一个惊人的想法：

干脆不要同一把钥匙了，用一对钥匙——一个公开的、一个私密的。
用公开钥匙加密的消息，只能用私有钥匙解开。

这就是非对称加密，RSA 就是最经典的一种。

关键思路是：找到一个数学“单向陷门函数”——正向计算很容易，反向计算极难，除非你掌握了特殊的秘密信息（私钥）。

同时也是 https 证书认证机制的思想

RSA 有 3 把钥匙和 3 个阶段

RSA 有三个核心角色：

1. 公钥 (n, e)：谁都可以拿到，用来加密。

2. 私钥 (d)：绝对秘密，用来解密。

3. 模数 n：公钥和私钥都包含它，它是一个巨大的整数，也是所有运算的“世界边界”。

使用 RSA 有三个阶段：

1. 密钥生成：选两个巨大素数，用它们算出 n、e、d。

2. 加密：把明文 m 变成密文 c，公式是 c = m^e mod n。

3. 解密：把密文 c 变回明文 m，公式是 m = c^d mod n。

下面我们一点点把他拆开来学习：

第一阶段：密钥生成

选择两个大素数 p 和 q

这不是随便选的。
现实中，p 和 q 都至少有几百个十进制位长，它们必须严格保密。

为什么要素数？
因为素数的特殊性质能让后面的模运算有一个非常漂亮的“周期”，这是正确解密的保证。
下面使用简化后的 python 代码进行演示

p = 61 # 实际上的 p 不应该这么简单，至少也是几百位
q = 53

计算模数 n

$$n=p\times q$$

n 虽然是公开的，但它应该是极难被分解回 p 和 q 的。
如果 n 比较简单，有人能够轻易分解，那么这个 rsa 就是不安全的
对于目前来说 2048 位的 n 做分解，要想获得正确的 p 和 q 全世界最快的计算机也要花比宇宙当前寿命还长的时间进行计算。

n = p * q
print(f"模数 n = {n}")   # 输出 3233

计算欧拉函数值

这里出现一个陌生的名字：欧拉函数
下面拓展一些相关的基础知识：

• 欧拉函数：设 m 是一个正整数，则在小于 m 的正整数中与 m 互质的整数个数记为$\phi (m)$ ，叫做欧拉函数
• 若 p 是素数，则 $\phi (p)=p-1$
• 若 m 和 n互质，则$\phi (mn)=\phi (m)\phi (n)=(m-1)(n-1)$
• 欧拉定理：设 m 是大于 1 的整数，如果 a 满足 $gcd(a,m)=1$，则：$a^{\phi (m)}\equiv 1(modm)$

在 RSA 场景里，因为 n 是两个素数乘积，有一个极其简单的公式：

$$\phi (n)=(p-1)(q-1)$$

φ(n) 表示“从 1 到 n 里，有多少个数与 n 互质”。
因为 n 只有两个质因数 p 和 q，计算起来就特别简单。

注意：φ(n) 必须保密。
如果敌人知道了 ϕ(n)，他就能轻易从公钥推出私钥。

phi = (p - 1) * (q - 1)
print(f"欧拉函数 phi = {phi}")   # 输出 3120

选公钥指数 e

我们要选一个 e，满足两个条件：

• 1 < e < ϕ(n)

• e 和 φ(n) 互质（最大公约数为 1）

实际中，e 通常选 65537，因为它二进制里只有两个 1，做幂运算很快，而且被验证安全性很好。

# 手工选一个符合条件的 e，这里选 17（保证 gcd(17, 3120) = 1）
e = 17
import math
assert math.gcd(e, phi) == 1, "e 必须与 phi 互质"

计算私钥指数 d

这是整个密钥生成里最关键的一步，
我们要找一个 d，使得：

$$e\times d\equiv 1(mod\phi (n))e\times d\equiv 1(mod\phi (n))$$

也就是

在模 φ(n) 的世界里，d 就是 e 的“倒数”。
e 乘上 d 的积除以 φ(n) 的余数为 1

既然 e 和 φ(n) 互质，这种“模倒数”一定存在且唯一。
用 python 代码表示就是：

d = pow(e, -1, phi)   # Python 3.8+ 内置模逆计算
print(f"私钥指数 d = {d}")   # 输出 2753

# 验证一下：e*d mod phi 应该等于 1
print((e * d) % phi)  # 输出 1

其中 pow(e,-1,phi) 这段代码就是获取 d 的一个运算，具体讲述起来比较麻烦，读者可以自行查找资料了解，如果不深究，记住便可。其内置算法为扩展欧几里得算法，不用担心时间复杂度

现在：

• 公钥：(n, e) —— 可以张贴在大街公告栏上。
• 私钥：(n, d) （其实 p、q、φ(n) 也要销毁或严密保管）。

第二阶段：上锁（加密）

假设别人拿到你的公钥 (n, e)，想给你发一条消息 m。
但 m 必须是一个小于 n 的整数。
现实里消息很长怎么办？用分块、填充等手段处理，我们先看原理。

加密公式极其简单：

$$c=m^e\mathrm{mod}n$$

也就是：把明文 m 做 e 次方，然后除以 n 取余数，得到密文 c。

# 明文消息：必须是整数且小于 n
m = 123
assert m < n, "明文必须小于模数 n"

# 加密：使用 Python 内置的 pow 进行快速模幂运算
c = pow(m, e, n)
print(f"明文 {m} -> 密文 {c}")   # 输出 855

算这个东西很快，因为有一种“快速幂取模”算法，不需要真的算出巨大的 m^e 再取模

关键点：

• 知道了 c、e、n，想反推出 m 异常困难——这是 RSA 困难问题的核心：求模 n 下的 e 次根，等价于分解 n。

第三阶段：开锁（解密）

你收到密文 c 之后，用自己的私钥 d 计算：
$$m=c^d\mathrm{mod}n$$

# 解密：只有拥有私钥 d 的人才能做到
m_dec = pow(c, d, n)
print(f"密文 {c} -> 解密后明文 {m_dec}")   # 输出 123，完美恢复

把 c = m^e mod n 代入，看上去像是在做：
$$m=(m^e{)}^d\mathrm{mod}n=m^{ed}\mathrm{mod}n$$
所以 RSA 能工作的核心原因就是：m 经过 ed 次方再取模 n 之后，回到了 m 自己。

换句话说，数字 m 在以 n 为模的世界里，存在一个“幂运算的循环周期”，而 ed 恰好满足“绕一圈回到原地”。

这正是下一节要证明的。

为什么解密能够完美恢复明文？

我们需要证明：
$$m^{ed}\equiv m\mathrm{mod}n$$
因为 e 和 d 满足 e * d ≡ 1 mod φ(n)，所以存在整数 k 使得：
$$ed=1+k\phi (n)$$
即证明：
$$m^{1+k\phi (n)}\equiv m\mathrm{mod}n$$
再根据则可得：
$$m^{\phi (n)}\equiv 1\mathrm{mod}n(当m与n互质时)$$
最后得到的结果，正是欧拉定理

[!NOTE] 关键解释
$ed=1+k\phi (n)$ => $m^{ed}\equiv m\mathrm{mod}n$
= $m^{1+k\phi (n)}\equiv m\mathrm{mod}n$
= $m(m^{\phi (n)}{)}^k\equiv m\ast 1\mathrm{mod}n$
= $m^{-1}m(m^{\phi (n)}{)}^k\equiv m^{-1}m\mathrm{mod}n$ (m 和 n互质的情况下)
= $m^{\phi (n)}\equiv 1\mathrm{mod}n$
注：$m^{-1}$ 是 m 的逆元，不是 m 的-1次方

如果 m 和 n 不互质怎么办？

你可能马上会问：“那万一 m 和 n 不互质怎么办？RSA 岂不是会解密失败？”

这正是 RSA 证明里更精妙的地方：

• n 只有 p 和 q 两个质因数，m 又小于 n，所以 m 如果不与 n 互质，那 m 就一定是 p 或 q 的倍数。
• 这种情况不能直接用欧拉定理，但可以分别对模 p 和模 q 去验证解密公式，再利用中国剩余定理合并回来。
• 最终结论：对任意 0 ≤ m < n，RSA 解密公式都必然成立。

所以，我们解释“本质是除 m”时，通常是针对互质的大多数情况给出直觉。严谨的完整证明会单独处理不互质的边界情况。

为什么 RSA 很难被破解？

RSA 的安全性基于一个信念：

从 (n, e) 求出 d 或者从 c 恢复 m，在计算上几乎不可能，除非你能分解 n 得到 p 和 q。

现在公认：

• 512 位 RSA 已经可被暴力分解。

• 1024 位处于“政府级攻击可能”的边缘。

• 2048 位 RSA 目前安全，预计至少维持到 2030 年。

可能的攻击路线（不分解 n）：

• 数学捷径攻击：利用实现错误（e 太小、d 太小、共用 n 等）。

• 侧信道攻击：不破数学，而是通过计时、功耗等物理信息窃取私钥。

• 量子计算机：Shor 算法能在多项式时间内分解大数，未来可摧毁 RSA。
  这也是业界正在向抗量子密码迁移的原因。

但对正确实现的 RSA-2048 来说，今天没有公开可行的破解方法。

完整的 python 脚本演示

下面是一个基础的 python 脚本演示，不是最终的 rsa，只体现了大部分的思想，还有一些其他操作没有实现，如果感兴趣，请读者自行查找相关资料

import math

# ========== 1. 密钥生成 ==========
# 选择两个大素数（仅演示用小素数）
p = 61
q = 53
n = p * q
phi = (p - 1) * (q - 1)

# 选择公钥指数 e，要求与 phi 互质
e = 17
assert math.gcd(e, phi) == 1, "e 必须与 phi 互质"

# 计算私钥指数 d（模逆）
d = pow(e, -1, phi)

print("=== RSA 密钥 ===")
print(f"公钥 (n={n}, e={e})")
print(f"私钥 (n={n}, d={d})")
print()

# ========== 2. 加密 ==========
m = 123   # 明文，必须小于 n
print(f"原始明文: {m}")
c = pow(m, e, n)
print(f"加密后密文: {c}")

# ========== 3. 解密 ==========
m_dec = pow(c, d, n)
print(f"解密后明文: {m_dec}")
print(f"解密成功: {m == m_dec}")

运行输出：

=== RSA 密钥 ===
公钥 (n=3233, e=17)
私钥 (n=3233, d=2753)

原始明文: 123
加密后密文: 855
解密后明文: 123
解密成功: True

签名过程

rsa 也可以用来进行数字签名，其实就是相较于加密来说，反过来了。
加密就是：谁都可以修改，但是不能够解密
签名就是：谁都可以签名，但是不能修改

• 发送方用自己的私钥 d 对消息的哈希值进行“加密”运算，得到签名。
• 接收方用发送方的公钥 e 对签名进行“解密”运算，得到哈希值，再与收到的消息哈希对比。

RSA 的一些局限性

1. 极慢且膨胀：运算速度比对称加密慢成百上千倍，只能用来包裹对称密钥；密钥和密文体积大，占用带宽和存储。
2. 绝对不能“裸用”：教科书式 RSA 是确定性的，必须加上安全的填充方案（如 OAEP），否则易受低指数攻击、选择密文攻击等。
3. 量子末日威胁：Shor 算法能在量子计算机上多项式时间分解大整数，RSA 的数学根基将被彻底摧毁。
4. 前向安全性缺失：传统 RSA 密钥交换不提供前向安全，私钥一旦泄露，所有历史会话都能被解密。
5. 实现极其脆弱：依赖强随机数生成，否则多设备可能共享素数因子而被批量破解；还需防范时序、功耗等侧信道攻击。
6. 与椭圆曲线比已无优势：同等安全强度下，ECC 的密钥更短、计算更快、签名更紧凑，现代协议多优先选择 ECC。

鸣谢：
[1].密码学基础 | RSA算法详解及证明 - 知乎