GMP大数库学习
在网络安全技术领域中各种加密算法的软件实现始终有一个共同话题是如何在普通的PC机上实现大数运算。普通的PC机内部字长最多时32位或64位，但各种加密算法中为了达到一定安全强度，都要求在128位、512位或1024位字长下进行加减乘除等数学运算，这叫做“大数运算”。
在此前提下，如何在普通的PC机上高效快速的实现大数运算成为加密算法在普通PC机上软件实现的重要问题。如python等语言都内建大数计算机制，但C/C++语言既没有内建大数运算机制，也没有对应的标准库实现。
基于此问题，许多优秀的大数运算库随之而来，下面介绍几种常用常见的大数库：
GMP大数库是GUN项目的一部分，诞生于1991年，作为一个任意精度的大整数运算库，它包含了任意精度的整数、浮点数的各种基础运算操作。它是一个C语言库，并提供了C++的包装类，主要应用于密码学应用和研究、互联网安全应用、代数系统、计算代数研究等。
GMP库运行速度非常快，官网上称自己是地球上最快的大数库，但GMP只提供了基础数学运算，并没有提供密码学的相关运算。
miracl库的使用许可针对教育科学研究或非商业目的的应用是免费的，它是C语言库，同时提供了较为简单C++包装类。在功能上它不但提供了高精度的大整数和分数的各种数学运算操作，且提供了许多密码学算法的功能模块，如RSA、AES、DSA等底层操作。尤其还提供了许多椭圆曲线密码学体制中的底层功能模块。
由于miracl库的内部实现采用了很多汇编代码，故运行速度是非常快的。
Crypto++库是一个C++开源库，提供很多密码算法的实现。
OpenSSL是一个C语言库，实现了SSL及相关加密技术，可以实现消息摘要、文件的加解密、数字证书、数字签名和随机数生成等。它的主要特征不是大数据，而是SSL协议的实现和应用。
在线文档：https://gmplib.org/manual/
官方手册：https://gmplib.org/gmp-man-6.2.1.pdf
见「参考1」
⚠️：由于GMP是C语言库，但也提供了C++的包装类，在编译时，如果要增加C++支持，./configure时加上--enable-cxx参数，这样才能使用c++库gmpxx.h。
以下面例子为例：
//test.cpp
#include <gmpxx.h>
#include <iostream>
using namespace std;
int main()
{
mpz_t a, b, c;
mpz_init(a);
mpz_init(b);
mpz_init(c);
gmp_scanf("%Zd%Zd", a, b);
mpz_add(c, a, b);
gmp_printf("c= %Zd\n", c);
return 0;
}
编译运行：
g++ test.cpp -o test -lgmp
./test
使用GMP库：
| 基本数据类型 | 函数类型 |
|---|---|
| mpz_t（整数） | mpz_开头 |
| mpq_t（有理数） | mpq_开头 |
| mpf_t（浮点数） | mpf_开头 |
如何使用呢？以浮点数为例分五步：
mpf_t fnum;
mpf_init(fnum); //或mpf_init(fnum,20)，此函数指针对类型mpf_t有效
mpf_set_str(fnum,"1.23",10); //以10为进制数，表示浮点数的字符串来赋值fnum
//mpf_set_str的原型
int mpf_init_set_str (mpf_ptr, const char *, int);
其中三个参数表示为多精度浮点数变量、字符串、进制。
mpf_mul(fnum,fnum,tmp); //fnum和tmp都是mpf_t类型的变量
mpf_clear(fnum);
下面使用GMP：求10000！
//test2.cpp
#include <gmp.h> //先引入gmp头文件
#include <stdio.h>
#include <string.h>
int main(int argc, const char *argv[])
{
mpz_t z_i, z_s, z_o; //定义多精度整数类型
//用1初始化变量
mpz_init_set_str(z_i, "1", 10);
mpz_init_set_str(z_s, "1", 10);
mpz_init_set_str(z_o, "1", 10);
int i;
//z_s=1*2*3*....*10000
for (i = 0; i < 10000; i++)
{
mpz_mul(z_s, z_s, z_i); //z_s=z_s*z_i
mpz_add(z_i, z_i, z_o); //z_i=z_i+z_o
}
gmp_printf("%Zd\n", z_s); //输出和printf类似
//释放空间
mpz_clear(z_i);
mpz_clear(z_s);
mpz_clear(z_o);
getchar();
return 0;
}
⚠️：一个变量只需初始化一次，如果非要多次初始化，在每次初始化操作之间释放变量。初始化后的变量可以进行任意次赋值，但为了效率，应避免过多的变量初始化和释放操作。
下面详细分析数据类型
gmp类型变量的本质是长度为1的结构体数组，变量的值存储在地址 _mp_d 对应的值中
typedef struct
{
int _mp_alloc; /* Number of *limbs* allocated and pointed
to by the _mp_d field. */
int _mp_size; /* abs(_mp_size) is the number of limbs the
last field points to. If _mp_size is
negative this is a negative number. */
mp_limb_t *_mp_d; /* Pointer to the limbs. */
} __mpz_struct;
typedef __mpz_struct mpz_t[1];
其中：
如果自己编写的函数要返回结果，应该仿照GMP的库函数，使用输出参数（即函数的参数有部分参数用于输出值），如果直接使用return语句，返回的仅仅是个指针。
//test1.c
#include <stdio.h>
#include <gmp.h>
void foo(mpz_t result, const mpz_t param, unsigned long n)
{
unsigned long i;
mpz_mul_ui(result, param, n);
for (i = 1; i < n; i++)
mpz_add_ui(result, result, i * 7);
}
int main(void)
{
mpz_t r, n;
mpz_init(r);
mpz_init_set_str(n, "123456", 0);
foo(r, n, 20L);
gmp_printf("%Zd\n", r);
return 0;
}
其中，上面foo函数的输入参数param设置为const。
GMP自己会管理自己申请的内存：
除了上述「3.1.1」中介绍的整数函数、有理数函数和浮点数函数外，还有：
另外，GMP的大部分函数一般把输出参数放在输入参数之前，此约定是受赋值运算符的启发，例如：gmz_mul(x,x,x)：此调用计算整数x的平方然后把计算结果再存入x中。
待补充
#include <iostream>
#include <gmpxx.h>
#include <cstdlib>
using namespace std;
mpz_class randbits(int bits) // base = 2
{
gmp_randclass a(gmp_randinit_default);
a.seed(rand());
mpz_class l(bits);
return a.get_z_bits(l);
}
inline mpz_class randprime(int bits)
{
mpz_class a = randbits(bits);
mpz_class ret;
mpz_nextprime(ret.get_mpz_t(), a.get_mpz_t());
return ret;
}
void setKey(mpz_class &n, mpz_class &e, mpz_class &d, const int nbits, int ebits = 16)
{
if (nbits / 2 <= ebits)
{
ebits = nbits / 2;
}
mpz_class p = randprime(nbits / 2); //随机取p
mpz_class q = randprime(nbits / 2); //随机取q
n = q * p; //计算n=p*q
mpz_class fn = (p - 1) * (q - 1); //计算欧拉数
mpz_class gcd;
do
{
e = randprime(ebits); //随机取e
mpz_gcd(gcd.get_mpz_t(), e.get_mpz_t(), fn.get_mpz_t()); //判断gcd(e,fn)=1是否成立
} while (gcd != 1);
//mpz_gcdext(g, s, t, a, b)： g = as + bt
mpz_gcdext(p.get_mpz_t(), d.get_mpz_t(), q.get_mpz_t(), e.get_mpz_t(), fn.get_mpz_t()); //计算d=e^{-1} mod fn
}
inline mpz_class encrypt(const mpz_class &m, const mpz_class &e, const mpz_class &n)
{
mpz_class ret;
mpz_powm(ret.get_mpz_t(), m.get_mpz_t(), e.get_mpz_t(), n.get_mpz_t()); //ret=m^e mod n
return ret;
}
inline mpz_class decrypt(const mpz_class &c, const mpz_class &d, const mpz_class &n)
{
return encrypt(c, d, n); //m=c^d mod n
}
int main()
{
int nbits;
cout << "输入大数比特数:";
cin >> nbits;
mpz_class n, e, d;
setKey(n, e, d, nbits); //密钥生成
cout << "公钥:(e=" << e.get_str() << ", n=" << n.get_str() << ")" << endl;
cout << "私钥:(d=" << d.get_str() << ", n=" << n.get_str() << ")" << endl;
cout << "输入加密数据:";
string s;
cin >> s;
mpz_class m(s);
mpz_class c;
c = encrypt(m, e, n); //加密
cout << "加密后:" << c.get_str() << endl;
c = decrypt(c, d, n); //解密
cout << "解密后:" << c.get_str() << endl;
if (c == m)
cout << "加/解密成功!" << endl
<< endl;
else
cout << "加/解密失败!" << endl
<< endl;
string q;
cout << "是否继续(Y/N):";
cin >> q;
if (q == "y" || q == "Y")
main();
return 0;
}
其中，mpz_class类型是有符号整数，具体参考：C++ GMP常用函数
待补充