mrec2m.c

miracl大数库 miracl大数库 miracl大数库

            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_NORMALIZED;

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

#endif
#endif

#ifndef MR_NOKOBLITZ

static void frobenius(_MIPD_ epoint *P)
{
#ifdef MR_OS_THREADS
    miracl *mr_mip=get_mip();
#endif
    if (P->marker==MR_EPOINT_INFINITY) return;

    modsquare2(_MIPP_ P->X,P->X);
    modsquare2(_MIPP_ P->Y,P->Y);
#ifndef MR_AFFINE_ONLY
    if (mr_mip->coord==MR_PROJECTIVE && P->marker==MR_EPOINT_GENERAL) modsquare2(_MIPP_ P->Z,P->Z);
#endif
}

/* creates a tnaf from a+tau.b into tm[.] */

static int itnaf(int mu,int a,int b,signed char *tm)
{
    int u,t,len=0;
    int r0=a;
    int r1=b;

    while (r0!=0 || r1!=0)
    {
        if ((r0%2)!=0)
        {
            t=(r0-2*r1)%4; if (t<0) t+=4;
            u=2-t;  
            r0-=u;
        }   
        else u=0;
        tm[len++]=u;
        t=r0;
        if (mu==1) r0=r1+r0/2;
        else       r0=r1-r0/2;
        r1=-t/2;
    }
    return len;
}

/* Here we use the post-processing algorithm of Lutz and Hasan */
/* rather than the more well known Solinas method - see */
/* http://vlsi.uwaterloo.ca/~ahasan/web_papers/technical_reports/web_Hi_Per_ECC.pdf */ 

static int tnaf(_MIPD_ big e,big hp,big hn)
{
    int n,u,t,i,j,len,mu,count;
    signed char tm[8];
    BOOL wrapped=FALSE;
    int m,a;

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

#ifdef MR_STATIC
    signed char tn[MIRACL*MR_STATIC+8];
#else
    signed char *tn=(signed char *)mr_alloc(_MIPP_ mr_mip->M+8,1);
#endif

    m=mr_mip->M;
    a=mr_mip->Asize;

    if (a==0) mu=-1;
    else      mu=1;

    copy(e,mr_mip->w1);
    zero(mr_mip->w2);
    for (i=0;i<m+8;i++) tn[i]=0;
    i=0;
    while (size(mr_mip->w1)!=0 || size(mr_mip->w2)!=0)
    {
        if (remain(_MIPP_ mr_mip->w1,2)!=0)
        {
            premult(_MIPP_ mr_mip->w2,2,mr_mip->w3);
            subtract(_MIPP_ mr_mip->w1,mr_mip->w3,mr_mip->w3);
            t=remain(_MIPP_ mr_mip->w3,4); if (t<0) t+=4;
            u=2-t;
            decr(_MIPP_ mr_mip->w1,u,mr_mip->w1);
            tn[i]+=u;
        }

        subdiv(_MIPP_ mr_mip->w1,2,mr_mip->w3);
        if (mu>0) add(_MIPP_ mr_mip->w2,mr_mip->w3,mr_mip->w1);
        else      subtract(_MIPP_ mr_mip->w2,mr_mip->w3,mr_mip->w1);
        negify(mr_mip->w3,mr_mip->w2);
        i++;
        if (i==m)
        {
            i=0;
            wrapped=TRUE;
        }
    }
    len=i;
    count=0;
    if (wrapped) forever
    {
        len=m;

        for (i=0;i<len;)
        {   
            if (tn[i]==0) 
            {
                i++;
                continue;
            }
            if (tn[i+1]==0)
            {
                if (tn[i]==1 || tn[i]==-1)
                {
                    i+=2;
                    continue;
                }
            }
            n=itnaf(mu,tn[i],tn[i+1],tm);  

            tn[i]=tm[0]; tn[i+1]=tm[1];
            for (j=2;j<n;j++)
                tn[i+j]+=tm[j];
            if (i+n>=len) len=i+n;
            i++;
        }
        count++;
        if (count<3 && len>m)
        { 
            for (i=m;i<len;i++)
            {
                tn[i-m]+=tn[i];
                tn[i]=0;
            }
            continue;
        }
        break;
    }

    zero(hp);
    zero(hn);   
    for (i=0;i<len;i++)
    {
        if (tn[i]==1)
        {
            expb2(_MIPP_ i,mr_mip->w3);
            add(_MIPP_ hp,mr_mip->w3,hp);
        }
        if (tn[i]==-1)
        {
            expb2(_MIPP_ i,mr_mip->w3);
            add(_MIPP_ hn,mr_mip->w3,hn);
        }
        tn[i]=0;
    }
    for (i=0;i<8;i++) tm[i]=0;
#ifndef MR_STATIC
    mr_free(tn);
#endif
    return len;
}

