RSA 加密算法

1. 概述

RSA 由罗纳德·李维斯特（Ronald Rivest）、阿迪·萨莫尔（Adi Shamir）和伦纳德·阿德曼（Leonard Adleman）于 1977 年提出，并在 1978 年发表原始论文；“RSA”来自三人姓氏的首字母。它是最早获得广泛应用的公钥算法之一，把公钥加密与数字签名从概念变成了可实现的方案。

RSA 主要用于加密少量密钥材料、生成数字签名，以及支撑数字证书、软件签名和 PKI 信任体系。PKCS #1 / RFC 8017 至今仍在规范 RSA 的加密与签名方案，NIST FIPS 186-5 也纳入了 RSA 数字签名。

Alice 要给 Bob 发送消息，她先获取 Bob 公开的公钥，再用公钥加密消息。密文可以通过公网传输，但只有 Bob 本地的私钥能恢复原文。

2. 问题

RSA 首先要解决的不是“怎样把消息算成一串数字”，而是一个通信难题：双方只能通过公网联系时，如何建立不依赖预先共享秘密的保密通信？

2.1 明文通过公网会发生什么

Alice 要通过公网给 Bob 发送“明天 10 点开会”。如果这句话以明文传输，攻击者可能读到它，也可能把“10 点”替换成“11 点”。

公网通信需要同时满足三个目标：

• 机密性：攻击者不能读懂消息。
• 完整性：Bob 能够发现消息被修改。
• 身份可信：Bob 能够确认消息确实来自 Alice。

加密首先解决机密性，防篡改和确认身份还需要其他机制。

2.2 共享一把密钥可以保护消息吗

一个直接方法是：Alice 先把密钥交给 Bob，随后用这把密钥加密消息；Bob 收到密文后，再用同一把密钥解密。加密和解密依赖同一个共享秘密，这就是对称加密。

对称加密计算快，适合保护大量数据。但它把问题向前推了一步：如果 Alice 和 Bob 只能通过公网联系，Alice 如何安全地把密钥交给 Bob？

如果密钥在传递或保管时泄露，攻击者就可以读取由它保护的消息。当通信对象增多时，密钥的分发、保管和更换也会越来越复杂。

2.3 能否只公开加密方法

密钥分发困难，是因为加密和解密共享同一个秘密。如果把它们拆成两把不同的密钥，就可以只公开加密所需的部分。

Bob 先在本地生成一对密钥：

• 公钥可以公开，任何人都能获取。
• 私钥只保留在 Bob 本地，不通过网络发送。

Alice 获取 Bob 的公钥，用它加密消息，然后通过公网发送密文。公钥可以生成密文，却不能直接用来解密；只有 Bob 本地的私钥能恢复原文。这就是非对称加密。

非对称加密避免了在通信前传递秘密密钥，但也带来了新问题：

• 公钥和私钥为什么能完成相反的运算？
• 公钥已经公开，为什么不能由它轻易算出私钥？
• Alice 怎样确认拿到的公钥真的属于 Bob？
• 非对称加密计算较慢，如何保护较长的消息？

RSA 利用数论构造这种公私钥关系，并把由公钥反推私钥的困难建立在大整数分解问题上。

3. 原理

RSA 的核心不是让公钥和私钥执行两种完全相反的计算，而是为两次模幂运算选择一对特殊的指数，使第二次运算能够抵消第一次运算。欧拉定理解释了这种抵消为什么成立。

3.1 公钥和私钥需要满足什么条件

RSA 先把消息编码为整数 $m$，并要求 $0\le m<n$。使用公钥指数 $e$ 加密：

$$c\equiv m^e\pmod n$$

再使用私钥指数 $d$ 解密：

$$m'\equiv c^d\equiv m^{ed}\pmod n$$

因此，问题可以归结为：怎样选择 $e$ 和 $d$，才能保证

$$m^{ed}\equiv m\pmod n$$

RSA 采用的条件是：

$$ed\equiv1\pmod{\varphi(n)}$$

其中 $\varphi(n)$ 是欧拉函数。这个条件为什么有效，需要从互质和简化剩余系说起。

3.2 什么是欧拉函数和简化剩余系

如果两个整数的最大公约数为 1，就称它们互质：

$$\gcd(a,n)=1$$

欧拉函数 $\varphi(n)$ 表示小于 $n$ 且与 $n$ 互质的正整数个数。这些整数模 $n$ 的余数组成一个简化剩余系。

例如，小于 10 且与 10 互质的正整数是：

$$R=\{1,3,7,9\}$$

因此 $\varphi(10)=4$。将其中每个数乘以一个与 10 互质的数 3，再对 10 取模：

