mrecgf2m.c

大数运算库

                {
                    flag[i]=3;                    /* w[i]=x[i] */
                    copy(mr_mip->w3,B[i]);
                    continue;
                }
                add2(x[i]->X,w[i]->X,B[i]);
                if (size(B[i])==0)
                { /* point at infinity */
                    flag[i]=1;                /* result is infinity */
                    copy(mr_mip->w3,B[i]);
                    continue;
                }
                add2(x[i]->Y,w[i]->Y,A[i]);
            }
        }

        multi_inverse2(_MIPP_ m,B,C); /* one inversion only */
        for (i=0;i<m;i++)
        {
            if (flag[i]==1)
            { /* point at infinity */
                epoint2_set(_MIPP_ NULL,NULL,0,w[i]);
                continue;
            }
            if (flag[i]==2)
            {
                continue;
            }
            if (flag[i]==3)
            {
                epoint2_copy(x[i],w[i]);
                continue;
            }
            modmult2(_MIPP_ A[i],C[i],mr_mip->w8);
            modsquare2(_MIPP_ mr_mip->w8,mr_mip->w6); /* m^2 */
            add2(mr_mip->w6,mr_mip->w8,mr_mip->w6);
            add2(mr_mip->w6,x[i]->X,mr_mip->w6);
            add2(mr_mip->w6,w[i]->X,mr_mip->w6);
            if (mr_mip->Asize==MR_TOOBIG)
                add2(mr_mip->w6,mr_mip->A,mr_mip->w6);
            else
                incr2(mr_mip->w6,mr_mip->Asize,mr_mip->w6);

            add2(w[i]->X,mr_mip->w6,mr_mip->w2);
            modmult2(_MIPP_ mr_mip->w2,mr_mip->w8,mr_mip->w2);
            add2(mr_mip->w2,mr_mip->w6,mr_mip->w2);
            add2(mr_mip->w2,w[i]->Y,w[i]->Y);
            copy(mr_mip->w6,w[i]->X);

            w[i]->marker=MR_EPOINT_GENERAL;

        }
        memkill(_MIPP_ mem,3*m);
        mr_free(flag);
        mr_free(C); mr_free(B); mr_free(A);
    }
    else
    { /* no speed-up for projective coordinates */
        for (i=0;i<m;i++) ecurve2_add(_MIPP_ x[i],w[i]);
    }
    MR_OUT
}

void ecurve2_mult(_MIPD_ big e,epoint *pa,epoint *pt)
{ /* pt=e*pa; */
    int i,j,n,ch,ce,nb,nbs,nzs;
    epoint *p;
    epoint *table[11];
#ifndef MR_GENERIC_MT
    miracl *mr_mip=get_mip();
#endif
    if (mr_mip->ERNUM) return;

    MR_IN(133)

    if (size(e)==0) 
    { /* multiplied by 0 */
        epoint2_set(_MIPP_ NULL,NULL,0,pt);
        MR_OUT
        return;
    }
    copy(e,mr_mip->w9);
    epoint2_norm(_MIPP_ pa);
    epoint2_copy(pa,pt);

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

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

    premult(_MIPP_ mr_mip->w9,3,mr_mip->w10);      /* h=3*e */
    p=epoint2_init(_MIPPO_ );
    epoint2_copy(pt,p);

    if (mr_mip->base==mr_mip->base2)
    {
        table[0]=epoint2_init(_MIPPO_ );
        epoint2_copy(p,table[0]);
        ecurve2_double(_MIPP_ p);

        for (i=1;i<=10;i++)
        { /* precomputation */
            table[i]=epoint2_init(_MIPPO_ );
            epoint2_copy(table[i-1],table[i]);
            ecurve2_add(_MIPP_ p,table[i]);
        }

  /* note that normalising this table doesn't really help */
        nb=logb2(_MIPP_ mr_mip->w10);

        for (i=nb-2;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);
            for (j=0;j<nbs;j++)
                ecurve2_double(_MIPP_ pt);
            if (n>0) 
                ecurve2_add(_MIPP_ table[n/2],pt);
            if (n<0) 
                 ecurve2_sub(_MIPP_ table[(-n)/2],pt);
            i-=nbs;
            if (nzs)
            {
                for (j=0;j<nzs;j++) ecurve2_double(_MIPP_ pt);
                i-=nzs;
            }
        }
        for (i=10;i>=0;i--) epoint2_free(table[i]);
    }
    else
    { 
        expint(_MIPP_ 2,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)();

            ecurve2_double(_MIPP_ pt);
            ce=compare(mr_mip->w9,mr_mip->w11); /* e(i)=1? */
            ch=compare(mr_mip->w10,mr_mip->w11); /* h(i)=1? */
            if (ch>=0) 
            {  /* h(i)=1 */
                if (ce<0) ecurve2_add(_MIPP_ p,pt);
                mr_psub(_MIPP_ mr_mip->w10,mr_mip->w11,mr_mip->w10);
            }
            if (ce>=0) 
            {  /* e(i)=1 */
                if (ch<0) ecurve2_sub(_MIPP_ p,pt);
                mr_psub(_MIPP_ mr_mip->w9,mr_mip->w11,mr_mip->w9);  
            }
            subdiv(_MIPP_ mr_mip->w11,2,mr_mip->w11);
        }
    }
    epoint2_free(p);
    MR_OUT
}

