原理详解：
RSA 是怎么工作的？

先想明白要造什么

回忆锁盒类比：我们要造一对「数学上配套」的钥匙——公钥公开加密，私钥独自解密，且外人无法从公钥推出私钥。RSA 的天才之处是找到了这样一对数字关系，它的原料是两样人人熟悉的东西：

• 素数：把两个大素数相乘一瞬间；把乘积拆回素数近乎永恒（正易反难的不对称）。
• 模运算：乘方之后只留余数，把天文数字压回固定范围，像钟表永远只显示 1–12 点。

密钥生成：五个步骤

1. 挑两个素数 p 和 q这是你的秘密核心，只有你知道。真实 RSA 里它们各约 300 位十进制长；教学演示中用 11、13 这类小素数即可。
2. 算乘积 n = p × qn 将公开（它是「锁」的一部分）。同时算 φ(n) = (p−1) × (q−1)，这是一个关键中间量，必须保密。
3. 选公钥指数 e挑一个与 φ(n) 互质（没有公因数）的数，常用 65537。公钥 = (e, n)，广而告之。
4. 算私钥指数 d找到 d，使得 (e × d) mod φ(n) = 1。d 是 e 在「φ(n) 世界」里的逆——只有知道 p、q 的人才能算出 φ(n)，从而才能算出 d。
5. 销毁中间量公钥 (e, n) 张贴出去；私钥 d 保密；p、q 和 φ(n) 用完即毁。锁与钥匙就此分家。

加密与解密：一条公式的故事

先把要发送的内容变成一个数字 m（比如字母按编码表转成数字），要求 m < n。然后：

先别急着问为什么能还原——直接感受一下数字（p=3, q=11, n=33, φ=20, e=3, d=7，发送 m=4）：

• 加密：c = 4³ mod 33 = 64 mod 33 = 31。原文 4 变成了面目全非的 31。
• 解密：m = 31⁷ mod 33 = 27,512,614,111 mod 33 = 4。原文完好归来。

为什么加密后必然能解回来？

背后是 18 世纪数学家欧拉发现的一条定律（欧拉定理）的推论，用大白话说：

在「mod n 的钟表世界」里，只要 e 和 d 配套（e×d ≡ 1 mod φ(n)），那么「用 e 转过的钟，再用 d 转回去，指针必然回到原位」：m 的 e 次方再 d 次方，等价于 m 的 (e×d) 次方，而 e×d 在 φ(n) 世界里等于 1，于是结局必然是 m。

e×d ≡ 1 (mod φ(n)) 这句话就是「配套」的数学定义：它是第 4 步生成 d 时唯一的要求。所以 RSA 不是「碰巧能解回来」，而是构造性地保证能解回来——d 从一开始就是按「解铃人」的身份算出来的。

顺带回答一个常见疑惑：「加密用 e、解密用 d，那用 d 加密、e 解密行不行？」行——这正是数字签名的原理：私钥「加密」= 签名，公钥「解密」= 验证签名（详见现实应用）。

三个诚实的附注

• 教学 RSA ≠ 工业 RSA：真实系统不会对文本逐字符加密，而是配合随机填充（OAEP）与混合加密，防止重放与模式泄露。实验室为了让人算得懂做了极简处理，区别在哪见现实应用。
• m 必须 < n：钟表盘只有 n 个刻度，超出就会「截断」。真实 RSA 的 n 巨大，所以能整块处理 256 字节数据。
• 素数必须随机挑选：若两人生成密钥时用了同样的 p、q，私钥就一样了。真实系统用密码学随机数挑素数，这曾是某些设备的真实漏洞来源。