经典非对称加密算法：RSA

为了避免玛丽女王的悲剧重演，我们需要更安全的加密算法。我们有了如 AES 的加密算法，但密钥在分发过程中真的安全吗？

单向函数（One-way Function）

对于每一个输入，函数值都容易计算（多项式时间）；但是对于一个随机的函数值，算出其对应的输入却比较困难（无法在多项式时间内使用确定性图灵机计算）。
—— Wikipedia 单向函数

最简单的单向函数是取模运算：$m \bmod n = a$

例如 $10 \bmod 3 = 1$，根据输入的数据10很容易知道输出结果是1，但是根据输出结果1无法知道输入数据是什么

$m$ 作为原文，$n$ 作为公开的密钥，$a$ 作为加密后的密文 —— 大家即使拿到了密钥也无法解密密文，但这太安全了，连密文的接收方都无法解密

密码学的新方向 —— 单向陷门函数（One-way Trapdoor Function）

单项陷门函数是有一个陷门的一类特殊单向函数。单项陷门函数包含两个明显特征：一是单向性，二是存在陷门。

单向函数存在 bug（陷门）吗？即可以实现单向函数的逆推。如果存在一种单向算法存在陷门，那么可以将这个算法称为单向陷门函数（One-way Trapdoor Function）

在1976年 W. Diffie 和 M. Hellman 提出了这样的美好设想：

信息的接收者提前生成两个密钥，将一个单项陷门函数作为加密密钥公开发布（即公钥），信息的发送者使用公钥加密信息，信息的接收者自己保留的解密密钥（即私钥）就是这个单项陷门函数的陷门，接收者可以使用私钥解密加密后的密文

密文可以被截获，但窃密者不持有私钥，无法解密密文。私钥永远在接收者手里，这样就没有了发送密钥被截获的风险

自此，密码学有了新的方向 —— 公钥密码，加解密的不对称也被称为非对称密码

之所以在前文说这是 Diffie 和 Hellman 的美好设想，是因为 Diffie 和 Hellman 并没有找到合适的单向陷门函数……

RSA加密算法

R. L. Rivest、A. Shamir 和 L. Adleman 三人在1978年发布了一篇题为《A Method for Obtaining Digital Signatures and Public-key Cryptosystems》的论文，他们在论文中描述了一种以他们名字命名的加密算法 —— RSA

如果对于给定的乘方取模运算 $m^e \bmod n = c$，其中 $m$ 作为原文、$c$ 作为加密后的密文、而密钥则变成了 $e$ 和 $n$，那么可以使用逆运算 $c^d \bmod n = m$ 来还原出原始的 $m$。即 $d$ 是这个乘方取模运算中的陷门。

试试把加密公式带入解密公式：

\[ \begin{array}{c} \left ( m^e \bmod n \right)^d \bmod n = m \end{array} \] \[ \begin{array}{c} m^{ed} \bmod n = m \end{array} \]

这可太像欧拉定理了 —— 但是欧拉定理本来长这样 $m^{\phi(n)} = 1 \pmod{n}$，同乘以 $m$，就成了 $m^{\phi(n)+1} = m \pmod{n}$。显然满足 $\phi(n)+1 = ed$

那么陷门 $d = \frac{\phi(n) + 1}{e} $

$\phi(n)$是欧拉函数，它表示小于等于 $n$ 且与 $n$ 互质的正整数的个数，可以写成：

\[ \phi(n) = n \cdot \left(1 - \frac{1}{p_1}\right) \cdot \left(1 - \frac{1}{p_2}\right) \cdot \ldots \cdot \left(1 - \frac{1}{p_m}\right) \]

其中的 $p$ 都是质数，根据欧拉给出的公式，可以知道 $p$ 与 $n$ 的关系：

\[ n = p_{1}^{k 1} p_{2}^{k 2} \ldots p_{m}^{k m} \]

我们知道欧拉函数的定义是基于正整数的质因数分解，而质因数分解是唯一的，所以所有正整数 $n$ 的欧拉函数 $\phi(n)$ 都是整数

但是，$d$ 就不一定了，如果 $n = 34, e = 15$，算出来的 $d = 7/3$，这对取模运算没有意义

回到欧拉公式，根据取模运算的性质 —— 等式左边 $k$ 个 $m^{\phi(n)}$ 相乘等式也成立，即 $(m^{\phi(n)})^k = 1 \pmod{n}$，根据上面的过程进一步可以得到 $d = \frac{k\phi(n) + 1}{e}$