void ecurve2_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;
#ifndef MR_GENERIC_MT
    miracl *mr_mip=get_mip();
#endif
    if (mr_mip->ERNUM) return;

    MR_IN(134)

    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]=epoint2_init(_MIPPO_ );
            epoint2_copy(x[i],G[k]);
            if (j!=0) ecurve2_add(_MIPP_ G[j],G[k]);
            k++;
        }
    }

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

    epoint2_set(_MIPP_ NULL,NULL,0,w);            /* w=0 */
    
    if (mr_mip->base==mr_mip->base2)
    {
        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;
            }
            ecurve2_double(_MIPP_ w);
            if (ea!=0) ecurve2_add(_MIPP_ G[ea],w);
        }    
    }
    else mr_berror(_MIPP_ MR_ERR_NOT_SUPPORTED);

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

void ecurve2_mult2(_MIPD_ big e,epoint *p,big ea,epoint *pa,epoint *pt)
{ /* pt=e*p+ea*pa; */
    int e1,h1,e2,h2;
    epoint *p1,*p2,*ps,*pd;
#ifndef MR_GENERIC_MT
    miracl *mr_mip=get_mip();
#endif
    if (mr_mip->ERNUM) return;

    MR_IN(135)

    if (size(e)==0) 
    {
        ecurve2_mult(_MIPP_ ea,pa,pt);
        MR_OUT
        return;
    }

    p2=epoint2_init(_MIPPO_ );
    epoint2_norm(_MIPP_ pa);
    epoint2_copy(pa,p2);
    copy(ea,mr_mip->w9);
    if (size(mr_mip->w9)<0)
    { /* p2 = -p2 */
        negify(mr_mip->w9,mr_mip->w9);
        epoint2_negate(_MIPP_ p2);
    }
    premult(_MIPP_ mr_mip->w9,3,mr_mip->w10);      /* 3*ea */

    p1=epoint2_init(_MIPPO_ );
    epoint2_norm(_MIPP_ p);
    epoint2_copy(p,p1);
    copy(e,mr_mip->w12);
    if (size(mr_mip->w12)<0)
    { /* p1= -p1 */
        negify(mr_mip->w12,mr_mip->w12);
        epoint2_negate(_MIPP_ p1);
    }
    premult(_MIPP_ mr_mip->w12,3,mr_mip->w13);    /* 3*e */

    epoint2_set(_MIPP_ NULL,NULL,0,pt);            /* pt=0 */

    if (compare(mr_mip->w10,mr_mip->w13)>=0)
         expint(_MIPP_ 2,logb2(_MIPP_ mr_mip->w10)-1,mr_mip->w11);
    else expint(_MIPP_ 2,logb2(_MIPP_ mr_mip->w13)-1,mr_mip->w11);

    ps=epoint2_init(_MIPPO_ );
    pd=epoint2_init(_MIPPO_ );

    epoint2_copy(p1,ps);
    ecurve2_add(_MIPP_ p2,ps);                    /* ps=p1+p2 */
    epoint2_copy(p1,pd);
    ecurve2_sub(_MIPP_ p2,pd);                    /* pd=p1-p2 */
    epoint2_norm(_MIPP_ ps);
    epoint2_norm(_MIPP_ pd);
    while (size(mr_mip->w11) > 1)
    { /* add/subtract method */
        if (mr_mip->user!=NULL) (*mr_mip->user)();

        ecurve2_double(_MIPP_ pt);

        e1=h1=e2=h2=0;
        if (compare(mr_mip->w9,mr_mip->w11)>=0)
        { /* e1(i)=1? */
            e2=1;  
            mr_psub(_MIPP_ mr_mip->w9,mr_mip->w11,mr_mip->w9);
        }
        if (compare(mr_mip->w10,mr_mip->w11)>=0)
        { /* h1(i)=1? */
            h2=1;  
            mr_psub(_MIPP_ mr_mip->w10,mr_mip->w11,mr_mip->w10);
        } 
        if (compare(mr_mip->w12,mr_mip->w11)>=0)
        { /* e2(i)=1? */
            e1=1;   
            mr_psub(_MIPP_ mr_mip->w12,mr_mip->w11,mr_mip->w12);
        }
        if (compare(mr_mip->w13,mr_mip->w11)>=0) 
        { /* h2(i)=1? */
            h1=1;  
            mr_psub(_MIPP_ mr_mip->w13,mr_mip->w11,mr_mip->w13);
        }

        if (e1!=h1)
        {
            if (e2==h2)
            {
                if (h1==1) ecurve2_add(_MIPP_ p1,pt);
                else       ecurve2_sub(_MIPP_ p1,pt);
            }
            else
            {
                if (h1==1)
                {
                    if (h2==1) ecurve2_add(_MIPP_ ps,pt);
                    else       ecurve2_add(_MIPP_ pd,pt);
                }
                else
                {
                    if (h2==1) ecurve2_sub(_MIPP_ pd,pt);
                    else       ecurve2_sub(_MIPP_ ps,pt);
                }
            }
        }
        else if (e2!=h2)
        {
            if (h2==1) ecurve2_add(_MIPP_ p2,pt);
            else       ecurve2_sub(_MIPP_ p2,pt);
        }

        subdiv(_MIPP_ mr_mip->w11,2,mr_mip->w11);
    }
    epoint2_free(p1);
    epoint2_free(p2);
    epoint2_free(ps);
    epoint2_free(pd);
    MR_OUT
}

