mrecn2.c

比较新的功能强大的rsa算法源代码,方便使用.

	zzn2_from_zzn(mr_mip->one,&one);

    for (i=0;i<m;i++)
	{
		if (p[i].marker==MR_EPOINT_NORMALIZED) w[i]=one;
        else w[i]=p[i].z;
	}

    if (!zzn2_multi_inverse(_MIPP_ m,w,work)) 
    {
       MR_OUT
       return FALSE;
    }

    for (i=0;i<m;i++)
    {
        p[i].marker=MR_EPOINT_NORMALIZED;
        zzn2_mul(_MIPP_ &(p[i].x),&work[i],&(p[i].x));    
        zzn2_mul(_MIPP_ &(p[i].y),&work[i],&(p[i].y));  
		zzn2_from_zzn(mr_mip->one,&(p[i].z));
    }    
    MR_OUT

    return TRUE;   
}

BOOL ecn2_add(_MIPD_ ecn2 *Q,ecn2 *P)
{ /* P+=Q */
    BOOL Doubling=FALSE;
    BOOL twist;
    zzn2 t2,t3,t4;
 
#ifdef MR_OS_THREADS
    miracl *mr_mip=get_mip();
#endif
 
    t2.a = mr_mip->w8; 
    t2.b = mr_mip->w9; 
    t3.a = mr_mip->w10; 
    t3.b = mr_mip->w11;
    t4.a = mr_mip->w12;
    t4.b = mr_mip->w13;

    twist=mr_mip->TWIST;
    if (mr_mip->ERNUM) return FALSE;

    if (P->marker==MR_EPOINT_INFINITY)
    {
        ecn2_copy(Q,P);
        return Doubling;
    }
    if (Q->marker==MR_EPOINT_INFINITY) return Doubling;

    if (Q==P)
    {
        Doubling=TRUE;
        if (P->marker==MR_EPOINT_INFINITY) 
        { /* 2 times infinity == infinity ! */
            return Doubling;
        }
    }

    MR_IN(205)

    if (!Doubling)
    { /* Addition */
        zzn2_add(_MIPP_ &(Q->x),&(Q->y),&t2);
        zzn2_add(_MIPP_ &(P->x),&(P->y),&t4);
        zzn2_mul(_MIPP_ &t4,&t2,&t4);          /* I = t4 = (x1+y1)(x2+y2) */
        if (Q->marker!=MR_EPOINT_NORMALIZED)
        {
            if (P->marker==MR_EPOINT_NORMALIZED)
                zzn2_copy(&(Q->z),&(P->z));
            else
                zzn2_mul(_MIPP_ &(Q->z),&(P->z),&(P->z));  /* Z = z1*z2 */
        }  
        else
        {
            if (P->marker==MR_EPOINT_NORMALIZED)
                zzn2_from_zzn(mr_mip->one,&(P->z));
        }
        zzn2_sqr(_MIPP_ &(P->z),&t2);    /* P->z = z1.z2 */
        if (mr_abs(mr_mip->Bsize)==MR_TOOBIG)
            zzn2_smul(_MIPP_ &t2,mr_mip->B,&t2);
        else
            zzn2_imul(_MIPP_ &t2,mr_mip->Bsize,&t2);
        if (twist) zzn2_txx(_MIPP_ &t2);              /* B = t2 = d*A^2 */
        zzn2_mul(_MIPP_ &(P->x),&(Q->x),&(P->x));     /* X = x1*x2 */
        zzn2_mul(_MIPP_ &(P->y),&(Q->y),&(P->y));     /* Y = y1*y2 */
        zzn2_sub(_MIPP_ &t4,&(P->x),&t4);
        zzn2_sub(_MIPP_ &t4,&(P->y),&t4);             /* I = (x1+y1)(x2+y2)-X-Y */ 
        zzn2_mul(_MIPP_ &(P->x),&(P->y),&t3);         /* E = t3 = X*Y */
        if (mr_abs(mr_mip->Asize)==MR_TOOBIG)
            zzn2_smul(_MIPP_ &(P->y),mr_mip->A,&(P->y));
        else
            zzn2_imul(_MIPP_ &(P->y),mr_mip->Asize,&(P->y));
        if (twist) zzn2_txx(_MIPP_ &(P->y));         /* Y=aY */
        zzn2_sub(_MIPP_ &(P->x),&(P->y),&(P->x));    /* X=X-aY */
        zzn2_mul(_MIPP_ &(P->z),&(P->x),&(P->z));
        zzn2_mul(_MIPP_ &(P->z),&t4,&(P->z));
        zzn2_sub(_MIPP_ &t3,&t2,&(P->y));
        zzn2_mul(_MIPP_ &(P->y),&t4,&(P->y));
        zzn2_add(_MIPP_ &t3,&t2,&t4);
        zzn2_mul(_MIPP_ &(P->x),&t4,&(P->x));
    }
    else
    { /* doubling */
        zzn2_add(_MIPP_ &(P->x),&(P->y),&t2);
        zzn2_sqr(_MIPP_ &t2,&t2);
        zzn2_sqr(_MIPP_ &(P->x),&(P->x));
        zzn2_sqr(_MIPP_ &(P->y),&(P->y));
        zzn2_sub(_MIPP_ &t2,&(P->x),&t2);
        zzn2_sub(_MIPP_ &t2,&(P->y),&t2);   /* E=(X+Y)^2-X^2-Y^2 */

        if (P->marker!=MR_EPOINT_NORMALIZED)
            zzn2_sqr(_MIPP_ &(P->z),&(P->z));
        else
            zzn2_from_zzn(mr_mip->one,&(P->z));

        zzn2_add(_MIPP_ &(P->z),&(P->z),&(P->z));
        if (mr_abs(mr_mip->Bsize)==MR_TOOBIG)
            zzn2_smul(_MIPP_ &(P->z),mr_mip->B,&(P->z));
        else
            zzn2_imul(_MIPP_ &(P->z),mr_mip->Bsize,&(P->z));
        if (twist) zzn2_txx(_MIPP_ &(P->z));
        if (mr_abs(mr_mip->Asize)==MR_TOOBIG)
            zzn2_smul(_MIPP_ &(P->y),mr_mip->A,&(P->y));
        else
            zzn2_imul(_MIPP_ &(P->y),mr_mip->Asize,&(P->y));
        if (twist) zzn2_txx(_MIPP_ &(P->y));
        zzn2_add(_MIPP_ &(P->x),&(P->y),&t3);
        zzn2_sub(_MIPP_ &(P->x),&(P->y),&t4);
        zzn2_mul(_MIPP_ &t3,&t4,&(P->x));

        zzn2_sub(_MIPP_ &t3,&(P->z),&t3);
        zzn2_mul(_MIPP_ &t2,&t3,&(P->y));
        zzn2_mul(_MIPP_ &t2,&t4,&(P->z));
    }

    if (zzn2_iszero(&(P->z)))
    {
        zzn2_from_zzn(mr_mip->one,&(P->x));
        zzn2_zero(&(P->y));
        P->marker=MR_EPOINT_INFINITY;
    }
    else P->marker=MR_EPOINT_GENERAL;
   
    MR_OUT
    return Doubling;
}

