mrecn2_opt.c

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

    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_STR_SZ_2;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_WIN_SZ_2,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_WIN_SZ_2,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_STR_SZ_2*4)

int ecn2_mul4_gls_v(_MIPD_ big *a,ecn2 *FT,big *b,ecn2 *Q,zzn2 *psi,ecn2 *R)
{ 
    int i,j,nadds;
    ecn2 VT[2*MR_STR_SZ_2];
    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_STR_SZ_2;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_WIN_SZ_2,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,MR_WIN_SZ_2P,2,MR_WIN_SZ_2,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 win,ecn2 *P,ecn2 *T)
{
    int sz;

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

    sz=calc_n(win);

    MR_IN(216)

    ecn2_norm(_MIPP_ P);
    ecn2_copy(P,&T[0]);
    ecn2_dos(_MIPP_ win,T); 

    MR_OUT
}

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

int ecn2_mul2(_MIPD_ big a,ecn2 *FT,big b,ecn2 *Q,ecn2 *R)
{
    int i,j,nadds;
    ecn2 T[2*MR_STR_SZ_2];
    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_STR_SZ_2;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_WIN_SZ_2,Q,T);

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

    nadds=ecn2_muln_engine(_MIPP_ 1,MR_WIN_SZ_2P,1,MR_WIN_SZ_2,&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++)
        {
            if (i&bp)
                ecn2_add(_MIPP_ &table[1<<j],&table[i]);
            bp<<=1;
        }
    }
    mr_free(w.x.a);
    mr_free(w.x.b);
    mr_free(w.y.a);
    mr_free(w.y.b);

/* create the table */

    len=n->len;
    bptr=0;
    B->table=mr_alloc(_MIPP_ 4*len*(1<<window),sizeof(mr_small));

    for (i=0;i<(1<<window);i++)
    {
        for (j=0;j<len;j++) B->table[bptr++]=table[i].x.a->w[j];
        for (j=0;j<len;j++) B->table[bptr++]=table[i].x.b->w[j];

        for (j=0;j<len;j++) B->table[bptr++]=table[i].y.a->w[j];
        for (j=0;j<len;j++) B->table[bptr++]=table[i].y.b->w[j];

        mr_free(table[i].x.a);
        mr_free(table[i].x.b);
        mr_free(table[i].y.a);
        mr_free(table[i].y.b);
    }
        
    mr_free(table);  

    MR_OUT
    return TRUE;
}

void ecn2_brick_end(ebrick *B)
{
    mirkill(B->n);
    mirkill(B->b);
    mirkill(B->a);
    mr_free(B->table);  
}

#else

/* use precomputated table in ROM */

void ecn2_brick_init(ebrick *B,const mr_small* rom,big a,big b,big n,int window,int nb)
{
    B->table=rom;
    B->a=a; /* just pass a pointer */
    B->b=b;
    B->n=n;
    B->window=window;  /* 2^4=16  stored values */
    B->max=nb;
}

#endif

/*
void ecn2_mul_brick(_MIPD_ ebrick *B,big e,zzn2 *x,zzn2 *y)
{
    int i,j,t,len,maxsize,promptr;
    ecn2 w,z;
 
#ifdef MR_STATIC
    char mem[MR_BIG_RESERVE(10)];
#else
    char *mem;
#endif
#ifdef MR_OS_THREADS
    miracl *mr_mip=get_mip();
#endif

    if (size(e)<0) mr_berror(_MIPP_ MR_ERR_NEG_POWER);
    t=MR_ROUNDUP(B->max,B->window);
    
    MR_IN(116)

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

    if (logb2(_MIPP_ e) > B->max)
    {
        mr_berror(_MIPP_ MR_ERR_EXP_TOO_BIG);
        MR_OUT
        return;
    }

    ecurve_init(_MIPP_ B->a,B->b,B->n,MR_BEST);
    mr_mip->TWIST=TRUE;
  
#ifdef MR_STATIC
    memset(mem,0,MR_BIG_RESERVE(10));
#else
    mem=memalloc(_MIPP_ 10);
#endif

    w.x.a=mirvar_mem(_MIPP_  mem, 0);
    w.x.b=mirvar_mem(_MIPP_  mem, 1);
    w.y.a=mirvar_mem(_MIPP_  mem, 2);
    w.y.b=mirvar_mem(_MIPP_  mem, 3);  
    w.z.a=mirvar_mem(_MIPP_  mem, 4);
    w.z.b=mirvar_mem(_MIPP_  mem, 5);      
    w.marker=MR_EPOINT_INFINITY;
    z.x.a=mirvar_mem(_MIPP_  mem, 6);
    z.x.b=mirvar_mem(_MIPP_  mem, 7);
    z.y.a=mirvar_mem(_MIPP_  mem, 8);
    z.y.b=mirvar_mem(_MIPP_  mem, 9);       
    z.marker=MR_EPOINT_INFINITY;

    len=B->n->len;
    maxsize=4*(1<<B->window)*len;

    for (i=t-1;i>=0;i--)
    {
        j=recode(_MIPP_ e,t,B->window,i);
        ecn2_add(_MIPP_ &w,&w);
        if (j>0)
        {
            promptr=4*j*len;
            init_big_from_rom(z.x.a,len,B->table,maxsize,&promptr);
            init_big_from_rom(z.x.b,len,B->table,maxsize,&promptr);
            init_big_from_rom(z.y.a,len,B->table,maxsize,&promptr);
            init_big_from_rom(z.y.b,len,B->table,maxsize,&promptr);
            z.marker=MR_EPOINT_NORMALIZED;
            ecn2_add(_MIPP_ &z,&w);
        }
    }
    ecn2_norm(_MIPP_ &w);
    ecn2_getxy(&w,x,y);
#ifndef MR_STATIC
    memkill(_MIPP_ mem,10);
#else
    memset(mem,0,MR_BIG_RESERVE(10));
#endif
    MR_OUT
}
*/