$$\{3,9,21,27\}\equiv\{3,9,1,7\}\pmod{10}$$

结果仍然是 $\{1,3,7,9\}$，只是顺序发生了变化。这个重排性质正是欧拉定理成立的关键。

3.3 欧拉定理为什么成立

欧拉定理指出：如果 $\gcd(a,n)=1$，那么

$$a^{\varphi(n)}\equiv1\pmod n$$

设模 $n$ 的一个简化剩余系为：

$$R=\{r_1,r_2,\ldots,r_{\varphi(n)}\}$$

将每个元素乘以 $a$，得到：

$$aR=\{ar_1,ar_2,\ldots,ar_{\varphi(n)}\}$$

要证明 $aR$ 只是 $R$ 的重排，需要确认两件事。

第一，每个 $ar_i$ 仍然与 $n$ 互质。因为 $a$ 和 $r_i$ 都与 $n$ 互质，它们的乘积也与 $n$ 互质，所以 $ar_i$ 对 $n$ 取模后仍属于简化剩余系。

第二，不同元素相乘后不会得到相同的余数。假设

$$ar_i\equiv ar_j\pmod n$$

由于 $\gcd(a,n)=1$，$a$ 在模 $n$ 下存在乘法逆元，因此等式两边可以消去 $a$：

$$r_i\equiv r_j\pmod n$$

简化剩余系中的余数互不相同，所以只有 $i=j$ 时等式才成立。因此，$aR$ 中的 $\varphi(n)$ 个元素既都属于简化剩余系，又互不重复，只能是 $R$ 的一次重排。

重排不会改变所有元素的乘积，所以：

$$(ar_1)(ar_2)\cdots(ar_{\varphi(n)}) \equiv r_1r_2\cdots r_{\varphi(n)} \pmod n$$

整理左侧：

$$a^{\varphi(n)}r_1r_2\cdots r_{\varphi(n)} \equiv r_1r_2\cdots r_{\varphi(n)} \pmod n$$

每个 $r_i$ 都与 $n$ 互质，因此它们的乘积在模 $n$ 下存在逆元，可以从等式两边消去，最终得到：

$$a^{\varphi(n)}\equiv1\pmod n$$

3.4 RSA如何生成相互配合的公钥和私钥

RSA 选择两个不同的大质数 $p$ 和 $q$，并计算：

$$n=pq$$

因为小于 $n$ 的整数中，不能与 $n$ 互质的数一定是 $p$ 或 $q$ 的倍数，所以：

$$\varphi(n)=(p-1)(q-1)$$

接着选择与 $\varphi(n)$ 互质的公钥指数 $e$，再求出 $e$ 在模 $\varphi(n)$ 下的乘法逆元 $d$：

$$ed\equiv1\pmod{\varphi(n)}$$

这个同余式等价于存在整数 $k$，使得：

$$ed=1+k\varphi(n)$$

扩展欧几里得算法可以求出满足

$$ed+\varphi(n)y=1$$

的一组整数系数，其中 $d$ 对 $\varphi(n)$ 取模后的最小正整数就是私钥指数。

3.5 为什么私钥能够还原明文

先考虑 $m$ 与 $n$ 互质的情况。将 $ed=1+k\varphi(n)$ 代入解密结果：

$$\begin{aligned} m^{ed} &=m^{1+k\varphi(n)}\\ &=m\left(m^{\varphi(n)}\right)^k \end{aligned}$$

根据欧拉定理，$m^{\varphi(n)}\equiv1\pmod n$，所以：

$$m^{ed}\equiv m\pmod n$$

例如，取 $p=5$、$q=11$，则 $n=55$、$\varphi(n)=40$。选择 $e=3$，通过扩展欧几里得算法得到 $d=27$：

$$3\times27=81=1+2\times40$$

如果消息为 $m=7$，加密结果为：

$$c\equiv7^3\equiv13\pmod{55}$$

解密时：

$$c^{27}\equiv(7^3)^{27}=7^{81}\equiv7\pmod{55}$$

消息因此被还原。

3.6 消息与模数不互质怎么办

上面的推导使用了欧拉定理，所以要求 $\gcd(m,n)=1$。但 RSA 不能假定每条消息都与 $n$ 互质，还需要补全这种情况。

因为 $n=pq$，可以分别在模 $p$ 和模 $q$ 下判断。以模 $p$ 为例：如果 $p\mid m$，那么 $m^{ed}$ 和 $m$ 模 $p$ 都等于 0；如果 $p\nmid m$，则可以根据费马小定理得到 $m^{p-1}\equiv1\pmod p$，仍有 $m^{ed}\equiv m\pmod p$。