通过选择 $k$ 的值，就可以得到正整数的 $d$，例如刚刚的 $n = 34, e = 15$：

\[ \begin{matrix} k=1 & d=\frac{7}{3} & & k=4 & d=\frac{13}{3} \end{matrix} \] \[ \begin{matrix} k=2 & d=\frac{11}{5} & & k=5 & d=\frac{27}{5} \end{matrix} \] \[ \begin{matrix} k=3 & d=\frac{49}{15} & & k=6 & d=\frac{97}{15} \end{matrix} \] \[ \begin{matrix} & & ... & & \end{matrix} \] \[ \begin{matrix} & k=14 & & d=15 & \end{matrix} \] \[ \begin{matrix} \end{matrix} \]

可以找到 $k=14$ 时 $d = 15$，但是 $k = 29$ 时 $d$ 也为正整数，这应该怎么选择？习惯性选择最小的正整数作为 $d$ 的取值

通常采用扩展欧几里得算法算法来快速计算符合条件的 $k$，我拜托 ChatGPT 写了个小程序来计算：

function extendedEuclidean(a, e) {
  if (e === 0) {
    return [1, 0, a];
  }

  const [x, y, gcd] = extendedEuclidean(e, a % e);
  return [y, x - Math.floor(a / e) * y, gcd];
}

function findK(n, e) {
  const phiN = phi(n);
  let k = 1;

  while (true) {
    const [x, y, gcd] = extendedEuclidean(k * phiN + 1, e);
    const d = (k * phiN + 1) / e;

    if (d > 0 && Number.isInteger(d)) {
      return k;
    }

    k++;
  }

  return -1; // No valid k found
}

function phi(n) {
  let result = n;
  let i = 2;

  while (i * i <= n) {
    if (n % i === 0) {
      while (n % i === 0) {
        n /= i;
      }
      result -= result / i;
    }
    i++;
  }

  if (n > 1) {
    result -= result / n;
  }

  return result;
}

const n = 30;
const e = 15;
const k = findK(n, e);

console.log(`k = ${k}`);

公钥 $e$ 和 $n$ 都是公开的，应该如何防止其他人计算出私钥 $d$？

当 $n$ 很小的时候很容易算出 $\phi(n)$，当 $n$ 为一个很大的数时就很难计算了，例如你可以试试下面这个 $n$：

n = 22112825529529666435281085255026230927612089502470015394413748319128822941402001986512729726569746599085900330031400051170742204560859276357953757185954298838958709229238491006703034124620545784566413664540684214361293017694020846391065875914794251435144458199

但是，$e$ 和 $n$ 都是由信息的接收者发布的，接收者可以通过直接指定 $p$ 的方法轻易求出 $\phi(n)$。

虽然这已经够简单了，但是欧拉给出的计算公式还是太复杂了，前文说过当 $n$ 很大的时候就很难计算出 $\phi(n)$ 了，可以再将其简化为 $n = pq$，$p$ 和 $q$ 是两个大质数，它们相乘可以得到一个非常难以分解的大数，这是 RSA 加密算法中的第二个单向函数。进而 $\phi(n)$ 就可以简化为 $\phi(n) = (p - 1)(q - 1)$

由信息的接收者选取 $p, q$ 和 $e$，将这两个大质数相乘得到 $n$，选取一个合适的 $k$ 使用 $d = \frac{k\phi(n) + 1}{e}$ 计算得到私钥 $d$。接收者发布 $e$ 和 $n$ 作为公钥，信息的发送者要发送信息 $m$ 需要使用公钥通过 $m^e \bmod n = c$ 对信息进行加密得到密文 $c$，接收者接到密文 $c$ 使用私钥通过 $c^d \bmod n = m$ 即可还原原文 $n$。而窃密者即使截获了密文也无法通过将 $n$ 分解成 $p, q$，无法计算得出私钥

下面是一段 C 语言代码，完成的正式 RSA 这一过程：

参考

[1] Diffie, W. and Hellman, M. New directions in cryptography[J]. IEEE Transactions on Information Theory, 1976, 22(6): 644-654.
[2] Rivest, R. L., Shamir, A., and Adleman, L. A Method for Obtaining Digital Signatures and Public-Key Cryptosystems[J]. Commun. ACM, 1978, 21(2): 120-126.
[3] Playclass

END

如有错误欢迎指出！

阿方的博客