困难通用8 分钟2,753 字

CRT在RSA算法中的应用简介

你有没有想过,当你在网上发消息时,信息是怎么安全地传到对方手机上的?背后就有RSA加密算法在保护它。RSA是一种“非对称加密”,就像你有一个带锁的盒子,大家都用同一把公锁(公钥)把信锁进去,但只有你一个人有开锁的私钥。私钥就是那个能解开所有盒子的钥匙。

但是,开锁(解密)的过程很慢,尤其是当锁特别大时。聪明的数学家发现了一个“偷懒”的办法:用中国剩余定理(CRT)把一个大锁拆成两个小锁,分别打开,再组合起来,速度能快三四倍。这就像你要算全班同学的总分,正常做法是每个同学加一遍;但如果把男女分开,先算男生总分、女生总分,再加起来,计算量也会变小!今天我们就来一步步拆解这个“偷懒”技巧。

1. RSA加密的“锁”是怎么造的?

先简单回顾RSA的工作原理(如果你已经知道,可以跳过这段)。

1.1 选两把“秘密钥匙”(两个大素数 p 和 q)

  • 想象你选两个不同的数字,比如小明身高 p = 3​​、小红身高 q = 11​​(实际中都是几百位的大数)。
  • 用它们算出一个“超级大数” n = p × q = 33​​,这相当于盒子的尺寸。
  • 再算一个叫“欧拉函数”的数:φ(n) = (p-1)×(q-1) = 2×10 = 20。这个数很特别,后面要用到。

1.2 制作公钥(大家都能用的锁)

  • 挑一个整数 e​,它要和 φ(n) 互质(没有公共因数)。通常选 e = 7​​(7和20没有公因数)。
  • 公钥 = (n, e) = (33, 7)。你可以把这个号码公开,谁都可以用它来加密信。

1.3 制作私钥(只有你的开锁器)

  • 需要找一个数字 d​,使得 e×d 除以 φ(n) 余1,即 e×d = 1 (mod φ(n))。
  • 7×d = 1 (mod 20),d=3 就满足,因为7×3=21,21÷20余1。
  • 私钥就是 d=3(实际还会保留 p 和 q 方便加速)。

加密​​:把明文 m(比如数字5)变成密文 c:c = m^e mod n = 5^7 mod 33。 解密​​:m = c^d mod n = (5^7)^3 mod 33。

你可能会想:直接算 5^21 mod 33 不就好了?但注意,这个指数 d 非常大(实际中2048位),直接算会慢到让你等到手机没电。这时候,CRT 就登场了。

2. 解密为什么慢?用生活例子类比

假设你要算 c^d mod n​​,其中 n 是2048位数,d也是这么大。这就像让你计算“3123456789...(几千位)的 987654321...次方,然后除以另一个几千位的数取余数”。即使计算机很聪明,也要花很久时间。

但是,如果你知道 n 是由两个素数 p 和 q 乘出来的,你就可以把问题拆成两个小问题:

  • 先算 c^d mod p(p 只有 n 的一半长)
  • 再算 c^d mod q(q 也只有一半)
  • 最后用中国剩余定理把两个结果合起来得到最终答案。

这就好比让全班同学计算“1+2+3+...+1000”的总和。如果一个个加,要加1000次;但如果用高斯公式(首尾相加),一步就能算出来。CRT就是我们解模幂运算的“高斯公式”。

3. 具体怎么拆?—— CRT 加速解密的数学步骤

知道 p 和 q 后,私钥拥有者可以预先算好三个“辅助数字”:

  1. dp = d mod (p-1)
  2. dq = d mod (q-1)
  3. qinv = 模 p 下 q 的逆元​​,也就是找一个数,使得 q × qinv ≡ 1 (mod p)

然后解密时只需要做三件小事:

  • 计算 m1 = c^{dp} mod p
  • 计算 m2 = c^{dq} mod q
  • 用 CRT 合并: h = (qinv × (m1 - m2)) mod p m = m2 + h × q

