《openssl 编程》之大数

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）? BN_rand/BN_pseudo_rand

生成一个随机的大数。

2） BN_rand_range/BN_pseudo_rand_range

生成随机数，但是给出了随机数的范围。

3） BN_dup

大数复制。

4)?? BN_generate_prime

生成素数。

?????? 5）? int BN_add_word(BIGNUM *a,BN_ULONG w)

给大数a加上w，如果成功，返回1。

示例：

#include <openssl/bn.h>

?

int???? main()

int????????????????? ret;

BIGNUM??????? *a;

BN_ULONG?? w;

a=BN_new();

BN_one(a);

w=2685550010;

ret=BN_add_word(a,w);

if(ret!=1)

??????? printf("a+=w err!n");

??????? BN_free(a);

??????? return -1;

}

BN_free(a);

return 0;

6)??? BIGNUM *BN_bin2bn(const unsigned char *s,int len,BIGNUM *ret)

将内存中的数据转换为大数，为内存地址，len为数据长度，ret为返回值。

int main()

??? BIGNUM *ret1,*ret2;

??? ret1=BN_new();

??? ret1=BN_bin2bn("242424ab",8,ret1);

??? ret2=BN_bin2bn("242424ab",NULL);

??? BN_free(ret1);

??? BN_free(ret2);

??? return 0;

注意：输入参数“242424ab”是asc码，对应的大数值为16进制的0x3234323432346162

7)? int BN_bn2bin(const BIGNUM *a,unsigned char *to)

将大数转换为内存形式。输入参数为大数a，to为输出缓冲区地址，缓冲区需要预先分配，返回值为缓冲区的长度。

int??? main()

?????? BIGNUM *ret1=NULL;

?????? char bin[50],*buf=NULL;

?????? int?????????? len;

?????? ret1=BN_bin2bn("242424ab",u5b8bu4f53; font-size:16px; text-indent:2em"> ?????? len=BN_bn2bin(ret1,bin);

?????? len=BN_num_bytes(ret1);

?????? buf=malloc(len);

?????? free(buf);

?????? BN_free(ret1);

?????? return 0;

本例的缓冲区分配有两种方法：静态分配和动态分配。动态分配时，先调用

BN_num_bytes函数获取大数对应的缓冲区的大小。

8)? char *BN_bn2dec(const BIGNUM *a)

将大数转换成整数字符串。返回值中存放整数字符串，它由内部分配空间，用户必须在外部用OPENSSL_free函数释放该空间。

#include <openssl/crypto.h>

??? BIGNUM *ret1=NULL;

??? char?? *p=NULL;

??? int??? len=0;

??? p=BN_bn2dec(ret1);

??? printf("%sn",p); /* 3617571600447332706 */

OPENSSL_free(p);

??? getchar();

??? 9） char *BN_bn2hex(const BIGNUM *a)

将大数转换为十六进制字符串。返回值为生成的十六进制字符串，外部需要用OPENSSL_free函数释放

??? p=BN_bn2hex(ret1);

??? OPENSSL_free(p);

输出的结果为：323432346162

10)? BN_cmp

比较两个大数。

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各个元素导出到内存中再写入密钥文件。

11.4???使用示例

?????? 1）示例1

?????? #include <string.h>

?????? #include <openssl/bio.h>

???????????????????????????

?????? int??? main()

?????? {

?????? ?????? ?????? BIGNUM *bn;

???????????????????? BIO??????? *b;

???????????????????? char a[20];

???????????????????? int?????????? ret;

???????????????????? bn=BN_new();

???????????????????? strcpy(a,"32");

???????????????????? ret=BN_hex2bn(&bn,a);

???????????????????? b=BIO_new(BIO_s_file());

????????????? ?????? ret=BIO_set_fp(b,stdout,BIO_NOCLOSE);

???????????????????? BIO_write(b,"aaa",3);

???????????????????? BN_print(b,bn);

???????????????????? 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];

???????????????????? a=BN_new();

???????????????????? strcpy(c,u5b8bu4f53; font-size:16px; text-indent:2em"> ???????????????????? ret=BN_hex2bn(&a,c);

???????????????????? b=BN_new();

???????????????????? strcpy(d,"100");

???????????????????? ret=BN_hex2bn(&b,d);

???????????????????? out=BIO_new(BIO_s_file());

???????????????????? ret=BIO_set_fp(out,u5b8bu4f53; font-size:16px; text-indent:2em"> ???????????????????? 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);

???????????????????? BN_free(a);

???????????????????? BN_free(b);

???????????????????? BN_free(add);

???????????????????? BIO_free(out);

????????????? }

?????? 3）? 示例3???????????

????????????? 减法运算

?????????????

???????????????????? BIO??????? *out;

???????????????????? sub=BN_new();

???????????????????? ret=BN_sub(sub,"bn 0x100 - 0x32 = 0x");

???????????????????? BN_free(sub);

?????? 4）示例4

????????????? 乘法运算

???????????????????? BN_CTX *ctx;

????????????????????

???????????????????? ctx=BN_CTX_new();

???????????????????? mul=BN_new();

???????????????????? ret=BN_mul(mul,b,ctx);

????????????? ?????? }

???????????????????? BN_free(mul);

???????????????????? BN_CTX_free(ctx);

?????? ?????? }

?????? 5）示例5

????????????? 除法运算

?????? ?????????????

?????? ?????? ?????? ctx=BN_CTX_new();

???????????????????? div=BN_new();

???????????????????? rem=BN_new();

???????????????????? ret=BN_div(div,rem,"bn 0x100 / 0x17 =0x");

???????????????????? BN_free(div);

???????????????????? BN_free(rem);

?????? 6）示例6

????????????? 平方运算

???????????????????? char c[20];

???????????????????? sqr=BN_new();

???????????????????? ret=BN_sqr(sqr,"bn 0x100 sqr? =0x");

???????????????????? BN_free(sqr);

????????????? }???????????

?????? 7）示例7

????????????? 次方运算

???????????????????? exp=BN_new();

???????????????????? ret=BN_exp(exp,"bn 0x100 exp 0x3? =0x");

???????????????????? BN_free(exp);

????????????? }