mrcurve.c

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

BOOL epoint_comp(_MIPD_ epoint *a,epoint *b)
{
#ifdef MR_OS_THREADS
    miracl *mr_mip=get_mip();
#endif
    if (mr_mip->ERNUM) return FALSE;
    if (a==b) return TRUE;
    if (a->marker==MR_EPOINT_INFINITY)
    {
        if (b->marker==MR_EPOINT_INFINITY) return TRUE;
        else return FALSE;
    }
    if (b->marker==MR_EPOINT_INFINITY)
        return FALSE;
    
    MR_IN(105)
    copy(a->Z,mr_mip->w1);
    copy(b->Z,mr_mip->w2);

    nres_modmult(_MIPP_ a->X,b->Z,mr_mip->w1);
    nres_modmult(_MIPP_ b->X,a->Z,mr_mip->w2);

    if (mr_compare(mr_mip->w1,mr_mip->w2)!=0) 
    {
        MR_OUT
        return FALSE;
    }

    nres_modmult(_MIPP_ a->Y,b->Z,mr_mip->w1);
    nres_modmult(_MIPP_ b->Y,a->Z,mr_mip->w2);

    if (mr_compare(mr_mip->w1,mr_mip->w2)!=0) 
    {
        MR_OUT
        return FALSE;
    }
    MR_OUT
    return TRUE;
 
}

int ecurve_add(_MIPD_ epoint *p,epoint *pa)
{  /* pa=pa+p; */

#ifdef MR_OS_THREADS
    miracl *mr_mip=get_mip();
#endif
    if (mr_mip->ERNUM) return MR_OVER;

    MR_IN(94)

    if (p==pa) 
    {
        ecurve_double(_MIPP_ pa);
        MR_OUT
        if (pa->marker==MR_EPOINT_INFINITY) return MR_OVER;
        return MR_DOUBLE;
    }
    if (pa->marker==MR_EPOINT_INFINITY)
    {
        epoint_copy(p,pa);
        MR_OUT 
        return MR_ADD;
    }
    if (p->marker==MR_EPOINT_INFINITY) 
    {
        MR_OUT
        return MR_ADD;
    }

    if (!ecurve_padd(_MIPP_ p,pa))
    {    
        ecurve_double(_MIPP_ pa);
        MR_OUT
        return MR_DOUBLE;
    }
    MR_OUT
    if (pa->marker==MR_EPOINT_INFINITY) return MR_OVER;
    return MR_ADD;
}

void epoint_negate(_MIPD_ epoint *p)
{ /* negate a point */
#ifdef MR_OS_THREADS
    miracl *mr_mip=get_mip();
#endif
    if (mr_mip->ERNUM) return;
    if (p->marker==MR_EPOINT_INFINITY) return;

    MR_IN(121)
    if (size(p->X)!=0) mr_psub(_MIPP_ mr_mip->modulus,p->X,p->X);
    MR_OUT
}

int ecurve_sub(_MIPD_ epoint *p,epoint *pa)
{
    int r;
#ifdef MR_OS_THREADS
    miracl *mr_mip=get_mip();
#endif
    if (mr_mip->ERNUM) return MR_OVER;

    MR_IN(104)

    if (p==pa)
    {
        epoint_set(_MIPP_ NULL,NULL,0,pa);
        MR_OUT
        return MR_OVER;
    } 
    if (p->marker==MR_EPOINT_INFINITY) 
    {
        MR_OUT
        return MR_ADD;
    }

    epoint_negate(_MIPP_ p);
    r=ecurve_add(_MIPP_ p,pa);
    epoint_negate(_MIPP_ p);

    MR_OUT
    return r;
}

