Miracle密码算法开源库（六）分析 :mrbits.c

Miracle密码算法开源库（六）分析 :mrbits.c

2021SC@SDUSC 山东大学软件学院软件工程应用与实践

1、mrbits.c结构

mrbits.c的总体结构如下，，主要实现了logb2()、expb2()、bigbits()、sftbit()几个在miracl开源库中比较重要的函数，这一次的博客就是读一下这函数的功能。

 2、源代码 

int logb2(_MIPD_ big x)
{ /* returns number of bits in x */int xl,lg2;mr_small top;
#ifdef MR_OS_THREADSmiracl *mr_mip=get_mip();
#endifif (mr_mip->ERNUM || size(x)==0) return 0;MR_IN(49)#ifndef MR_ALWAYS_BINARYif (mr_mip->base==mr_mip->base2){
#endifxl=(int)(x->len&MR_OBITS);lg2=mr_mip->lg2b*(xl-1);top=x->w[xl-1];while (top>=1){lg2++;top/=2;}#ifndef MR_ALWAYS_BINARY}else {copy(x,mr_mip->w0);insign(PLUS,mr_mip->w0);lg2=0;while (mr_mip->w0->len>1){
#ifdef MR_FP_ROUNDINGmr_sdiv(_MIPP_ mr_mip->w0,mr_mip->base2,mr_invert(mr_mip->base2),mr_mip->w0);
#elsemr_sdiv(_MIPP_ mr_mip->w0,mr_mip->base2,mr_mip->w0);
#endiflg2+=mr_mip->lg2b;}while (mr_mip->w0->w[0]>=1){lg2++;mr_mip->w0->w[0]/=2;}}
#endifMR_OUTreturn lg2;
}

logb2()方法的主要作用就是求一个大数字以2为底的对数或其近似解。当mr_mip->base等于mr_mip->base2也就是说这个大数字可以被2整除的时候，该函数会先获取这个大数字的长度xl，lg2就等于mr_mip->lg2b*(xl-1)，top为x->w[xl-1]，接着再循环中lg2每自加1，top就除以2，最后返回lg2。在另一种情况下只能近似求解，先调用copy方法把x复制给mr_mip->w0，再把mr_mip->w0转化为绝对值，再把lg2赋值为0，之后在w0的len属性大于1的限制条件下循环，每调用一次mr_sdiv方法让mr_mip->w0->len除以mr_mip->base2，lg2都加一次mr_mip->lg2b。然后在w0的w[0]属性大于等于1的限制条件下循环，lg2每自加2，w[0]都除以2。最后返回lg2。

void sftbit(_MIPD_ big x,int n,big z)
{ /* shift x by n bits */int m;mr_small sm;
#ifdef MR_OS_THREADSmiracl *mr_mip=get_mip();
#endifif (mr_mip->ERNUM) return;copy(x,z);if (n==0) return;MR_IN(47)m=mr_abs(n);sm=mr_shiftbits((mr_small)1,m%mr_mip->lg2b);if (n>0){ /* shift left */#ifndef MR_ALWAYS_BINARYif (mr_mip->base==mr_mip->base2){
#endifmr_shift(_MIPP_ z,n/mr_mip->lg2b,z);mr_pmul(_MIPP_ z,sm,z);
#ifndef MR_ALWAYS_BINARY}else{expb2(_MIPP_ m,mr_mip->w1);multiply(_MIPP_ z,mr_mip->w1,z);}
#endif}else{ /* shift right */#ifndef MR_ALWAYS_BINARYif (mr_mip->base==mr_mip->base2){
#endifmr_shift(_MIPP_ z,n/mr_mip->lg2b,z);
#ifdef MR_FP_ROUNDINGmr_sdiv(_MIPP_ z,sm,mr_invert(sm),z);
#elsemr_sdiv(_MIPP_ z,sm,z);
#endif#ifndef MR_ALWAYS_BINARY}else{expb2(_MIPP_ m,mr_mip->w1);divide(_MIPP_ z,mr_mip->w1,z);}
#endif}MR_OUT
}

