论如何用 GMP 库实现 RSA 核心运算

WJYwangjingyi · 2025-12-11 14:42:36 · 科技·工程

~~被 @xuan_never 大佬压力了啊~~

所以就有了这篇我的第一篇文章兼第一篇申请全站推荐的文章。

前言

其实本来想投休闲・娱乐的，主要是因为 RSA 在网上已经有很多权威开源的实现，比如 OpenSSL 库（但这个好像配置有点复杂），而且我做这个本来也是为了休闲娱乐，但碍于本文专业知识多，所以就扔科技・工程了。

本人才初中，可能有些解释不严谨，如有错误，请勿乱喷。

本项目采用的语言为 C++，支持的系统为 Windows Vista 及以上，系统要求为安装了 KB2999226 更新或 ucrt 运行时库，且支持中文环境。

项目地址

懒得搞 GitHub 了，而且访问还不稳定，就放个人题库里了。

一开始代码为了存云剪贴板不卡，码风很紧凑，懒得展开了，~~而且应该没人看~~，如有需要请自行解决。

~~应该没有人打得开这篇文章打不开题库吧~~

前置知识

RSA 介绍 & 数学原理 & 证明

由于本文主要讲实现，数学原理啥的不是重点，这里只提供一个腾讯的学习链接，想学者自行前往。

RSA 流程简介

准备工作

选取两个质数 p, q，并计算 n = p \times q 与 \phi(n)。
- 注：\phi(n) 为欧拉函数，代表小于或等于 n 的正整数中与 n 互质的数的个数，在这里 \phi(n) = (p - 1) \times (q - 1)。
选取一个与 \phi(n) 互质的数 e，计算 e 模 \phi(n) 的模反元素 d。
- 即求出满足 e \times d \equiv 1 \pmod {\phi(n)} 的 d。
将明文分割并转换为在 [0,n) 之间的整数序列。

经过以上处理，我们就得到了以下内容：

公钥（意即公开的密钥）：(e,n)（普遍写法）或 (n,e)。
私钥（意即不公开的密钥，私藏的密钥）：(d,n)（普遍写法）或 (n,d)。
处理好的，可以方便直接地用于加密解密的数据。

加密解密

为了方便，只展示一个整数的流程，假如明文是 x，密文是 y，那么流程如下：

加密：计算 y = x^e \bmod n。
解密：计算 x = y^d \bmod n。

~~很简单对吧~~

从以上流程可以看出，RSA 的优势为可以公开公钥供公众加密消息给自己，其他人还无法解密，安全依赖为两个大质数 p, q 的乘积 n 分解困难。

不过由于现在技术的发展，只有多于 2048 位二进制的 n 才被认为是安全的（自 2009 年 768 位 RSA 被成功破解后，1024 位 RSA 不再被视为足够安全，具体请自行查阅相关资料）。

同时，小 e（如 e = 3）存在通用破解方法，也不被视为安全，普遍使用的 e 一般为 65537。

注：若无特殊说明，以下说的 RSA 的位均指二进制位。

具体实现

环境准备

本文/本项目采用的 GMP 库是 MSYS2 官方源为 MinGW 编译的 GMP 6.3.0-2 预编译库，采用的编译器为由 niXman 维护的 MinGW 15.2.0 POSIX 线程模型、UCRT 运行时库的 x64 版与 x86/x32 版。

当然，如果你有实力，可以下载源码并自行编译。

补充知识：

GMP 为了性能大量手写了汇编指令，因此一般比手写函数快。
MSYS2 的 GMP 预编译库是有胖二进制的（即将所有为不同平台写的汇编指令（注意修饰对象）打包），可以在运行时选择最优 CPU 指令集，以保证不同平台下的性能。

代码编写

GMP 库的使用简介

GMP 有两个头文件，分别为：

C 接口 gmp.h。
C++ 接口 gmpxx.h（对 gmp.h 进行了部分 C++ 封装）。