int ecurve_mult(_MIPD_ big e,epoint *pa,epoint *pt)
{ /* pt=e*pa; */
    int i,j,n,nb,nbs,nzs,nadds;
    epoint *table[MR_ECC_STORE_N];

#ifdef MR_STATIC
    char mem[MR_ECP_RESERVE(MR_ECC_STORE_N)];  
#else
    char *mem;
#endif

#ifndef MR_ALWAYS_BINARY
    epoint *p;
    int ce,ch;
#endif
#ifdef MR_OS_THREADS
    miracl *mr_mip=get_mip();
#endif
    if (mr_mip->ERNUM) return 0;

    MR_IN(95)
    if (size(e)==0) 
    { /* multiplied by 0 */
        epoint_set(_MIPP_ NULL,NULL,0,pt);
        MR_OUT
        return 0;
    }
    copy(e,mr_mip->w9);
    epoint_copy(pa,pt);

    if (size(mr_mip->w9)<0)
    { /* pt = -pt */
        negify(mr_mip->w9,mr_mip->w9);
        epoint_negate(_MIPP_ pt);
    }

    if (size(mr_mip->w9)==1)
    { 
        MR_OUT
        return 0;
    }

    premult(_MIPP_ mr_mip->w9,3,mr_mip->w10);      /* h=3*e */

#ifndef MR_STATIC
#ifndef MR_ALWAYS_BINARY
    if (mr_mip->base==mr_mip->base2)
    {
#endif
#endif

#ifdef  MR_STATIC
        memset(mem,0,MR_ECP_RESERVE(MR_ECC_STORE_N));
#else
        mem=(char *)ecp_memalloc(_MIPP_ MR_ECC_STORE_N);
#endif

        for (i=0;i<=MR_ECC_STORE_N-1;i++)
            table[i]=epoint_init_mem(_MIPP_ mem,i);

        epoint_copy(pt,table[0]);
        epoint_copy(table[0],table[MR_ECC_STORE_N-1]);
        ecurve_double(_MIPP_ table[MR_ECC_STORE_N-1]);

        for (i=1;i<MR_ECC_STORE_N-1;i++)
        { /* precomputation */
            epoint_copy(table[i-1],table[i]);
            ecurve_add(_MIPP_ table[MR_ECC_STORE_N-1],table[i]);
        }
        ecurve_add(_MIPP_ table[MR_ECC_STORE_N-2],table[MR_ECC_STORE_N-1]);

        nb=logb2(_MIPP_ mr_mip->w10);
        nadds=0;
        epoint_set(_MIPP_ NULL,NULL,0,pt);
        for (i=nb-1;i>=1;)
        { /* add/subtract */
            if (mr_mip->user!=NULL) (*mr_mip->user)();
            n=mr_naf_window(_MIPP_ mr_mip->w9,mr_mip->w10,i,&nbs,&nzs,MR_ECC_STORE_N);
            for (j=0;j<nbs;j++)
                ecurve_double(_MIPP_ pt);
            if (n>0) {ecurve_add(_MIPP_ table[n/2],pt); nadds++;}
            if (n<0) {ecurve_sub(_MIPP_ table[(-n)/2],pt); nadds++;}
            i-=nbs;
            if (nzs)
            {
                for (j=0;j<nzs;j++) ecurve_double(_MIPP_ pt);
                i-=nzs;
            }
        }

        ecp_memkill(_MIPP_ mem,MR_ECC_STORE_N);


#ifndef MR_STATIC
#ifndef MR_ALWAYS_BINARY
    }
    else
    { 
        mem=ecp_memalloc(_MIPP_ 1);
        p=epoint_init_mem(_MIPP_ mem,0);
        epoint_copy(pt,p);

        nadds=0;
        expb2(_MIPP_ logb2(_MIPP_ mr_mip->w10)-1,mr_mip->w11);
        mr_psub(_MIPP_ mr_mip->w10,mr_mip->w11,mr_mip->w10);
        subdiv(_MIPP_ mr_mip->w11,2,mr_mip->w11);
        while (size(mr_mip->w11) > 1)
        { /* add/subtract method */
            if (mr_mip->user!=NULL) (*mr_mip->user)();

            ecurve_double(_MIPP_ pt);
            ce=mr_compare(mr_mip->w9,mr_mip->w11); /* e(i)=1? */
            ch=mr_compare(mr_mip->w10,mr_mip->w11); /* h(i)=1? */
            if (ch>=0) 
            {  /* h(i)=1 */
                if (ce<0) {ecurve_add(_MIPP_ p,pt); nadds++;}
                mr_psub(_MIPP_ mr_mip->w10,mr_mip->w11,mr_mip->w10);
            }
            if (ce>=0) 
            {  /* e(i)=1 */
                if (ch<0) {ecurve_sub(_MIPP_ p,pt); nadds++;}
                mr_psub(_MIPP_ mr_mip->w9,mr_mip->w11,mr_mip->w9);  
            }
            subdiv(_MIPP_ mr_mip->w11,2,mr_mip->w11);
        }
        ecp_memkill(_MIPP_ mem,1);
    }
#endif
#endif
    MR_OUT
    return nadds;
}

#ifndef MR_NO_ECC_MULTIADD
#ifndef MR_STATIC

