欧拉定理在RSA加密中的应用

创建时间：2025-12-24 16:52:08

加密的本质

就是一份明文，经过一轮计算，变成密文，再经过一轮计算，恢复成明文。
我工作的前几年主要就是做透明加解密，很多人经常只注意到加密，却忽视了解密的逆运算。

对称加密和非对称加密

  • 典型的对称加密如AES，加解密不仅依赖同样的密钥，而且依赖“对称”的运算，主要是逆元模乘和异或。这很好理解。
  • 典型的非对称加解密如RSA，加解密使用不用的密钥，所以他的难点在于：
    要找出一种数学关系，使得加解密使用两个不同的密钥d和e，A和B能实现一种逆运算，并且A和B无法互相推导。
    A和B实现互逆运算容易，但是如何保证A和B无法互相推导非常难！那么欧拉定理是如何解决这个问题的呢？

先说如何实现加解密互逆运算

欧拉定理： 当M和n互质时， (M ^ φ(n)) % n = 1

这个公式意思是M的φ(n)次方取模n等于1，其中φ(n)表示小于n且与n互质的数的个数。
公式中的这个结果：1，就保证了加解密的互逆： 

∵(M ^ φ(n)) % n = 1
∴(M ^ (φ(n) * k)) % n = ((M ^ (φ(n))) ^ k) % n = 1 ^ k = 1
∴(M ^ (φ(n) * k + 1)) % n = (M ^ (φ(n) * k)) % n * ((M ^ 1) % n) = (1 ^ k) * M = M

也就是说 (M ^ (φ(n) * k + 1)) % n = M, 这样M 就能被解密还原了。
那么我们为什么要构造这个奇怪的： k * φ(n) + 1 呢？
因为我们要确保运算可以拆成加密和解密两步： 

当d和e在模φ(n)下互为逆元时，
∵ (d * e) % φ(n) = 1
∴ d * e = k * φ(n) + 1
也就是说 k * φ(n) + 1 正好可以转化为 d * e，也就可以拆解出 d 和 e，
加密时，设明文为M，公钥为e, 密文为N，则，
N = (M ^ e) % n
解密时，设私钥为d，则，
(N ^ d) % n = (((M ^ e) % n) ^ d) % n = (M ^ (d * e)) % n = (M ^ (φ(n) * k + 1)) % n = M
这样M使用d和e经过两轮运算后被还原成了M。

也就是说：
(M ^ (d * e)) % n = M
这就是RSA的核心，还原运算被拆成了两步，分别作为加密和解密，并且使用不同的密钥d和e。
这里显然e和n就是公钥，d就是私钥。

再说公钥和私钥为何无法直接互相推导

首先我们找两个大质数p和q，计算得n = p * q， 那么有欧拉函数 φ(n) = (p-1) * (q-1),
φ(n)可以通过p和q简单算出，相反如果没有p和q，就要去分解 n 了，目前在数学上是做不到的。
那么现在我们随机给出一个较小的 e，和 n 一起作为公钥，方便加密计算。
由于我们知道 φ(n) 的值，且d和e是模φ(n)下互为逆元，即(d * e) % φ(n) = 1， 我们可以通过欧几里得扩展算法求得私钥 d。
而破解者只知道 n, 却拿不到 φ(n)， 也就无法通过 e 求得 d。

所以我们经常说的RSA里的两个大质数P和q其实只是种子，并不参与加解密运算。

同时可以发现RSA的加解密都是基于幂运算，并且通常解密所用的私钥d远大于加密所用的公钥e。
虽然我们可以通过类似于(2 ^ 100) % n = ((2 ^ 10) ^ 10) % n这样的分解来简化运算，但是计算量仍然很大。
所以很多应用场合例如https，RSA只用于传输一次性的临时通话密钥，大量的通信数据仍是用这个临时密钥基于效率更高的AES等算法加解密。

🔢 一个简单的计算实例

我们用一个简单的例子来计算一下，这会非常直观。假设参数为：p=3, q=7, e=5, M=10。

  1. 计算基本参数：

    • 模数 n = p * q = 3 * 7 = 21
    • φ(n) = (p-1) * (q-1) = 2 * 6 = 12
    • 根据 e * d ≡ 1 (mod φ(n))，计算出私钥 d = 5。

  2. 加密过程：

    • 密文 C = M^e mod n = 10^5 mod 21。
    • 逐步计算：10^2 mod 21 = 16， 10^4 mod 21 = (16^2) mod 21 = 4， 10^5 mod 21 = (10^4 * 10) mod 21 = (4 * 10) mod 21 = 40 mod 21 = 19。
    • 所以，密文 C = 19。

  3. 解密过程：

    • 明文 m = C^d mod n = 19^5 mod 21。
    • 为简化计算，可以利用模运算性质：19 ≡ -2 (mod 21)，所以 19^5 ≡ (-2)^5 = -32 ≡ -32 + 2 * 21 = -32 + 42 = 10 (mod 21)。
    • 最终，解密出的明文 m = 10，与原始明文一致。
返回