在本文中，主要涉及整数运算，其在 gmpxx.h 中的封装为 mpz_class，除此之外还有分数 mpq_class（底层为两个 mpz_class 存分子分母）、浮点数 mpf_class（通过构造函数第二个参数或成员函数 set_prec 指定精度（小数点后二进制位数）），这里不过多赘述。

对于 gmpxx.h 没有封装的函数，我们只能使用其 C 版本，需要使用 mpz_class 的成员函数 get_mpz_t 获取其封装的底层 C 变量 mpz_t（只读版本，实际返回值为 mpz_srcptr（const）或 mpz_ptr（非 const））才能传入这些函数并使用，在接下来会遇到。

辅助函数

快速幂函数

加密或解密的计算过程类似于快速幂，我们可以手写一个竞赛版的 O(n \log n) 的，但更快的是 GMP 自带的 C 函数 mpz_powm，它直接返回模运算后的非负余数，有时需要特殊处理（比如需要保留原数正负性的时候），不过对于始终为正的 RSA 不需要，如下：

inline mpz_class fast_pow(const mpz_class &x, const mpz_class &y, const mpz_class &mod){
    mpz_class ans;
    mpz_powm(ans.get_mpz_t(), x.get_mpz_t(), y.get_mpz_t(), mod.get_mpz_t());
    return ans;
}

注：

由于在这里模数始终为 n，因此可以直接使用 n。
对于高安全性场景，我们需要使用抗时序攻击（简单来说就是测量你的程序运行时间来推测信息的攻击方式）的 mpz_powm_sec 来代替 mpz_powm，但这会导致性能下降一些。

最大公约数函数

我们在验证 e 的正确性时，需要求 e 与 \phi(n) 的最大公约数，我们可以直接使用模版函数 std::__gcd（GCC 拓展）或 std::gcd（C++17 以上），也可以使用 C 函数 mpz_gcd，如下：

inline mpz_class gcd(const mpz_class &a, const mpz_class &b){
    mpz_class g;
    mpz_gcd(g.get_mpz_t(), a.get_mpz_t(), b.get_mpz_t());
    return g;
}

扩展欧几里得函数

我们在已知 p, q, e 时，需要求出 d 并提供给用户解密，这时我们就需要用扩展欧几里得算法，如下：

inline tuple<mpz_class, mpz_class> exgcd(const mpz_class &a, const mpz_class &b){
    mpz_class g,x,y;
    mpz_gcdext(g.get_mpz_t(), x.get_mpz_t(), y.get_mpz_t(), a.get_mpz_t(), b.get_mpz_t());
    return {x,y};
}//扩展欧几里得
inline mpz_class get_d(const mpz_class &p, const mpz_class &q, const mpz_class &e){
    mpz_class x, y, m=(p-1)*(q-1);
    tie(x, y)=exgcd(e, m);
    return (x % m + m) % m;//处理解，保证 d 合法
}//计算 d

素数测试函数

在进行 RSA 时，我们需要两个质数 p, q，我们可以通过随机一个数并检验的方式获取，但对于这种大数我们没有任何可以确定它是素数的方式，只能进行概率测试。

在 GMP 中，我们可以用 mpz_probab_prime_p 对一个数字进行一次 Baillie-PSW（BPSW）测试 + 自定义次 Miller-Rabin 素性测试（如需了解请自行搜索），判断其为素数的可能性，原型为：

int mpz_probab_prime_p(const mpz_t n, int reps);

这里 n 是被测试的数字，reps 代表进行 max(0,reps-24) 次 Miller-Rabin 素性测试（别问我为什么这样，问 GMP 官方去），一般 reps 取 25。

函数返回值：2 代表确定是素数，1 代表可能是素数（误判率 4^{-reps}（并不是 4^{24-reps}，很奇怪对吧）），0 代表确定是合数（~~你说这个怎么就是确定呢~~）。

代码如下：

inline bool is_prime(const mpz_class &x){
    return mpz_probab_prime_p(x.get_mpz_t(), 25);
}

获取随机大数函数