void ecurve_multn(_MIPD_ int n,big *y,epoint **x,epoint *w)
{ /* pt=e[o]*p[0]+e[1]*p[1]+ .... e[n-1]*p[n-1]   */
    int i,j,k,m,nb,ea;
    epoint **G;
#ifdef MR_OS_THREADS
    miracl *mr_mip=get_mip();
#endif
    if (mr_mip->ERNUM) return;

    MR_IN(114)

    m=1<<n;
    G=(epoint **)mr_alloc(_MIPP_ m,sizeof(epoint*));

    for (i=0,k=1;i<n;i++)
    {
        for (j=0; j < (1<<i) ;j++)
        {
            G[k]=epoint_init(_MIPPO_ );
            epoint_copy(x[i],G[k]);
            if (j!=0) ecurve_add(_MIPP_ G[j],G[k]);
            k++;
        }
    }

    nb=0;
    for (j=0;j<n;j++) if ((k=logb2(_MIPP_ y[j])) > nb) nb=k;

    epoint_set(_MIPP_ NULL,NULL,0,w);            /* w=0 */
    
#ifndef MR_ALWAYS_BINARY
    if (mr_mip->base==mr_mip->base2)
    {
#endif
        for (i=nb-1;i>=0;i--)
        {
            if (mr_mip->user!=NULL) (*mr_mip->user)();
            ea=0;
            k=1;
            for (j=0;j<n;j++)
            {
                if (mr_testbit(_MIPP_ y[j],i)) ea+=k;
                k<<=1;
            }
            ecurve_double(_MIPP_ w);
            if (ea!=0) ecurve_add(_MIPP_ G[ea],w);
        }    
#ifndef MR_ALWAYS_BINARY
    }
    else mr_berror(_MIPP_ MR_ERR_NOT_SUPPORTED);
#endif

    for (i=1;i<m;i++) epoint_free(G[i]);
    mr_free(G);
    MR_OUT
}

#endif

/* PP=P+Q, PM=P-Q. */

static BOOL ecurve_add_sub(_MIPD_ epoint *P,epoint *Q,epoint *PP,epoint *PM)
{ 
 #ifdef MR_OS_THREADS
    miracl *mr_mip=get_mip();
#endif
   
    if (P->marker==MR_EPOINT_NORMALIZED)
    {
        if (Q->marker==MR_EPOINT_NORMALIZED)
            copy(mr_mip->one,mr_mip->w1);
        else copy(Q->Z,mr_mip->w1);
    }
    else 
    {
        if (Q->marker==MR_EPOINT_NORMALIZED)
            copy(P->Z,mr_mip->w1);
        else nres_modmult(_MIPP_ P->Z,Q->Z,mr_mip->w1);         /* w1 = A = Z1*Z2 */
    }
    nres_modmult(_MIPP_ mr_mip->w1,mr_mip->w1,mr_mip->w2);      /* w2 = B = dA^2   */
    if (mr_abs(mr_mip->Bsize)==MR_TOOBIG)                   
        nres_modmult(_MIPP_ mr_mip->w2,mr_mip->B,mr_mip->w2);
    else
        nres_premult(_MIPP_ mr_mip->w2,mr_mip->Bsize,mr_mip->w2);
    nres_modmult(_MIPP_ P->X,Q->X,mr_mip->w3);              /* w3 = C = X1*X2 */
    nres_modmult(_MIPP_ P->Y,Q->Y,mr_mip->w4);              /* w4 = D = Y1*Y2 */
    nres_modmult(_MIPP_ mr_mip->w3,mr_mip->w4,mr_mip->w5);  /* w5 = E = C*D     */
    nres_modmult(_MIPP_ P->X,Q->Y,mr_mip->w7);              /* w7 = F = X1.Y2 */
    nres_modmult(_MIPP_ Q->X,P->Y,mr_mip->w8);              /* w8 = G = X2.Y1 */

    if (mr_abs(mr_mip->Asize)==MR_TOOBIG)                   /* w4 = aD */
        nres_modmult(_MIPP_ mr_mip->w4,mr_mip->A,mr_mip->w4);
    else
        nres_premult(_MIPP_ mr_mip->w4,mr_mip->Asize,mr_mip->w4);

/* P+Q */

    nres_modsub(_MIPP_ mr_mip->w3,mr_mip->w4,mr_mip->w6);   /* w6 = H = C-aD */
    nres_modadd(_MIPP_ mr_mip->w7,mr_mip->w8,PP->Z);        /* X1*Y2+X2*Y1   */
    nres_modadd(_MIPP_ mr_mip->w5,mr_mip->w2,PP->X);
    nres_modmult(_MIPP_ PP->X,mr_mip->w6,PP->X);
    nres_modsub(_MIPP_ mr_mip->w5,mr_mip->w2,PP->Y);
    nres_modmult(_MIPP_ PP->Y,PP->Z,PP->Y);
    nres_modmult(_MIPP_ PP->Z,mr_mip->w6,PP->Z);
    nres_modmult(_MIPP_ PP->Z,mr_mip->w1,PP->Z);

    if (size(PP->Z)==0)
    {
        copy(mr_mip->one,PP->X);
        zero(PP->Y);
        PP->marker=MR_EPOINT_INFINITY;
    }
    else PP->marker=MR_EPOINT_GENERAL;

/* P-Q */

    nres_modadd(_MIPP_ mr_mip->w3,mr_mip->w4,mr_mip->w6);  /* w6 = C+aD */
    nres_modsub(_MIPP_ mr_mip->w8,mr_mip->w7,PM->Z);       /* X2*Y1-X1*Y2 */
    nres_modsub(_MIPP_ mr_mip->w5,mr_mip->w2,PM->X);
    nres_modmult(_MIPP_ PM->X,mr_mip->w6,PM->X);
    nres_modadd(_MIPP_ mr_mip->w5,mr_mip->w2,PM->Y);
    nres_modmult(_MIPP_ PM->Y,PM->Z,PM->Y);
    nres_modmult(_MIPP_ PM->Z,mr_mip->w6,PM->Z);
    nres_modmult(_MIPP_ PM->Z,mr_mip->w1,PM->Z);

    if (size(PM->Z)==0)
    {
        copy(mr_mip->one,PM->X);
        zero(PM->Y);
        PM->marker=MR_EPOINT_INFINITY;
    }
    else PM->marker=MR_EPOINT_GENERAL;

    return TRUE;
}

