41、C++项目实战：RSA加密算法实现

RSA加密，说实话，是每个C++工程师都应该亲手实现一遍的经典算法。它不光是密码学的基石，更是理解大数运算、模幂运算和数论原理的最佳实践。我记得刚入行那会儿，总觉得RSA是数学家的事，直到有一次项目里需要自己实现一个轻量级的加密模块，才真正体会到——纸上得来终觉浅。

这一章，我们就从零开始，用C++把RSA的核心逻辑撸一遍。不依赖OpenSSL，不依赖第三方库，纯手工打造。

RSA的核心原理

RSA的安全性，说白了就是基于一个事实：两个大质数相乘很容易，但反过来分解很难。你想想看，给你两个100位的质数，乘起来也就一眨眼的功夫。但给你一个200位的合数，想找出它的两个质因子？嗯，超级计算机也得算到天荒地老。

整个流程分三步走：

  1. 密钥生成——选两个大质数，算出公钥和私钥
  2. 加密——用公钥把明文变成密文
  3. 解密——用私钥把密文变回明文

我在项目中遇到过一个问题：很多人觉得加密和解密是对称的，其实不是。公钥加密，私钥解密，这是单向的。私钥也能加密，但那叫签名，用途不一样。

密钥生成的数学步骤

咱们一步步来，别急。

  1. 随机选两个大质数 p 和 q。越大越安全，但计算也越慢。
  2. 计算 n = p * q。这个 n 就是公钥和私钥都要用到的模数。
  3. 计算欧拉函数 φ(n) = (p-1) * (q-1)。
  4. 选一个公钥指数 e，要求 1 < e < φ(n)，且 e 与 φ(n) 互质。常用的是65537。
  5. 计算私钥指数 d，满足 e * d ≡ 1 (mod φ(n))。说白了就是求 e 关于 φ(n) 的模逆元。

公钥就是 (n, e)，私钥就是 (n, d)。就这么简单。

重要提醒：p 和 q 用完就要销毁。我见过有人把 p 和 q 打印到日志里，那等于把私钥拱手送人。

大数运算——RSA的硬骨头

C++自带的 int 类型最大也就64位，根本装不下RSA需要的几百位大数。所以，我们必须自己实现一个大数类。

我个人习惯用 std::vector 来存储大数的每一位，每个元素存32位。这样既方便运算，又能充分利用CPU的位宽。

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <cstdint>

class BigInt {
private:
    std::vector<uint32_t> digits;  // 小端存储，digits[0]是最低位
    bool is_negative;

public:
    BigInt() : is_negative(false) { digits.push_back(0); }
    
    BigInt(uint64_t num) : is_negative(false) {
        while (num > 0) {
            digits.push_back(num & 0xFFFFFFFF);
            num >>= 32;
        }
        if (digits.empty()) digits.push_back(0);
    }
    
    // 从字符串构造
    BigInt(const std::string& str) {
        is_negative = false;
        size_t start = 0;
        if (str[0] == '-') {
            is_negative = true;
            start = 1;
        }
        *this = BigInt(0);
        for (size_t i = start; i < str.size(); ++i) {
            *this = *this * 10 + (str[i] - '0');
        }
    }
    
    // 大数乘法
    BigInt operator*(const BigInt& other) const {
        BigInt result;
        result.digits.resize(digits.size() + other.digits.size(), 0);
        
        for (size_t i = 0; i < digits.size(); ++i) {
            uint64_t carry = 0;
            for (size_t j = 0; j < other.digits.size(); ++j) {
                uint64_t product = static_cast<uint64_t>(digits[i]) * 
                                   other.digits[j] + 
                                   result.digits[i + j] + 
                                   carry;
                result.digits[i + j] = product & 0xFFFFFFFF;
                carry = product >> 32;
            }
            if (carry > 0) {
                result.digits[i + other.digits.size()] += carry;
            }
        }
        
        // 去除前导零
        while (result.digits.size() > 1 && result.digits.back() == 0) {
            result.digits.pop_back();
        }
        
        result.is_negative = is_negative ^ other.is_negative;
        return result;
    }
    
    // 大数取模
    BigInt operator%(const BigInt& modulus) const {
        BigInt result = *this;
        // 这里用长除法实现，篇幅原因省略具体实现
        // 实际项目中可以用更高效的Barrett约减
        return result;
    }
    
    // 输出
    std::string toString() const {
        std::string result;
        BigInt temp = *this;
        BigInt ten(10);
        while (temp.digits.size() > 1 || temp.digits[0] > 0) {
            BigInt remainder;
            // 除以10取余数，篇幅原因省略
            // result += (remainder.digits[0] + '0');
        }
        std::reverse(result.begin(), result.end());
        if (is_negative) result = "-" + result;
        return result.empty() ? "0" : result;
    }
};

