mrecn2.c

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

    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);
    PD.x.a= mirvar_mem(_MIPP_ mem, 16);
    PD.x.b= mirvar_mem(_MIPP_ mem, 17);
    PD.y.a= mirvar_mem(_MIPP_ mem, 18);
    PD.y.b= mirvar_mem(_MIPP_ mem, 19);

    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_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;
            }
            tba[j]--;  pba[j]--; 
            if (pba[j]==0)
            {
                if (sa[j]==PLUS)
                {
                    if (na[j]>0) {ecn2_add(_MIPP_ &Ta[j*sza+na[j]/2],R); nadds++;}
                    if (na[j]<0) {ecn2_sub(_MIPP_ &Ta[j*sza+(-na[j])/2],R); nadds++;}
                }
                else
                {
                    if (na[j]>0) {ecn2_sub(_MIPP_ &Ta[j*sza+na[j]/2],R); nadds++;}
                    if (na[j]<0) {ecn2_add(_MIPP_ &Ta[j*sza+(-na[j])/2],R); nadds++;}
                }
            }         
        }
        for (j=0;j<wb;j++)
        { /* deal with the second group */
            if (tbb[j]==0)
            {
                nb[j]=mr_naf_window(_MIPP_ mb[j],mb3[j],i,&nbs,&nzs,szb);
                tbb[j]=nbs+nzs;
                pbb[j]=nbs;
            }
            tbb[j]--;  pbb[j]--; 
            if (pbb[j]==0)
            {
                if (sb[j]==PLUS)
                {
                    if (nb[j]>0) {ecn2_add(_MIPP_ &Tb[j*szb+nb[j]/2],R);  nadds++;}
                    if (nb[j]<0) {ecn2_sub(_MIPP_ &Tb[j*szb+(-nb[j])/2],R);  nadds++;}
                }
                else
                {
                    if (nb[j]>0) {ecn2_sub(_MIPP_ &Tb[j*szb+nb[j]/2],R);  nadds++;}
                    if (nb[j]<0) {ecn2_add(_MIPP_ &Tb[j*szb+(-nb[j])/2],R);  nadds++;}
                }
            }         
        }
    }
    ecn2_norm(_MIPP_ R);  
    return nadds;
}

/* Routines to support Galbraith, Lin, Scott (GLS) method for ECC */
/* requires an endomorphism psi */

/* *********************** */

/* Precompute T - first half from i.P, second half from i.psi(P) */ 

void ecn2_precomp_gls(_MIPD_ int sz,BOOL norm,ecn2 *P,zzn2 *psi,ecn2 *T)
{
    int i,j;

#ifdef MR_OS_THREADS
    miracl *mr_mip=get_mip();
#endif

    j=0;

    MR_IN(219)

    ecn2_norm(_MIPP_ P);
    ecn2_copy(P,&T[0]);
    
    ecn2_pre(_MIPP_ sz,norm,T); /* precompute table */

    for (i=sz;i<sz+sz;i++)
    {
        ecn2_copy(&T[i-sz],&T[i]);
        ecn2_psi(_MIPP_ psi,&T[i]);
    }

    MR_OUT
}

/* Calculate a[0].P+a[1].psi(P) using interleaving method */

#define MR_MUL2_GLS_RESERVE (2+2*MR_ECC_STORE_N2*4)

int ecn2_mul2_gls(_MIPD_ big *a,ecn2 *P,zzn2 *psi,ecn2 *R)
{
    int i,j,nadds;
    ecn2 T[2*MR_ECC_STORE_N2];
    big a3[2];
#ifdef MR_OS_THREADS
    miracl *mr_mip=get_mip();
#endif

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

    for (j=i=0;i<2;i++)
        a3[i]=mirvar_mem(_MIPP_ mem, j++);

    for (i=0;i<2*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].marker=MR_EPOINT_INFINITY;
    }
    MR_IN(220)

    ecn2_precomp_gls(_MIPP_ MR_ECC_STORE_N2,TRUE,P,psi,T);

    for (i=0;i<2;i++) premult(_MIPP_ a[i],3,a3[i]); /* calculate for NAF */

    nadds=ecn2_muln_engine(_MIPP_ 0,0,2,MR_ECC_STORE_N2,NULL,NULL,a,a3,NULL,T,R);

    ecn2_norm(_MIPP_ R);

    MR_OUT

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