void ecn2_negate(_MIPD_ ecn2 *u,ecn2 *w)
{
#ifdef MR_OS_THREADS
    miracl *mr_mip=get_mip();
#endif

    ecn2_copy(u,w);
    if (w->marker!=MR_EPOINT_INFINITY)
        zzn2_negate(_MIPP_ &(w->x),&(w->x));
}


BOOL ecn2_sub(_MIPD_ ecn2 *Q,ecn2 *P)
{
    BOOL Doubling;
#ifdef MR_OS_THREADS
    miracl *mr_mip=get_mip();
#endif
    zzn2 lam;

    lam.a = mr_mip->w14;
    lam.b = mr_mip->w15;

    ecn2_negate(_MIPP_ Q,Q);

    Doubling=ecn2_add(_MIPP_ Q,P);

    ecn2_negate(_MIPP_ Q,Q);

    return Doubling;
}

/*

BOOL ecn2_add_sub(_MIPD_ ecn2 *P,ecn2 *Q,ecn2 *PP,ecn2 *PM)
{  PP=P+Q, PM=P-Q. Assumes P and Q are both normalized, and P!=Q 
 #ifdef MR_OS_THREADS
    miracl *mr_mip=get_mip();
#endif
    zzn2 t1,t2,lam;

    if (mr_mip->ERNUM) return FALSE;

    PP->marker=MR_EPOINT_NORMALIZED;
    PM->marker=MR_EPOINT_NORMALIZED;

    return TRUE;
}

*/