/*   Routines to implement Brickell et al's method for fast
 *   computation of x*G mod n, for fixed G and n, using precomputation. 
 *
 *   Elliptic curve over GF(2^m) version of mrebrick.c
 *
 *   This idea can be used to substantially speed up certain phases 
 *   of the Digital Signature Standard (ECS) for example.
 *
 *   See "Fast Exponentiation with Precomputation"
 *   by E. Brickell et al. in Proceedings Eurocrypt 1992
 */

BOOL ebrick2_init(_MIPD_ ebrick2 *B,big x,big y,big a2,big a6,int m,int a,int b,int c,int nb)
{ /* (x,y) is the fixed base                            *
   * a2 and a6 the parameters of the curve              *
   * m, a, b, c are the m in the 2^m modulus, and a,b,c *
   * are the parameters of the irreducible bases,       *
   * trinomial if b!=0, otherwise pentanomial           *
   * nb is the maximum number of bits in the multiplier */

    int i,base,best,store,time;
    epoint *w;
#ifndef MR_GENERIC_MT
    miracl *mr_mip=get_mip();
#endif
    if (nb<2 || mr_mip->ERNUM) return FALSE;

    MR_IN(136)

    best=0;
    for (i=1,base=2;;base*=2,i++)
    { /* try to find best base as power of 2 */
        store=nb/i+1;
        time=store+base-3;  /* no floating point! */
        if (best==0 || time<best) best=time;
        else break; 
    }
    B->base=base;
    B->store=store;
    B->table=mr_alloc(_MIPP_ store,sizeof(epoint *));
    if (B->table==NULL)
    {
        mr_berror(_MIPP_ MR_ERR_OUT_OF_MEMORY);   
        MR_OUT
        return FALSE;
    }
    B->a6=mirvar(_MIPP_ 0);
    copy(a6,B->a6);
    B->a2=mirvar(_MIPP_ 0);
    copy(a2,B->a2);
    B->m=m;
    B->a=a;
    B->b=b;
    B->c=c;   

    if (!ecurve2_init(_MIPP_ m,a,b,c,a2,a6,TRUE,MR_AFFINE))
    {
        MR_OUT
        return FALSE;
    }
    w=epoint2_init(_MIPPO_ );
    B->table[0]=epoint2_init(_MIPPO_ );
    epoint2_set(_MIPP_ x,y,0,B->table[0]);

    for (i=1;i<store;i++) 
    { /* calculate look-up table */
        B->table[i]=epoint2_init(_MIPPO_ );
        convert(_MIPP_ base,mr_mip->w1);
        ecurve2_mult(_MIPP_ mr_mip->w1,B->table[i-1],w);
        epoint2_copy(w,B->table[i]);
    }
    epoint2_free(w);
    MR_OUT
    return TRUE;
}

