密钥生成

取两个大素数 $p,q$，令 $n=pq$、$\varphi(n)=(p-1)(q-1)$。选公钥指数 $e$ 与 $\varphi(n)$ 互素，求私钥 $d\equiv e^{-1}\pmod{\varphi(n)}$。公钥 $(n,e)$，私钥 $(n,d)$。

加密与解密

$c=m^e\bmod n,\qquad m=c^d\bmod n$
正确性由欧拉定理：$ed\equiv1\pmod{\varphi(n)}$ 故 $m^{ed}\equiv m\pmod n$。公钥加密、私钥解密，且无需事先共享密钥。

安全基础

破解需从公开的 $n$ 还原 $p,q$（即大整数分解），目前无高效经典算法；密钥取 2048+ 位即安全。注意：教科书 RSA 须配 OAEP 填充才抗实际攻击。

例题

例　$p=3,q=11\Rightarrow n=33,\varphi=20$；取 $e=7$，则 $d=3$（$7\times3=21\equiv1\bmod20$）。加密 $m=2$：$c=2^7\bmod33=29$；解密 $29^3\bmod33=2$ ✓。

应用

RSA 撑起 HTTPS 证书、数字签名、安全邮件几十年。现实多用「混合加密」：RSA 只用来安全传输对称密钥，真正的大量数据用 AES 加密——兼顾安全与速度。