模 $q$ 的结论相同。因此，$m^{ed}-m$ 同时是 $p$ 和 $q$ 的倍数。由于 $p$、$q$ 是不同的质数，它也是 $pq=n$ 的倍数，所以对所有消息都有：

$$m^{ed}\equiv m\pmod n$$

这说明 RSA 的加密和解密能够相互抵消；欧拉定理给出主要结构，分别对 $p$、$q$ 讨论则补全了非互质消息的情况。

3.7 能否通过公钥破解RSA

攻击者能够获得公钥 $(n,e)$ 和密文 $c$，但不知道组成 $n$ 的质数 $p$、$q$。最直接的通用破解方法是先分解 $n$，再按照正常的私钥生成过程恢复 $d$：

1. 将 $n$ 分解为 $p\times q$。
2. 计算 $\varphi(n)=(p-1)(q-1)$。
3. 计算 $e$ 在模 $\varphi(n)$ 下的逆元，得到私钥指数 $d$。
4. 计算 $m\equiv c^d\pmod n$，恢复消息。

NIST SP 800-56B 给出的 RSA 基本密钥形式也是公钥 $(n,e)$、私钥 $(n,d)$，其中 $n=pq$，而 $p$、$q$ 必须保密。

在前面的示例中，$n=55$ 很容易被分解为 $5\times11$。攻击者随后得到 $\varphi(n)=40$，再由 $3d\equiv1\pmod{40}$ 求出 $d=27$，便可以解密密文。真实 RSA 使用极大的质数，目的就是让第一步无法在可接受时间内完成。

如果依次尝试不超过 $\sqrt n$ 的因数，试除法的时间复杂度是：

$$O(\sqrt n)$$

若 $n$ 的二进制长度为 $L$，则 $n\approx2^L$，复杂度可以写成：

$$O\left(2^{L/2}\right)$$

实际分解大型 RSA 模数不会使用试除法。目前已知最快的通用经典算法是通用数域筛，其启发式时间复杂度为：

$$\exp\left( \left(\sqrt[3]{\frac{64}{9}}+o(1)\right) (\ln n)^{1/3}(\ln\ln n)^{2/3} \right)$$

它比 $O(\sqrt n)$ 快，但相对于输入长度 $L=\log_2n$ 仍不是多项式时间。分解出 $p$、$q$ 后，计算 $\varphi(n)$、求 $d$ 和解密都可以高效完成，因此破解过程的主要成本集中在大整数分解。

这只描述了密钥正确生成、协议正确使用时的数学攻击。弱随机数、重复质数、错误填充和侧信道泄露可能绕过大整数分解，直接暴露私钥或明文。

3.8 RSA破解的代码实现

下面的代码实现上一节的破解过程：先分解 $n$，再计算 $\varphi(n)$ 和私钥指数 $d$，最后通过快速模幂恢复明文。

这段代码只适用于题目刻意给出的较小模数。真实 RSA 的模数无法使用试除法在可接受时间内完成分解。

#include <iostream>
#include <tuple>
#include <utility>

using i64 = long long;
using ExtGcdResult = std::tuple<i64, i64, i64>;

// 返回 (g, x, y)，满足 g = a * x + b * y
ExtGcdResult ext_gcd(i64 a, i64 b) {
  i64 r0 = a, x0 = 1, y0 = 0;
  i64 r1 = b, x1 = 0, y1 = 1;

  while (r1 != 0) {
    i64 q = r0 / r1;
    std::tie(r0, x0, y0, r1, x1, y1) =
        std::make_tuple(
            r1, x1, y1,
            r0 % r1, x0 - q * x1, y0 - q * y1
        );
  }

  return {r0, x0, y0};
}

// 求 a 在模 mod 下的乘法逆元
i64 mod_inverse(i64 a, i64 mod) {
  auto [g, x, y] = ext_gcd(a, mod);
  if (g != 1) {
    return -1;
  }
  return (x % mod + mod) % mod;
}

// 计算 base^exponent mod mod
i64 mod_pow(i64 base, i64 exponent, i64 mod) {
  i64 result = 1 % mod;
  base %= mod;

  while (exponent > 0) {
    if (exponent & 1) {
      result = static_cast<__int128>(result) * base % mod;
    }
    base = static_cast<__int128>(base) * base % mod;
    exponent >>= 1;
  }

  return result;
}

// 试除分解 n = p * q
std::pair<i64, i64> factorize(i64 n) {
  if (n % 2 == 0) {
    return {2, n / 2};
  }

  for (i64 p = 3; p <= n / p; p += 2) {
    if (n % p == 0) {
      return {p, n / p};
    }
  }

  return {0, 0};
}

