Miracle密码算法开源库（八）分析 :mrcrt.c

Miracle密码算法开源库（八）分析 :mrcrt.c

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

1、mrcrt.c结构

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

2、源代码 

void crt(_MIPD_ big_chinese *c,big *u,big x)
{ /* Chinese Remainder Thereom                  ** Calculate x given remainders u[i] mod M[i] */int i,j,k;
#ifdef MR_OS_THREADSmiracl *mr_mip=get_mip();
#endifif (c->NP<2 || mr_mip->ERNUM) return;MR_IN(74)copy(u[0],c->V[0]);for (k=0,i=1;i<c->NP;i++){ /* Knuth page 274 */subtract(_MIPP_ u[i],c->V[0],c->V[i]);mad(_MIPP_ c->V[i],c->C[k],c->C[k],c->M[i],c->M[i],c->V[i]);k++;for (j=1;j<i;j++,k++){subtract(_MIPP_ c->V[i],c->V[j],c->V[i]);mad(_MIPP_ c->V[i],c->C[k],c->C[k],c->M[i],c->M[i],c->V[i]);}if (size(c->V[i])<0) add(_MIPP_ c->V[i],c->M[i],c->V[i]);}zero(x);convert(_MIPP_ 1,mr_mip->w1);for (i=0;i<c->NP;i++){multiply(_MIPP_ mr_mip->w1,c->V[i],mr_mip->w2);add(_MIPP_ x,mr_mip->w2,x);         multiply(_MIPP_ mr_mip->w1,c->M[i],mr_mip->w1);}   MR_OUT
}

 crt()方法de主要作用就是计算中国人剩余定理（Chinese remainder theorem）方程组的解。

中国剩余定理又称孙子定理, 主要是为了解线同余方程组。

1. x ≡ a1 ( mod  m1 )
2. x ≡ a2 ( mod m2 )
3. x ≡ a3 ( mod m3 ) 
4.        .........
5. x ≡ an ( mod mn )

成立条件是m1,m2, ... ,mn 两两互质, 则对任意的整数：a1,a2, ... ,an，方程组S 有解 

并且可以构造出通解  x =  ( a1*t1*M1 + a2*t2*M2 + a3*t3*M3 +...+ an*tn*Mn ) +  KM 

在模M的意义下 x = ( a1*t1*M1 + a2*t2*M2 + a3*t3*M3 +...+ an*tn*Mn ) 

M = m1 * m2 * m3 * ... * mn ,

Mi = M / mi 

 t i  为   M i  模 m i  意义下的逆元, 即 ti * Mi ≡ 1  ( mod mi ) 。显然带入方程组中可验证正确性。

该方法的输入数据为big_chinese类型（包含多个大数字类型数据和一个int类型的结构体）的指针*c、大数字类型的指针*u和最后用于保存该线同余方程组解的x。该方法首先调用copy方法把u[0]复制给c->V[0]，然后再进行次数为c->NP的循环：调用subtract方法把u[i]减去c->V[0]赋值给c->V[i]，再调用mad方法使得（c->V[i]*c->C[k]+c->C[k]）/c->M[i]的商，之后把商赋值给c->V[i]，然后在j自增且小于i的前提下循环：调用subtract方法把c->V[i]减去c->V[j]赋值给c->V[i]，再调用mad方法使得（c->V[i]*c->C[k]+c->C[k]）/c->M[i]的商，之后把商赋值给c->V[i]。结束循环后调用zero方法把x清零，再调用 convert方法把mr_mip->w1转化为1的大数字形式。最后进行次数为c->NP的循环：调用multiply方法把mr_mip->w1*c->V[i]赋值给mr_mip->w2，再调用add方法把x加上mr_mip->w2，之后再调用multiply方法把mr_mip->w1*c->M[i]赋值给mr_mip->w2。

BOOL crt_init(_MIPD_ big_chinese *c,int r,big *moduli)
{ /* calculate CRT constants */int i,j,k;
#ifdef MR_OS_THREADSmiracl *mr_mip=get_mip();
#endifif (r<2 || mr_mip->ERNUM) return FALSE;for (i=0;i<r;i++) if (size(moduli[i])<2) return FALSE;MR_IN(73)c->M=(big *)mr_alloc(_MIPP_ r,sizeof(big));if (c->M==NULL) {mr_berror(_MIPP_ MR_ERR_OUT_OF_MEMORY);MR_OUTreturn FALSE;}c->C=(big *)mr_alloc(_MIPP_ r*(r-1)/2,sizeof(big));if (c->C==NULL){mr_free(c->M);mr_berror(_MIPP_ MR_ERR_OUT_OF_MEMORY);MR_OUTreturn FALSE;}c->V=(big *)mr_alloc(_MIPP_ r,sizeof(big));if (c->V==NULL){mr_free(c->M);mr_free(c->C);mr_berror(_MIPP_ MR_ERR_OUT_OF_MEMORY);MR_OUTreturn FALSE;}for (k=0,i=0;i<r;i++){ c->V[i]=mirvar(_MIPP_ 0);c->M[i]=mirvar(_MIPP_ 0);copy(moduli[i],c->M[i]);for (j=0;j<i;j++,k++){c->C[k]=mirvar(_MIPP_ 0);invmodp(_MIPP_ c->M[j],c->M[i],c->C[k]);}}c->NP=r;    MR_OUTreturn TRUE;
}

crt_init()方法的主要作用就是初始化一个长度为r的big_chinese 类型的指针*c。首先调用mr_alloc方法创建r个big数据类型长度的内存空间给c->M，如果c->M为空则报错，调用mr_free()方法清空c->M并退出。再调用mr_alloc方法创建r*(r-1)/2个big数据类型长度的内存空间给c->C，如果c->C为空则报错，调用mr_free()方法清空c->C并退出。接着用mr_alloc方法创建r个big数据类型长度的内存空间给c->V，如果c->V为空则报错，调用mr_free()方法清空c->V并退出。接着进行r次循环：调用mirvar方法把 c->V[i]和c->M[i]赋值为0的flash类型数据，然后在j自增且小于i的前提下循环：调用mirvar方法把 c->C[k]赋值为0的flash类型数据，再调用invmodp方法进行c->M[j] mod c->M[i]并且赋值给 c->C[k]的操作。最后把 c->NP赋值为r。如果成功地初始化*c则返回true，赋值返回false。

void crt_end(big_chinese *c)
{ /* clean up after CRT */int i,j,k;if (c->NP<2) return;for (k=0,i=0;i<c->NP;i++){mirkill(c->M[i]);for (j=0;j<i;j++)mirkill(c->C[k++]); mirkill(c->V[i]);}   mr_free(c->M);mr_free(c->V);mr_free(c->C);c->NP=0;
}

crt_end()方法的主要作用就是清空一个的big_chinese 类型的指针*c的内存空间。首先进行c->NP次循环：调用mirkill()方法释放c->M[i] 、c->V[i]的内存空间，再在j自增且小于i的前提下循环：调用mirkill()方法释放c->C[k++]。最后调用 mr_free方法释放c->M、c->V、c->C的内存空间。