#endif

BOOL epoint2_multi_norm(_MIPD_ int m,big *work,epoint **p)
{ /* Normalise an array of points of length m<20 - requires a workspace array of length m */

#ifdef MR_OS_THREADS
    miracl *mr_mip=get_mip();
#endif
 
#ifndef MR_AFFINE_ONLY
    int i;
    big w[MR_MAX_M_T_S];
    if (mr_mip->coord==MR_AFFINE) return TRUE;
    if (mr_mip->ERNUM) return FALSE;   
    if (m>MR_MAX_M_T_S) return FALSE;

    MR_IN(192)

    for (i=0;i<m;i++)
    {
        if (p[i]->marker==MR_EPOINT_NORMALIZED) w[i]=mr_mip->one;
        else w[i]=p[i]->Z;

    }

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

    for (i=0;i<m;i++)
    {
        copy(mr_mip->one,p[i]->Z);
        p[i]->marker=MR_EPOINT_NORMALIZED;
#ifndef MR_NO_SS
        if (mr_mip->SS)
        {
            modmult2(_MIPP_ p[i]->X,work[i],p[i]->X);
            modmult2(_MIPP_ p[i]->Y,work[i],p[i]->Y); 
        }
        else
        {
#endif
            modmult2(_MIPP_ p[i]->X,work[i],p[i]->X);    /* X/Z */
            modmult2(_MIPP_ work[i],work[i],mr_mip->w1);
            modmult2(_MIPP_ p[i]->Y,mr_mip->w1,p[i]->Y);    /* Y/ZZ */
#ifndef MR_NO_SS
        }
#endif

    }    
    MR_OUT
#endif
    return TRUE;   
}

static void table_init(_MIPD_ epoint *g,epoint **table)
{ /* A precomputation option for the multiplication of a  */
  /* fixed point, would be to precalculate and normalize  */
  /* this table */
    int i,n,n3,nf,nb,t;
#ifdef MR_OS_THREADS
    miracl *mr_mip=get_mip();
#endif
    
#ifndef MR_NOKOBLITZ

    if (mr_mip->KOBLITZ)
    {
       epoint2_copy(g,table[0]);
       epoint2_copy(g,table[MR_ECC_STORE_2M-1]);
       frobenius(_MIPP_ table[MR_ECC_STORE_2M-1]);
       frobenius(_MIPP_ table[MR_ECC_STORE_2M-1]);  
       nf=2;
       for (i=1;i<MR_ECC_STORE_2M;i++)
       {  /* Consider i expressed as NAF */
           n=i;
           n3=3*i+1;
           t=n3;
           nb=0;
           while (t>1)
           { /* number of bits in n3 */
               t>>=1;
               nb++;
           }
           while (nb>nf) 
           { /* move to next power of tau */
               frobenius(_MIPP_ table[MR_ECC_STORE_2M-1]); 
               nf++;
           }

           n3-=(1<<nb); /* subtract MSB */
           n=n3-n;      /* get index of previously calculated value */

           if (i==MR_ECC_STORE_2M-1)
           { /* last one.. */
                if (n>0) ecurve2_add(_MIPP_ table[n/2],table[i]);
                else     ecurve2_sub(_MIPP_ table[(-n)/2],table[i]);   
           }
           else
           { /* mostly mixed additions... */
                if (n>0) epoint2_copy(_MIPP_ table[n/2],table[i]);
                if (n<0) 
                {
                    epoint2_copy(_MIPP_ table[(-n)/2],table[i]);
                    epoint2_negate(_MIPP_ table[i]);
                }
                ecurve2_add(_MIPP_ table[MR_ECC_STORE_2M-1],table[i]);
           }    
       }
    }
    else
    {
#endif

        epoint2_copy(g,table[0]);
        epoint2_copy(g,table[MR_ECC_STORE_2M-1]);
        ecurve2_double(_MIPP_ table[MR_ECC_STORE_2M-1]);

       /* epoint2_norm(_MIPP_ table[MR_ECC_STORE_2M-1]);  makes additions below faster */
        for (i=1;i<MR_ECC_STORE_2M-1;i++)
        {  
            epoint2_copy(table[i-1],table[i]);
            ecurve2_add(_MIPP_ table[MR_ECC_STORE_2M-1],table[i]);
        }
        ecurve2_add(_MIPP_ table[MR_ECC_STORE_2M-2],table[MR_ECC_STORE_2M-1]);

#ifndef MR_NOKOBLITZ
    }
#endif
}

