C++ 实现 RSA 加密解密算法完整源码与步骤详解

青禾

发布时间：2026-10-16 | 6人浏览过

原创

本文详细讲解如何在 C++ 中从零开始实现 RSA 加密解密算法。内容涵盖密钥对生成的数学原理、模幂运算的实现以及完整的工程化代码示例，旨在通过结构化程序展示非对称加密的实际应用过程。

RSA 算法基础与核心原理

RSA 算法是一种广泛使用的非对称加密算法。与对称加密仅使用一个密钥不同，RSA 使用一对相关联的密钥：公钥（Public Key）和私钥（Private Key）。

公钥 (e, n)：对外公开，用于数据加密或验证数字签名。
私钥 (d, n)：严格保密，用于数据解密或生成数字签名。

其安全性建立在“大整数分解”的难度之上。只要两个素数的乘积足够大，逆向推导出这两个素数在计算上是极其困难的。

第一步：生成密钥对

构建 RSA 系统的第一步是生成公钥和私钥。以下是具体的数学操作顺序：

第1步：选择并判断两个大素数 P 和 Q

随机选择两个不相等的大素数 $P$ 和 $Q$，并使用函数 primeNum 验证其素数属性。

typedef long long ll;
// 判断素数函数实现
typedef long long ll;
ll primeNum(ll num)
{
    if (num == 1 || num == 0)
        return 0;
    for (int i = 2; i * i <= num; i++)
    {
        if (num % i == 0)
            return 0;
    }
    return 1; // 返回1表示是素数
}

第2步：计算 modulus N 和 Euler totient T

将 P 和 Q 相乘得到 N（这是公钥和私钥的共同部分），并计算 $T = (P-1)(Q-1)$。


ll n = p * q;
ll t = (p - 1) * (q - 1);

第3步：选取指数 E 并求 D

选择一个整数 $E$，满足 $1 < E < T$，且 $E$ 与 $T$ 互质（最大公约数为 1）。接着，根据欧拉定理，求解 $D$ 使得 $(E \times D) \pmod T = 1$。


// 简化版的寻找乘法逆元 D (实际应用中通常使用扩展欧几里得算法)
ll d = 1;
while (((e * d) % t) != 1)
    d++;

// 此时公钥为 (e, n)，私钥为 (d, n)
//

第二步：实现加密与解密的核心逻辑

RSA 的加密和解密本质上都是模幂运算。假设明文为 $M$，密文为 $C$，则加密公式为 $C = M^e \pmod n$，解密公式为 $M = C^d \pmod n$。

第4步：编写模幂运算函数 candp

为了高效处理大数运算中的取余，这里使用递归实现的模幂函数。该函数能够处理较大的指数的平方取余操作。

/**
* b: 底数 (明文或密文)
* p: 指数 (e 或 d)
* k: 模数 (n)
*/
ll candp(ll b, ll p, ll k)
{
    if (p == 1)
        return b % k;
    if (p == 2)
        return b * b % k;
    if (p % 2 == 0) { // 偶数次方
        ll sum = candp(b, p / 2, k);
        return sum * sum % k;
    }
    if (p % 2 == 1) { // 奇数次方
        ll sun = candp(b, p / 2, k);
        return sun * sun * b % k;
    }
    return 0;
}

// 加密操作示意
//

第5步：构建加密流程 Encryption

输入用户指定的公钥 $(e, n)$ 及明文 $M$。注意，**明文数值必须小于 N**。系统将调用 candp 计算出密文 $C$。

ll encryption()
{
    ll n, e, x, y; // x为明文, y为密文
    cout << "请输入公钥(e，n)" << endl;
    cin >> e >> n;
    cout << "请输入明文(需小于" << n << ")" << endl;
    cin >> x;
    
    y = candp(x, e, n);
    cout << "密文为:" << y << endl;
    return 0;
}

第6步：构建解密流程 Decode

接收方持有私钥 $(d, n)$ 和截获的密文 $C$。输入后，系统调用 candp 还原明文 $M$。

ll decode()
{
    ll n, d, x, y; // x为明文, y为密文
    cout << "请输入私钥(d，n)" << endl;
    cin >> d >> n;
    cout << "请输入密文: ";
    cin >> y;

    x = candp(y, d, n);
    cout << "明文为:" << x << endl;
    return 0;
}

// 解密示意图
//

工程化集成与测试运行

在实际开发中，应当采用模块化设计，将声明与实现分离。以下是完整的文件结构和主函数调用示例。

第7步：定义头文件 RSA.h

#pragma once
#include <iostream>
using namespace std;
typedef long long ll;

ll primeNum(ll num);
ll coprime(ll a, ll b);
ll candp(ll b, ll p, ll k);
ll key();
ll encryption();
ll decode();
void menu();