/* Precomputation of  3P, 5P, 7P etc. into PT. Assume PT[0] contains P */

#define MR_PRE_2 (6+2*MR_MAX_M_T_S)

static void ecn2_pre(_MIPD_ int sz,BOOL norm,ecn2 *PT)
{
    int i,j;
    ecn2 P2;
#ifdef MR_OS_THREADS
    miracl *mr_mip=get_mip();
#endif

#ifndef MR_STATIC
	zzn2 *work=(zzn2 *)mr_alloc(_MIPP_ sz,sizeof(zzn2));
    char *mem = memalloc(_MIPP_ 6+2*sz);
#else
	zzn2 work[MR_MAX_M_T_S];
    char mem[MR_BIG_RESERVE(MR_PRE_2)];
    memset(mem, 0, MR_BIG_RESERVE(MR_PRE_2));
#endif
    j=0;
    P2.x.a=mirvar_mem(_MIPP_ mem, j++);
    P2.x.b=mirvar_mem(_MIPP_ mem, j++);
    P2.y.a=mirvar_mem(_MIPP_ mem, j++);
    P2.y.b=mirvar_mem(_MIPP_ mem, j++);
    P2.z.a=mirvar_mem(_MIPP_ mem, j++);
    P2.z.b=mirvar_mem(_MIPP_ mem, j++);

    for (i=0;i<sz;i++)
    {
        work[i].a= mirvar_mem(_MIPP_ mem, j++);
        work[i].b= mirvar_mem(_MIPP_ mem, j++);
    }

    ecn2_copy(&PT[0],&P2);
    ecn2_add(_MIPP_ &P2,&P2);
    for (i=1;i<sz;i++)
    {
        ecn2_copy(&PT[i-1],&PT[i]);
        ecn2_add(_MIPP_ &P2,&PT[i]);
		
    }
	if (norm) ecn2_multi_norm(_MIPP_ sz,work,PT);

#ifndef MR_STATIC
    memkill(_MIPP_ mem, 6+2*sz);
	mr_free(work);
#else
    memset(mem, 0, MR_BIG_RESERVE(MR_PRE_2));
#endif
}

#ifndef MR_DOUBLE_BIG
#define MR_MUL_RESERVE (1+6*MR_ECC_STORE_N2)
#else
#define MR_MUL_RESERVE (2+6*MR_ECC_STORE_N2)
#endif

int ecn2_mul(_MIPD_ big k,ecn2 *P)
{
    int i,j,nb,n,nbs,nzs,nadds;
    big h;
    ecn2 T[MR_ECC_STORE_N2];
#ifdef MR_OS_THREADS
    miracl *mr_mip=get_mip();
#endif

#ifndef MR_STATIC
    char *mem = memalloc(_MIPP_ MR_MUL_RESERVE);
#else
    char mem[MR_BIG_RESERVE(MR_MUL_RESERVE)];
    memset(mem, 0, MR_BIG_RESERVE(MR_MUL_RESERVE));
#endif

    j=0;
#ifndef MR_DOUBLE_BIG
    h=mirvar_mem(_MIPP_ mem, j++);
#else
    h=mirvar_mem(_MIPP_ mem, j); j+=2;
#endif
    for (i=0;i<MR_ECC_STORE_N2;i++)
    {
        T[i].x.a= mirvar_mem(_MIPP_ mem, j++);
        T[i].x.b= mirvar_mem(_MIPP_ mem, j++);
        T[i].y.a= mirvar_mem(_MIPP_ mem, j++);
        T[i].y.b= mirvar_mem(_MIPP_ mem, j++);
        T[i].z.a= mirvar_mem(_MIPP_ mem, j++);
        T[i].z.b= mirvar_mem(_MIPP_ mem, j++);
    }

    MR_IN(207)

    ecn2_norm(_MIPP_ P);

	nadds=0;
    premult(_MIPP_ k,3,h);
    ecn2_copy(P,&T[0]);
    ecn2_pre(_MIPP_ MR_ECC_STORE_N2,FALSE,T);
    nb=logb2(_MIPP_ h);

    ecn2_zero(P);

    for (i=nb-1;i>=1;)
    {
        if (mr_mip->user!=NULL) (*mr_mip->user)();
        n=mr_naf_window(_MIPP_ k,h,i,&nbs,&nzs,MR_ECC_STORE_N2);
 
        for (j=0;j<nbs;j++) ecn2_add(_MIPP_ P,P);
       
        if (n>0) {nadds++; ecn2_add(_MIPP_ &T[n/2],P);}
        if (n<0) {nadds++; ecn2_sub(_MIPP_ &T[(-n)/2],P);}
        i-=nbs;
        if (nzs)
        {
            for (j=0;j<nzs;j++) ecn2_add(_MIPP_ P,P);
            i-=nzs;
        }
    }

    ecn2_norm(_MIPP_ P);
    MR_OUT

#ifndef MR_STATIC
    memkill(_MIPP_ mem, MR_MUL_RESERVE);
#else
    memset(mem, 0, MR_BIG_RESERVE(MR_MUL_RESERVE));
#endif
	return nadds;
}

