Miracle密码算法开源库（九）分析 :mrebrick.c

Miracle密码算法开源库（九）分析 :mrebrick.c

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

1、mrebrick.c结构

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

  2、源代码 

BOOL ebrick_init(_MIPD_ ebrick *B,big x,big y,big a,big b,big n,int window,int nb)
{ /* Uses Montgomery arithmetic internally              ** (x,y) is the fixed base                            ** a,b and n are parameters and modulus of the curve  ** window is the window size in bits and              ** nb is the maximum number of bits in the multiplier */int i,j,k,t,bp,len,bptr,is;epoint **table;epoint *w;#ifdef MR_OS_THREADSmiracl *mr_mip=get_mip();
#endifif (nb<2 || window<1 || window>nb || mr_mip->ERNUM) return FALSE;t=MR_ROUNDUP(nb,window);if (t<2) return FALSE;MR_IN(115)#ifndef MR_ALWAYS_BINARYif (mr_mip->base != mr_mip->base2){mr_berror(_MIPP_ MR_ERR_NOT_SUPPORTED);MR_OUTreturn FALSE;}
#endifB->window=window;B->max=nb;table=(epoint **)mr_alloc(_MIPP_ (1<<window),sizeof(epoint *));if (table==NULL){mr_berror(_MIPP_ MR_ERR_OUT_OF_MEMORY);   MR_OUTreturn FALSE;}B->a=mirvar(_MIPP_ 0);B->b=mirvar(_MIPP_ 0);B->n=mirvar(_MIPP_ 0);copy(a,B->a);copy(b,B->b);copy(n,B->n);ecurve_init(_MIPP_ a,b,n,MR_BEST);w=epoint_init(_MIPPO_ );epoint_set(_MIPP_ x,y,0,w);table[0]=epoint_init(_MIPPO_ );table[1]=epoint_init(_MIPPO_ );epoint_copy(w,table[1]);for (j=0;j<t;j++)ecurve_double(_MIPP_ w);k=1;for (i=2;i<(1<<window);i++){table[i]=epoint_init(_MIPPO_ );if (i==(1<<k)){k++;epoint_norm(_MIPP_ w);epoint_copy(w,table[i]);for (j=0;j<t;j++)ecurve_double(_MIPP_ w);continue;}bp=1;for (j=0;j<k;j++){if (i&bp){is=1<<j;ecurve_add(_MIPP_ table[is],table[i]);}bp<<=1;}epoint_norm(_MIPP_ table[i]);}epoint_free(w);/* create the table */len=n->len;bptr=0;B->table=(mr_small *)mr_alloc(_MIPP_ 2*len*(1<<window),sizeof(mr_small));for (i=0;i<(1<<window);i++){for (j=0;j<len;j++){B->table[bptr++]=table[i]->X->w[j];}for (j=0;j<len;j++){B->table[bptr++]=table[i]->Y->w[j];}epoint_free(table[i]);}mr_free(table);  MR_OUTreturn TRUE;
}void ebrick_end(ebrick *B)
{mirkill(B->n);mirkill(B->b);mirkill(B->a);mr_free(B->table);  
}

ebrick_init()方法的主要作用就是将 GF（p） 椭圆曲线乘法与预计算的 Comb 方法实例初始化。。内部内存被分配为 20000个椭圆曲线点，这些大数字将被预先计算和存储。*B是要被初始化的ebrick结构体指针，其他的输入数据都是为了完善*b的各种属性。该方法在函数内部使用蒙哥马利算法来初始化*B。输入数据a、b、n确定了一个曲线函数y2 =（x3 + ax + b） mod n，x、y组合成一个该曲线上的二维坐标点(x,y) ，window确定了以位和为单位的窗口大小，对于更大的输入数据windows需要更多的空间来存储数据，输入数据nb限定了指数中要使用的最大位数。

void ebrick_init(ebrick *B,const mr_small* rom,big a,big b,big n,int window,int nb)
{B->table=rom;B->a=a; /* just pass a pointer */B->b=b;B->n=n;B->window=window;  /* 2^4=16  stored values */B->max=nb;
}