void ecn2_mul_brick_gls(_MIPD_ ebrick *B,big *e,zzn2 *psi,zzn2 *x,zzn2 *y)
{
    int i,j,k,t,len,maxsize,promptr,se[2];
    ecn2 w,z;
 
#ifdef MR_STATIC
    char mem[MR_BIG_RESERVE(10)];
#else
    char *mem;
#endif
#ifdef MR_OS_THREADS
    miracl *mr_mip=get_mip();
#endif

    for (k=0;k<2;k++) se[k]=exsign(e[k]);

    t=MR_ROUNDUP(B->max,B->window);
    
    MR_IN(222)

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

    if (logb2(_MIPP_ e[0])>B->max || logb2(_MIPP_ e[1])>B->max)
    {
        mr_berror(_MIPP_ MR_ERR_EXP_TOO_BIG);
        MR_OUT
        return;
    }

    ecurve_init(_MIPP_ B->a,B->b,B->n,MR_BEST);
    mr_mip->TWIST=TRUE;
  
#ifdef MR_STATIC
    memset(mem,0,MR_BIG_RESERVE(10));
#else
    mem=memalloc(_MIPP_ 10);
#endif

    z.x.a=mirvar_mem(_MIPP_  mem, 0);
    z.x.b=mirvar_mem(_MIPP_  mem, 1);
    z.y.a=mirvar_mem(_MIPP_  mem, 2);
    z.y.b=mirvar_mem(_MIPP_  mem, 3);       
    z.marker=MR_EPOINT_INFINITY;

    w.x.a=mirvar_mem(_MIPP_  mem, 4);
    w.x.b=mirvar_mem(_MIPP_  mem, 5);
    w.y.a=mirvar_mem(_MIPP_  mem, 6);
    w.y.b=mirvar_mem(_MIPP_  mem, 7);  
#ifndef MR_AFFINE_ONLY
    w.z.a=mirvar_mem(_MIPP_  mem, 8);
    w.z.b=mirvar_mem(_MIPP_  mem, 9); 
#endif    
    w.marker=MR_EPOINT_INFINITY;

    len=B->n->len;
    maxsize=4*(1<<B->window)*len;

    for (i=t-1;i>=0;i--)
    {
        ecn2_add(_MIPP_ &w,&w);
        for (k=0;k<2;k++)
        {
            j=recode(_MIPP_ e[k],t,B->window,i);
            if (j>0)
            {
                promptr=4*j*len;
                init_big_from_rom(z.x.a,len,B->table,maxsize,&promptr);
                init_big_from_rom(z.x.b,len,B->table,maxsize,&promptr);
                init_big_from_rom(z.y.a,len,B->table,maxsize,&promptr);
                init_big_from_rom(z.y.b,len,B->table,maxsize,&promptr);
                z.marker=MR_EPOINT_NORMALIZED;
                if (k==1) ecn2_psi(_MIPP_ psi,&z);
                if (se[k]==PLUS) ecn2_add(_MIPP_ &z,&w);
                else             ecn2_sub(_MIPP_ &z,&w);
            }
        }      
    }
    ecn2_norm(_MIPP_ &w);
    ecn2_getxy(&w,x,y);
#ifndef MR_STATIC
    memkill(_MIPP_ mem,10);
#else
    memset(mem,0,MR_BIG_RESERVE(10));
#endif
    MR_OUT
}