/* Calculates a[0]*P+a[1]*psi(P) + b[0]*Q+b[1]*psi(Q) 
   where P is fixed, and precomputations are already done off-line into FT
   using ecn2_precomp_gls. Useful for signature verification */

#define MR_MUL4_GLS_V_RESERVE (4+2*MR_ECC_STORE_N2*4)

int ecn2_mul4_gls_v(_MIPD_ big *a,int ns,ecn2 *FT,big *b,ecn2 *Q,zzn2 *psi,ecn2 *R)
{ 
    int i,j,nadds;
    ecn2 VT[2*MR_ECC_STORE_N2];
    big a3[2],b3[2];
#ifdef MR_OS_THREADS
    miracl *mr_mip=get_mip();
#endif

#ifndef MR_STATIC
    char *mem = memalloc(_MIPP_ MR_MUL4_GLS_V_RESERVE);
#else
    char mem[MR_BIG_RESERVE(MR_MUL4_GLS_V_RESERVE)];       
 	memset(mem, 0, MR_BIG_RESERVE(MR_MUL4_GLS_V_RESERVE));   
#endif
    j=0;
    for (i=0;i<2;i++)
    {
        a3[i]=mirvar_mem(_MIPP_ mem, j++);
        b3[i]=mirvar_mem(_MIPP_ mem, j++);
    }
    for (i=0;i<2*MR_ECC_STORE_N2;i++)
    {
        VT[i].x.a=mirvar_mem(_MIPP_  mem, j++);
        VT[i].x.b=mirvar_mem(_MIPP_  mem, j++);
        VT[i].y.a=mirvar_mem(_MIPP_  mem, j++);
        VT[i].y.b=mirvar_mem(_MIPP_  mem, j++);       
        VT[i].marker=MR_EPOINT_INFINITY;
    }

    MR_IN(217)

    ecn2_precomp_gls(_MIPP_ MR_ECC_STORE_N2,TRUE,Q,psi,VT); /* precompute for the variable points */
    for (i=0;i<2;i++)
    { /* needed for NAF */
        premult(_MIPP_ a[i],3,a3[i]);
        premult(_MIPP_ b[i],3,b3[i]);
    }
    nadds=ecn2_muln_engine(_MIPP_ 2,ns,2,MR_ECC_STORE_N2,a,a3,b,b3,FT,VT,R);
    ecn2_norm(_MIPP_ R);

    MR_OUT

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

/* Calculate a.P+b.Q using interleaving method. P is fixed and FT is precomputed from it */

void ecn2_precomp(_MIPD_ int sz,BOOL norm,ecn2 *P,ecn2 *T)
{
#ifdef MR_OS_THREADS
    miracl *mr_mip=get_mip();
#endif

    MR_IN(216)

    ecn2_norm(_MIPP_ P);
    ecn2_copy(P,&T[0]);
    ecn2_pre(_MIPP_ sz,norm,T); 

    MR_OUT
}

#ifndef MR_DOUBLE_BIG
#define MR_MUL2_RESERVE (2+2*MR_ECC_STORE_N2*4)
#else
#define MR_MUL2_RESERVE (4+2*MR_ECC_STORE_N2*4)
#endif

int ecn2_mul2(_MIPD_ big a,int ns,ecn2 *FT,big b,ecn2 *Q,ecn2 *R)
{
    int i,j,nadds;
    ecn2 T[2*MR_ECC_STORE_N2];
    big a3,b3;
#ifdef MR_OS_THREADS
    miracl *mr_mip=get_mip();
#endif

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

    j=0;
#ifndef MR_DOUBLE_BIG
    a3=mirvar_mem(_MIPP_ mem, j++);
	b3=mirvar_mem(_MIPP_ mem, j++);
#else
    a3=mirvar_mem(_MIPP_ mem, j); j+=2;
	b3=mirvar_mem(_MIPP_ mem, j); j+=2;
#endif    
    for (i=0;i<2*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].marker=MR_EPOINT_INFINITY;
    }

    MR_IN(218)

    ecn2_precomp(_MIPP_ MR_ECC_STORE_N2,TRUE,Q,T);

    premult(_MIPP_ a,3,a3); 
	premult(_MIPP_ b,3,b3); 

    nadds=ecn2_muln_engine(_MIPP_ 1,ns,1,MR_ECC_STORE_N2,&a,&a3,&b,&b3,FT,T,R);

    ecn2_norm(_MIPP_ R);

    MR_OUT

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


#ifndef MR_STATIC

BOOL ecn2_brick_init(_MIPD_ ebrick *B,zzn2 *x,zzn2 *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;
    ecn2 *table;
    ecn2 w;

#ifdef MR_OS_THREADS
    miracl *mr_mip=get_mip();
#endif

    if (nb<2 || window<1 || window>nb || mr_mip->ERNUM) return FALSE;

    t=MR_ROUNDUP(nb,window);

    if (t<2) return FALSE;

    MR_IN(221)

#ifndef MR_ALWAYS_BINARY
    if (mr_mip->base != mr_mip->base2)
    {
        mr_berror(_MIPP_ MR_ERR_NOT_SUPPORTED);
        MR_OUT
        return FALSE;
    }
#endif

    B->window=window;
    B->max=nb;
    table=mr_alloc(_MIPP_ (1<<window),sizeof(ecn2));
    if (table==NULL)
    {
        mr_berror(_MIPP_ MR_ERR_OUT_OF_MEMORY);   
        MR_OUT
        return 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_AFFINE);
    mr_mip->TWIST=TRUE;

    w.x.a=mirvar(_MIPP_ 0);
    w.x.b=mirvar(_MIPP_ 0);
    w.y.a=mirvar(_MIPP_ 0);
    w.y.b=mirvar(_MIPP_ 0);
    w.marker=MR_EPOINT_INFINITY;
    ecn2_set(_MIPP_ x,y,&w);

    table[0].x.a=mirvar(_MIPP_ 0);
    table[0].x.b=mirvar(_MIPP_ 0);
    table[0].y.a=mirvar(_MIPP_ 0);
    table[0].y.b=mirvar(_MIPP_ 0);
    table[0].marker=MR_EPOINT_INFINITY;
    table[1].x.a=mirvar(_MIPP_ 0);
    table[1].x.b=mirvar(_MIPP_ 0);
    table[1].y.a=mirvar(_MIPP_ 0);
    table[1].y.b=mirvar(_MIPP_ 0);
    table[1].marker=MR_EPOINT_INFINITY;

    ecn2_copy(&w,&table[1]);
    for (j=0;j<t;j++)
        ecn2_add(_MIPP_ &w,&w);

    k=1;
    for (i=2;i<(1<<window);i++)
    {
        table[i].x.a=mirvar(_MIPP_ 0);
        table[i].x.b=mirvar(_MIPP_ 0);
        table[i].y.a=mirvar(_MIPP_ 0);
        table[i].y.b=mirvar(_MIPP_ 0);
        table[i].marker=MR_EPOINT_INFINITY;
        if (i==(1<<k))
        {
            k++;
            ecn2_copy(&w,&table[i]);
            
            for (j=0;j<t;j++)
                ecn2_add(_MIPP_ &w,&w);
            continue;
        }
        bp=1;
        for (j=0;j<k;j++)
        {