手写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而不是直接调OpenSSL

1.1 市面大数库这么多，为什么偏偏是Miracl

很多人一听到“实现RSA”第一反应是OpenSSL一行命令搞定。这话没毛病，生产环境我也用OpenSSL，但注意场景不同。OpenSSL对使用者来说是个黑盒，你只知道RSA_public_encrypt传参返回，至于内部的大数乘法怎么做、素性检测轮数怎么配、CRT参数怎么算，根本接触不到。一旦碰到需要魔改密钥格式、研究侧信道防护、复现某种攻击实验的需求，就完全无从下手。

大数库层面其实有三个常见选择：GMP、Miracl、mbedTLS的bignum模块。GMP是通用的高精度运算库，性能是天花板级别，但它的API完全是数学导向的，没有素性检测、没有密码学专用的模幂模板，你得自己组合原语。mbedTLS的bignum模块倒是密码学专用，但它是嵌入式风格，接口设计比较紧凑，教学演示时不够直观。Miracl正好在两者中间——既有专门的isprime、powmod、xgcd这类密码学函数，代码风格又很直白，很适合一步一步展示RSA的每一个数学环节。

我选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.a

Miracl目前开源在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 -lm

Windows环境下通常是直接用C++ Builder或Visual Studio编译源码，稍微配置一下项目路径和预定义宏就行。我的建议很简单：不管你用什么系统，第一件事先编译里面自带的示例程序，确认库能跑通再继续，不然后面所有问题都会混在一起，很难排查。

编译时还有个小坑：Miracl的性能和汇编优化开关有很大关系。linux目录下的makefile会检测机器架构，但某些老版本默认配置比较保守。如果你的CPU支持64位指令集，建议把miracl.h里相关的硬件加速宏打开，尤其是后面生成3072位密钥的时候，性能差距能有好几倍。

2.2 big类型的初始化、进制设置与常用API

Miracl是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之后，模数n=p×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 p，mp = cp^dP mod p powmod(cq, dQ, q, mq); // cq = c mod q，mq = 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做这些攻击实验其实很有教学价值，因为你能控制每一个数。比如想演示低指数攻击，选e=3，明文很短，加密后直接对密文做整数开三次方，用二分法或牛顿迭代就能恢复明文。这个实验做完，对“为什么实际要用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的人来说，这个“自己动手从底层走一遍”的过程，值得投入。

本文还有配套的精品资源，点击获取