/* Double addition, using Joint Sparse Form */
/* R=aP+bQ */

#define MR_MUL2_JSF_RESERVE 24

int ecn2_mul2_jsf(_MIPD_ big a,ecn2 *P,big b,ecn2 *Q,ecn2 *R)
{
    int e1,h1,e2,h2,bb,nadds;
    ecn2 P1,P2,PS,PD;
    big c,d,e,f;
#ifdef MR_OS_THREADS
    miracl *mr_mip=get_mip();
#endif

#ifndef MR_STATIC
    char *mem = memalloc(_MIPP_ MR_MUL2_JSF_RESERVE);
#else
    char mem[MR_BIG_RESERVE(MR_MUL2_JSF_RESERVE)];
    memset(mem, 0, MR_BIG_RESERVE(MR_MUL2_JSF_RESERVE));
#endif

    c = mirvar_mem(_MIPP_ mem, 0);
    d = mirvar_mem(_MIPP_ mem, 1);
    e = mirvar_mem(_MIPP_ mem, 2);
    f = mirvar_mem(_MIPP_ mem, 3);
    P1.x.a= mirvar_mem(_MIPP_ mem, 4);
    P1.x.b= mirvar_mem(_MIPP_ mem, 5);
    P1.y.a= mirvar_mem(_MIPP_ mem, 6);
    P1.y.b= mirvar_mem(_MIPP_ mem, 7);
    P2.x.a= mirvar_mem(_MIPP_ mem, 8);
    P2.x.b= mirvar_mem(_MIPP_ mem, 9);
    P2.y.a= mirvar_mem(_MIPP_ mem, 10);
    P2.y.b= mirvar_mem(_MIPP_ mem, 11);
    PS.x.a= mirvar_mem(_MIPP_ mem, 12);
    PS.x.b= mirvar_mem(_MIPP_ mem, 13);
    PS.y.a= mirvar_mem(_MIPP_ mem, 14);
    PS.y.b= mirvar_mem(_MIPP_ mem, 15);
    PS.z.a= mirvar_mem(_MIPP_ mem, 16);
    PS.z.b= mirvar_mem(_MIPP_ mem, 17);
    PD.x.a= mirvar_mem(_MIPP_ mem, 18);
    PD.x.b= mirvar_mem(_MIPP_ mem, 19);
    PD.y.a= mirvar_mem(_MIPP_ mem, 20);
    PD.y.b= mirvar_mem(_MIPP_ mem, 21);
    PD.z.a= mirvar_mem(_MIPP_ mem, 22);
    PD.z.b= mirvar_mem(_MIPP_ mem, 23);

    MR_IN(206)

    ecn2_norm(_MIPP_ Q); 
    ecn2_copy(Q,&P2); 

    copy(b,d);
    if (size(d)<0) 
    {
        negify(d,d);
        ecn2_negate(_MIPP_ &P2,&P2);
    }

    ecn2_norm(_MIPP_ P); 
    ecn2_copy(P,&P1); 

    copy(a,c);
    if (size(c)<0) 
    {
        negify(c,c);
        ecn2_negate(_MIPP_ &P1,&P1);
    }

    mr_jsf(_MIPP_ d,c,e,d,f,c);   /* calculate joint sparse form */
 
    if (compare(e,f)>0) bb=logb2(_MIPP_ e)-1;
    else                bb=logb2(_MIPP_ f)-1;

    /*ecn2_add_sub(_MIPP_ &P1,&P2,&PS,&PD);*/

    ecn2_copy(&P1,&PS);
    ecn2_copy(&P1,&PD);
    ecn2_add(_MIPP_ &P2,&PS);
    ecn2_sub(_MIPP_ &P2,&PD);

    ecn2_zero(R);
	nadds=0;
   
    while (bb>=0) 
    { /* add/subtract method */
        if (mr_mip->user!=NULL) (*mr_mip->user)();
        ecn2_add(_MIPP_ R,R);
        e1=h1=e2=h2=0;

        if (mr_testbit(_MIPP_ d,bb)) e2=1;
        if (mr_testbit(_MIPP_ e,bb)) h2=1;
        if (mr_testbit(_MIPP_ c,bb)) e1=1;
        if (mr_testbit(_MIPP_ f,bb)) h1=1;

        if (e1!=h1)
        {
            if (e2==h2)
            {
                if (h1==1) {ecn2_add(_MIPP_ &P1,R); nadds++;}
                else       {ecn2_sub(_MIPP_ &P1,R); nadds++;}
            }
            else
            {
                if (h1==1)
                {
                    if (h2==1) {ecn2_add(_MIPP_ &PS,R); nadds++;}
                    else       {ecn2_add(_MIPP_ &PD,R); nadds++;}
                }
                else
                {
                    if (h2==1) {ecn2_sub(_MIPP_ &PD,R); nadds++;}
                    else       {ecn2_sub(_MIPP_ &PS,R); nadds++;}
                }
            }
        }
        else if (e2!=h2)
        {
            if (h2==1) {ecn2_add(_MIPP_ &P2,R); nadds++;}
            else       {ecn2_sub(_MIPP_ &P2,R); nadds++;}
        }
        bb-=1;
    }
    ecn2_norm(_MIPP_ R); 

    MR_OUT
#ifndef MR_STATIC
    memkill(_MIPP_ mem, MR_MUL2_JSF_RESERVE);
#else
    memset(mem, 0, MR_BIG_RESERVE(MR_MUL2_JSF_RESERVE));
#endif
	return nadds;

}