void ecurve_mult2(_MIPD_ big e,epoint *p,big ea,epoint *pa,epoint *pt)
{ /* pt=e*p+ea*pa; */
    int e1,h1,e2,h2,bb;
    epoint *p1,*p2,*ps[2];
#ifdef MR_STATIC
    char mem[MR_ECP_RESERVE(4)];
#else
    char *mem;
#endif
#ifdef MR_OS_THREADS
    miracl *mr_mip=get_mip();
#endif

    if (mr_mip->ERNUM) return;

    MR_IN(103)

    if (size(e)==0) 
    {
        ecurve_mult(_MIPP_ ea,pa,pt);
        MR_OUT
        return;
    }
#ifdef MR_STATIC
    memset(mem,0,MR_ECP_RESERVE(4));
#else
    mem=ecp_memalloc(_MIPP_ 4);
#endif
    p2=epoint_init_mem(_MIPP_ mem,0);
    p1=epoint_init_mem(_MIPP_ mem,1);
    ps[0]=epoint_init_mem(_MIPP_ mem,2);
    ps[1]=epoint_init_mem(_MIPP_ mem,3);

    epoint_copy(pa,p2);
    copy(ea,mr_mip->w9);
    if (size(mr_mip->w9)<0)
    { /* p2 = -p2 */
        negify(mr_mip->w9,mr_mip->w9);
        epoint_negate(_MIPP_ p2);
    }

    epoint_copy(p,p1);
    copy(e,mr_mip->w12);
    if (size(mr_mip->w12)<0)
    { /* p1= -p1 */
        negify(mr_mip->w12,mr_mip->w12);
        epoint_negate(_MIPP_ p1);
    }

    epoint_set(_MIPP_ NULL,NULL,0,pt);            /* pt=0 */ 
    ecurve_add_sub(_MIPP_ p1,p2,ps[0],ps[1]);     /* ps[0]=p1+p2, ps[1]=p1-p2 */

    mr_jsf(_MIPP_ mr_mip->w9,mr_mip->w12,mr_mip->w10,mr_mip->w9,mr_mip->w13,mr_mip->w12);
  
/*    To use a simple NAF instead, substitute this for the JSF 
        premult(_MIPP_ mr_mip->w9,3,mr_mip->w10);      3*ea  
        premult(_MIPP_ mr_mip->w12,3,mr_mip->w13);     3*e  
*/ 

#ifndef MR_ALWAYS_BINARY
    if (mr_mip->base==mr_mip->base2)
    {
#endif
        if (mr_compare(mr_mip->w10,mr_mip->w13)>=0) bb=logb2(_MIPP_ mr_mip->w10)-1;
        else                                        bb=logb2(_MIPP_ mr_mip->w13)-1;

        while (bb>=0) /* for the simple NAF, this should be 1 */
        {
            if (mr_mip->user!=NULL) (*mr_mip->user)();
            ecurve_double(_MIPP_ pt);

            e1