11 大数¶
11.1 介绍¶
大数一般指的是位数很多的数。 计算机表示的数的大小是有限的,精度也是有限的,它不能支持大数运算。 密码学中采用了很多大数计算,为了让计算机实现大数运算,用户需要定义自己的大数表示方式并及实现各种大数运算。 Openssl为我们提供了这些功能,主要用于非对称算法。
11.2 openssl大数表示¶
crypto/bn.h中定义了大数的表示方式,如下:
struct bignum_st { BN_ULONG *d; int top; int dmax; int neg; int flags; }; /* 各项意义如下: d :BN_ULONG(应系统而异,win32下为4个字节)数组指针首地址, 大数就存放在这里面,不过是倒放的。 比如,用户要存放的大数为 12345678000(通过BN_bin2bn放入), 则 d 的内容如下: 0x30 0x30 0x30 0x38 0x37 0x36 0x35 0x34 0x33 0x32 0x31 ; top :用来指明大数占多少个BN_ULONG空间,上例中top为3。 dmax:d数组的大小。 neg :是否为负数, 如果 为1,则是负数,为0,则为正数。 flags:用于存放一些标记, 比如flags 含有 BN_FLG_STATIC_DATA 时, d 的内存是静态分配的; 含有 BN_FLG_MALLOCED 时,d 的内存是动态分配的。 */
11.3 大数函数¶
大数函数一般都能根据函数名字知道其实现的功能。下面简单介绍了几个函数。
1)
int BN_rand(BIGNUM *rnd, int bits, int top, int bottom);
int BN_priv_rand(BIGNUM *rnd, int bits, int top, int bottom);
int BN_pseudo_rand(BIGNUM *rnd, int bits, int top, int bottom);
生成一个随机的大数。
2)
int BN_rand_range(BIGNUM *rnd, BIGNUM *range);
int BN_priv_rand_range(BIGNUM *rnd, BIGNUM *range);
int BN_pseudo_rand_range(BIGNUM *rnd, BIGNUM *range);
生成随机数,但是给出了随机数的范围。
3)
BIGNUM *BN_copy(BIGNUM *to, const BIGNUM *from);
BIGNUM *BN_dup(const BIGNUM *from);
void BN_with_flags(BIGNUM *dest, const BIGNUM *b, int flags);
大数复制。
4)
int BN_generate_prime_ex(BIGNUM *ret, int bits, int safe, const BIGNUM *add,
const BIGNUM *rem, BN_GENCB *cb);
#if OPENSSL_API_COMPAT < 0x00908000L
BIGNUM *BN_generate_prime(BIGNUM *ret, int num, int safe, BIGNUM *add,
BIGNUM *rem, void (*callback)(int, int, void *),
void *cb_arg);
生成素数。
5) int BN_add_word(BIGNUM *a, BN_ULONG w)
给大数a加上w,
BN_add_word() adds w to a ("a+=w").
BN_sub_word() subtracts w from a ("a-=w").
BN_mul_word() multiplies a and w ("a*=w").
BN_div_word() divides a by w ("a/=w") and returns the remainder.
BN_mod_word() returns the remainder of a divided by w ("a%w").
For BN_div_word() and BN_mod_word(), w must not be 0.
return 1 for success, 0 on error
6) 转换
6.1
BIGNUM * BN_bin2bn(const unsigned char *s, int len, BIGNUM *ret)
将 s 中的换为大数,
入参
s : 为内存地址,
len : 为数据长度,
出参:
ret : 为返回值。
6.2
int BN_bn2bin(const BIGNUM *a, unsigned char *to)
将大数转换为内存形式。
入参:
a : 大数,
to : 为输出缓冲区地址,缓冲区需要预先分配,可以为NULL,
return : 返回冲区的长度。
BN_bn2bin() returns the length of the big-endian number placed at to.
BN_bin2bn() returns the BIGNUM, NULL on error
6.3
char *BN_bn2dec(const BIGNUM *a)
将大数转换成整数字符串。
return : 返回值中存放 整数字符串,它由内部分配空间,
用户必须在外部用OPENSSL_free函数释放该空间。
int BN_dec2bn(BIGNUM **a, const char *str); //将整数字符串转换成大数。
6.4
char *BN_bn2hex(const BIGNUM *a)
将大数转换为十六进制字符串。
return: 返回值为生成的十六进制字符串,
外部需要用OPENSSL_free函数释放
int BN_hex2bn(BIGNUM **a, const char *str); // 将十六进制字符串转换为大数
BN_bn2hex() and BN_bn2dec() return a null-terminated string, or NULL on error.
BN_hex2bn() and BN_dec2bn() return the number of characters used in parsing,
or 0 on error, in which case no new BIGNUM will be created.
10) 比较
int BN_cmp(BIGNUM *a, BIGNUM *b); 比较两个大数。
int BN_ucmp(BIGNUM *a, BIGNUM *b); 比较两个大数绝对值。
int BN_is_zero(BIGNUM *a);
int BN_is_one(BIGNUM *a);
int BN_is_word(BIGNUM *a, BN_ULONG w);
int BN_is_odd(BIGNUM *a);
11)BIGNUM *BN_mod_inverse( BIGNUM *in,
const BIGNUM *a,
const BIGNUM *n,
BN_CTX *ctx)
计算ax=1(mod n)。
用户使用openssl函数编程时, 一般用不着进行大数运算。
BN_bin2bn、BN_hex2bn、BN_dec2bn、BN_bin2bn、BN_bn2bin、BN_bn2hex和BN_bn2dec比较常用。
比如给定RSA密钥的内存形式,用户可以调用BN_bin2bn来构造RSA密钥的大数元素来进行RSA运算,
或者已经生成了RSA密钥,用户调用BN_bn2bin将RSA各个元素导出到内存中再写入密钥文件。
#include <openssl/bio.h>
#include <openssl/bn.h>
int main()
{
int ret;
BIGNUM *a;
BN_ULONG w;
a=BN_new();
//BN_zero(a);
//BN_one(a);
//BN_set_word(a,16);
//BN_set_word(a,256);
w=2685550010;
//w=0x2685550010;
ret=BN_add_word(a,w);
if(ret!=1) {
printf("a+=w err!\n");
BN_free(a);
return -1;
}
BIO *bio_out;
bio_out = BIO_new_fp(stdout, BIO_NOCLOSE);
//int BN_print(BIO *fp, const BIGNUM *a);
BIO_printf(bio_out, "-------------------\n");
BN_print(bio_out, a);
BIO_printf(bio_out, "\n-------------------\n");
int bits = BN_num_bits(a);
BIO_printf(bio_out, "bits = %d \n" ,bits);
bits = BN_num_bytes(a);
BIO_printf(bio_out, "bytes = %d \n" ,bits);
BN_free(a);
return 0;
}
#include <openssl/bio.h>
#include <openssl/bn.h>
int main()
{
BIGNUM *ret1,*ret2;
ret1=BN_new();
ret1=BN_bin2bn("242424ab",8, ret1);
ret2=BN_bin2bn("242424ab",8, NULL);
// printf
BIO *bio_out;
bio_out = BIO_new_fp(stdout, BIO_NOCLOSE);
BN_print(bio_out, ret1); // 16进制打印
BIO_printf(bio_out, "\n");
BN_print(bio_out, ret2);
BIO_printf(bio_out, "\n");
BIO_free(bio_out);
// free
BN_free(ret1);
BN_free(ret2);
return 0;
}
#include <openssl/bio.h>
#include <openssl/bn.h>
int main()
{
BIGNUM *ret = NULL;
char bin[50]={'s'}, *buf = NULL;
int len;
ret = BN_bin2bn("242424ab",8, NULL);
len = BN_bn2bin(ret,bin);
len = BN_num_bytes(ret);
buf = (char *) malloc(len + 1);
len = BN_bn2bin(ret,buf);
// new bio
BIO *bio_out;
bio_out = BIO_new_fp(stdout, BIO_NOCLOSE);
// bio printf
BN_print(bio_out, ret); // 16进制打印
BIO_printf(bio_out, "\n");
BIO_printf(bio_out,"%s\n", buf);
BIO_free(bio_out);
free (buf);
BN_free(ret);
return 0;
}
#include <openssl/bn.h>
#include <openssl/crypto.h>
int main()
{
BIGNUM *ret1 = NULL;
char *p = NULL;
int len = 0;
ret1 = BN_bin2bn("242424ab",8, NULL);
p = BN_bn2dec(ret1);
printf("%s\n",p); /* 3617571600447332706 */
BN_free(ret1);
OPENSSL_free(p);
//getchar();
return 0;
}
/************************************************************************
* 转换
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);
int BN_bn2lebinpad(const BIGNUM *a, unsigned char *to, int tolen);
BIGNUM *BN_lebin2bn(const unsigned char *s, int len, BIGNUM *ret);
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);
int BN_print(BIO *fp, const BIGNUM *a);
int BN_print_fp(FILE *fp, const BIGNUM *a);
int BN_bn2mpi(const BIGNUM *a, unsigned char *to);
BIGNUM *BN_mpi2bn(unsigned char *s, int len, BIGNUM *ret);
************************************************************************/
#include <openssl/bio.h>
#include <openssl/bn.h>
#include <string.h>
int main()
{
BIGNUM *ret1 = NULL, * ret2 = BN_new();
char *p = NULL;
int len = 0;
int i;
// new bio
BIO *bio_out;
bio_out = BIO_new_fp(stdout, BIO_NOCLOSE);
BIO_printf(bio_out,"\n---- BN_bin2bn ----\n");
ret1 = BN_bin2bn("242424ab",8, NULL); /* 二进制 转 bn*/
char arr[1024] = {6};
memset(arr,8,100);
BN_bn2bin(ret1,arr);
for ( i = 0; i < 10; i ++){
printf("%02x " ,arr[i]);
}
p = BN_bn2hex(ret1); /* bn 转 16进制字符串*/
//printf("\n0x%s\n",p);
BIO_printf(bio_out,"\n0x%s\n", p);
OPENSSL_free(p); // free
int ret = 0;
BIO_printf(bio_out,"\n---- BN_hex2bn / BN_bn2hex ----\n");
BIGNUM * a = BN_new();
//const char * pstr = "ABFE12";
const char * pstr = "ABFE12";
ret = BN_hex2bn(&a,pstr); // 将十六进制字符串转换为大数
OPENSSL_assert(ret == strlen(pstr));
BN_print(bio_out, a); // 十六进制打印
p = BN_bn2hex(a); // 大数 转 十六进制字符串/
BIO_printf(bio_out,"\n0x%s\n", p);
OPENSSL_free(p); // free
BN_free(a);
/*hex to bn*/
BIO_printf(bio_out,"\n---- BN_dec2bn ----\n");
BN_dec2bn(&ret2,"254"); /* 10进制字符串 转换 bn*/
BN_print(bio_out, ret2); // 16进制打印
BIO_printf(bio_out,"\n");
BN_free(ret1);
BN_free(ret2);
//getchar();
return 0;
}
11.4 使用示例¶
- 示例1
#include <openssl/bn.h>
#include <openssl/bio.h>
#include <string.h>
int main()
{
BIGNUM *bn;
BIO *b;
char a[20];
int ret;
bn = BN_new();
strcpy(a,"32");
//ret = BN_dec2bn(&bn,a); /* 10进制字符串 转换 bn*/
ret = BN_hex2bn(&bn,a); // 16进制字符串 转换 bn
b = BIO_new(BIO_s_file());
ret = BIO_set_fp(b,stdout,BIO_NOCLOSE);
BN_print(b,bn);
BIO_write(b,"\naaa",4);
BIO_printf(b,"\nbbb\n");
BN_free(bn);
return 0;
}
- 示例2 : 加法运算
/******************
示例2:
加法运算
*****************/
#include <openssl/bn.h>
#include <string.h>
#include <openssl/bio.h>
int main()
{
BIGNUM *a, *b, *add;
BIO *out;
char c[20], d[20];
int ret;
a = BN_new();
strcpy(c,"32");
ret = BN_hex2bn(&a,c); // 16进制字符串 转换 bn
b = BN_new();
strcpy(d,"100");
ret = BN_hex2bn(&b,d);
out = BIO_new(BIO_s_file());
ret = BIO_set_fp(out,stdout,BIO_NOCLOSE);
add = BN_new();
ret = BN_add(add,a,b);
if(ret!=1) {
printf("err.\n");
return -1;
}
BIO_puts(out,"bn 0x32 + 0x100 = 0x");
BN_print(out,add);
BIO_puts(out,"\n");
BN_free(a);
BN_free(b);
BN_free(add);
BIO_free(out);
return 0;
}
- 示例3 : 减法运算
/******************
示例3 :
减法运算
*****************/
#include <openssl/bn.h>
#include <string.h>
#include <openssl/bio.h>
int main()
{
BIGNUM *a, *b, *sub;
BIO *out;
char c[20], d[20];
int ret;
a = BN_new();
strcpy(c,"100");
ret = BN_hex2bn(&a, c); // 16进制字符串 转换 bn
b = BN_new();
strcpy(d,"32");
ret = BN_hex2bn(&b, d);
out = BIO_new(BIO_s_file());
ret = BIO_set_fp(out, stdout, BIO_NOCLOSE);
sub = BN_new();
ret = BN_sub(sub, a, b);
if(ret != 1) {
printf("err.\n");
return -1;
}
BIO_puts(out, "bn : 0x100 - 0x32 = 0x");
BN_print(out, sub);
BIO_puts(out, "\n");
BN_free(a);
BN_free(b);
BN_free(sub);
BIO_free(out);
return 0;
}
- 示例4 : 乘法运算
/******************
示例4 :
乘法运算
*****************/
#include <openssl/bn.h>
#include <string.h>
#include <openssl/bio.h>
int main()
{
BIGNUM *a, *b, *mul;
BN_CTX *ctx;
BIO *out;
char c[20],d[20];
int ret;
ctx = BN_CTX_new();
a = BN_new();
strcpy(c,"32");
ret = BN_hex2bn(&a,c); // 16进制字符串 转换 bn
b = BN_new();
strcpy(d,"100");
ret = BN_hex2bn(&b,d);
out = BIO_new(BIO_s_file());
ret = BIO_set_fp(out,stdout,BIO_NOCLOSE);
mul = BN_new();
ret = BN_mul(mul,a,b,ctx);
if(ret != 1) {
printf("err.\n");
return -1;
}
BIO_puts(out,"bn : 0x32 * 0x100 = 0x");
BN_print(out,mul);
BIO_puts(out,"\n");
BN_free(a);
BN_free(b);
BN_free(mul);
BIO_free(out);
BN_CTX_free(ctx);
return 0;
}
- 示例5 : 除法运算
/******************
示例5:
除法运算
*****************/
#include <openssl/bn.h>
#include <string.h>
#include <openssl/bio.h>
int main()
{
BIGNUM *a, *b, *div, *rem;
BN_CTX *ctx;
BIO *out;
char c[20], d[20];
int ret;
ctx = BN_CTX_new();
a = BN_new();
strcpy(c,"100");
ret = BN_hex2bn(&a,c); // 16进制字符串 转换 bn
b = BN_new();
strcpy(d,"17");
ret = BN_hex2bn(&b,d);
out = BIO_new(BIO_s_file());
ret = BIO_set_fp(out,stdout,BIO_NOCLOSE);
div = BN_new();
rem = BN_new();
ret = BN_div(div,rem,a,b,ctx);
if(ret != 1){
printf("err.\n");
return -1;
}
BIO_puts(out,"bn : 0x100 / 0x17 = 0x");
BN_print(out,div);
BIO_puts(out,"\n");
BIO_puts(out,"bn : 0x100 % 0x17 = 0x");
BN_print(out,rem);
BIO_puts(out,"\n");
BN_free(a);
BN_free(b);
BN_free(div);
BN_free(rem);
BIO_free(out);
BN_CTX_free(ctx);
return 0;
}
- 示例6 : 平方运算
/******************
示例6:
平方运算
*****************/
#include <openssl/bn.h>
#include <string.h>
#include <openssl/bio.h>
int main()
{
BIGNUM *a, *sqr;
BN_CTX *ctx;
BIO *out;
char c[20];
int ret;
ctx = BN_CTX_new();
a = BN_new();
strcpy(c,"100");
ret = BN_hex2bn(&a,c); // 16进制字符串 转换 bn
sqr = BN_new();
out = BIO_new(BIO_s_file());
ret = BIO_set_fp(out,stdout,BIO_NOCLOSE);
ret = BN_sqr(sqr,a,ctx);
if(ret != 1) {
printf("err.\n");
return -1;
}
BIO_puts(out,"bn : 0x100 sqr = 0x");
BN_print(out,sqr);
BIO_puts(out,"\n");
BN_free(a);
BN_free(sqr);
BIO_free(out);
BN_CTX_free(ctx);
return 0;
}
- 示例7 : 次方运算
/******************
示例7 :
次方运算
*****************/
#include <openssl/bn.h>
#include <string.h>
#include <openssl/bio.h>
int main()
{
BIGNUM *a, *exp, *b;
BN_CTX *ctx;
BIO *out;
char c[20],d[20];
int ret;
ctx = BN_CTX_new();
a = BN_new();
strcpy(c,"100");
ret = BN_hex2bn(&a,c); // 16进制字符串 转换 bn
b = BN_new();
strcpy(d,"3");
ret = BN_hex2bn(&b,d);
exp = BN_new();
out = BIO_new(BIO_s_file());
ret = BIO_set_fp(out,stdout,BIO_NOCLOSE);
ret = BN_exp(exp,a,b,ctx);
if(ret !=1 ) {
printf("err.\n");
return -1;
}
BIO_puts(out,"bn : 0x100 exp 0x3 = 0x");
BN_print(out,exp);
BIO_puts(out,"\n");
BN_free(a);
BN_free(b);
BN_free(exp);
BIO_free(out);
BN_CTX_free(ctx);
return 0;
}
1.初始化函数
BIGNUM *BN_new(void); 新生成一个BIGNUM结构
void BN_free(BIGNUM *a); 释放一个BIGNUM结构,释放完后a=NULL;
void BN_init(BIGNUM *); 初始化所有项均为0,一般为BN_ init(&c)
void BN_clear(BIGNUM *a); 将a中所有项均赋值为0,但是内存并没有释放
void BN_clear_free(BIGNUM *a); 相当与将BN_free和BN_clear综合,要不就赋值0,要不就释放空间。
2.上下文情景函数,存储计算中的中间过程
BN_CTX *BN_CTX_new(void);申请一个新的上下文结构
void BN_CTX_init(BN_CTX *c);将所有的项赋值为0,一般BN_CTX_init(&c)
void BN_CTX_free(BN_CTX *c);释放上下文结构,释放完后c=NULL;
3.复制以及交换函数
BIGNUM *BN_copy(BIGNUM *a, const BIGNUM *b);将b复制给a,正确返回a,错误返回NULL
BIGNUM *BN_dup(const BIGNUM *a);新建一个BIGNUM结构,将a复制给新建结构返回,错误返回NULL
BIGNUM *BN_swap(BIGNUM *a, BIGNUM *b);交换a,b
4.取位函数
int BN_num_bytes(const BIGNUM *a);返回a的位数,大量使用
int BN_num_bits(const BIGNUM *a);
int BN_num_bits_word(BN_ULONG w);他返回有意义比特的位数,例如0x00000432 为11。
5.基本计算函数
int BN_add(BIGNUM *r, const BIGNUM *a, const BIGNUM *b);r=a+b
int BN_sub(BIGNUM *r, const BIGNUM *a, const BIGNUM *b);r=a-b
int BN_mul(BIGNUM *r, BIGNUM *a, BIGNUM *b, BN_CTX *ctx);r=a*b
int BN_sqr(BIGNUM *r, BIGNUM *a, BN_CTX *ctx);r=a*a,效率高于bn_mul(r,a,a)
int BN_div(BIGNUM *dv, BIGNUM *rem, const BIGNUM *a, const BIGNUM *d,
BN_CTX *ctx);d=a/b,r=a%b
int BN_mod(BIGNUM *rem, const BIGNUM *a, const BIGNUM *m, BN_CTX *ctx);r=a%b
int BN_nnmod(BIGNUM *rem, const BIGNUM *a, const BIGNUM *m, BN_CTX *ctx);r=abs(a%b)
int BN_mod_add(BIGNUM *ret, BIGNUM *a, BIGNUM *b, const BIGNUM *m,
BN_CTX *ctx);r=abs((a+b)%m))
int BN_mod_sub(BIGNUM *ret, BIGNUM *a, BIGNUM *b, const BIGNUM *m,
BN_CTX *ctx); r=abs((a-b)%m))
int BN_mod_mul(BIGNUM *ret, BIGNUM *a, BIGNUM *b, const BIGNUM *m,
BN_CTX *ctx); r=abs((a*b)%m))
int BN_mod_sqr(BIGNUM *ret, BIGNUM *a, const BIGNUM *m, BN_CTX *ctx); r=abs((a*a)%m))
int BN_exp(BIGNUM *r, BIGNUM *a, BIGNUM *p, BN_CTX *ctx);r=pow(a,p)
int BN_mod_exp(BIGNUM *r, BIGNUM *a, const BIGNUM *p,
const BIGNUM *m, BN_CTX *ctx); r=pow(a,p)%M
int BN_gcd(BIGNUM *r, BIGNUM *a, BIGNUM *b, BN_CTX *ctx);r=a,b最大公约数
int BN_add_word(BIGNUM *a, BN_ULONG w);
int BN_sub_word(BIGNUM *a, BN_ULONG w);
int BN_mul_word(BIGNUM *a, BN_ULONG w);
BN_ULONG BN_div_word(BIGNUM *a, BN_ULONG w);
BN_ULONG BN_mod_word(const BIGNUM *a, BN_ULONG w);
BIGNUM *BN_mod_inverse(BIGNUM *r, BIGNUM *a, const BIGNUM *n,
BN_CTX *ctx);模逆,((a*r)%n==1).
6.比较函数
int BN_cmp(BIGNUM *a, BIGNUM *b); -1 if a < b, 0 if a == b and 1 if a > b.
int BN_ucmp(BIGNUM *a, BIGNUM *b); 比较a,b觉得值,返回值和上同。
int BN_is_zero(BIGNUM *a);
int BN_is_one(BIGNUM *a);
int BN_is_word(BIGNUM *a, BN_ULONG w);
int BN_is_odd(BIGNUM *a); 上面四个返回1,假如条件成立,否则将返回0
7.设置函数
int BN_zero(BIGNUM *a); 设置a为0
int BN_one(BIGNUM *a); 设置a为1
const BIGNUM *BN_value_one(void); 返回一个为1的大数
int BN_set_word(BIGNUM *a, unsigned long w); 设置a为w
unsigned long BN_get_word(BIGNUM *a); 假如a能表示为long型,那么返回一个long型数
8.随机数函数
int BN_rand(BIGNUM *rnd, int bits, int top, int bottom);
产生一个加密用的强bits的伪随机数,
若top=-1,最高位为0,top=0,最高位为1,top=1,最高位和次高位为1,bottom为真,随机数为偶数
int BN_pseudo_rand(BIGNUM *rnd, int bits, int top, int bottom);
产生一个伪随机数,应用于某些目的。
int BN_rand_range(BIGNUM *rnd, BIGNUM *range); 产生的0<rnd<range
int BN_pseudo_rand_range(BIGNUM *rnd, BIGNUM *range); 同上面道理
9.产生素数函数
BIGNUM *BN_generate_prime(BIGNUM *ret, int bits,int safe, BIGNUM *add,
BIGNUM *rem, void (*callback)(int, int, void *), void *cb_arg);
产生一个bits位的素数,后面几个参数都可以为NULL
int BN_is_prime(const BIGNUM *p, int nchecks,
void (*callback)(int, int, void *), BN_CTX *ctx, void *cb_arg);
判断是否为素数,返回0表示成功,1表示错误概率小于0。25,-1表示错误
10.位数函数
int BN_set_bit(BIGNUM *a, int n); 将a中的第n位设置为1,假如a小于n位将扩展
int BN_clear_bit(BIGNUM *a, int n); 将a中的第n为设置为0,假如a小于n位将出错
int BN_is_bit_set(const BIGNUM *a, int n);测试是否已经设置,1表示已设置
int BN_mask_bits(BIGNUM *a, int n); 将a截断至n位,假如a小于n位将出错
int BN_lshift(BIGNUM *r, const BIGNUM *a, int n); a左移n位,结果存于r
int BN_lshift1(BIGNUM *r, BIGNUM *a); a左移1位,结果存于r
int BN_rshift(BIGNUM *r, BIGNUM *a, int n); a右移n位,结果存于r
int BN_rshift1(BIGNUM *r, BIGNUM *a); a左移1位,结果存于r
11.与字符串的转换函数
int BN_bn2bin(const BIGNUM *a, unsigned char *to);将abs(a)转化为字符串存入to,to的空间必须大于BN_num_bytes(a)
BIGNUM *BN_bin2bn(const unsigned char *s, int len, BIGNUM *ret);将s中的len位的正整数转化为大数
char *BN_bn2hex(const BIGNUM *a);转化为16进制字符串
char *BN_bn2dec(const BIGNUM *a);转化为10进制字符串
int BN_hex2bn(BIGNUM **a, const char *str);同上理
int BN_dec2bn(BIGNUM **a, const char *str);同上理
int BN_print(BIO *fp, const BIGNUM *a);将大数16进制形式写入内存中
int BN_print_fp(FILE *fp, const BIGNUM *a); 将大数16进制形式写入文件
int BN_bn2mpi(const BIGNUM *a, unsigned char *to);
BIGNUM *BN_mpi2bn(unsigned char *s, int len, BIGNUM *ret);
12.其他函数
下面函数可以进行更有效率的模乘和模除,假如在重复在同一模下重复进行模乘和模除计算,计算r=(a*b)%m 利用了recp=1/m
BN_RECP_CTX *BN_RECP_CTX_new(void);
void BN_RECP_CTX_init(BN_RECP_CTX *recp);
void BN_RECP_CTX_free(BN_RECP_CTX *recp);
int BN_RECP_CTX_set(BN_RECP_CTX *recp, const BIGNUM *m, BN_CTX *ctx);
int BN_mod_mul_reciprocal(BIGNUM *r, BIGNUM *a, BIGNUM *b,
BN_RECP_CTX *recp, BN_CTX *ctx);
下面函数采用蒙哥马利算法进行模幂计算,可以提高效率,他也主要应用于在同一模下进行多次幂运算
BN_MONT_CTX *BN_MONT_CTX_new(void);
void BN_MONT_CTX_init(BN_MONT_CTX *ctx);
void BN_MONT_CTX_free(BN_MONT_CTX *mont);
int BN_MONT_CTX_set(BN_MONT_CTX *mont, const BIGNUM *m, BN_CTX *ctx);
BN_MONT_CTX *BN_MONT_CTX_copy(BN_MONT_CTX *to, BN_MONT_CTX *from);
int BN_mod_mul_montgomery(BIGNUM *r, BIGNUM *a, BIGNUM *b,
BN_MONT_CTX *mont, BN_CTX *ctx);
int BN_from_montgomery(BIGNUM *r, BIGNUM *a, BN_MONT_CTX *mont,
BN_CTX *ctx);
int BN_to_montgomery(BIGNUM *r, BIGNUM *a, BN_MONT_CTX *mont,
BN_CTX *ctx);