实战：RSA算法（大数运算+模幂+欧拉定理）

RSA算法，说白了就是目前最主流的非对称加密方案。你想想看，我们在网上购物、登录银行系统，背后都有它的影子。我当年第一次接触RSA时，觉得这东西特别神秘——公钥加密、私钥解密，感觉像变魔术一样。后来自己动手实现了一遍，才发现核心原理其实并不复杂，就是大数运算、模幂计算和欧拉定理的组合拳。

RSA的核心数学原理

先聊聊RSA的数学基础。它依赖一个简单的事实：两个大素数相乘很容易，但反过来分解大整数却极其困难。这就是RSA安全性的根本保障。

具体来说，RSA涉及以下几个关键步骤：

  1. 选择两个大素数 p 和 q（通常512位以上）
  2. 计算 n = p × q（n的位数就是密钥长度）
  3. 计算欧拉函数 φ(n) = (p-1)(q-1)
  4. 选择公钥指数 e（通常取65537，满足1 < e < φ(n)且gcd(e, φ(n)) = 1）
  5. 计算私钥指数 d，满足 e × d ≡ 1 (mod φ(n))

嗯，这里要注意：d就是私钥的核心，一旦泄露，整个加密体系就崩塌了。

核心公式：

  • 加密：c = m^e mod n
  • 解密：m = c^d mod n

其中 m 是明文，c 是密文。为什么能解密？因为 m^(e×d) ≡ m (mod n)，这背后就是欧拉定理在撑腰。

大数运算——RSA的基石

我在项目中遇到过一个问题：C++自带的整数类型最大也就64位，而RSA需要处理几百甚至上千位的大数。怎么办？必须自己实现大数运算库。

我个人习惯用数组或vector存储大数，每个元素存一个"数字位"（比如0-9999）。这样就能轻松处理任意长度的整数了。

// 大数结构体示例
struct BigInt {
    vector<uint32_t> digits;  // 每个元素存0-9999
    bool is_negative;
    
    BigInt() : is_negative(false) {
        digits.push_back(0);
    }
    
    // 从字符串构造
    BigInt(const string& str) {
        // 解析字符串，逐位存入digits
    }
};

大数运算需要实现的基本操作包括：

  • 加法/减法：注意进位/借位处理
  • 乘法：模拟竖式计算，复杂度O(n²)
  • 除法/取模：模拟长除法，最麻烦的部分
  • 比较：先比长度，再比每一位

我的经验：实现大数除法时，可以用"试商法"——先估算商的每一位，再逐步调整。我曾经在这里踩过坑，试商不准导致死循环，调试了一整天。

模幂运算——快速计算的秘诀

RSA加密和解密都需要计算 m^e mod n。如果直接算 m^e，那个数字大得离谱，根本存不下。所以必须用快速模幂算法（也叫"反复平方"法）。

核心思想很简单：把指数 e 写成二进制，比如 e = 13 = 1101₂，那么：

m^13 = m^8 × m^4 × m^1

每次平方取模，遇到二进制位为1就乘到结果里。这样计算量从O(e)降到了O(log e)。

// 快速模幂算法
BigInt modPow(BigInt base, BigInt exp, BigInt mod) {
    BigInt result = BigInt("1");
    base = base % mod;
    
    while (exp > BigInt("0")) {
        // 如果当前最低位是1
        if (exp.digits[0] % 2 == 1) {
            result = (result * base) % mod;
        }
        // 平方取模
        base = (base * base) % mod;
        // 右移一位（除以2）
        exp = exp / BigInt("2");
    }
    return result;
}

你看，这个算法每次循环只做一次乘法和一次取模，效率非常高。我实测过，1024位的RSA加密，用这个算法只需要几毫秒。

欧拉定理——解密正确性的保证

为什么解密能还原出原文？这就要请出欧拉定理了。

欧拉定理说：如果 a 和 n 互质，那么 a^φ(n) ≡ 1 (mod n)。

在RSA中，我们有：

  • e × d ≡ 1 (mod φ(n))，即 e×d = k×φ(n) + 1
  • 那么 c^d ≡ (m^e)^d ≡ m^(e×d) ≡ m^(k×φ(n)+1) ≡ (m^φ(n))^k × m ≡ 1^k × m ≡ m (mod n)

嗯，这里要注意：这个推导假设 m 和 n 互质。如果 m 是 p 或 q 的倍数怎么办？实际上这种情况概率极低（1/p + 1/q ≈ 0），而且可以用中国剩余定理单独处理，不影响整体正确性。

避坑指南：我曾经在实现RSA时忽略了 p 和 q 的素数检测，直接用了随机大数。结果加密解密偶尔会失败，排查了好久才发现是 p 或 q 不是素数，导致 φ(n) 计算错误。所以一定要做Miller-Rabin素数检测，至少检测10轮以上。

完整RSA实现流程

把上面这些拼起来，就是一个完整的RSA实现：

// RSA密钥生成
void generateRSAKey(int bits, BigInt& n, BigInt& e, BigInt& d) {
    // 1. 生成两个大素数
    BigInt p = generatePrime(bits / 2);
    BigInt q = generatePrime(bits / 2);
    
    // 2. 计算 n 和 φ(n)
    n = p * q;
    BigInt phi = (p - BigInt("1")) * (q - BigInt("1"));
    
    // 3. 选择公钥指数（常用65537）
    e = BigInt("65537");
    
    // 4. 计算私钥指数（扩展欧几里得算法）
    d = modInverse(e, phi);
}

// RSA加密
BigInt rsaEncrypt(BigInt m, BigInt e, BigInt n) {
    return modPow(m, e, n);
}

// RSA解密
BigInt rsaDecrypt(BigInt c, BigInt d, BigInt n) {
    return modPow(c, d, n);
}

性能优化建议：解密时可以用中国剩余定理（CRT）加速。因为知道 p 和 q，可以分别计算 m_p = c^d mod p 和 m_q = c^d mod q，再用CRT合并。这样速度能提升约4倍。我在实际项目中就是这么做的。

RSA知识体系总览

下面这张图帮你理清RSA的完整脉络：

RSA算法知识体系 RSA 非对称加密 大数运算 模幂运算 欧拉定理 大数运算技术 • 数组/vector存储 • 加法/减法/乘法/除法 • Miller-Rabin素数检测 模幂运算技术 • 反复平方算法 • 二进制指数分解 • 每次平方取模 欧拉定理应用 • φ(n) = (p-1)(q-1) • e×d ≡ 1 mod φ(n) • 解密正确性证明 密钥生成：p, q → n, φ(n) → e, d 加密：c = m^e mod n 解密：m = c^d mod n

实际应用中的注意事项

RSA虽然强大，但用起来有不少坑。我总结了几点：

问题 原因 解决方案
加密速度慢 大数模幂运算耗时 使用CRT加速解密；公钥指数选65537
明文长度限制 m必须小于n 分段加密，每段不超过密钥长度-11字节
选择密文攻击 攻击者可以篡改密文 使用OAEP填充方案
素数生成慢 大素数检测需要大量计算 先筛除小因子，再用Miller-Rabin

安全警告：千万不要自己实现RSA用于生产环境！我见过太多"自制RSA"出现各种漏洞——随机数不够随机、素数检测不充分、填充方案缺失。实际项目中请使用OpenSSL、Crypto++等成熟库。自己实现只适合学习目的。

好了，RSA的核心内容就这些。说白了就是：大数运算做地基，模幂计算当工具，欧拉定理保正确。你动手实现一遍，这些概念就全串起来了。

公众号:蓝海资料掘金营，微信deep3321

← 上一章 📖 返回目录 下一章 →