RSA 的数学问题可以写成：c = m^e mod n，为什么再求 c^d mod n 能得到 m？答案依赖公私钥指数之间的模逆关系，而不是对指数取普通倒数。

这篇笔记最初是在阅读 doujinlong1 的 RSA 原理文章后，继续补充“为什么能够解密”的推导。下面重新展开证明，并用 PKCS #1 核对密钥条件，不把参考文章改作自己的原创教程。

密钥与模幂的关系

取不同素数 p、q，令 n=pq，φ(n)=(p−1)(q−1)。选择与 φ(n) 互质的正整数 e，再取正整数 d，使：

ed ≡ 1 (mod φ(n))
即 ed = 1 + kφ(n)，k 为非负整数

公钥：(n, e)
私钥核心参数：(n, d)
加密：c = m^e mod n
解密：m' = c^d mod n
明文代表元范围：0 ≤ m < n

d 是 e 关于模 φ(n) 的乘法逆元，不是实数 1/e。PKCS #1 使用 λ(n)=lcm(p−1,q−1) 表达指数条件，上述以 φ(n) 构造的关系也满足要求。RFC 8017 密钥定义

先看与 n 互质的情况

当 gcd(m,n)=1，欧拉定理给出 m^φ(n) ≡ 1 (mod n)，于是：

c^d ≡ m^(ed)
    ≡ m^(1+kφ(n))
    ≡ m × (m^φ(n))^k
    ≡ m (mod n)

这个简洁证明有互质前提。如果 m 恰好是 p 的倍数，不能不加说明地继续套用欧拉定理。

代入时还用到了模运算的相容性：(ab) mod n = ((a mod n)(b mod n)) mod n；已经取余的结果再次模 n 不变。例如 23、19 分别模 5 得 3、4，乘积还需再模 5，得到 2，而不是把 12 当最终余数。因此可以逐步取模，并把 (m^e mod n)^d 的同余关系写成 m^(ed)，不必真的先计算巨大整数幂。

不互质时，用两个素数分别证明

考虑模 p：若 p 整除 m，则 m^ed 与 m 都为 0；否则费马小定理给出 m^(p−1) ≡ 1 (mod p)，而 ed−1 是 p−1 的倍数，仍有 m^ed ≡ m (mod p)。

模 q 同理。由中国剩余定理，模 pq 的代表元唯一，所以 m^ed ≡ m (mod n)。结合 0≤m<n，就能还原原代表元，包括 m=0。

小整数算例

p=61，q=53，n=3233，φ(n)=3120
e=17，d=2753
ed=46801=1+15×3120

明文 m=65
密文 c=65^17 mod 3233=2790
解密 2790^2753 mod 3233=65

大指数应逐次取模，不要用浮点数先算完整幂。下面是整数教学计算：

function modPow(base, exponent, modulus) {
  if (modulus <= 0n || exponent < 0n) {
    throw new RangeError("模数必须为正，指数不能为负");
  }
  let result = 1n % modulus;
  base = ((base % modulus) + modulus) % modulus;
  while (exponent > 0n) {
    if ((exponent & 1n) === 1n) result = result * base % modulus;
    base = base * base % modulus;
    exponent >>= 1n;
  }
  return result;
}
const encrypted = modPow(65n, 17n, 3233n);
console.log(encrypted.toString()); // 2790
console.log(modPow(encrypted, 2753n, 3233n).toString()); // 65

数学原理不是完整安全方案

小素数没有安全性，这段代码也不是抗侧信道实现。直接对明文做确定性模幂的“裸 RSA”不适合作业务加密；应使用经过审查的密码库及标准编码，例如 RSAES-OAEP。RFC 8017 OAEP

“私钥加密、公钥解密”同样不是完整签名方案：还涉及摘要、编码及专门安全要求。理解模幂可逆，是理解 RSA 的起点，不代表已经实现密钥管理、加密或签名系统。