从两个素数 p、q 生成密钥对 (n, e, d)，实现平文 m 的加密和解密的 RSA 概念演示。使用教育用小规模数值，以手工可追踪的水平体验公钥密码的工作原理。
参数设置
素数 p
—
素数 q
—
公开指数 e
—
平文 m
—
如果 p、q 不是素数，将被舍入到最近的素数。e 需要满足 gcd(e, φ(n)) = 1。
计算结果
—
公开模数 n=p·q
—
欧拉函数 φ(n)
—
秘密指数 d
—
密文 c=m^e mod n
密钥对与加密流
左＝密钥对 (n, φ, e, d)／右＝加密流 m → [^e mod n] → c → [^d mod n] → m'
理论·主要公式
RSA 是以素因数分解的困难性为安全基础的公钥密码。密钥生成按以下步骤进行。
选择两个素数 p、q，计算公开模数和欧拉函数：
$$n = p\,q, \qquad \varphi(n) = (p-1)(q-1)$$
公开指数 e 与 φ(n) 互质：gcd(e, φ(n)) = 1。秘密指数 d 是 e 在模 φ(n) 意义下的逆元（用扩展欧几里得算法计算）：
$$e\,d \equiv 1 \pmod{\varphi(n)}$$
加密和解密都用模 n 下的幂运算进行：
$$c = m^{e} \bmod n, \qquad m' = c^{d} \bmod n$$
前提条件为 0 ≤ m < n。根据费马-欧拉定理，m' = m 被保证成立。
RSA 密码模拟器是什么
🙋
我听说过 RSA 这个名字，但最终它是在做什么？我打开了这个模拟器，出现了很多数字，有点吓到我了。
🎓
简单来说，就是秘密地拥有两个素数 p、q，只公开它们的乘积 n = p·q。在模拟器的初始值中，p=11，q=13，所以 n=143。虽然任何人都能看到 n，但从 n 进行"素因数分解"来找出原始的 p、q 非常困难，这就是安全性的原理。看看"密钥对"的框，应该能看到 n 和 e 是公开的，而 p、q、d 是秘密的，都用不同颜色区分了。
RSA 是在模 n 下进行计算的，所以平文 m 必须满足 0 ≤ m < n。比如 p=3, q=5，那么 n=15，而 m=42 显然超出范围。这种情况下，即使加密了，解密也只能恢复"m mod n"，无法回到原始的 42。需要增大 p、q 使得 n 超过 100，或者让 m 更小。实际实现中，长消息通常会被分割成"小于 n 的块"进行加密，或与对称密钥密码组合使用。
实际应用
HTTPS / TLS 的密钥交换和签名：当浏览器连接网站时显示的"锁形图标"背后，RSA 被广泛用于服务器证书签名验证和通信初期的共同密钥交换。沿着证书链向上查找，会发现根 CA 的公钥进行的 RSA 签名。
PGP / GnuPG 的电子邮件加密和签名：个人和企业使用 RSA 密钥对来进行电子邮件的加密和签名，以及软件发布的签名（如 Linux 发行版的包签名等）。这类长期维护身份的用途与 RSA 的特性很吻合，人们用指纹（fingerprint）来验证密钥身份的文化已经根深蒂固。