void ebrick2_end(ebrick2 *B)
{
    int i;
    for (i=0;i<B->store;i++)
        epoint2_free(B->table[i]);
    mirkill(B->a2);
    mirkill(B->a6);
    mr_free(B->table);  
}

int mul2_brick(_MIPD_ ebrick2 *B,big e,big x,big y)
{
    int i,ndig,d;
    int *digits;
    epoint *w,*w1;
#ifndef MR_GENERIC_MT
    miracl *mr_mip=get_mip();
#endif

    if (size(e)<0) mr_berror(_MIPP_ MR_ERR_NEG_POWER);

    MR_IN(137)

    digits=mr_alloc(_MIPP_ B->store,sizeof(int));
    if (digits==NULL)
    {
        mr_berror(_MIPP_ MR_ERR_OUT_OF_MEMORY);
        MR_OUT
        return 0;        
    }

    if (!ecurve2_init(_MIPP_ B->m,B->a,B->b,B->c,B->a2,B->a6,FALSE,MR_PROJECTIVE))
    {
        MR_OUT
        return 0;
    }
    copy(e,mr_mip->w1);
    for (ndig=0;size(mr_mip->w1)>0;ndig++)
    { /* break up exponent into digits, using 'base' */
      /* (note base is a power of 2.) This is fast.  */
        digits[ndig]=subdiv(_MIPP_ mr_mip->w1,B->base,mr_mip->w1);
    }

    if (ndig>B->store)
    {
        mr_free(digits);
        mr_berror(_MIPP_ MR_ERR_EXP_TOO_BIG);
        MR_OUT
        return 0;
    }

    w=epoint2_init(_MIPPO_ );
    w1=epoint2_init(_MIPPO_ );

    for (d=B->base-1;d>0;d--)
    { /* brickell's method */
        for (i=0;i<ndig;i++)
        {
            if (mr_mip->user!=NULL) (*mr_mip->user)();
            if (digits[i]==d) ecurve2_add(_MIPP_ B->table[i],w1);
        }
        ecurve2_add(_MIPP_ w1,w);
    }
    d=epoint2_get(_MIPP_ w,x,y);
    epoint2_free(w1);
    epoint2_free(w);

    for (i=0;i<ndig;i++) digits[i]=0;
    mr_free(digits);
    MR_OUT
    return d;
}

#endif