// 已知公钥 (n, e) 和密文 c，恢复明文 m
i64 decrypt(i64 n, i64 e, i64 c) {
  auto [p, q] = factorize(n);
  if (p == 0) {
    return -1;
  }

  i64 phi = (p - 1) * (q - 1);
  i64 d = mod_inverse(e, phi);
  if (d == -1) {
    return -1;
  }

  return mod_pow(c, d, n);
}

int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);

  i64 n, e, c;
  while (std::cin >> n >> e >> c) {
    std::cout << decrypt(n, e, c) << '\n';
  }
}

分解 $n$ 需要 $O(\sqrt n)$ 次试除；扩展欧几里得算法和快速模幂分别需要 $O(\log\varphi(n))$ 和 $O(\log d)$ 次迭代。因此，总时间复杂度由分解过程主导：

$$O(\sqrt n)$$

附录

A.1 扩展欧几里得算法

扩展欧几里得算法的核心是：欧几里得算法产生的每个余数，始终是原始整数 $a$ 和 $b$ 的线性组合。 普通欧几里得算法只保留余数，扩展欧几里得算法同时记录这个线性组合的两个系数。

练习：洛谷 P1082「同余方程」。题目要求计算 $ax\equiv1\pmod b$ 的最小正整数解，本质是从 $ax+by=1$ 中求出 $a$ 的系数 $x$。

余数如何递推

令欧几里得算法最初的两个数为：

$$r_0=a,\qquad r_1=b$$

每轮进行带余除法：

$$r_{i-1}=q_i r_i+r_{i+1}$$

因此，下一个余数为：

$$r_{i+1}=r_{i-1}-q_i r_i$$

其中：

$$q_i=\left\lfloor\frac{r_{i-1}}{r_i}\right\rfloor$$

当余数变为 0 时停止，最后一个非零余数就是 $\gcd(a,b)$。

线性组合的系数如何递推

假设每个余数都写成 $a$ 和 $b$ 的线性组合：

$$r_i=x_i a+y_i b$$

最初两个数对应的系数为：

$$\begin{aligned} r_0=a&=1\cdot a+0\cdot b\\ r_1=b&=0\cdot a+1\cdot b \end{aligned}$$

所以：

$$(x_0,y_0)=(1,0),\qquad(x_1,y_1)=(0,1)$$

将线性组合代入余数递推式：

$$\begin{aligned} r_{i+1} &=r_{i-1}-q_i r_i\\ &=(x_{i-1}a+y_{i-1}b)-q_i(x_i a+y_i b)\\ &=(x_{i-1}-q_i x_i)a+(y_{i-1}-q_i y_i)b \end{aligned}$$

因此，系数的递推公式是：

$$\boxed{ \begin{aligned} x_{i+1}&=x_{i-1}-q_i x_i\\ y_{i+1}&=y_{i-1}-q_i y_i \end{aligned} }$$

当算法到达最后一个非零余数 $r_k=\gcd(a,b)$ 时，同时得到：

$$\gcd(a,b)=x_k a+y_k b$$

这就是扩展欧几里得算法比普通欧几里得算法“扩展”的部分。算法只需迭代维护相邻两个余数及其系数，并按照上面的公式不断更新。

返回值可以直接使用 std::tuple 表示，三个元素依次是 $\gcd(a,b)$、$a$ 的系数 $x$ 和 $b$ 的系数 $y$。循环始终保持两个不变量：

$$r_0=ax_0+by_0,\qquad r_1=ax_1+by_1$$

右侧的元组会先使用旧状态完成计算，再统一写回左侧变量，因此不会因为提前修改某个变量而破坏本轮递推。对于 P1082，输入保证 $\gcd(a,b)=1$；算法返回的 $x$ 可能为负数，需要将它转换到模 $b$ 的标准范围。

C++ 实现

#include <iostream>
#include <tuple>

using ExtGcdResult =
    std::tuple<long long, long long, long long>;

// 返回 (g, x, y)，满足 g = a * x + b * y
ExtGcdResult ext_gcd(long long a, long long b) {
  long long r0 = a, x0 = 1, y0 = 0;
  long long r1 = b, x1 = 0, y1 = 1;

  while (r1 != 0) {
    long long q = r0 / r1;
    std::tie(r0, x0, y0, r1, x1, y1) =
        std::make_tuple(
            r1, x1, y1,
            r0 % r1, x0 - q * x1, y0 - q * y1
        );
  }

  return {r0, x0, y0};
}

int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);

  long long a, b;
  std::cin >> a >> b;

  auto [g, x, y] = ext_gcd(a, b);
  long long answer = (x % b + b) % b;
  std::cout << answer << '\n';
}