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)。比如 p61、q53那么 φ(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 * qn 就是加解密都要用的模数。计算φ(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能还原的完整逻辑链。举一个具体例子方便后面验证代码取 p61、q53那么 n3233、φ(n)3120。设 e17因为17与3120互质用扩展欧几里得算出 d2753。你可以直接验算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))这种基于系统时间的随机数在安全性面前等于没有。教学版我建议直接用固定素数比如 p61、q53。这样每次运行结果完全一致方便对着推导验证。等你要做工程版时再换成系统的安全随机数接口比如读取系统熵源或调用平台安全API这一步不会影响算法逻辑只影响素数来源。3. C代码实现从模幂到加解密主流程现在开始写代码。我用的是纯C标准库用到了 C17 的结构化绑定编译时记得加-stdc17。为了不打断思路我按“工具函数 - 核心算法 - 主流程”的顺序逐步给出。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) tuplelong 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() { // 固定测试参数p61, q53, e17 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 完整运行结果用固定参数 p61、q53、e17 编译运行输出如下p 61, q 53 n 3233, phi(n) 3120 公钥: (n3233, e17) 私钥: (n3233, d2753) 明文: 42 密文: 2557 解密后明文: 42看到最后一行的解密后明文: 42和明文完全一致说明整套流程是通的。如果你自己改了明文只要结果能还原也算通。4.2 手动验算42是怎么变成2557再变回来的很多读者可能会觉得“代码跑通了就完事”但我强烈建议你手动推一遍加解密因为这会让你对快速模幂产生真正的手感。以明文 m42 为例加密是42^17 mod 3233。把指数17拆成二进制10001也就是16 1。快速模幂过程res 1base 42第0位是1res 1×42 42base 42² mod 3233 1764第1位是0base 1764² mod 3233 1550第2位是0base 1550² mod 3233 381第3位是0base 381² mod 3233 2909第4位是1res 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 密钥选择三禁忌e1、不互质、p约等于q第一e1 完全不行。任何数m^1 mod n m加密等于没加密。第二e 与 φ(n) 不互质时模逆元不存在generate_key会直接报错退出。代码里已经做了 gcd 检查但自己手写时容易漏。第三p 和 q 不能太接近。如果 p≈q攻击者可以从 n 出发猜测差值进行分解。比如 n10403如果 p101、q103两者只差2穷举很容易就试出来了。工程上选取素数时还会检查两者差值不能让它们落在同一量级的窄区间里。另外p 和 q 要避免是连续素数、斐波那契序列等有规律的结构否则攻击者利用规律可以直接推算。5.3 调试与验证技巧中间量打印和固定回归基准我调试教学代码时发现最有效率的方法是“全过程打印”。不只是打印最终明文连 φ(n)、d、公钥、私钥、加密后密文全部打印出来。一旦解密失败能立刻定位是密钥生成错了还是加密过程错了。还有一个更隐蔽的坑明文取 0 或 1。0^e mod n 01^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对你来说就不再是一个黑盒了。最后再分享一个小技巧我验证实现是否正确习惯用 p61、q53、e17 这一组参数加密 42 得到 2557解密回来 42。只要这一组结果对就说明算法主线没有大问题。之后做任何扩展都以这组结果作为回归基准。这个习惯能帮你省掉后面大量排查时间。