我们在随机大数时，可以用 GMP 的 mpz_urandomb，但我们需要先制作一个 GMP 的随机种子 gmp_randstate_t。

GMP 随机种子

类似于 rand 与 mt19937 等，我们在使用 GMP 的随机数时需要一个种子，这个种子就是 gmp_randstate_t，它在使用前需要用 gmp_randinit_default 初始化，随后可以使用 gmp_randseed_ui 或 gmp_randseed 进行种子设定，传入值分别为 unsigned long int 与 mpz_t，封装如下：

inline void init_state_ui(gmp_randstate_t &state){
    gmp_randinit_default(state);
    gmp_randseed_ui(state, (unsigned long long)rand_uint() << 32 | rand_uint());
}
inline void init_state(gmp_randstate_t &state){
    mpz_class seed;
    gmp_randinit_default(state);
    for(int i = 0; i < 32; i++)
        seed = seed << 32 | rand_uint();
    gmp_randseed(state, seed.get_mpz_t());
}

在使用完毕后，为了避免泄露，记得使用 gmp_randclear(state) 进行清理。

随机 `int`

上面用到了 rand_uint 用于随机一个 unsigned int，对于普通场景，使用 rand 或 mt19937 可以很好实现，但对于安全性场景，这些显然就不安全了，因为这些随机数算法固定，攻击者完全可以根据算法预测行为，这里提供一个用 \text{Windows API} BCryptGenRandom 实现的硬件随机数（简单来说随机数不用算法生成，而是动态根据你的电脑的运行状态，比如读写随机延迟，电源电压变化等来生成随机数）：

inline unsigned int rand_uint(){
    unsigned int x = 1;//这里赋值一个初值
    BYTE b[4];//用于调用 BCryptGenRandom
    if(!BCRYPT_SUCCESS(BCryptGenRandom(NULL, b, sizeof(b), BCRYPT_USE_SYSTEM_PREFERRED_RNG)))//用 BCRYPT_SUCCESS 判断调用是否成功
        x ^= random_device{}() ^ get_time();//如果不成功，尝试混合时间等生成
    else for(BYTE c : b) x = x << 8 | c ^ x >> 24;//如果成功，将数混合初值存入 x
    return x;
}

这里提供一个 get_time 实现，但实际上，在新版编译器中（编译器太旧可能会有函数实现问题），除了你的电脑特别拉且系统特别卡，才有极低可能导致调用失败，其概率可视为 0，毕竟微软官方将其视为“必须成功”的 API。

inline long long get_time(){
    using namespace chrono;
    return duration_cast<milliseconds>(steady_clock::now().time_since_epoch()).count();
}//获取毫秒数

随机大数

经过了以上准备，我们可以用 mpz_urandomb 获取大数了，实现如下：

inline mpz_class rand_mpz(gmp_randstate_t &state, const unsigned int &bits){
    mpz_class x;
    mpz_urandomb(x.get_mpz_t(), state, bits);
    return x;
}

注意需要先初始化一个 gmp_randstate_t，这里 bits 是二进制位数。

随机大素数函数

随机了大数，我们就要用它来生成素数了，一种常见的方式是不断随机并判断，但这样效率低下（根据素数分布公式，期望随机 k \ln 2 个数才能找到一个素数（这里 k 是素数二进制位数），加上随机化开销，实际运行效率并不高），我们需要用优化的 mpz_nextprime 来快速获取某个数的下一个素数（底层大致为枚举 + mpz_probab_prime_p），如下：

inline mpz_class rand_prime(gmp_randstate_t &state, const unsigned int &bits){
    mpz_class x = rand_mpz(state, bits);
    mpz_nextprime(x.get_mpz_t(), x.get_mpz_t());//这里直接覆盖原数据即可
    return x;
}

随机 e 函数

当然，用随机大数函数，我们可以随机 e，而不一定用 65537，如下：