最后的 m 就是解密结果。

为什么可以这样做?因为费马小定理

你可能会有疑问:mp = c^{dp} mod p 和 m2 = c^{dq} mod q 为什么就能代表原来的 c^d mod p 和 c^d mod q?答案是:指数可以“变小”。

根据费马小定理:如果 c 和 p 互质,那么 c^{p-1} ≡ 1 mod p。也就是说,指数每增加 (p-1),结果不变。所以: c^d mod p = c^{d mod (p-1)} mod p 即使 c 和 p 不互质(比如 c 正好是 p 的倍数),这个公式仍然成立(因为两边都是0)。

所以用 dp = d mod (p-1) 代替 d,结果完全一样。而 dp 大约只有 d 的一半长,计算量大大减少。

4. 常见错误(新手最容易踩的坑)

  1. 负数取模​​:在C++里 (m1 - m2) % p 可能得到负数。必须写成 ((m1 - m2) % p + p) % p。Python则自动返回正数。
  2. 忘记对指数先取模​​:直接使用原始的d而不是dp/dq,那就没加速了。
  3. 求逆元方法不对​​:暴力枚举只适合小数字,实际要用扩展欧几里得算法或快速幂(如果模是素数)。
  4. 混淆公钥和私钥​​:CRT加速只用于解密(或者签名),加密不需要(因为加密者不知道p和q)。

5. 完整可运行示例(含中文注释)

下面用 C++ 和 Python 演示一个超小规模的 RSA 加解密,并使用 CRT 加速。所有变量都加了中文注释,方便你理解每一步在干什么。

C++ 代码

cpp
#include <iostream>
using namespace std;

// 快速幂:计算 a 的 b 次方再对 m 取余
long long fast_pow(long long a, long long b, long long m) {
    long long res = 1 % m;      // 结果,至少是1(如果m=1,则结果为0)
    a %= m;                     // 先把底数缩小
    while (b > 0) {
        if (b & 1) res = (res * a) % m;  // 如果当前二进制位为1,乘一次
        a = (a * a) % m;                // 底数平方
        b >>= 1;                        // 指数右移一位(除以2)
    }
    return res;
}

// 求逆元:找一个数 x,使得 a*x ≡ 1 (mod m)
// 这里简单用暴力枚举(仅适用于小数字教学演示)
long long mod_inverse(long long a, long long m) {
    a = a % m;
    for (long long i = 1; i < m; i++) {
        if ((a * i) % m == 1)
            return i;
    }
    return -1; // 不存在(正常情况下不会发生)
}

// 使用 CRT 加速的 RSA 解密
// 输入:密文 c,素数 p,素数 q,预计算的 dp,dq,qinv
long long rsa_decrypt_crt(long long c, long long p, long long q,
                          long long dp, long long dq, long long qinv) {
    // 1. 计算 m1 = c^{dp} mod p
    long long m1 = fast_pow(c, dp, p);
    // 2. 计算 m2 = c^{dq} mod q
    long long m2 = fast_pow(c, dq, q);
    // 3. 合并:计算差并确保为非负数
    long long diff = (m1 - m2) % p;
    if (diff < 0) diff += p;          // C++ 中 % 可能为负,转成正数
    long long h = (qinv * diff) % p;
    long long m = m2 + h * q;         // 最终解密结果
    return m;
}

