从数学角度的 RSA 加密算法原理
1. 数学基础 - RSA 群
要理解 RSA，首先要理解抽象代数中的群（Group）。群是一个包含集合与二元运算的代数结构，必须满足四个条件：封闭性、结合律、存在单位元、存在逆元。
RSA 使用的是一个极其特殊的群：模 $n$ 的整数乘法群，记作 $\mathbb{Z}_n^$。任何一个从中选取的元素 $a$, $b$ 都满足 $a \cdot b \pmod n$ 仍然在 $\mathbb{Z}_n^$ 中，即
$$\forall a, b \in \mathbb{Z}_n^, (a \cdot b) \bmod n \in \mathbb{Z}_n^$$
那么如何构造一个满足 RSA 需求的 $\mathbb{Z}_n^*$ 群呢？这就引入了模数 $n$ 的构建。
1.1 核心参数的构建
模数 $n$： 选取两个极大的素数 $p$ 和 $q$，令 $n = p \cdot q$。
群的集合： 包含所有从 $1$ 到 $n-1$ 之间，且与 $n$ 互质的正整数。
群的大小（欧拉函数）： 根据欧拉函数，集合中元素的个数为 $\phi(n) = (p-1)(q-1)$。
1.2 举个简单的例子
假设 $p=3, q=5$，则 $n=15$，群大小 $\phi(15) = 8$。群集合为：
$$\mathbb{Z}_{15}^* = \lbrace 1, 2, 4, 7, 8, 11, 13, 14 \rbrace$$
在这个集合中任取元素进行模 15 乘法，结果永远在集合内（封闭性）；
例如 $7 \times 13 = 91 \equiv 1 \pmod{15}$。
2. RSA 核心机制 - 公钥、私钥与加解密
在 $\mathbb{Z}_n^*$ 群的框架下，RSA 的加解密变得极其简洁。为了直观展示，我们选取两个相对较小的素数：$p = 3$ 和 $q = 5$ ，也就是上面提到的例子。
2.1 密钥生成
计算模数 $n$ 与群大小 $\phi(n)$：
$n = p \times q = 15$
$\phi(n) = (p-1)(q-1) = 8$
公钥指数 $e$：
选择一个与 $\phi(n)$ 互质的数。例如 $e = 11$，则公钥为 $(e, n) = (11, 15)$。
私钥指数 $d$：
计算 $e$ 在模 $\phi(n)$ 下的乘法逆元，满足 $e \cdot d \equiv 1 \pmod{\phi(n)}$。例如 $d = 3$，则私钥为 $(d, n) = (3, 15)$.
2.2 加解密过程
假设你要向我发送一个极其机密的数字明文 $M = 2$（注意，要求 $0 \leq M < n$）。
加密过程（使用公钥）：
公式：$C \equiv M^e \pmod n$
代入：$C \equiv 2^{11} \pmod{15} = 8 $
解密过程（使用私钥）：
公式：$M \equiv C^d \pmod n$
代入：$M \equiv 8^3 \pmod{15} = 2$
2.3 为什么解密能成功？
这得益于群论中的欧拉定理：对于群内的任意元素 $M$，都有 $M^{\phi(n)} \equiv 1 \pmod n$。在我们这个例子中，也就是 $2^{8} \equiv 1 \pmod{15}$
由于我们在生成密钥时，刻意让 $e \times d \equiv 1 \pmod{\phi(n)}$。
因此：
$$C^d = (M^e)^d = M^{e \cdot d} = M^{k \cdot \phi(n) + 1} = (M^{\phi(n)})^k \cdot M^1 \quad (k \in \mathbb{N})$$
而根据欧拉公式：
$$ (M^{\phi(n)})^k \cdot M^1 = (cn + 1)^k \cdot M^1 \quad (c \in \mathbb{N})$$
处理 $ (cn + 1)^k $ ，我们需要用到二项式定理：
$$ (cn + 1)^k = \sum_{i=0}^{k} C^i_k (cn)^i \cdot 1^{k-i}$$
我们可以将上式轻轻的展开为：
$$ C^0_k (cn)^0 \cdot 1^{k-0} + \sum_{i=1}^{k} C^i_k (cn)^i \cdot 1^{k-i}$$
也就是：
$$ 1 + \sum_{i=1}^{k} C^i_k (cn)^i \cdot 1^{k-i}$$
由于$\sum_{i=1}^{k} C^i_k (cn)^i \cdot 1^{k-i}$的每一项都包含 $n$，因此原式可以简化为：
$$ (cn + 1)^k = 1 + A \cdot n \quad (A \in \mathbb{N})$$
所以：
$$C^d = (cn + 1)^k \cdot M^1 = (1 + A \cdot n) \cdot M = M + A \cdot M \cdot n \equiv M \pmod n$$
3. 安全性分析 - RSA 的数学难题
假设一个攻击者想要破解 RSA，他们需要从公钥 $(e, n)$ 中推断出私钥 $d$。这就涉及到一个核心的数学问题：大整数分解问题。
回忆一下，想要获取私钥 $d$，攻击者首先需要知道 $\phi(n)$，而 $\phi(n)$ 的计算依赖于 $p$ 和 $q$ 的值。由于 $n = p \cdot q$，攻击者必须分解 $n$ 来找到 $p$ 和 $q$。
对于小的 $n$，分解是相对容易的，但随着 $n$ 的增大，分解的难度呈指数级增长。当前已知的算法，如一般数域筛选法（GNFS），在处理数百位的 $n$ 时需要极其庞大的计算资源。因此，RSA 的安全性在很大程度上依赖于选择足够大的 $p$ 和 $q$。
4. 需要注意的细节
4.1 明文的限制
RSA 要求明文 $M$ 必须满足 $0 \leq M < n$。因此，在 TLS 实际应用中，是通过 RSA 算法来加密一个随机生成的对称密钥，通过对称密钥来加密实际的通信数据。
其次，算法要求是对群内的任意元素 $M$ 进行运算，事实上，群内的元素是与 $n$ 互质的整数，也就是与 $p$ 和 $q$ 都不共享任何因数的整数，而 $M$ 恰好不和 $p$ 和 $q$ 互质的概率很低。其次，数学计算能够证明，就算 $ M \notin \mathbb{Z}_n^* $，加密和解密过程仍然能够成功。