ebrick_init()方法还重载有另一种形式实现，该方法只是粗暴地将*B所需地各种属性用输入数据替代，而不是使用蒙哥马利算法来初始化*B。

void ebrick_end(ebrick *B)
{mirkill(B->n);mirkill(B->b);mirkill(B->a);mr_free(B->table);  
}

brick_end()方法的主要作用就是释放brick结构体指针*B所占用的内存空间。首先调用mirkill()方法将通过将B->n、B->b、B->a这几个大数字归零并释放其内存，可以安全地杀死这个大数字。再调用mr_free()方法释放由calloc()方法动态分配给B->table的内存空间。

void ebrick_init(ebrick *B,const mr_small* rom,big a,big b,big n,int window,int nb)
{B->table=rom;B->a=a; /* just pass a pointer */B->b=b;B->n=n;B->window=window;  /* 2^4=16  stored values */B->max=nb;
}#endifint mul_brick(_MIPD_ ebrick *B,big e,big x,big y)
{int i,j,t,d,len,maxsize,promptr;epoint *w,*z;#ifdef MR_STATICchar mem[MR_ECP_RESERVE(2)];
#elsechar *mem;
#endif
#ifdef MR_OS_THREADSmiracl *mr_mip=get_mip();
#endifif (size(e)<0) mr_berror(_MIPP_ MR_ERR_NEG_POWER);t=MR_ROUNDUP(B->max,B->window);MR_IN(116)#ifndef MR_ALWAYS_BINARYif (mr_mip->base != mr_mip->base2){mr_berror(_MIPP_ MR_ERR_NOT_SUPPORTED);MR_OUTreturn 0;}
#endifif (logb2(_MIPP_ e) > B->max){mr_berror(_MIPP_ MR_ERR_EXP_TOO_BIG);MR_OUTreturn 0;}ecurve_init(_MIPP_ B->a,B->b,B->n,MR_BEST);
#ifdef MR_STATICmemset(mem,0,MR_ECP_RESERVE(2));
#elsemem=(char *)ecp_memalloc(_MIPP_ 2);
#endifw=epoint_init_mem(_MIPP_ mem,0);z=epoint_init_mem(_MIPP_ mem,1);len=B->n->len;maxsize=2*(1<<B->window)*len;j=recode(_MIPP_ e,t,B->window,t-1);if (j>0){promptr=2*j*len;init_point_from_rom(w,len,B->table,maxsize,&promptr);}for (i=t-2;i>=0;i--){j=recode(_MIPP_ e,t,B->window,i);ecurve_double(_MIPP_ w);if (j>0){promptr=2*j*len;init_point_from_rom(z,len,B->table,maxsize,&promptr);ecurve_add(_MIPP_ z,w);}}d=epoint_get(_MIPP_ w,x,y);
#ifndef MR_STATICecp_memkill(_MIPP_ mem,2);
#elsememset(mem,0,MR_ECP_RESERVE(2));
#endifMR_OUTreturn d;
}

mul_brick()方法地主要作用就是使用存储在 ebrick 结构中的预计算值进行 GF（p） 椭圆曲线乘法。首先调用 ecurve_init方法初始化当前活动 GF （p） 椭圆曲线的内部参数：y2 =（x3 + Ax + B） mod p,再调用ecp_memalloc方法在椭圆形曲线点保留2个空间，然后调用epoint_init_mem方法从预分配字形字段阵列 mem 中初始化这两个椭圆曲线点的内存。之后调用init_point_from_rom方法从 ROM 内存中初始化椭圆形曲线点w。接着循环调用recode方法为Comb方法重编码指数，然后调用ecurve_double方法把在活动曲线上的w乘以2倍，再循环调用init_point_from_rom方法从 ROM 内存中初始化椭圆形曲线点z，接着调用ecurve_add方法把在活动曲线上的w、z相加给w。循环结束以后调用epoint_get方法获得w上的坐标(x,y)，最后调用ecp_memkill方法删除并设置为零以前由 ecp_memalloc分配的2个内存空间椭圆形曲线点。