sftbit()方法的主要作用就是把一个大数字x移动n位（n有正负，代表左右）获得大数字z。首先调用copy方法把x复制给在，再获得整数n的绝对值m，然后获得sm：把1左移m%mr_mip->lg2b的位数（也就是2的m%mr_mip->lg2b次方）。当n大于0且x可被2整除的情况下，先调用mr_shift方法把z乘以2的n/mr_mip->lg2b次方，再调用mr_pmul方法让z乘以sm。如果x不能被2整除，先调用expb2方法获得2的m次方赋值给mr_mip->w1，再调用 multiply方法将z乘以 mr_mip->w1。当n小于0且x可被2整除的情况下，先调用mr_shift方法把z乘以2的n/mr_mip->lg2b次方，再调用mr_sdivl方法让z除以sm。如果x不能被2整除，先调用expb2方法获得2的m次方赋值给mr_mip->w1，再调用divide方法将z除以 mr_mip->w1。

void expb2(_MIPD_ int n,big x)
{ /* sets x=2^n */int r,p;
#ifndef MR_ALWAYS_BINARYint i;
#endif
#ifdef MR_OS_THREADSmiracl *mr_mip=get_mip();
#endifif (mr_mip->ERNUM) return;convert(_MIPP_ 1,x);if (n==0) return;MR_IN(149)if (n<0){mr_berror(_MIPP_ MR_ERR_NEG_POWER);MR_OUTreturn;}r=n/mr_mip->lg2b;p=n%mr_mip->lg2b;#ifndef MR_ALWAYS_BINARYif (mr_mip->base==mr_mip->base2){
#endifmr_shift(_MIPP_ x,r,x);x->w[x->len-1]=mr_shiftbits(x->w[x->len-1],p);
#ifndef MR_ALWAYS_BINARY}else{for (i=1;i<=r;i++)mr_pmul(_MIPP_ x,mr_mip->base2,x);mr_pmul(_MIPP_ x,mr_shiftbits((mr_small)1,p),x);}
#endifMR_OUT
}

expb2()方法的主要作用就是获得2的n次方并且转化为大数字赋值给x。首先调用convert方法把x转换为1的大数字形式，再看n是否小于0。是的话异常报错退出。否则的话获得n除以lg2b的商r和余数p。如果mr_mip->base等于mr_mip->base2的话，先将x乘以2的r次方，再把w[x->len-1]左移p位。不等于的话在i小于等于r的限制条件下循环调用mr_pmul把x乘以mr_mip->base2，最后把x乘以2的p次方。

void bigbits(_MIPD_ int n,big x)
{ /* sets x as random < 2^n */mr_small r;mr_lentype wlen;
#ifdef MR_FPmr_small dres;
#endif
#ifdef MR_OS_THREADSmiracl *mr_mip=get_mip();
#endifzero(x);if (mr_mip->ERNUM || n<=0) return;MR_IN(150)expb2(_MIPP_ n,mr_mip->w1);wlen=mr_mip->w1->len;do{r=brand(_MIPPO_ );if (mr_mip->base==0) x->w[x->len++]=r;else                 x->w[x->len++]=MR_REMAIN(r,mr_mip->base);} while (x->len<wlen);
#ifndef MR_ALWAYS_BINARYif (mr_mip->base==mr_mip->base2){
#endifx->w[wlen-1]=MR_REMAIN(x->w[wlen-1],mr_mip->w1->w[wlen-1]);mr_lzero(x);#ifndef MR_ALWAYS_BINARY}else{divide(_MIPP_ x,mr_mip->w1,mr_mip->w1);}
#endifMR_OUT
}

bigbits()方法的主要作用就是生成一个小于2^n 的随机大数字。首先等于zero将x清零，再调用expb2方法获得2的n次方wl，然后获取w1的len属性wlen。之后在x的len属性小于wlen的限制条件下循环调用brand方法获取一个随机整数人，使得w[x->len++]等于r或者r除以mr_mip->base的余数。最后看x是否可以被2整除，是的话x->w[wlen-1]就等于x->w[wlen-1]除以mr_mip->w1->w[wlen-1]的余数，在调用mr_lzero方法清除x的前置零；不是的话调用divide方法将x除以,mr_mip->w1。最后的x就是生成的随机数。