小技巧：大数乘法里，我习惯用 uint64_t 做中间变量，这样两个32位数相乘不会溢出。你想想看，如果直接用32位，进位就丢了，那结果全错。

模幂运算——RSA的心脏

RSA的加密和解密，本质上都是模幂运算：c = m^e mod n。直接算 m^e？别闹，那个数比宇宙中的原子还多。必须用快速幂算法，也叫"平方-乘"法。

原理很简单：把指数 e 写成二进制，从高位到低位遍历。每遍历一位，结果先平方一次。如果当前位是1，再乘一次底数。最后取模。

BigInt modPow(const BigInt& base, const BigInt& exponent, const BigInt& modulus) {
    BigInt result(1);
    BigInt b = base % modulus;
    BigInt exp = exponent;
    
    while (exp > BigInt(0)) {
        // 如果当前最低位是1
        if (exp.digits[0] & 1) {
            result = (result * b) % modulus;
        }
        // 平方
        b = (b * b) % modulus;
        // 右移一位
        exp = exp >> 1;  // 需要实现右移运算符
    }
    
    return result;
}

我曾经在这个函数上栽过跟头。当时没注意 base 可能比 modulus 大，结果算出来的值全不对。后来养成了习惯——任何模幂运算前，先对底数取模。

完整的RSA实现

有了大数类和模幂运算，RSA就水到渠成了。咱们把整个流程串起来：

class RSA {
private:
    BigInt n;  // 模数
    BigInt e;  // 公钥指数
    BigInt d;  // 私钥指数
    
public:
    // 密钥生成
    void generateKeys(int bits = 1024) {
        // 1. 生成两个大质数
        BigInt p = generatePrime(bits / 2);
        BigInt q = generatePrime(bits / 2);
        
        // 2. 计算 n = p * q
        n = p * q;
        
        // 3. 计算 φ(n) = (p-1) * (q-1)
        BigInt phi = (p - 1) * (q - 1);
        
        // 4. 选择公钥指数 e = 65537
        e = BigInt(65537);
        
        // 5. 计算私钥指数 d = e^(-1) mod φ(n)
        d = modInverse(e, phi);  // 扩展欧几里得算法
        
        // 销毁 p 和 q
        // p = q = BigInt(0);
    }
    
    // 加密
    BigInt encrypt(const BigInt& plaintext) {
        return modPow(plaintext, e, n);
    }
    
    // 解密
    BigInt decrypt(const BigInt& ciphertext) {
        return modPow(ciphertext, d, n);
    }
};

注意：上面的 generatePrime 函数没有实现。生成大质数需要先随机生成大数，然后用Miller-Rabin素性测试验证。Miller-Rabin测试有概率性，但多测几轮，出错概率比被雷劈还低。

RSA的完整流程图

下面这张图，把RSA从密钥生成到加解密的完整流程画出来了。我建议你对照着代码看，思路会清晰很多。

RSA加密算法完整流程 第一阶段：密钥生成 选大质数 p, q n = p × q φ(n) = (p-1)(q-1) e, d 第二阶段：加密（使用公钥 e, n） 明文 m（整数形式） c = m^e mod n 密文 c 第三阶段：解密（使用私钥 d, n） 密文 c m = c^d mod n 明文 m（还原）

实际项目中的注意事项

代码写完了，但离真正能用还差几步。我踩过的坑，列出来给你参考：

问题 原因 解决方案
加密后解密失败 明文大于 n 分块加密，每块小于 n
性能太慢 大数乘法效率低 用Karatsuba乘法或FFT
密钥生成卡死 质数生成算法太慢 用Miller-Rabin + 预筛法
内存泄漏 大数对象频繁拷贝 实现移动语义，减少拷贝

经验之谈：RSA不适合加密大量数据。实际项目中，RSA只用来加密一个对称密钥（比如AES的密钥），然后用AES加密真正的数据。这叫"混合加密"，既安全又高效。

写在最后

RSA的实现，说难不难，说简单也不简单。核心就三件事：大数运算、模幂运算、密钥生成。把这三块啃下来，剩下的就是组装。

我个人建议，初学者先不要追求性能，把功能跑通再说。等你能用自己写的RSA加密一段文字再解密回来，那种成就感，嗯，值得。

如果你在实现过程中遇到问题，比如大数乘法算不对、模逆元求不出来，别急。把每一步的中间结果打印出来，对照着数学公式一步步检查。调试密码算法，耐心比聪明更重要。

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

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