前言
RSA（Rivest–Shamir–Adleman）算法是一种公钥加密算法，过程主要经历 钥生成，钥分发，加密和解密。
钥分发，加密和解密 比较简单。
思想
如果我们能找到三个大数 $e, d, n$，满足对于任意 $0 \leq x < n$，都有
$$\left(x^e\right)^d \bmod n = x$$
那么，我们把 $e$ 和 $n$ 作为公钥，$d$ 作为私钥，即可解密。
注意到在给出 $e$ 和 $n$ 的情况下找到一个这样的 $d$ 几乎不可能。
钥生成
- 选择两个大质数 $p$ 和 $q$
为了让分解更加困难，$p$ 和 $q$ 应当随机地选择。并且不要太接近。 - 计算 $n = pq$
$n$ 为模数，RSA 的位数就指的是这个 $n$ 的位数。
$n$ 作为公钥的一部分发布。 - 计算 $\lambda\left(n\right)$
$\lambda\left(n\right)$ 为 Carmichael 函数。
因为 $n = pq$，$\lambda\left(n\right) = \operatorname{lcm}\left(\lambda\left(a\right), \lambda\left(b\right)\right)$。
将 $\lambda\left(n\right)$ 保密。 - 选择一个 $1 < e < \lambda\left(n\right)$，并且要求 $e$ 与 $\lambda\left(n\right)$ 互质。
目前 RSA 算法一般选择 $e = 2^{16} + 1$
$e$ 作为公钥的一部分发布。 - 计算 $d$，$d$ 为 $e$ 在模 $\lambda\left(n\right)$ 意义下的逆元。
$d$ 为私钥。
我们来证明 $\left(x^e\right)^d \bmod n = x$。
如果我们证明 $\left(x^e\right)^d \bmod p = x$ 且 $\left(x^e\right)^d \bmod q = x$，那么原来模 $n$ 也成立。
因为 $ed \bmod \lambda\left(pq\right) = 1$，且 $\lambda\left(pq\right) = \operatorname{lcm}\left(p - 1, q - 1\right)$，因此 $ed - 1 = k\left(p - 1\right)$，其中 $k$ 是整数。
因此在模 $p$ 的意义下，$x^{ed} = x^{ed - 1} \cdot x = x^{k\left(p - 1\right)} \cdot x = x$。
模 $q$ 同理。