RSA加密算法，听起来像是只有密码学大佬才玩得转的东西，但拆开来看，核心就是三条公式、两个素数、一次乘法取模。这篇博文我打算用C++把整个RSA从密钥生成到加解密完整写一遍，代码可以直接跑，数学原理我会用尽可能直白的方式讲透，不绕弯子、不堆公式。适合刚接触公钥密码的学生、准备面试的开发者，以及任何想搞清楚RSA到底怎么回事的读者。
先说清楚这篇博文的定位：它是一个“轻量级教学版”，不是工业级实现。工业级RSA需要处理1024位以上的大整数、安全的随机数源、填充方案等等，这些在C++标准库里没有现成的东西。而教学版可以用内置的long long类型承载几百以内的素数，跑通整个加解密流程，把“算法长什么样、每一步为什么这么做”彻底搞明白。有了这个底子，后面想再往工程方向走，剩下的只是换大脑数运算库的事。
1. 先搞懂RSA在做什么：从一把钥匙到两把钥匙
很多人第一次接触RSA，卡住的不是代码，而是“为什么要这么做”。所以我把数学原理放在最前面，这部分消化了，代码就是按公式填空。
1.1 对称加密的尴尬：钥匙怎么安全送出去
在RSA出现之前，主流加密都是对称加密：加密用一把钥匙，解密也用同一把钥匙。就好比你家里只有一个保险箱，你和家人每人拿一把相同的钥匙，谁都能开。这在一个封闭小圈子里没问题，但一旦两个人相隔两地，怎么安全地把同一把钥匙送到对方手里，就成了死结。
你可以说“我坐飞机亲自送过去”，那只有一个人的时候可行。但网购时代，成千上万人同时要和服务器建立安全连接，不可能每人派个信使送钥匙。公钥加密的思路完全不同：锁和钥匙分离。别人用你的公钥（可以随便公开）把消息锁进箱子，只有你手里的私钥能打开。即使公钥和密文都被半路截走，没有私钥也解不开。RSA正是实现这种模式最经典的代表，它靠的是“单向函数”：正向计算极简单，反向破解极困难。
1.2 RSA依赖的三个数学工具：模运算、欧拉函数、模逆元
第一个是模运算。模就是取余数，a mod b表示a除以b的余数。这个概念你用钟表就能理解：13点其实就是下午1点，因为13 mod 12 = 1。模运算把无限的数字拉回一个有限范围，RSA所有计算都发生在这个范围内。
第二个是欧拉函数 φ(n)。它表示“小于n且与n互质的正整数个数”。这里不需要背公式，只需要记住一个关键结论：当 n 等于两个不同素数 p 和 q 的乘积时，φ(n) = (p - 1) * (q - 1)。比如 p=61、q=53，那么 φ(3233) = 60 * 52 = 3120。这个函数的出现，是RSA能够双向还原的“命门”。
第三个是模逆元。如果a * x ≡ 1 (mod m)，就说 x 是 a 在模 m 下的逆元。类比普通乘法里的倒数，a * (1/a) = 1；模运算里也有类似概念，但怎么求x就不是一除就完事，需要后面说的扩展欧几里得算法。
把这三个工具串起来，还需要一条定理：欧拉定理。它说如果 a 与 n 互质，那么a^φ(n) ≡ 1 (mod n)。RSA解密能成功，本质就是靠它把密文“转”回明文。这条定理不需要自己证明，考试和面试也不考证明，你只需要知道它的存在。
1.3 密钥生成的五个步骤：从选素数到求私钥指数
RSA密钥生成可以压缩成五步：
- 选两个大素数 p 和 q。
- 计算
n = p * q，n 就是加解密都要用的模数。 - 计算
φ(n) = (p - 1) * (q - 1)。 - 选一个公钥指数 e，要求
1 < e < φ(n)，并且 e 与 φ(n) 互质。常用 17 或 65537。 - 求私钥指数 d，满足
e * d ≡ 1 (mod φ(n))，也就是 d 是 e 在模 φ(n) 下的逆元。
为什么这样设计？加密公式是c = m^e mod n，解密公式是m = c^d mod n。把加密代入解密，就变成m^(e*d) mod n。因为e*d可以写成1 + k*φ(n)，所以m^(e*d) = m * (m^φ(n))^k ≡ m (mod n)。最后一步用的就是欧拉定理。这就是RSA能还原的完整逻辑链。
举一个具体例子，方便后面验证代码：取 p=61、q=53，那么 n=3233、φ(n)=3120。设 e=17（因为17与3120互质），用扩展欧几里得算出 d=2753。你可以直接验算：17 * 2753 = 46801，而46801 mod 3120 = 1，完全吻合。
2. 动手前的三个设计决策：让代码既简单又能跑
写代码之前，我先回答几个自己当初纠结过的问题。这些决策直接决定了代码的形态。
2.1 要不要上大数运算？轻量级版的定位
一句话回答：教学版不需要，硬上反而坏事。
真实RSA的密钥至少1024位，对应大约300位十进制数字，早就超出任何C++内置整数类型的范围。如果我从大数运算开始讲，光是加减乘除和取模就要写几百行，算法的核心反而被淹没了。我用过的教学方案里，最有效的其实是“小数字跑通逻辑”：
- p、q取几十到几百的小素数；
- n大约在几千到几十万这个量级；
- 所有中间结果都能用
long long装下； - 每步都能用计算器手动验算。
long long最大约9.22 * 10^18，也就是19位十进制数，完全够用。等逻辑跑通，再换大数库就是替换类型和少数运算函数的事，架构不用变。这个取舍，我认为是“轻量级版”最核心的设计决策。
2.2 快速模幂：直接先乘方再取模会翻车
加密要做m^e mod n。最朴素的想法是先把m^e算出来，再对 n 取模。但有两个问题：一是指数一大就爆。42的17次方还能忍，工业级指数是几百位的数字，根本没有类型能存。二是慢。就算存得下，乘法的次数也是指数级别的，完全不现实。
所以要用快速模幂算法，把指数按二进制拆开。比如指数17的二进制是10001，即17 = 16 + 1，那么m^17 = m^16 * m^1。算法维护一个base变量，每轮把base平方，对应二进制每个位的权重；如果当前二进制位是1，就把res乘上当前的base。因为每一步都取模，中间数值始终不会超过mod * mod的量级。
复杂度从 O(指数) 降到 O(log 指数)，这就是“快速”的来源。后面你会发现，整个RSA的性能基本就是被快速模幂的几个乘法撑起来的。
2.3 扩展欧几里得算法：模逆元一口气求出来
求 d 需要解e * d ≡ 1 (mod φ(n))，也就是找到 d 使e*d - k*φ(n) = 1。这个式子左边是“a乘以未知数 + b乘以未知数 = gcd(a, b)”的形式，正是扩展欧几里得算法的看家本领。
普通欧几里得算法求最大公约数大家都会：不停取余。扩展欧几里得算法在求gcd的同时，反推出满足a*x + b*y = gcd(a,b)的一组整数 (x, y)。当 gcd(e, φ) = 1 时，e*x + φ*y = 1，那 x 就是我们要的 d。递归实现的代码很短，后面我会给完整版。
还有一个细节：算法求出的 x 可能是负数。x 的绝对值加上 φ 之后，才是范�模 φ(n) 下的逆元，也就是最终 d 需要在[0, φ(n))区间内。
2.4 随机数从哪来：教学版和工程版的分界线
工业级RSA的两个素数必须是随机选取的，而且随机数源必须是密码学安全的。所谓“密码学安全”，简单说就是攻击者无法预测下一个随机数。srand(time(0))这种基于系统时间的随机数，在安全性面前等于没有。
教学版我建议直接用固定素数，比如 p=61、q=53。这样每次运行结果完全一致，方便对着推导验证。等你要做工程版时，再换成系统的安全随机数接口（比如读取系统熵源或调用平台安全API），这一步不会影响算法逻辑，只影响素数来源。
3. C++代码实现：从模幂到加解密主流程
现在开始写代码。我用的是纯C++标准库，用到了 C++17 的结构化绑定，编译时记得加-std=c++17。为了不打断思路，我按“工具函数 -> 核心算法 -> 主流程”的顺序逐步给出。
3.1 基础工具：快速模幂、试除素数和辗转相除
先看快速模幂。这是RSA加密解密共用最频繁的函数，没有它就谈不上性能。
#include <iostream> #include <tuple> #include <cstdlib> using namespace std; // 快速模幂：计算 (base^exp) % mod long long mod_pow(long long base, long long exp, long long mod) { long long res = 1; base %= mod; while (exp > 0) { if (exp & 1) // 当前二进制位是1 res = res * base % mod; base = base * base % mod; // 权重平方 exp >>= 1; // 右移一位 } return res; }这里最关键的是base %= mod和每一步都取模。如果漏掉，base平方可能瞬间膨胀，long long直接就溢出了。
然后是素数判定。教学版用试除法就够：判断 n 是否是素数，只需要试到 √n。这里有个细节，循环条件写成i * i <= n可能有溢出风险（n很大时），更好的写法是i <= n / i。
// 简单的素数判定（试除法） bool is_prime(long long n) { if (n < 2) return false; if (n % 2 == 0) return n == 2; for (long long i = 3; i <= n / i; i += 2) { if (n % i == 0) return false; } return true; } // 返回满足 prime >= n 的最小素数 long long next_prime(long long n) { if (n <= 2) return 2; if (n % 2 == 0) ++n; while (!is_prime(n)) n += 2; return n; }next_prime函数是给主函数选素数用的。你可以传一个大概范围内的数，它自动帮你递推到最近的素数。放在教学版里，比手动查素数表省事。
gcd 直接用辗转相除，递归写法只有一行：
long long gcd(long long a, long long b) { return b == 0 ? a : gcd(b, a % b); }无参情况下，递归深度最多几十层，不用担心栈溢出。
3.2 求模逆元的核心：递归回代一页纸
扩展欧几里得的递归实现，我推荐用 tuple 返回，逻辑比引用参数好理解得多。
// 扩展欧几里得算法：返回 (gcd, x, y)，满足 a*x + b*y = gcd(a,b) tuple<long long, long long, long long> ext_gcd(long long a, long long b) { if (b == 0) return {a, 1, 0}; auto [g, x1, y1] = ext_gcd(b, a % b); return {g, y1, x1 - (a / b) * y1}; }理解这段的关键在回代过程：递归到底层后返回一组解(g, x1, y1)，它们满足b*x1 + (a%b)*y1 = g。而我们想要的是a*x + b*y = g。利用a % b = a - (a/b)*b，把左边变换一下，就能推出新的解：
x = y1y = x1 - (a / b) * y1
这就是代码里return {g, y1, x1 - (a/b) * y1}的含义。担心看不明白的读者，拿起笔推一层就能通，这也是这一小段代码最值得动手推的地方。
有了ext_gcd，模逆元就是顺手的事：
// 计算 a 在模 m 下的逆元，要求 gcd(a, m) = 1 long long mod_inverse(long long a, long long m) { auto [g, x, y] = ext_gcd(a, m); if (g != 1) { cerr << "逆元不存在，请检查 a 和 m 是否互质" << endl; exit(1); } return (x % m + m) % m; // 调整到 [0, m) 范围 }注意最后一行：x可能是负数，所以先取模再加m再取模，这是负数取模的通用处理方式。
3.3 密钥结构体、加解密函数与主流程
用一个结构体把三个关键数字打包：
struct RSAKey { long long n; // 模数 long long e; // 公钥指数 long long d; // 私钥指数 }; RSAKey generate_key(long long p, long long q, long long e) { long long n = p * q; long long phi = (p - 1) * (q - 1); if (gcd(e, phi) != 1) { cerr << "e 与 phi(n) 必须互质" << endl; exit(1); } long long d = mod_inverse(e, phi); return {n, e, d}; }generate_key里做了互质检查，这一步很必要，因为 e 不合法时后面求 d 必然出错。
加解密函数就是快速模幂的封装：
long long encrypt(long long m, long long e, long long n) { return mod_pow(m, e, n); } long long decrypt(long long c, long long d, long long n) { return mod_pow(c, d, n); }至此，RSA 的核心逻辑已经完整。主函数我写成“演示模式”，每一步都打印出来：
int main() { // 固定测试参数：p=61, q=53, e=17 long long p = 61, q = 53, e = 17; RSAKey key = generate_key(p, q, e); cout << "p = " << p << ", q = " << q << endl; cout << "n = " << key.n << ", phi(n) = " << (p - 1) * (q - 1) << endl; cout << "公钥: (n=" << key.n << ", e=" << key.e << ")" << endl; cout << "私钥: (n=" << key.n << ", d=" << key.d << ")" << endl; long long m = 42; // 明文，这里用一个整数做示范 long long c = encrypt(m, key.e, key.n); long long m2 = decrypt(c, key.d, key.n); cout << "明文: " << m << endl; cout << "密文: " << c << endl; cout << "解密后明文: " << m2 << endl; return 0; }如果你不满足于固定素数，可以换成动态选素数的写法：
long long p = next_prime(200 + rand() % 100); long long q = next_prime(400 + rand() % 100);但教学阶段我建议还是固定参数跑通，后面再折腾。
4. 跑通Demo：密钥生成、加密、解密全流程实测
代码写完了，最重要的是跑起来并验证结果。这一步能确认你的算法理解是不是对的。
4.1 完整运行结果
用固定参数 p=61、q=53、e=17 编译运行，输出如下：
p = 61, q = 53 n = 3233, phi(n) = 3120 公钥: (n=3233, e=17) 私钥: (n=3233, d=2753) 明文: 42 密文: 2557 解密后明文: 42看到最后一行的解密后明文: 42和明文完全一致，说明整套流程是通的。如果你自己改了明文，只要结果能还原，也算通。
4.2 手动验算：42是怎么变成2557再变回来的
很多读者可能会觉得“代码跑通了就完事”，但我强烈建议你手动推一遍加解密，因为这会让你对快速模幂产生真正的手感。以明文 m=42 为例：
加密是42^17 mod 3233。把指数17拆成二进制10001，也就是16 + 1。快速模幂过程：
- res = 1，base = 42；
- 第0位是1，res = 1×42 = 42，base = 42² mod 3233 = 1764；
- 第1位是0，base = 1764² mod 3233 = 1550；
- 第2位是0，base = 1550² mod 3233 = 381；
- 第3位是0，base = 381² mod 3233 = 2909；
- 第4位是1，res = 42×2909 mod 3233 = 2557。
所以密文是2557，和代码输出一致。
解密是2557^2753 mod 3233，结果自然回到42。这里不需要手算完整过程，你只需要验证一个关键数字：17 × 2753 = 46801，而46801 mod 3120 = 1。这正好说明 d 是 e 在模 φ(n) 下的逆元，逻辑闭环。
看见没有，整条链路其实就两件事：生成密钥时用一次扩展欧几里得，加解密时用两次快速模幂。RSA的骨架就这么简单。
5. 避坑指南：我踩过的溢出、密钥选择和调试坑
代码看着顺，但实际写的时候我踩过不少坑。这里整理成清单，希望对你有用。
5.1 long long的乘法溢出边界
快速模幂里有一个隐患：base * base % mod和res * base % mod。如果mod本身很大，base也可能很大，两个数相乘会超过 long long 的上限。
经验法则：当mod小于sqrt(9.22 * 10^18)，也就是大约 30亿 时，直接相乘基本安全。超过这个值，要么把乘法换成__int128做中间过渡再转回 long long，要么实现教科书式的大数乘法取模。教学版里 n 通常只有几千几万，完全不用慌。但如果你想测试 long long 的极限，这个坑一定会出现。
// 用 __int128 防溢出的 mul_mod 示例 long long mul_mod(long long a, long long b, long long mod) { return (long long)((__int128)a * b % mod); }设计这个函数是为了教学演示防溢出，真做大整数还是得靠大数库。
5.2 密钥选择三禁忌：e=1、不互质、p约等于q
第一，e=1 完全不行。任何数m^1 mod n = m，加密等于没加密。
第二，e 与 φ(n) 不互质时，模逆元不存在，generate_key会直接报错退出。代码里已经做了 gcd 检查，但自己手写时容易漏。
第三，p 和 q 不能太接近。如果 p≈q，攻击者可以从 n 出发，猜测差值进行分解。比如 n=10403，如果 p=101、q=103，两者只差2，穷举很容易就试出来了。工程上选取素数时还会检查两者差值，不能让它们落在同一量级的窄区间里。
另外，p 和 q 要避免是连续素数、斐波那契序列等有规律的结构，否则攻击者利用规律可以直接推算。
5.3 调试与验证技巧：中间量打印和固定回归基准
我调试教学代码时发现最有效率的方法是“全过程打印”。不只是打印最终明文，连 φ(n)、d、公钥、私钥、加密后密文全部打印出来。一旦解密失败，能立刻定位是密钥生成错了还是加密过程错了。
还有一个更隐蔽的坑：明文取 0 或 1。0^e mod n = 0，1^e mod n = 1，这会导致“加密后密文等于明文”，看起来就像算法失效。实际上这是正常数学现象，不是bug，但初学者很容易被吓到。测试用明文建议选 2 以上的数，比如学号尾号、生日数字。
字符串转数字也有讲究。不要直接拿char类型强转当数字，因为 char 本身可能有符号位问题。最简单的教学约定是直接用 ASCII 码：'A'对应 65，作为明文数字。这样解密回来后转回字符就行。但这属于扩展玩法，先把整数流程跑通再玩字符串。
6. 从教学版到工程版：补齐这四块拼图
轻量级版跑通之后，你可能会问：这个能直接拿去做真实产品吗？答案是绝对不能。差距在四个方面，每块都是硬骨头。
6.1 大数：从long long换到任意精度
第一件事就是把 long long 换成任意精度大数。真实RSA的 n 是1024位甚至2048位的二进制数，约合300到600位十进制数。工程上一般直接用一套成熟的密码学大数库，里面封装了大数加减乘除、模幂、求逆等操作。好消息是，你不需要重写业务逻辑：只要把函数参数类型从 long long 换成大数类型，其余算法结构完全复用。这也是我把解耦做得很清晰的原因。
6.2 素数判定：从试除法到Miller-Rabin
试除法在 n 为几位数时很爽，但到了几百位的量级，试到 √n 会慢到天荒地老。工业级实现用的是 Miller-Rabin 素性检测，它能在多项式时间内给出“极大概率是素数”的结论。再配合固定的小素数表做预筛选，速度还能再提升几个量级。这块其实是密码学实现的隐藏重点：密钥生成的大部分CPU时间都花在找素数上。
6.3 填充与语义安全：为什么裸RSA不能直接上线
裸RSA有一个致命弱点：确定性强。同一个明文，两次加密得到的密文完全相同。攻击者如果掌握明文空间，可以通过枚举比对密文，直接猜出明文。这在真实场景中是不可接受的。
解决方案是在加密前做填充，经典的有 OAEP 填充。简单说，就是把固定格式的随机字节和明文混在一起，再作为一个整体做模幂运算。这样即使明文相同，只要随机字节不同，密文就完全不同。这是“语义安全”的核心要求。到这里你会发现，真实RSA的数学内核仍然是课本上那套欧拉定理，但外面包了好几层防护壳。
6.4 密钥管理：公钥认证和私钥存储
最后一块拼图是密钥管理。公钥怎么证明它是你的？需要证书体系。私钥怎么存才安全？硬件安全模块、安全容器等，都是一套专门的体系。这部分跟算法本身关系不大，但任何真实系统都逃不开。知道它的存在，比现在钻进去研究更重要。
我从第一次手写RSA到现在，最大的体会是：很多看似高深的算法，拆到底层就是“一个数学结论 + 一个快速算法 + 一堆工程防护”。RSA的数学结论是欧拉定理，快速算法是快速模幂和扩展欧几里得，工程防护则是大数、随机素数、填充方案这老三样。建议你拿到这部分代码后，先把 p、q 的值换掉跑一遍流程；再把消息改成让自己有感的数字，比如生日或学号，手动用计算器验算密文；最后再试着把模数加大到 long long 允许的极限，感受一下溢出问题。三步走完，RSA对你来说就不再是一个黑盒了。
最后再分享一个小技巧：我验证实现是否正确，习惯用 p=61、q=53、e=17 这一组参数，加密 42 得到 2557，解密回来 42。只要这一组结果对，就说明算法主线没有大问题。之后做任何扩展，都以这组结果作为回归基准。这个习惯，能帮你省掉后面大量排查时间。