int main() {
    // 设置小素数方便演示(实际中都是几百位的)
    long long p = 3, q = 11;          // 两个素数
    long long n = p * q;              // 模数 n = 33
    long long phi = (p-1) * (q-1);    // 欧拉函数 φ(n) = 20
    long long e = 7, d = 3;           // 公钥指数 e,私钥指数 d (7*3=21≡1 mod 20)

    // 明文(要加密的数字)
    long long m_original = 5;         // 明文设为5

    // 加密:计算 c = m^e mod n
    long long c = fast_pow(m_original, e, n);  // 得到密文14
    cout << "密文: " << c << endl;

    // 普通解密:直接计算 c^d mod n
    long long m_normal = fast_pow(c, d, n);
    cout << "普通解密结果: " << m_normal << endl;  // 应该等于5

    // CRT 加速解密所需的预计算参数
    long long dp = d % (p - 1);           // dp = 3 % 2 = 1
    long long dq = d % (q - 1);           // dq = 3 % 10 = 3
    long long qinv = mod_inverse(q, p);   // q=11对模p=3的逆元,因为11%3=2,2的逆元是2

    cout << "dp=" << dp << ", dq=" << dq << ", qinv=" << qinv << endl;

    // 使用CRT解密
    long long m_crt = rsa_decrypt_crt(c, p, q, dp, dq, qinv);
    cout << "CRT解密结果: " << m_crt << endl;  // 应该也是5

    // 注意:实际RSA中数字长度成百上千位,但原理一模一样
    return 0;
}

Python 代码(语法更简洁,适合直接跑)

python
def fast_pow(a, b, m):
    """快速幂:计算 a^b mod m"""
    res = 1 % m
    a %= m
    while b:
        if b & 1:
            res = (res * a) % m
        a = (a * a) % m
        b >>= 1
    return res

def mod_inverse(a, m):
    """求逆元(暴力枚举,仅教学用)"""
    a %= m
    for i in range(1, m):
        if (a * i) % m == 1:
            return i
    return None

def rsa_decrypt_crt(c, p, q, dp, dq, qinv):
    """使用CRT加速RSA解密"""
    m1 = fast_pow(c, dp, p)          # c^{dp} mod p
    m2 = fast_pow(c, dq, q)          # c^{dq} mod q
    h = (qinv * (m1 - m2)) % p       # Python % 自动得到正数
    m = m2 + h * q
    return m

if __name__ == "__main__":
    # 小素数例子
    p, q = 3, 11                     # 两个素数
    n = p * q                        # 模数 33
    phi = (p-1) * (q-1)              # 欧拉函数 20
    e, d = 7, 3                      # 公钥指数、私钥指数

    m_original = 5                   # 明文
    c = fast_pow(m_original, e, n)   # 加密得密文14
    print(f"密文: {c}")

    m_normal = fast_pow(c, d, n)     # 普通解密
    print(f"普通解密结果: {m_normal}")

    # 预计算CRT参数
    dp = d % (p - 1)                 # dp = 1
    dq = d % (q - 1)                 # dq = 3
    qinv = mod_inverse(q, p)         # qinv = 2 (因为11%3=2, 2*2=4≡1)
    print(f"dp={dp}, dq={dq}, qinv={qinv}")

    m_crt = rsa_decrypt_crt(c, p, q, dp, dq, qinv)
    print(f"CRT解密结果: {m_crt}")   # 输出5,和明文一样

6. 为什么这个加速很重要?

现在很多网站(银行、支付宝、微信)都在用RSA加密。如果每次解密都要算2048位的巨大幂模,速度会非常慢,可能点击一个链接后要等好几秒。用了CRT后,大模数被拆成两个1024位的运算,计算量变成了原来的1/4左右,实际速度能提升3~4倍。所以几乎所有的RSA解密软件(比如OpenSSL、Java的RSA实现)都内置了CRT加速。

7. 总结与拓展

中国剩余定理(CRT)是数论里一个古老而美丽的结果。它告诉我们:如果知道一个数除以几个两两互质的数的余数,就能唯一确定这个数。在RSA解密中,我们把“大模数”分成“小模数”,分别计算再合并,大大提高了效率。

下次当你用手机支付、发加密消息时,背后就有CRT在帮你“偷懒”。如果你想继续探索,可以学习:

  • Garner算法​​:另一种更高效的CRT合并方式。
  • RSA签名​​:签名中也能用CRT加速。
  • 其他密码系统​​:比如Paillier加密、ElGamal加密等,有时也会用到类似技巧。

数学不是枯燥的公式,它是帮我们偷懒的聪明工具。希望这篇文章能让你觉得“原来数学可以这么实用”!

同类知识点