C/C实现RSA加密算法这标题一看就是很多人在找的东西。我最初接触RSA是在大学学密码学那会儿课本上讲得头头是道但真到了要自己动手写代码才发现从数学公式到能跑的C语言程序之间隔着一整个世界的坑。最近因为一个模拟项目X的需要我又把这段代码翻出来重构了一遍顺手把整个实现过程、踩过的坑、还有一些网上资料里语焉不详的细节全部整理出来希望对正在啃这块硬骨头的朋友有帮助。这篇文章不打算只贴一份能跑的代码那样没多大意义——网上一搜一大把。我想重点讲清楚几个东西RSA算法背后的数学原理到底怎么映射到C语言的数据结构上大数运算怎么在没有现成库的情况下自己实现以及密钥生成、加解密、签名验签这几个核心环节在实际编码中各自有哪些容易翻车的细节。适合人群是已经学过C语言基础语法、看得懂指针和结构体但第一次接触密码学编程的读者。看完之后你不仅能自己写出一套能用的RSA实现还知道为什么网上很多源码跑不通、改不动。1. 整体设计与思路拆解1.1 RSA算法的数学核心与代码映射RSA的安全性建立在“大整数分解困难”这个数学假设上。整套算法其实只依赖四个数学操作模幂运算计算m的e次方模n、最大公约数求解用于找e和φ(n)互素、乘法逆元求解用于计算私钥d、以及Miller-Rabin素性检测用于生成大素数。这四个操作听上去都不复杂大学数论课的基础内容。但一旦涉及实际密钥长度——比如1024位甚至2048位——问题就来了C语言里最大的内置类型unsigned long long也就64位连个128位的小数都装不下更别说1024位的大整数了。所以C语言实现RSA第一道坎不是算法本身而是大数存储和运算。这里有两种路线可以选择调用现成的大数库比如OpenSSL的BN接口或者GMP开发效率最高业界也都是这么干的。自己实现一套大数运算核心思路是把大整数拆成数组用数组元素存储“数字的某一段”然后模拟手算加减乘除的过程。我在模拟项目X中选择了自己实现。原因很现实第一项目要求不依赖第三方库纯C环境编译运行第二理解了底层的大数运算之后再去看OpenSSL的代码会顺畅得多。当然如果目标是实际生产项目直接上OpenSSL是明智的但是学习的话自己造一遍轮子收获更大。1.2 动手之前先明确的设计决策编写之前我想清楚了三件事这也直接影响后面的代码结构。第一密钥长度定为多少我选择了512位作为默认。理由很实际1024位的RSA在现代安全标准里已经算入门级别但对于一个教学演示项目来说512位跑起来速度更快写代码调试时数字更短出错更容易定位数据结构和算法逻辑和1024位完全一致。代码里用宏定义控制密钥长度换长密钥只需改一个数字。第二大数用什么方式存储我用了无符号32位整数数组每个元素存放大数的一个“分段”分段大小是32位而不是8位或者64位。选32位是因为乘法运算时两个32位数相乘的结果是64位恰好能用unsigned long long无损保存中间结果不会溢出。如果单个元素用64位两个相乘就是128位C语言原生类型装不下就得另想办法复杂度陡增。第三私钥指数d怎么计算标准做法是用扩展欧几里得算法求e关于φ(n)的乘法逆元。这个我在代码里单独实现了一个函数后面会详细讲。1.3 为什么好多网上的源码跑不通我在找参考代码的时候发现网上流传的C语言RSA实现存在几个典型问题。不少代码为了简化直接用int甚至long存大数密钥长度只敢开到32位或者64位这样的“RSA”本质上只是演示了数学公式完全没有实际应用价值。更有一些代码在计算明文/密文时直接把字符串按字节切分每个字节作为一块独立加密这确实能跑但会暴露大量统计特征从密码学角度讲属于不安全的“教科书模式”。我在自己的实现里特意避开了这些坑大数运算用数组实现加解密按块处理每块尽可能填满密钥长度对应的数据位而不是简单按字节切。2. 大数运算库的底层实现2.1 大数的数据结构与基本运算大数数据结构是我这个实现的地基。设计如下#define RSA_KEY_BITS 512 #define RSA_WORD_BITS 32 #define RSA_WORDS ((RSA_KEY_BITS) / (RSA_WORD_BITS)) // 16个32位字 typedef struct { uint32_t words[RSA_WORDS]; int len; // 实际使用的字数从最高有效位往下数 } bignum_t;len字段记录实际使用了几段避免对全零的高位做无意义的循环。例如数字5words[0]5len1而一个真正的512位大数len会是16。我实现了一套完整的大数运算原语每个都对应数学上的一个基本操作比较函数compare_bignum类似strcmp的思路从最高位往下逐段比较。加法和减法模拟十进制手算的进位/借位只不过从“逢十进一”变成“逢2^32进一”。乘法和除法这是最核心也最复杂的部分。乘法我用了标准的多精度乘法两层循环逐段相乘并累加进位中间结果用unsigned long long承接。模运算求a mod m实现方式是“试商法”——逐位逼近商然后减去商与除数的乘积。这里其实还有个优化空间后面我会讲到。大数乘法的核心代码长这样static void big_mul(const bignum_t *a, const bignum_t *b, bignum_t *res) { uint64_t tmp[RSA_WORDS * 2] {0}; int i, j; for (i 0; i a-len; i) { uint64_t carry 0; for (j 0; j b-len; j) { uint64_t cur tmp[i j] (uint64_t)a-words[i] * b-words[j] carry; tmp[i j] (uint32_t)cur; carry cur 32; } tmp[i j] carry; } // 将tmp截断或赋回res }内层循环里有一个关键点tmp[ij]在累加当前乘积之前可能已经有一个来自之前迭代的残留值这个值加上当前两个单词的乘积64位再加上低位进位最大可能达到多少能保证不溢出64位吗我当时专门算过——两个32位数相乘最大值约2^64再加上一个32位的残留值大约是2^64 2^32这需要靠carry变量的巧妙处理来确保不溢出。实际更稳妥的做法是每次算乘积前把tmp[ij]先放进另一个unsigned long long变量。因为整个累加链条里tmp[ij]的值本身不会超过32位每次都会被截断所以累加的三个数分别是32位、64位、32位总和最多约2^642^33依然在unsigned long long的169位范围内。用64位变量暂存然后截断低32位赋值给tmp高32位作为新的进位这套代码我在模拟项目X里跑了大量随机测试没有发现溢出问题。2.2 蒙哥马利模幂RSA性能的关键RSA的核心运算是模幂也就是计算base^exp mod mod。如果直接用最简单的循环乘法计算量是不可接受的。512位指数的二进制表示有512位意味着要做约512次平方和平均256次乘法运算每次乘法又是一个512位大数乘法复杂度是O(n^2)级别这算下来很可观。标准做法有两种一种是“平方-乘”算法配合每次取模另一种是蒙哥马利模幂。两者的核心区别在于前者的取模运算是普通的除法比较慢蒙哥马利算法把取模替换成一系列移位和加法对于二进制计算机来说移位操作成本极低。我当时选的是“平方-乘”配合优化的模约减因为实现简单逻辑容易理解而且512位密钥长度下性能足够好。bignum_t big_powmod(const bignum_t *base, const bignum_t *exp, const bignum_t *mod) { bignum_t result {1}; bignum_t base_cur *base; // 从exp最高位到最低位扫描 for (int i exp-len - 1; i 0; i--) { for (int bit 31; bit 0; bit--) { // 每轮先平方取模 big_mul(result, result, tmp); big_mod(tmp, mod, result); // 如果当前位为1再乘base if ((exp-words[i] bit) 1) { big_mul(result, base_cur, tmp); big_mod(tmp, mod, result); } } } return result; }这个算法的正确性依据很简单从指数的二进制位来看每扫描一位相当于对当前结果做一次平方如果该位是1就再乘一次底数。这本质上就是在做“边平方边模”的快速模幂。2.3 费马小定理与Miller-Rabin素性检测RSA需要两个大素数p和q。怎么在C里拿到可靠的素数我用的是“随机生成素性检测”的组合素性检测用Miller-Rabin。Miller-Rabin的核心依据是费马小定理的扩展如果n是素数那么对于任意a1an-1满足a^(n-1) ≡ 1 (mod n)同时还满足一个平方根的“非平凡性”条件。反过来如果n是合数那么至少有3/4的a会暴露它的合数本质。所以随机取k个a做测试如果每次都通过那么n是合数的概率不超过(1/4)^k。我做了20轮测试误判概率低至2^-40对教学演示项目来说算是非常安全的上边界。Miller-Rabin里有个容易出错的细节先把n-1写成d * 2^s的形式其中d是奇数。在实际测试时先计算a^d mod n如果结果等于1或者n-1这轮测试通过否则不断平方看能不能在s-1步内变成n-1。如果一次都没有就判定n是合数。int miller_rabin(const bignum_t *n, int rounds) { // 先排除小的偶数等特殊情况 // 找到 d 和 s 使得 n-1 d * 2^s bignum_t d *n; big_sub_word(d, 1, d); int s 0; while (big_is_even(d)) { big_shr(d, 1, d); s; } for (int r 0; r rounds; r) { bignum_t a random_bignum_range(two, nminus2); bignum_t x big_powmod(a, d, n); if (big_is_one(x) || big_equal(x, nminus1)) continue; int composite 1; for (int i 0; i s - 1; i) { big_mul(x, x, tmp); big_mod(tmp, n, x); if (big_equal(x, nminus1)) { composite 0; break; } } if (composite) return 0; } return 1; }注意Miller-Rabin的前提是待测数n必须是奇数。生成随机奇数之后再交给Miller-Rabin如果测试不通过就把这个数加2继续测而不是重新生成随机数——这样能极大地缩短平均搜索时间。3. 密钥生成与加解密完整流程3.1 密钥生成的关键步骤与参数选择密钥生成分五个步骤每一步都有必须满足的约束条件。第一步生成两个512位的大素数p和q。在这个具体实现里我生成的是256位的素数这样p和q的乘积n正好是512位。两个素数的位数大致相等使得分解n的难度最大。第二步计算n p * qfai(n) (p-1) * (q-1)。注意这里必须用p-1和q-1相乘直接拿p*q当φ(n)会让整个算法崩溃我当时调试时因为忽略了减1导致后面公钥私钥校验永远不通过。第三步选择公钥指数e。教材里喜欢用e3或者e65537其实e3非常常见于教科书但实际使用中有微小的安全风险如果不同用户用了相同的e和相同的消息且明文相同攻击者可以利用中国剩余定理破解。所以实际工程中通常用65537因为它是费马数F4二进制表示是10000000000000001只有两个bit为1计算模幂的效率很高。我选择了65537作为默认公钥指数并且在代码里检查gcd(e, fai(n))必须等于1如果不等于1就重新生成p和q。第四步用扩展欧几里得算法求d满足e*d ≡ 1 (mod fai(n))。这一步对应数论里的乘法逆元数学套路是固定的但写成C代码时要处理负数情况——中间变量可能是负数需要加上fai(n)让它回到正数范围。第五步销毁p、q、φ(n)。这三个值只用于生成密钥对如果泄漏攻击者就能从n反推出d。我的代码里在密钥生成完以后用一个循环把存放这些值的数组全部清零。下面这个表格把密钥生成过程中的每个输入输出、约束和参数选择逻辑说清楚参数值/取值方式约束条件我的说明p, q256位随机素数p ! q且位数相近用Miller-Rabin测试20轮生成失败自动2np * q512位就是公钥的一部分也是模运算的模数φ(n)(p-1)(q-1)绝不公开只在生成阶段参与计算e65537gcd(e, φ(n))1工程通用值二进制只有2个1模幂快de关于φ(n)的逆元e*d ≡ 1 mod φ(n)用扩展欧几里得计算私钥核心3.2 分组加密的块大小与填充方式RSA本质上只能对小于n的整数做运算所以原始数据要先切成块每块转成一个小于n的整数。块大小怎么定有很多人直接用1字节或者2字节简单是简单但留下两个问题一个是每块的空间利用率太低2048位密钥每块只能传1字节浪费大量带宽另一个是密文块太小会暴露频率特征。正确的做法是把块大小设为密钥字节数减11。为什么要减11因为实际加解密流程还要考虑一个东西——填充。如果明文块数值恰好为0那密文就永远是0也会泄露信息。所以标准做法是给每块加一个“OAEP”或者至少是“PKCS#1 v1.5”格式的填充里面包含随机数和固定标志字节这样即使同一块明文多次加密密文也不相同。我的实现里用了简化的填充方案每块数据前加一个固定前缀字节0x02表示“块起始”块末尾补一个随机盐保证最终块的值小于n且在解密时能正确恢复出原始数据。实际操作中我最开始用的是最简方案——明文直接按字节分组每组不超过密钥字节数的整数倍。后来发现一块长度超过一半密钥的时候运算结果根本解不回来原因是模n之后的数值可能大于原消息需要额外长度存储。换成“密钥长度减11”之后这个问题就彻底消失了。这个11字节的开销是标准填充必须付出的代价。3.3 加密与解密的函数调用关系公钥加密的入口是rsa_encrypt它接收公钥(n, e)和明文块输出密文块。函数内部做一件事把明文块从字节数组转成大数调用big_powmod计算密文再把结果转回字节数组。私钥解密入口是rsa_decrypt接收私钥d和n把密文块转成大数同样调big_powmod但指数换成d结果就是明文块。下面这段是完整的加密块处理函数核心逻辑 c int rsa_encrypt_block(const uint8_t *plain, int plain_len, rsa_pubkey_t *pub, uint8_t *cipher, int *cipher_len) { bignum_t m, c; big_from_bytes(m, plain, plain_len); // 确保m小于n if (big_compare(m, pub-n) 0) { return -1; // 块太长 } big_powmod(m, pub-e, pub-n, c); big_to_bytes(c, cipher, cipher_len); return 0; }解密那边结构一模一样只是指数换成私钥d。为了速度还有一个小优化选择——使用中国剩余定理加速私钥运算把模幂分解成模p和模q两个半规模运算再用CRT组合理论上能快三到四倍。但我没有在初版实现里加这个因为CRT的代码复杂度更高而且要再次接触p和q——之前费了心思把p和q销毁了。如果把p和q保留下来加速解密又得对私钥存储结构做额外设计。权衡后512位密钥下直接模幂的速度已满足教学演示需求CRT留作进阶优化方向。4. 签名验签与消息哈希的配合4.1 签名验签的逻辑本质RSA签名验证和加解密在数学形式上是“对称”的签名就是用私钥对消息的哈希值做“解密”也就是私钥指数运算验证就是用公钥对签名做“加密”公钥指数运算。所谓“解密”这里只是借用概念因为私钥只有持有者知道所以能生成有效签名的只可能是持钥者。但签名的直接对象不能是消息本身。原因一是RSA运算长度有限消息通常比模数长二是如果直接对消息做签名运算别人可以伪造任意签名的“消息”——只要拿公钥算一次就知道它对应的原文完全失去防伪能力。正确做法是先对消息取哈希摘要比如SHA-256再把摘要用固定格式填充到块大小最后对填充结果做签名运算。我在模拟项目X里整合了一个本地实现的SHA-256因为不想让整个项目依赖外部库。签名过程分三步对消息做SHA-256哈希把哈希值填充到块大小内调用rsa_sign_private进行模幂运算。验证过程反过来先算消息的SHA-256用公钥对签名做模幂运算解出填充后的哈希比对两边哈希值一致则验证通过。4.2 签名的编码格式填充的固定前缀签名填充和加密填充略有不同。加密填充用的是0x02前缀表示“公钥操作”签名填充则用0x01前缀表示“私钥操作”。这个区别来自标准设计防止同一块数据既被当作加密又被当作签名而造成混乱。后面接的是哈希算法的标识头一共是2字节算法标识32字节SHA-256摘要再加上填充字节通常是0xFF最后以0x00结尾。这样设计有个好处验证方可以明确知道恢复出来的数据里包含哪个哈希算法即便将来升级到SHA-384或者SHA-512旧的验签代码依然可以兼容验证老签名。#define SHA256_DIGEST_LEN 32 int rsa_sign(const uint8_t *msg, int msg_len, rsa_privkey_t *priv, uint8_t *sig, int *sig_len) { uint8_t hash[SHA256_DIGEST_LEN]; sha256(msg, msg_len, hash); // 构造 DigestInfo 块 uint8_t block[RSA_KEY_BITS/8]; block[0] 0x01; // 填充 0xFF int pad RSA_KEY_BITS/8 - 3 - SHA256_DIGEST_LEN; for (int i 1; i pad; i) block[i] 0xFF; block[pad1] 0x00; block[pad2] 0x30; block[pad3] 0x31; // DER header for SHA-256 memcpy(block pad 4, hash, SHA256_DIGEST_LEN); // 对block做私钥模幂 // ... }4.3 签名验证过程与常见陷阱验证的代码数学上只是把签名值做公钥模幂然后检查恢复出的块是否符合“0x01 ... 0x00 || DER header || hash”的结构。如果块的第一字节不是0x01或者后续的0xFF和0x00结构不对或者哈希算法标识不匹配都要直接返回验证失败。这中间有个经典的实现陷阱叫“信息泄露”。有时候验证方只比对哈希值不去管填充字节是否严格符合格式这在某些攻击场景下会给攻击者可乘之机。比如有的实现允许填充部分全零攻击者可能构造一个等价签名的伪造块导致签名验证通过。所以我的实现里有一个严格检查填充的函数任何一步不对就直接返回失败不做模糊的“宽容处理”。5. 常见问题与排查技巧实录5.1 加密结果解密不回来的几种情况这是所有新手第一次调试RSA时必踩的坑。现象是加密后的密文用私钥一解出来一堆乱码或者错误数据。排查思路按顺序来——先检查明文块长度有没有超过n的字节数。如果每块明文长度超过密钥字节长度那模运算就会破坏数据没有任何密钥能解回来。其次检查填充格式加密时如果加了随机盐解密时是否能够正确剥离有些实现加密有填充但解密没去填充肉眼很难发现。最后检查大数转字节的字节序问题大数的高字节是放在数组前面还是后面我踩过这个坑——把大数转回字节数组时用了小端序而明文转换时用了大端序导致加解密各有一次字节序翻转结果自然不对。5.2 大数乘法溢出与中间值处理讲一个我在调试过程中真实遇到的bug。在做大数乘法时我最初把tmp数组定义成32位而不是64位结果在算乘法中间值的低32位时进位信息直接丢掉了。表现是小数字相乘一切正常换成512位的大数字相乘结果首位总是莫名其妙少了一点点导致后面所有操作跟着错。排查了整整一个下午最后把tmp数组改成64位并且在每次赋值时强制截断低32位进入结果数组一切恢复正常。提醒一下大数乘法中间结果的类型宽度必须是单字宽度的两倍这是硬性约束。如果图省事用和结果数组同宽的变量零测试用例永远不会出问题但大数字一上来就崩。5.3 素数生成效率低与随机数质量问题刚开始写Miller-Rabin时我用的随机数源是C标准库的rand()每次都随机生成一个全新的奇数来做测试。结果问题来了生成一个256位素数平均要试多少次概率上大约每116次随机奇数中才有一个是素数粗略估计但rand()的周期只有2^31而且它的低位随机性不佳。当随机数来源本身质量差的时候生成的“素数”可能是伪素数也可能连续几十万次都找不到合适的数。解决办法有两个一个是用更高质量的随机数源在Linux下可以直接读/dev/urandom在Windows下用系统的密码学随机数API另一个是对于单个候选数如果Miller-Rabin一轮失败就让它加2进入下一个奇数继续测试而不是从头随机生成新数。这样做能显著提升搜索速率。5.4 常见问题速查表现象可能原因排查/解决方法加密后无法解密明文块过长缩短块长度确保明文数值小于n加密解密结果颠倒字节序处理不一致统一大数和字节数组的转换方向大数字相乘结果异常中间变量类型位数不足用两倍字长的类型存中间结果素数生成极慢随机数质量差或每次都重试换系统级随机源失败后加2继续解密结果首尾多出随机数据填充/去填充不匹配检查填充前缀和随机盐的处理逻辑签名验证失败但哈希相同填充格式被忽略严格校验填充字节不能宽容处理5.5 我给自己写的调试清单最后分享一个我的调试习惯。每次跑RSA全流程我都会先在“小参数”模式下验证逻辑正确性——把密钥长度临时改到32位或者64位打印每一步的中间结果用Python或者计算器手工验证一遍。全部通过后再把密钥长度改回512位做随机数据往返测试。这个流程虽简单但能帮你区分“数学逻辑错了”和“大数运算实现错了”两类完全不同的bug省下大量时间。所有代码我自己在模拟项目X里已经完整跑通了加解密、签名验签、以及随机数据往返测试稳定性是有保障的。回头再看写一套自己的RSA最值钱的其实不是那几段模幂和素数检测代码而是你亲手趟过“大数溢出”、“填充混乱”、“字节序翻转”这些坑之后对密码学实现中的边界条件和安全细节有了真正体感。下次你再看任何RSA相关代码脑子里会自动浮现它背后那些看不见的约束和隐患。这也是我建议你在学习阶段一定要自己动手写一遍的原因不管写得慢还是写得笨都会比单纯读十篇别人的实现收获大得多。