简介这份压缩包提供基于大数库Miracl的RSA算法完整实现面向信息安全、密码学方向的开发者与学习者可用于理解非对称加密原理及大数运算库的工程用法。包内共16个文件以C源码RSA_main.c、头文件miracl.h、mirdef.h、静态库ms32.lib与可执行程序RSA.exe为主另含pdb/obj/pch等编译调试产物压缩包大小约361KB便于打开工程查看或直接运行验证。目前已有974人学习下载。实现涵盖大素数选取、公钥私钥生成、模幂加密及模逆元解密等核心环节代码调用mirsys、powmod、invmod等Miracl接口配合VS6工程配置可帮助读者快速跑通RSA加解密全流程同时Miracl对大整数运算的优化及错误处理机制也为扩展数字签名、密钥交换等应用提供了参考。 RSA大家都熟但真要让你不借助OpenSSL把这套算法从头跑通能一次写对的人真不多。我前段时间正好需要用底层大数库把RSA完整实现一遍——不是拿现成库调接口而是密钥生成、加解密、签名验签全链路自己写选的就是Miracl这个老牌大数库。这篇文章就把整个实现过程、关键API的踩坑点以及我调了整整一晚上才搞定的性能问题一次性说清楚。如果你正在做密码学课程设计、毕业设计或者工作需要自己维护一套加解密代码这篇应该能帮你省掉大量查资料的弯路。Miracl作为大数库API很贴近密码学原语Miller-Rabin素性检测、模幂、模逆这些RSA必需的操作都有现成函数比起自己用GMP硬拼要舒服太多。下面我按实际开发顺序来讲从编译库开始一直到中文文本加解密跑通为止。1. 先想清楚为什么用Miracl手写RSA而不是直接调OpenSSL1.1 市面大数库这么多为什么偏偏是Miracl很多人一听到“实现RSA”第一反应是OpenSSL一行命令搞定。这话没毛病生产环境我也用OpenSSL但注意场景不同。OpenSSL对使用者来说是个黑盒你只知道RSA_public_encrypt传参返回至于内部的大数乘法怎么做、素性检测轮数怎么配、CRT参数怎么算根本接触不到。一旦碰到需要魔改密钥格式、研究侧信道防护、复现某种攻击实验的需求就完全无从下手。大数库层面其实有三个常见选择GMP、Miracl、mbedTLS的bignum模块。GMP是通用的高精度运算库性能是天花板级别但它的API完全是数学导向的没有素性检测、没有密码学专用的模幂模板你得自己组合原语。mbedTLS的bignum模块倒是密码学专用但它是嵌入式风格接口设计比较紧凑教学演示时不够直观。Miracl正好在两者中间——既有专门的isprime、powmod、xgcd这类密码学函数代码风格又很直白很适合一步一步展示RSA的每一个数学环节。库定位API风格适合场景GMP通用高精度数学库高性能、底层需要极致性能的数学运算Miracl密码学专用大数库贴近密码学原语教学研究、算法复现、定制密钥流程OpenSSL完整密码学库黑盒调用生产环境、标准协议对接我选Miracl还有一个原因它是C代码没有复杂的模板机制调试时能直接跟进库内部看进位、看模约化过程对理解RSA真正“发生了什么”非常有帮助。1.2 手撕RSA到底能收获什么自己用大数库实现一遍RSA最大的收获不是那几行代码而是把数学符号和内存里的数据一一对应起来。比如RSA参数里的p、q、n、φ(n)、e、d教材上只是公式但用Miracl实现时你得亲手调bigrand生成素数、用xgcd求模逆、拿powmod做加解密。每一步都对应一个具体的函数返回值参数之间的大小关系、互素关系都会在调试过程中根深蒂固地扎进脑子里。另外一个很实际的收获是排查问题的能力。网上关于“rsa public key not find”这类报错的讨论不少很多人懵在不知道去哪查。自己写过一遍密钥生成和读取流程后看到这个提示立刻会想到是文件格式解析、进制转换还是环境初始化的问题而不是无头苍蝇一样乱试。对我来说这也是我坚持不用OpenSSL封装而是用底层大数库重写的主要原因。2. 环境搭建Miracl编译与big类型的基础用法2.1 三步编译出libmiracl.aMiracl目前开源在GitHub上源码下载后编译比想象中简单但有个细节要注意不同平台要用不同的配置。以Linux为例仓库根目录下有linux目录里面放着gcc的配置脚本直接进linux目录执行make就能生成libmiracl.a。git clone https://github.com/miracl/MIRACL.git cd MIRACL/linux make跑完以后静态库文件就在linux目录下。如果你要用它编译自己的程序记得带上头文件路径和库路径还要链接数学库gcc my_rsa.c -o my_rsa -I./MIRACL -L./MIRACL/linux -lmiracl -lmWindows环境下通常是直接用C Builder或Visual Studio编译源码稍微配置一下项目路径和预定义宏就行。我的建议很简单不管你用什么系统第一件事先编译里面自带的示例程序确认库能跑通再继续不然后面所有问题都会混在一起很难排查。编译时还有个小坑Miracl的性能和汇编优化开关有很大关系。linux目录下的makefile会检测机器架构但某些老版本默认配置比较保守。如果你的CPU支持64位指令集建议把miracl.h里相关的硬件加速宏打开尤其是后面生成3072位密钥的时候性能差距能有好几倍。2.2 big类型的初始化、进制设置与常用APIMiracl是C语言库核心数据类型叫做big本质上是一个链表结构表示的大整数。用之前必须先初始化MIRACL全局环境这个全局指针mip贯穿所有API调用。最基础的模板长这样#include miracl.h #include stdio.h int main() { miracl *mip mirsys(5000, 16); // 5000字节内存池16进制模式 big a mirvar(0); // 初始化大数变量初值为0 big b mirvar(0); cinstr(a, 123456789ABCDEF); cinstr(b, 987654321); add(a, b, a); // a a b cotstr(a, buffer); // 转成字符串输出 printf(%s\n, buffer); mirexit(); return 0; }这里最关键的是mirsys的第二个参数——进制数。设为16以后所有cinstr、cotstr都按十六进制处理调试时非常直观能直接看到大数在内存里的十六进制形态。十六进制每一位对应4个bit算位数也方便比如一个1024位的RSA模数表示成十六进制就是256个字符。日常开发用得最多的API其实就那么几个mirvar初始化、cinstr把字符串转大数、cotstr把大数转字符串、bigrand生成随机大数、isprime做素性检测、powmod做模幂运算、xgcd求扩展欧几里得。把这些函数拼起来RSA的全流程就能搭出来了。3. RSA关键环节拆解素性检测、密钥参数与模幂运算3.1 大素数是怎么“找”出来的RSA的起点是两个大素数p和q它们的乘积是模数n。实际项目里p和q的位数要接近但不要太接近否则容易被费马分解这类方法攻击。以1024位RSA为例p和q各取512位比较常见。用Miracl生成大素数的思路不复杂先随机生成一个512位的奇数然后调用nxprime取“不小于该数的下一个素数”再用isprime做Miller-Rabin素性检测确认一遍。核心代码大概是这个样子big p mirvar(0); do { bigrand(512, p); // 生成0到2^512之间的随机数 setbit(p, 511); // 确保最高位为1使p一定是512位 setbit(p, 0); // 确保最低位为1使p为奇数 nxprime(p, p); // 从p开始找下一个可能是素数的数 } while (!isprime(p, 32)); // 做32轮Miller-Rabin检测这里isprime的第二个参数是检测轮数。Miller-Rabin是概率性算法一轮对合成数的误判概率上限是1/4所以32轮后误判概率低到2的负64次方量级足够日常使用。我在实验里曾经为了省时间调成10轮结果有个合数一直没测出来后来解密数字全乱排查到深夜才发现是这里的问题。不要省轮数。这里还有一个必须做的操作在bigrand之前要给随机数发生器设置种子。常见做法是irand(time(NULL))否则每次程序启动生成的密钥都一样安全性等于零。如果是安全要求更高的场景应该从系统熵源获取种子不能只用时间。3.2 e/d的计算为什么公共指数固定选65537生成p和q之后模数np×q欧拉函数φ(n)(p−1)(q−1)。公钥指数e的选择业界默认用65537也就是0x10001。为什么选这个数因为65537的二进制表示是10000000000000001只有两个bit是1模幂运算时用平方-乘方法只需要做一次额外乘法计算效率很高同时它和φ(n)互素的概率非常高但不代表一定互素所以代码里还是要判断。私钥指数d要满足e×d ≡ 1 mod φ(n)也就是e在模φ(n)下的乘法逆元。Miracl里求逆元用xgcd全称是扩展欧几里得算法。注意一点儿这个函数能同时算出逆元和最大公约数别记错参数位置。big e mirvar(0); big d mirvar(0); big phi mirvar(0); big gcd mirvar(0); big tmp mirvar(0); cinstr(e, 10001); // 公钥指数65537十六进制表示 decr(p, 1, tmp); // tmp p - 1 decr(q, 1, phi); // phi q - 1 multiply(tmp, phi, phi); // phi (p - 1) * (q - 1) xgcd(e, phi, d, tmp, gcd); // 第3个参数得到e在mod phi下的逆元第5个参数得到gcd if (size(gcd) ! 1) { // e和phi不互素需要重新生成p或q }心里要有数公钥是(n, e)私钥是(n, d)。这段代码里算出的gcd理论上必须是1如果不是说明e和φ(n)有公因子这种情况下必须重新换一对p、q。虽然概率很小但生产级代码必须处理。3.3 加解密与签名验签powmod一鱼多吃RSA的核心运算就是模幂c m² mod n解密就是m c^d mod n。Miracl里的powmod直接支持这个操作函数签名是powmod(x, y, n, result)意思是计算x的y次幂模n结果放到result。使用起来非常直接// 加密过程 powmod(m, e, n, c); // 解密过程 powmod(c, d, n, m);签名和加密在数学运算上其实是一样的只是密钥用法反过来签名用私钥d对消息m计算s m^d mod n验签用公钥e恢复s^e mod n再跟原始消息比对。这个顺序很多人会搞混我自己也错过一次。用Miracl代码一写就非常清晰因为参数就是明明白白摆在那里的。这里注意一个约束RSA只能处理小于n的整数。如果明文m的数值比n还大运算结果就无法唯一恢复。所以实际使用要把明文分块每块转换成的整数值要小于n。这就是为什么后面处理字符串的时候必须做分组也是为什么RSA不适合直接加密大数据流实际场景里通常只用来加密对称密钥。顺便说一句理解了这层之后回头再看TLS里的RSA密钥交换就非常顺了。所谓RSA密钥交换本质就是客户端生成一个随机密钥材料用服务器公钥加密后传过去服务端再用私钥解出来后续的对称加密密钥由双方基于这个材料派生。它复用的一模一样的公钥加密/私钥解密逻辑。3.4 解密提速用CRT省下3/4时间RSA解密用的私钥指数d通常和n差不多大直接算模幂很慢。实际工程中几乎都会用中国剩余定理CRT加速原理是利用p和q分别做模幂最后再合并结果。Miracl下CRT解密的标准姿势是提前计算出这组参数dP d mod (p−1)dQ d mod (q−1)qInv q的逆元模p解密时先分别计算powmod(cp, dP, p, mp); // cp c mod pmp cp^dP mod p powmod(cq, dQ, q, mq); // cq c mod qmq cq^dQ mod q然后合并结果。合并公式是m mq q × h其中h (qInv × (mp − mq)) mod p。代码写出来大概是subtract(mp, mq, h); if (size(h) 0) add(h, p, h); // 处理负数 multiply(qInv, h, h); divide(h, p, tmp); // h对p取模商存tmp丢弃 multiply(h, q, h); add(h, mq, m);CRT加速的效果非常显著。因为p、q都是n的一半位数两个模幂运算的规模大幅降低整体解密速度能提升3-4倍。密钥生成阶段就把dP、dQ、qInv算好存到私钥结构里解密时直接调用。这也是真实证书和密钥文件里常见这些字段的原因。4. 完整实操用Miracl跑通密钥生成和文本加解密4.1 密钥生成Demo从随机数到公私钥对把前面的逻辑整合起来一个完整的密钥生成函数骨架是这样bool rsa_generate_key(big n, big e, big d, int bits) { miracl *mip mirsys(5000, 16); big p mirvar(0), q mirvar(0); big phi mirvar(0), tmp mirvar(0), gcd mirvar(0); irand(time(NULL)); do { // 生成两位大约bits/2位的素数 bigrand(bits / 2, p); setbit(p, bits / 2 - 1); setbit(p, 0); nxprime(p, p); bigrand(bits / 2, q); setbit(q, bits / 2 - 1); setbit(q, 0); nxprime(q, q); if (compare(p, q) 0) continue; // p和q不能相等 multiply(p, q, n); // n p * q decr(p, 1, tmp); decr(q, 1, phi); multiply(tmp, phi, phi); // phi (p-1)*(q-1) cinstr(e, 10001); xgcd(e, phi, d, tmp, gcd); } while (size(gcd) ! 1); // 实际项目里应当继续生成并保存dP、dQ、qInv return true; }这段代码跑通以后可以顺便打印p、q、n、d的十六进制字符串对照教科书公式一一验证。我第一次跑通时打印出来看了很久才真正把“公钥(n,e)”“私钥(n,d)”这些抽象概念和内存里的数据对应起来。4.2 文本加解密Demo字符串到十六进制大数的转换RSA处理的是大整数而日常消息是字符串中间必须做转换。最简单的办法是把字符串的每个字节转成十六进制拼成一个十六进制字符串再用cinstr转成大数。加密端代码类似这样// 假设plaintext是一个ASCII字符串已转成十六进制hex_str cinstr(m, hex_str); powmod(m, e, n, c); cotstr(c, hex_cipher); printf(cipher: %s\n, hex_cipher);解密端反过来先把密文的十六进制字符串用cinstr转回大数powmod恢复出m再用cotstr转成十六进制字符串最后按每两个字符一个字节还原出原始文本。这里面有个天然的大坑如果明文十六进制字符串前面带有“0x”前缀cinstr会解析失败。我一开始从别处复制了一段带0x的字符串调试了很久才发现。另外要注意Miracl的cotstr输出的是全大写十六进制做字节还原时不能假设小写统一转成大写或小写再处理。4.3 中文与长明文的分组处理细节中文文本和英文最大的区别是编码长度。英文一个字符一个字节中文用UTF-8的话一个汉字通常占3个字节。RSA不会关心你原文是什么编码它只关心你喂进来的字节流所以转换逻辑要对“字节”操作而不是对“字符”操作。假设生成的是1024位RSA密钥模数n是1024位也就是128字节。理论上任何小于n的整数都能被加密但为了安全起见留给填充空间一般每个明文块取n字节数减1甚至减11如果使用PKCS#1 v1.5填充。无填充教学演示时我习惯把每个明文块限制在最大字节数以内逐块加密int max_block bytes_in_n - 1; // 比如128字节模数每块最多127字节 for (offset 0; offset len; offset max_block) { size_t block_len min(max_block, len - offset); // 取block_len字节 → 转十六进制 → cinstr转big → powmod加密 // 将密文十六进制追加到输出buffer }解密时按块数循环每块恢复出十六进制明文再逐字节还原成原始数据。只要所有块的整数值都小于n这个过程就能完美还原。这个分块思路是所有RSA工程实现的基础理解了它后面再看PKCS#1填充标准、OAEP实现都会顺畅很多。5. 踩坑记录素性误判、密钥读取失败与性能优化5.1 素性检测不等于安全随机数种子也必须管好很多人跑通isprime以后觉得万事大吉但素性检测只是其中一环。第一个坑是随机数种子irand(time(NULL))如果用同一秒运行生成的随机数完全一样密钥自然一样。我在教学演示时遇到过学生把程序跑两次发现两个一模一样的私钥当场尴尬。生产环境一定要从操作系统的随机源读取种子。第二个坑是Miller-Rabin轮数。有些教程为了演示性能会改成isprime(p)不传轮数或者传个位数。Miracl默认值虽然还行但我在前文说过了自定义就尽量给够32轮。对于1024位以上的大整数32轮检测的开销完全在可接受范围内没必要为了省这点时间留下安全隐患。还有一个细节是大素数生成后要检查p和q是否过于接近。如果两个数相差很小攻击者可能通过费马分解直接从n还原出p和q。Miracl里可以用subtract(p, q, diff)看差的绝对值如果差值太小重新生成其中一个大数。标准参考是p和q的二进制表示位数相同但高位模式不要完全相同。5.2 “rsa public key not find”这类报错的源头在哪里网上关于“rsa public key not find”的讨论很多这个报错在各类激活工具、自研加密工具里都很常见但本质上都是密钥读取阶段出了问题。用Miracl做底层开发时最容易遇到几种情况密钥文件不是纯十六进制文本而是PEM格式。PEM文件有-----BEGIN PUBLIC KEY-----头尾中间是Base64编码。Miracl没有自带PEM解析器你需要先剥掉头尾做Base64解码再转成十六进制字符串最后cinstr载入。漏掉一步都读不出来。十六进制字符串里混入了空白字符。从文本文件读取的密钥往往带换行符、空格直接把整个字符串交给cinstr解析结果必然不对。读取后先做一次清洗去掉所有非十六进制字符。环境没有初始化。有些人习惯把RSA逻辑拆到多个模块结果调用powmod之前忘了mirsys程序直接段错误或者返回垃圾值表现看起来就像“找不到密钥”。我自己的排查思路是先用printf把从文件读出来的每个字节的十六进制值打印出来肉眼确认格式是不是和生成时一模一样。一般看到第3种问题最多——初始化顺序不对密钥加载函数在mirsys之前就被调用了。5.3 性能瓶颈从512位到3072位配置和优化方向我用Miracl试过从512位到3072位不同长度的密钥生成性能差异非常直观。512位几乎是秒出1024位在普通电脑上大概1到2秒2048位可能需要十几秒3072位就不是“等一下”能解决的了素性检测和模逆运算都会明显变慢。如果只是在做课程设计用1024位已经完全够演示。但如果你关注的是长期安全性现在不少场景在推荐3072位RSA这时性能优化就必须提上日程。基于Miracl的优化方向主要有三个确保编译时打开了当前CPU架构的优化选项尤其是64位指令集相关宏这个影响最明显。解密使用CRT加速前面已经写了具体方法能快3-4倍私钥操作必须做。模幂运算本身用powmod就够了Miracl内部已实现了Montgomery约化。如果你自己写了朴素模幂性能会差几个数量级别重新造这个轮子。另外一个常见的坑是内存池大小。mirsys(5000, 16)的第一个参数是内存池字节数如果位数很大但池子开得不够程序会在某个神秘的地方崩溃。建议直接按最大位数估算生成3072位密钥时我把池子开到mirsys(10000, 16)省得反复调。5.4 教科书RSA的坑填充、低指数与攻击实验千万不要把教学演示用的“教科书RSA”直接搬到生产环境这个我必须强调。不加填充的RSA有一个致命问题同样的明文永远产生同样的密文攻击者可以枚举常见明文并比对密文。另外当公钥指数e很小且明文也很小时m的e次方可能小于n此时直接对密文开e次方就能还原明文这就是低加密指数攻击我在crypto攻击类的题目里见到很多次。用Miracl做这些攻击实验其实很有教学价值因为你能控制每一个数。比如想演示低指数攻击选e3明文很短加密后直接对密文做整数开三次方用二分法或牛顿迭代就能恢复明文。这个实验做完对“为什么实际要用65537”“为什么要做填充”的理解比背书深刻得多。安全实现至少要加PKCS#1 v1.5填充更推荐OAEP。OAEP的细节比较多包括概率性填充、两个哈希函数、掩码生成函数等等。我在Miracl里自己实现过一版简单OAEP核心还是把随机字节和哈希结果跟明文混在一起再转成大数加密解密端逆操作。过程比较繁琐但是做完以后再看OpenSSL的RSA接口反而有种“原来它是在替我做这些事”的透亮感。我还想额外说一个点网上经常能看到“rsa签名验签”相关的需求很多人以为签名就是反向加密。在教科书层面这个说法没错但实际工程里绝不能直接对整条消息做模幂必须对消息的哈希值签名否则消息长度限制和伪造性都会出问题。用Miracl实现时要先对消息做哈希可以用库里的SHA系列函数也可以外部实现把哈希值转成大数再走私钥模幂。验签时恢复哈希值再和本地计算的哈希比对。最后再分享一个小建议如果时间允许建议在跑通基础版以后把私钥从“裸d”升级成CRT参数形式也就是保存p、q、dP、dQ、qInv。这样不仅能感受到解密速度的提升还能提前接触到真实私钥文件的内部结构。等你再看到PEM私钥里的那几行Base64就不会觉得那是神秘黑盒了。我当时做完这个升级以后回头再去读OpenSSL的RSA结构体定义基本一眼就能看懂每个字段的含义。对于一个想真正吃透RSA的人来说这个“自己动手从底层走一遍”的过程值得投入。本文还有配套的精品资源点击获取 手写RSA全流程：基于Miracl大数库的密钥生成与加解密实践
简介这份压缩包提供基于大数库Miracl的RSA算法完整实现面向信息安全、密码学方向的开发者与学习者可用于理解非对称加密原理及大数运算库的工程用法。包内共16个文件以C源码RSA_main.c、头文件miracl.h、mirdef.h、静态库ms32.lib与可执行程序RSA.exe为主另含pdb/obj/pch等编译调试产物压缩包大小约361KB便于打开工程查看或直接运行验证。目前已有974人学习下载。实现涵盖大素数选取、公钥私钥生成、模幂加密及模逆元解密等核心环节代码调用mirsys、powmod、invmod等Miracl接口配合VS6工程配置可帮助读者快速跑通RSA加解密全流程同时Miracl对大整数运算的优化及错误处理机制也为扩展数字签名、密钥交换等应用提供了参考。 RSA大家都熟但真要让你不借助OpenSSL把这套算法从头跑通能一次写对的人真不多。我前段时间正好需要用底层大数库把RSA完整实现一遍——不是拿现成库调接口而是密钥生成、加解密、签名验签全链路自己写选的就是Miracl这个老牌大数库。这篇文章就把整个实现过程、关键API的踩坑点以及我调了整整一晚上才搞定的性能问题一次性说清楚。如果你正在做密码学课程设计、毕业设计或者工作需要自己维护一套加解密代码这篇应该能帮你省掉大量查资料的弯路。Miracl作为大数库API很贴近密码学原语Miller-Rabin素性检测、模幂、模逆这些RSA必需的操作都有现成函数比起自己用GMP硬拼要舒服太多。下面我按实际开发顺序来讲从编译库开始一直到中文文本加解密跑通为止。1. 先想清楚为什么用Miracl手写RSA而不是直接调OpenSSL1.1 市面大数库这么多为什么偏偏是Miracl很多人一听到“实现RSA”第一反应是OpenSSL一行命令搞定。这话没毛病生产环境我也用OpenSSL但注意场景不同。OpenSSL对使用者来说是个黑盒你只知道RSA_public_encrypt传参返回至于内部的大数乘法怎么做、素性检测轮数怎么配、CRT参数怎么算根本接触不到。一旦碰到需要魔改密钥格式、研究侧信道防护、复现某种攻击实验的需求就完全无从下手。大数库层面其实有三个常见选择GMP、Miracl、mbedTLS的bignum模块。GMP是通用的高精度运算库性能是天花板级别但它的API完全是数学导向的没有素性检测、没有密码学专用的模幂模板你得自己组合原语。mbedTLS的bignum模块倒是密码学专用但它是嵌入式风格接口设计比较紧凑教学演示时不够直观。Miracl正好在两者中间——既有专门的isprime、powmod、xgcd这类密码学函数代码风格又很直白很适合一步一步展示RSA的每一个数学环节。库定位API风格适合场景GMP通用高精度数学库高性能、底层需要极致性能的数学运算Miracl密码学专用大数库贴近密码学原语教学研究、算法复现、定制密钥流程OpenSSL完整密码学库黑盒调用生产环境、标准协议对接我选Miracl还有一个原因它是C代码没有复杂的模板机制调试时能直接跟进库内部看进位、看模约化过程对理解RSA真正“发生了什么”非常有帮助。1.2 手撕RSA到底能收获什么自己用大数库实现一遍RSA最大的收获不是那几行代码而是把数学符号和内存里的数据一一对应起来。比如RSA参数里的p、q、n、φ(n)、e、d教材上只是公式但用Miracl实现时你得亲手调bigrand生成素数、用xgcd求模逆、拿powmod做加解密。每一步都对应一个具体的函数返回值参数之间的大小关系、互素关系都会在调试过程中根深蒂固地扎进脑子里。另外一个很实际的收获是排查问题的能力。网上关于“rsa public key not find”这类报错的讨论不少很多人懵在不知道去哪查。自己写过一遍密钥生成和读取流程后看到这个提示立刻会想到是文件格式解析、进制转换还是环境初始化的问题而不是无头苍蝇一样乱试。对我来说这也是我坚持不用OpenSSL封装而是用底层大数库重写的主要原因。2. 环境搭建Miracl编译与big类型的基础用法2.1 三步编译出libmiracl.aMiracl目前开源在GitHub上源码下载后编译比想象中简单但有个细节要注意不同平台要用不同的配置。以Linux为例仓库根目录下有linux目录里面放着gcc的配置脚本直接进linux目录执行make就能生成libmiracl.a。git clone https://github.com/miracl/MIRACL.git cd MIRACL/linux make跑完以后静态库文件就在linux目录下。如果你要用它编译自己的程序记得带上头文件路径和库路径还要链接数学库gcc my_rsa.c -o my_rsa -I./MIRACL -L./MIRACL/linux -lmiracl -lmWindows环境下通常是直接用C Builder或Visual Studio编译源码稍微配置一下项目路径和预定义宏就行。我的建议很简单不管你用什么系统第一件事先编译里面自带的示例程序确认库能跑通再继续不然后面所有问题都会混在一起很难排查。编译时还有个小坑Miracl的性能和汇编优化开关有很大关系。linux目录下的makefile会检测机器架构但某些老版本默认配置比较保守。如果你的CPU支持64位指令集建议把miracl.h里相关的硬件加速宏打开尤其是后面生成3072位密钥的时候性能差距能有好几倍。2.2 big类型的初始化、进制设置与常用APIMiracl是C语言库核心数据类型叫做big本质上是一个链表结构表示的大整数。用之前必须先初始化MIRACL全局环境这个全局指针mip贯穿所有API调用。最基础的模板长这样#include miracl.h #include stdio.h int main() { miracl *mip mirsys(5000, 16); // 5000字节内存池16进制模式 big a mirvar(0); // 初始化大数变量初值为0 big b mirvar(0); cinstr(a, 123456789ABCDEF); cinstr(b, 987654321); add(a, b, a); // a a b cotstr(a, buffer); // 转成字符串输出 printf(%s\n, buffer); mirexit(); return 0; }这里最关键的是mirsys的第二个参数——进制数。设为16以后所有cinstr、cotstr都按十六进制处理调试时非常直观能直接看到大数在内存里的十六进制形态。十六进制每一位对应4个bit算位数也方便比如一个1024位的RSA模数表示成十六进制就是256个字符。日常开发用得最多的API其实就那么几个mirvar初始化、cinstr把字符串转大数、cotstr把大数转字符串、bigrand生成随机大数、isprime做素性检测、powmod做模幂运算、xgcd求扩展欧几里得。把这些函数拼起来RSA的全流程就能搭出来了。3. RSA关键环节拆解素性检测、密钥参数与模幂运算3.1 大素数是怎么“找”出来的RSA的起点是两个大素数p和q它们的乘积是模数n。实际项目里p和q的位数要接近但不要太接近否则容易被费马分解这类方法攻击。以1024位RSA为例p和q各取512位比较常见。用Miracl生成大素数的思路不复杂先随机生成一个512位的奇数然后调用nxprime取“不小于该数的下一个素数”再用isprime做Miller-Rabin素性检测确认一遍。核心代码大概是这个样子big p mirvar(0); do { bigrand(512, p); // 生成0到2^512之间的随机数 setbit(p, 511); // 确保最高位为1使p一定是512位 setbit(p, 0); // 确保最低位为1使p为奇数 nxprime(p, p); // 从p开始找下一个可能是素数的数 } while (!isprime(p, 32)); // 做32轮Miller-Rabin检测这里isprime的第二个参数是检测轮数。Miller-Rabin是概率性算法一轮对合成数的误判概率上限是1/4所以32轮后误判概率低到2的负64次方量级足够日常使用。我在实验里曾经为了省时间调成10轮结果有个合数一直没测出来后来解密数字全乱排查到深夜才发现是这里的问题。不要省轮数。这里还有一个必须做的操作在bigrand之前要给随机数发生器设置种子。常见做法是irand(time(NULL))否则每次程序启动生成的密钥都一样安全性等于零。如果是安全要求更高的场景应该从系统熵源获取种子不能只用时间。3.2 e/d的计算为什么公共指数固定选65537生成p和q之后模数np×q欧拉函数φ(n)(p−1)(q−1)。公钥指数e的选择业界默认用65537也就是0x10001。为什么选这个数因为65537的二进制表示是10000000000000001只有两个bit是1模幂运算时用平方-乘方法只需要做一次额外乘法计算效率很高同时它和φ(n)互素的概率非常高但不代表一定互素所以代码里还是要判断。私钥指数d要满足e×d ≡ 1 mod φ(n)也就是e在模φ(n)下的乘法逆元。Miracl里求逆元用xgcd全称是扩展欧几里得算法。注意一点儿这个函数能同时算出逆元和最大公约数别记错参数位置。big e mirvar(0); big d mirvar(0); big phi mirvar(0); big gcd mirvar(0); big tmp mirvar(0); cinstr(e, 10001); // 公钥指数65537十六进制表示 decr(p, 1, tmp); // tmp p - 1 decr(q, 1, phi); // phi q - 1 multiply(tmp, phi, phi); // phi (p - 1) * (q - 1) xgcd(e, phi, d, tmp, gcd); // 第3个参数得到e在mod phi下的逆元第5个参数得到gcd if (size(gcd) ! 1) { // e和phi不互素需要重新生成p或q }心里要有数公钥是(n, e)私钥是(n, d)。这段代码里算出的gcd理论上必须是1如果不是说明e和φ(n)有公因子这种情况下必须重新换一对p、q。虽然概率很小但生产级代码必须处理。3.3 加解密与签名验签powmod一鱼多吃RSA的核心运算就是模幂c m² mod n解密就是m c^d mod n。Miracl里的powmod直接支持这个操作函数签名是powmod(x, y, n, result)意思是计算x的y次幂模n结果放到result。使用起来非常直接// 加密过程 powmod(m, e, n, c); // 解密过程 powmod(c, d, n, m);签名和加密在数学运算上其实是一样的只是密钥用法反过来签名用私钥d对消息m计算s m^d mod n验签用公钥e恢复s^e mod n再跟原始消息比对。这个顺序很多人会搞混我自己也错过一次。用Miracl代码一写就非常清晰因为参数就是明明白白摆在那里的。这里注意一个约束RSA只能处理小于n的整数。如果明文m的数值比n还大运算结果就无法唯一恢复。所以实际使用要把明文分块每块转换成的整数值要小于n。这就是为什么后面处理字符串的时候必须做分组也是为什么RSA不适合直接加密大数据流实际场景里通常只用来加密对称密钥。顺便说一句理解了这层之后回头再看TLS里的RSA密钥交换就非常顺了。所谓RSA密钥交换本质就是客户端生成一个随机密钥材料用服务器公钥加密后传过去服务端再用私钥解出来后续的对称加密密钥由双方基于这个材料派生。它复用的一模一样的公钥加密/私钥解密逻辑。3.4 解密提速用CRT省下3/4时间RSA解密用的私钥指数d通常和n差不多大直接算模幂很慢。实际工程中几乎都会用中国剩余定理CRT加速原理是利用p和q分别做模幂最后再合并结果。Miracl下CRT解密的标准姿势是提前计算出这组参数dP d mod (p−1)dQ d mod (q−1)qInv q的逆元模p解密时先分别计算powmod(cp, dP, p, mp); // cp c mod pmp cp^dP mod p powmod(cq, dQ, q, mq); // cq c mod qmq cq^dQ mod q然后合并结果。合并公式是m mq q × h其中h (qInv × (mp − mq)) mod p。代码写出来大概是subtract(mp, mq, h); if (size(h) 0) add(h, p, h); // 处理负数 multiply(qInv, h, h); divide(h, p, tmp); // h对p取模商存tmp丢弃 multiply(h, q, h); add(h, mq, m);CRT加速的效果非常显著。因为p、q都是n的一半位数两个模幂运算的规模大幅降低整体解密速度能提升3-4倍。密钥生成阶段就把dP、dQ、qInv算好存到私钥结构里解密时直接调用。这也是真实证书和密钥文件里常见这些字段的原因。4. 完整实操用Miracl跑通密钥生成和文本加解密4.1 密钥生成Demo从随机数到公私钥对把前面的逻辑整合起来一个完整的密钥生成函数骨架是这样bool rsa_generate_key(big n, big e, big d, int bits) { miracl *mip mirsys(5000, 16); big p mirvar(0), q mirvar(0); big phi mirvar(0), tmp mirvar(0), gcd mirvar(0); irand(time(NULL)); do { // 生成两位大约bits/2位的素数 bigrand(bits / 2, p); setbit(p, bits / 2 - 1); setbit(p, 0); nxprime(p, p); bigrand(bits / 2, q); setbit(q, bits / 2 - 1); setbit(q, 0); nxprime(q, q); if (compare(p, q) 0) continue; // p和q不能相等 multiply(p, q, n); // n p * q decr(p, 1, tmp); decr(q, 1, phi); multiply(tmp, phi, phi); // phi (p-1)*(q-1) cinstr(e, 10001); xgcd(e, phi, d, tmp, gcd); } while (size(gcd) ! 1); // 实际项目里应当继续生成并保存dP、dQ、qInv return true; }这段代码跑通以后可以顺便打印p、q、n、d的十六进制字符串对照教科书公式一一验证。我第一次跑通时打印出来看了很久才真正把“公钥(n,e)”“私钥(n,d)”这些抽象概念和内存里的数据对应起来。4.2 文本加解密Demo字符串到十六进制大数的转换RSA处理的是大整数而日常消息是字符串中间必须做转换。最简单的办法是把字符串的每个字节转成十六进制拼成一个十六进制字符串再用cinstr转成大数。加密端代码类似这样// 假设plaintext是一个ASCII字符串已转成十六进制hex_str cinstr(m, hex_str); powmod(m, e, n, c); cotstr(c, hex_cipher); printf(cipher: %s\n, hex_cipher);解密端反过来先把密文的十六进制字符串用cinstr转回大数powmod恢复出m再用cotstr转成十六进制字符串最后按每两个字符一个字节还原出原始文本。这里面有个天然的大坑如果明文十六进制字符串前面带有“0x”前缀cinstr会解析失败。我一开始从别处复制了一段带0x的字符串调试了很久才发现。另外要注意Miracl的cotstr输出的是全大写十六进制做字节还原时不能假设小写统一转成大写或小写再处理。4.3 中文与长明文的分组处理细节中文文本和英文最大的区别是编码长度。英文一个字符一个字节中文用UTF-8的话一个汉字通常占3个字节。RSA不会关心你原文是什么编码它只关心你喂进来的字节流所以转换逻辑要对“字节”操作而不是对“字符”操作。假设生成的是1024位RSA密钥模数n是1024位也就是128字节。理论上任何小于n的整数都能被加密但为了安全起见留给填充空间一般每个明文块取n字节数减1甚至减11如果使用PKCS#1 v1.5填充。无填充教学演示时我习惯把每个明文块限制在最大字节数以内逐块加密int max_block bytes_in_n - 1; // 比如128字节模数每块最多127字节 for (offset 0; offset len; offset max_block) { size_t block_len min(max_block, len - offset); // 取block_len字节 → 转十六进制 → cinstr转big → powmod加密 // 将密文十六进制追加到输出buffer }解密时按块数循环每块恢复出十六进制明文再逐字节还原成原始数据。只要所有块的整数值都小于n这个过程就能完美还原。这个分块思路是所有RSA工程实现的基础理解了它后面再看PKCS#1填充标准、OAEP实现都会顺畅很多。5. 踩坑记录素性误判、密钥读取失败与性能优化5.1 素性检测不等于安全随机数种子也必须管好很多人跑通isprime以后觉得万事大吉但素性检测只是其中一环。第一个坑是随机数种子irand(time(NULL))如果用同一秒运行生成的随机数完全一样密钥自然一样。我在教学演示时遇到过学生把程序跑两次发现两个一模一样的私钥当场尴尬。生产环境一定要从操作系统的随机源读取种子。第二个坑是Miller-Rabin轮数。有些教程为了演示性能会改成isprime(p)不传轮数或者传个位数。Miracl默认值虽然还行但我在前文说过了自定义就尽量给够32轮。对于1024位以上的大整数32轮检测的开销完全在可接受范围内没必要为了省这点时间留下安全隐患。还有一个细节是大素数生成后要检查p和q是否过于接近。如果两个数相差很小攻击者可能通过费马分解直接从n还原出p和q。Miracl里可以用subtract(p, q, diff)看差的绝对值如果差值太小重新生成其中一个大数。标准参考是p和q的二进制表示位数相同但高位模式不要完全相同。5.2 “rsa public key not find”这类报错的源头在哪里网上关于“rsa public key not find”的讨论很多这个报错在各类激活工具、自研加密工具里都很常见但本质上都是密钥读取阶段出了问题。用Miracl做底层开发时最容易遇到几种情况密钥文件不是纯十六进制文本而是PEM格式。PEM文件有-----BEGIN PUBLIC KEY-----头尾中间是Base64编码。Miracl没有自带PEM解析器你需要先剥掉头尾做Base64解码再转成十六进制字符串最后cinstr载入。漏掉一步都读不出来。十六进制字符串里混入了空白字符。从文本文件读取的密钥往往带换行符、空格直接把整个字符串交给cinstr解析结果必然不对。读取后先做一次清洗去掉所有非十六进制字符。环境没有初始化。有些人习惯把RSA逻辑拆到多个模块结果调用powmod之前忘了mirsys程序直接段错误或者返回垃圾值表现看起来就像“找不到密钥”。我自己的排查思路是先用printf把从文件读出来的每个字节的十六进制值打印出来肉眼确认格式是不是和生成时一模一样。一般看到第3种问题最多——初始化顺序不对密钥加载函数在mirsys之前就被调用了。5.3 性能瓶颈从512位到3072位配置和优化方向我用Miracl试过从512位到3072位不同长度的密钥生成性能差异非常直观。512位几乎是秒出1024位在普通电脑上大概1到2秒2048位可能需要十几秒3072位就不是“等一下”能解决的了素性检测和模逆运算都会明显变慢。如果只是在做课程设计用1024位已经完全够演示。但如果你关注的是长期安全性现在不少场景在推荐3072位RSA这时性能优化就必须提上日程。基于Miracl的优化方向主要有三个确保编译时打开了当前CPU架构的优化选项尤其是64位指令集相关宏这个影响最明显。解密使用CRT加速前面已经写了具体方法能快3-4倍私钥操作必须做。模幂运算本身用powmod就够了Miracl内部已实现了Montgomery约化。如果你自己写了朴素模幂性能会差几个数量级别重新造这个轮子。另外一个常见的坑是内存池大小。mirsys(5000, 16)的第一个参数是内存池字节数如果位数很大但池子开得不够程序会在某个神秘的地方崩溃。建议直接按最大位数估算生成3072位密钥时我把池子开到mirsys(10000, 16)省得反复调。5.4 教科书RSA的坑填充、低指数与攻击实验千万不要把教学演示用的“教科书RSA”直接搬到生产环境这个我必须强调。不加填充的RSA有一个致命问题同样的明文永远产生同样的密文攻击者可以枚举常见明文并比对密文。另外当公钥指数e很小且明文也很小时m的e次方可能小于n此时直接对密文开e次方就能还原明文这就是低加密指数攻击我在crypto攻击类的题目里见到很多次。用Miracl做这些攻击实验其实很有教学价值因为你能控制每一个数。比如想演示低指数攻击选e3明文很短加密后直接对密文做整数开三次方用二分法或牛顿迭代就能恢复明文。这个实验做完对“为什么实际要用65537”“为什么要做填充”的理解比背书深刻得多。安全实现至少要加PKCS#1 v1.5填充更推荐OAEP。OAEP的细节比较多包括概率性填充、两个哈希函数、掩码生成函数等等。我在Miracl里自己实现过一版简单OAEP核心还是把随机字节和哈希结果跟明文混在一起再转成大数加密解密端逆操作。过程比较繁琐但是做完以后再看OpenSSL的RSA接口反而有种“原来它是在替我做这些事”的透亮感。我还想额外说一个点网上经常能看到“rsa签名验签”相关的需求很多人以为签名就是反向加密。在教科书层面这个说法没错但实际工程里绝不能直接对整条消息做模幂必须对消息的哈希值签名否则消息长度限制和伪造性都会出问题。用Miracl实现时要先对消息做哈希可以用库里的SHA系列函数也可以外部实现把哈希值转成大数再走私钥模幂。验签时恢复哈希值再和本地计算的哈希比对。最后再分享一个小建议如果时间允许建议在跑通基础版以后把私钥从“裸d”升级成CRT参数形式也就是保存p、q、dP、dQ、qInv。这样不仅能感受到解密速度的提升还能提前接触到真实私钥文件的内部结构。等你再看到PEM私钥里的那几行Base64就不会觉得那是神秘黑盒了。我当时做完这个升级以后回头再去读OpenSSL的RSA结构体定义基本一眼就能看懂每个字段的含义。对于一个想真正吃透RSA的人来说这个“自己动手从底层走一遍”的过程值得投入。本文还有配套的精品资源点击获取