bignuminc

发表于 | 分类于 ，

编程时使用的大数运算

在编程中，有时候会遇到大数运算的情况（大于语言本身定义的最大长度的数的运算，一般都是64位）。在密码学或者自定义数据类型，如数据库中deicmal类型，定义了数的精度和比例(precision 精度，有效数字。scale不知道怎么翻译了…就是小数点的位数)。在这种情况下需要自己定义针对大数的运算。

大数运算的原理

一般语言中提供的最大长度的数就是64位，8bytes，能表示的最大数是无符号类型的64位的数。想要存储更大的数，只要进行分段即可。算法也基本上都是基于竖式计算的方法进行分段运算。具体的算法和相关的优化此处就不讨论了。

GO语言中的大数运算

我日常主要使用C和go，这里也只讲这两种语言的大数运算。各种语言都会遇到大数运算的需求，因此我们也没必要去造轮子自己写一遍。

go的math/big包中就实现了大数运算的各种运算法则，还是很方便的，也就不再讲了。

C语言中的大数运算

c语言的原则导致官方提供的库是很少的，但是这么多年的发展，也存在各种稳定的库实现。

gmp

一般大数运算都是用gmp库，libgmp。用法也比较简单。编译时需要增加选项-lgmp进行链接。由于不符合我的要求所以没有深入了解。网上文章很多，就不造轮子了。

openssl

openssl算是公认的加密算法库实现的标准了。一般系统中都内置了openssl库。既然是实现加密算法的，那一定需要用到大数运算。这次有大数运算的简单需求后，不想引入新的依赖，所以我想openssl内部的接口能否满足我的需求呢。经过查询发现<openssl/bn.h>中(bn =》bignumber)提供了大数运算的接口。网上的教程大多是错误的，通过查阅openssl的官方文档简单总结了一下openssl中大数运算的接口调用。

definition

1
2
3
4
BIGNUM		//struct
BN_CTX		//struct
BN_ULONG	//unsigned long
...

赋值

1
2
3
int BN_bn2bin(const BIGNUM *a, unsigned char *to);
 int BN_bn2binpad(const BIGNUM *a, unsigned char *to, int tolen);
 BIGNUM *BN_bin2bn(const unsigned char *s, int len, BIGNUM *ret);

BN_bn2bin 从大数存储结构转换为二进制数的字符串形式, to 为目标存储区，需要长度足够存二进制的数，形式是字符串%s

BN_bn2binpad 转换为二进制，用0填充到指定长度

BN_bin2bn 从正二进制字符串转换为big number结构

以上均为大端序

1
2
int BN_bn2lebinpad(const BIGNUM *a, unsigned char *to, int tolen);
 BIGNUM *BN_lebin2bn(const unsigned char *s, int len, BIGNUM *ret);

以上为小端序版本

1
2
3
4
char *BN_bn2hex(const BIGNUM *a);
 char *BN_bn2dec(const BIGNUM *a);
 int BN_hex2bn(BIGNUM **a, const char *str);
 int BN_dec2bn(BIGNUM **a, const char *str);

BN_bn2hex 从BIGNUM 转换为十六进制字符串

BN_bn2dec 从BIGNUM转换为十进制字符串

BN_hex2bn 从十六进制字符串转换为BIGNUM，可以带负号’-‘， 不带十六进制标示0x，总体呈现为“-deadbeef“

BN_dec2bn 从十进制转换为BIGNUM，可以带负号

1
2
int BN_print(BIO *fp, const BIGNUM *a);
int BN_print_fp(FILE *fp, const BIGNUM *a);

以十六进制，带负号形式，打印存储的大数

1
2
int BN_bn2mpi(const BIGNUM *a, unsigned char *to);
BIGNUM *BN_mpi2bn(unsigned char *s, int len, BIGNUM *ret);

这一组函数很有用，在进行数据通信的时候，数据都是以十六进制流的形式通信。此处定义了一种格式，以4字节大端序表示数据长度，随后跟着同样以大端序呈现的数据。（转换输出后的结果会讲MSB最高有效位作为符号位使用，但是不知道为什么他自己的解析函数并没有解析符号位，还是以正数使用为主。（采用MSB表示的以null byte为前缀，这一句定义没有get到)

运算

运算的接口比较好理解，我用到的也不多，就不细说了。

openssl需要安装openssl-devel （或者形如libssl-devel等）。编译时需要使用-lcrypto 进行链接。

[引用]

openssl官方文档