static void prepare_naf(_MIPD_ big e,big hp,big hn)
{ /* prepare NAF - exponent = hp-hn = (3e-e)/2 */
  /* return number of bits */
#ifdef MR_OS_THREADS
    miracl *mr_mip=get_mip();
#endif
#ifndef MR_NOKOBLITZ
    if (mr_mip->KOBLITZ)
    {
        tnaf(_MIPP_ e,hp,hn);
    }
    else
    {
#endif
        copy(e,hn);
        premult(_MIPP_ hn,3,hp); 
        subdiv(_MIPP_ hn,2,hn);
        subdiv(_MIPP_ hp,2,hp);
#ifndef MR_NOKOBLITZ
    }
#endif
}

void ecurve2_mult(_MIPD_ big e,epoint *pa,epoint *pt)
{ /* pt=e*pa; */
    int i,j,n,nb,nbs,nzs;
#ifndef MR_AFFINE_ONLY
/*    int coord;  */
    big work[MR_ECC_STORE_2M];
#endif
    epoint *table[MR_ECC_STORE_2M];
#ifdef MR_STATIC
    char mem[MR_ECP_RESERVE(MR_ECC_STORE_2M)];
 /*   char mem[MR_ECP_RESERVE_A(MR_ECC_STORE_2M)];   Reserve space for AFFINE (x,y) only */
#ifndef MR_AFFINE_ONLY
    char mem1[MR_BIG_RESERVE(MR_ECC_STORE_2M)];
#endif
#else
    char *mem;
#ifndef MR_AFFINE_ONLY
    char *mem1;
#endif
#endif
#ifndef MR_ALWAYS_BINARY
    epoint *p;
    int ch,ce;
#endif
#ifdef MR_OS_THREADS
    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;
    }
    epoint2_norm(_MIPP_ pa); 
    epoint2_copy(pa,pt);

    copy(e,mr_mip->w9);

    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;
    }

    prepare_naf(_MIPP_ mr_mip->w9,mr_mip->w10,mr_mip->w9);

    if (size(mr_mip->w9)==0 && size(mr_mip->w10)==0)
    { /* multiplied by 0 */
        epoint2_set(_MIPP_ NULL,NULL,0,pt);
        MR_OUT
        return;
    }

#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_2M));
    /*    memset(mem,0,MR_ECP_RESERVE_A(MR_ECC_STORE_2M)); */
#ifndef MR_AFFINE_ONLY
        memset(mem1,0,MR_BIG_RESERVE(MR_ECC_STORE_2M));
#endif
#else
        mem=ecp_memalloc(_MIPP_ MR_ECC_STORE_2M);
#ifndef MR_AFFINE_ONLY
        mem1=(char *)memalloc(_MIPP_ MR_ECC_STORE_2M);
#endif
#endif

        for (i=0;i<=MR_ECC_STORE_2M-1;i++)
		{
            table[i]=epoint_init_mem(_MIPP_ mem,i);
#ifndef MR_AFFINE_ONLY
            work[i]=mirvar_mem(_MIPP_ mem1,i);
#endif
		}

        table_init(_MIPP_ pt,table);

#ifndef MR_AFFINE_ONLY
        epoint2_multi_norm(_MIPP_ MR_ECC_STORE_2M,work,table);
#endif

        nb=logb2(_MIPP_ mr_mip->w10);

        if ((n=logb2(_MIPP_ mr_mip->w9))>nb)
        {
            nb=n;
            epoint2_negate(_MIPP_ pt);
        }
        epoint2_set(_MIPP_ NULL,NULL,0,pt);

        for (i=nb-1;i>=0;)
        { /* 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_2M);
/* printf("n= %d nbs= %d nzs= %d \n",n,nbs,nzs); */
            for (j=0;j<nbs;j++)
            {
#ifndef MR_NOKOBLITZ
                if (mr_mip->KOBLITZ) frobenius(_MIPP_ pt);
                else
#endif
                    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++) 
                {
#ifndef MR_NOKOBLITZ
                    if (mr_mip->KOBLITZ) frobenius(_MIPP_ pt);
                    else
#endif
                        ecurve2_double(_MIPP_ pt);
                }
                i-=nzs;
            }
        }
/*
#ifndef MR_AFFINE_ONLY
        coord=mr_mip->coord;      switch to AFFINE coordinates 
        mr_mip->coord=MR_AFFINE;
#endif
*/
#ifdef MR_STATIC
/*        memset(mem,0,MR_ECP_RESERVE_A(MR_ECC_STORE_2M)); */
        memset(mem,0,MR_ECP_RESERVE(MR_ECC_STORE_2M));
#else
        ecp_memkill(_MIPP_ mem,MR_ECC_STORE_2M);
#endif