/* General purpose multi-exponentiation engine, using inter-leaving algorithm. Calculate aP+bQ+cR+dS...
   Inputs are divided into two groups of sizes wa<4 and wb<4. For the first group if the points are fixed the 
   first precomputed Table Ta[] may be taken from ROM. For the second group if the points are variable Tb[j] will
   have to computed online. Each group has its own precomputed store size, sza (=8?) and szb (=20?) respectively. 
   The values a,b,c.. are provided in ma[] and mb[], and 3.a,3.b,3.c (as required by the NAF) are provided in 
   ma3[] and mb3[]. If only one group is required, set wb=0 and pass NULL pointers.
   */

int ecn2_muln_engine(_MIPD_ int wa,int sza,int wb,int szb,big *ma,big *ma3,big *mb,big *mb3,ecn2 *Ta,ecn2 *Tb,ecn2 *R)
{ /* general purpose interleaving algorithm engine for multi-exp */
    int i,j,tba[4],pba[4],na[4],sa[4],tbb[4],pbb[4],nb[4],sb[4],nbits,nbs,nzs;
    int nadds;
#ifdef MR_OS_THREADS
    miracl *mr_mip=get_mip();
#endif

    ecn2_zero(R);

    nbits=0;
    for (i=0;i<wa;i++) {sa[i]=exsign(ma[i]); tba[i]=0; j=logb2(_MIPP_ ma3[i]); if (j>nbits) nbits=j; }
    for (i=0;i<wb;i++) {sb[i]=exsign(mb[i]); tbb[i]=0; j=logb2(_MIPP_ mb3[i]); if (j>nbits) nbits=j; }
    
    nadds=0;
    for (i=nbits-1;i>=1;i--)
    {
        if (mr_mip->user!=NULL) (*mr_mip->user)();
        if (R->marker!=MR_EPOINT_INFINITY) ecn2_add(_MIPP_ R,R);
        for (j=0;j<wa;j++)
        { /* deal with the first group */
            if (tba[j]==0)
            {
                na[j]=mr_naf_window(_MIPP_ ma[j],ma3[j],i,&nbs,&nzs,sza);
                tba[j]=nbs+nzs;
                pba[j]=nbs;