inline mpz_class rand_e(const mpz_class &p, const mpz_class &q, gmp_randstate_t &state, const unsigned int &bits){
    mpz_class m = (p - 1) * (q - 1);
    mpz_class x;
    do x = rand_mpz(state, bits);
    while(gcd(x, m) != 1);
    return x;
}

最后

封装完以上函数，我们就可以~~快乐地~~头脑风暴地写一个简单的加密程序了。

:::info[例子]

#include <bits/stdc++.h>
#include <windows.h>
#include <gmpxx.h>
using namespace std;
inline mpz_class fast_pow(const mpz_class &x, const mpz_class &y, const mpz_class &mod){
    mpz_class ans;
    mpz_powm(ans.get_mpz_t(), x.get_mpz_t(), y.get_mpz_t(), mod.get_mpz_t());
    return ans;
}
inline mpz_class gcd(const mpz_class &a, const mpz_class &b){
    mpz_class g;
    mpz_gcd(g.get_mpz_t(), a.get_mpz_t(), b.get_mpz_t());
    return g;
}
inline tuple<mpz_class, mpz_class> exgcd(const mpz_class &a, const mpz_class &b){
    mpz_class g,x,y;
    mpz_gcdext(g.get_mpz_t(), x.get_mpz_t(), y.get_mpz_t(), a.get_mpz_t(), b.get_mpz_t());
    return {x,y};
}
inline mpz_class get_d(const mpz_class &p, const mpz_class &q, const mpz_class &e){
    mpz_class x, y, m=(p-1)*(q-1);
    tie(x, y)=exgcd(e, m);
    return (x % m + m) % m;
}
inline unsigned int rand_uint(){
    unsigned int x = 1;
    BYTE b[4];
    BCryptGenRandom(NULL, b, sizeof(b), BCRYPT_USE_SYSTEM_PREFERRED_RNG);
    for(BYTE c : b) x = x << 8 | c ^ x >> 24;
    return x;
}//前面的带错误处理的版本是为了规范，实际上并不需要
inline void init_state(gmp_randstate_t &state){
    mpz_class seed;
    gmp_randinit_default(state);
    for(int i = 0; i < 32; i++)
        seed = seed << 32 | rand_uint();
    gmp_randseed(state, seed.get_mpz_t());
}
inline mpz_class rand_mpz(gmp_randstate_t &state, const unsigned int &bits){
    mpz_class x;
    mpz_urandomb(x.get_mpz_t(), state, bits);
    return x;
}
inline mpz_class rand_prime(gmp_randstate_t &state, const unsigned int &bits){
    mpz_class x = rand_mpz(state, bits);
    mpz_nextprime(x.get_mpz_t(), x.get_mpz_t());
    return x;
}
inline mpz_class rand_e(const mpz_class &p, const mpz_class &q, gmp_randstate_t &state, const unsigned int &bits){
    mpz_class m = (p - 1) * (q - 1);
    mpz_class x;
    do x = rand_mpz(state, bits);
    while(gcd(x, m) != 1);
    return x;
}
int main(){
    unsigned int bits = 1024;
    mpz_class x;
    cin >> x;//要加密的内容
    gmp_randstate_t state;
    init_state(state);
    mpz_class p = rand_prime(state, bits);
    mpz_class q = rand_prime(state, bits);
    mpz_class n = p * q;
    mpz_class e = rand_e(p, q, state, bits);
    mpz_class d = get_d(p, q, e);
    mpz_class y = fast_pow(x, e, n);
    cout << y << '\n' << d << '\n' << n;
    gmp_randclear(state);//别忘了清理
    return 0;
}

:::

附言

本文中代码大多为了理解而与项目的源码不同，但核心函数是一致的。

本文只选取了源码中关于 GMP 的部分内容，其余还有大部分关于交互、输入检查、多线程加速、中文输出修复等内容。

~~看到源码真的别喷~~

:::info[AI 使用说明] 本文使用 DeepSeek 进行了查错、润色。 :::

后记

~~写完文章后发现漏了一堆标点真的无语~~

~~怎么还有一堆多余空格~~

也许以后会写篇文章把所有实现都介绍下……