mrec2m.c

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

#ifndef MR_AFFINE_ONLY
        memkill(_MIPP_ mem1,MR_ECC_STORE_2M);
/*        mr_mip->coord=coord; */
#endif

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

        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) > 0)
        { /* add/subtract method */
            if (mr_mip->user!=NULL) (*mr_mip->user)();

            ecurve2_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) 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);
        }
        ecp_memkill(_MIPP_ mem,1);
    }
#endif
#endif
    epoint2_norm(_MIPP_ pt);
    MR_OUT
}

#ifndef MR_NO_ECC_MULTIADD
#ifndef MR_STATIC

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;
#ifdef MR_OS_THREADS
    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]=epoint_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 */
    
#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;
            }
            ecurve2_double(_MIPP_ w);
            if (ea!=0) ecurve2_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

void ecurve2_mult2(_MIPD_ big e,epoint *p,big ea,epoint *pa,epoint *pt)
{ /* pt=e*p+ea*pa; */
    int e1,h1,e2,h2,n,nb;
    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
#ifndef MR_AFFINE_ONLY
    big work[2];
    work[0]=mr_mip->w14;
    work[1]=mr_mip->w15;
#endif
    if (mr_mip->ERNUM) return;

    MR_IN(135)

    if (size(e)==0) 
    {
        ecurve2_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);

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

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

#ifdef MR_NOKOBLITZ
    mr_jsf(_MIPP_ mr_mip->w9,mr_mip->w12,mr_mip->w10,mr_mip->w9,mr_mip->w13,mr_mip->w12);
#else
    if (mr_mip->KOBLITZ)
    {
        prepare_naf(_MIPP_ mr_mip->w9,mr_mip->w10,mr_mip->w9);
        prepare_naf(_MIPP_ mr_mip->w12,mr_mip->w13,mr_mip->w12);
    }
    else
        mr_jsf(_MIPP_ mr_mip->w9,mr_mip->w12,mr_mip->w10,mr_mip->w9,mr_mip->w13,mr_mip->w12);
#endif

    nb=logb2(_MIPP_ mr_mip->w10);
    if ((n=logb2(_MIPP_ mr_mip->w13))>nb) nb=n;
    if ((n=logb2(_MIPP_ mr_mip->w9))>nb) nb=n;
    if ((n=logb2(_MIPP_ mr_mip->w12))>nb) nb=n;

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

    expb2(_MIPP_ nb-1,mr_mip->w11);

    epoint2_copy(p1,ps[0]);
    ecurve2_add(_MIPP_ p2,ps[0]);                    /* ps=p1+p2 */
    epoint2_copy(p1,ps[1]);
    ecurve2_sub(_MIPP_ p2,ps[1]);                    /* pd=p1-p2 */

#ifndef MR_AFFINE_ONLY
    epoint2_multi_norm(_MIPP_ 2,work,ps);
#endif
    while (size(mr_mip->w11) > 0)
    { /* add/subtract method */
        if (mr_mip->user!=NULL) (*mr_mip->user)();
#ifndef MR_NOKOBLITZ
        if (mr_mip->KOBLITZ) frobenius(_MIPP_ pt);
        else
#endif            
            ecurve2_double(_MIPP_ pt);

        e1=h1=e2=h2=0;
        if (mr_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 (mr_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 (mr_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 (mr_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[0],pt);
                    else       ecurve2_add(_MIPP_ ps[1],pt);
                }
                else
                {
                    if (h2==1) ecurve2_sub(_MIPP_ ps[1],pt);
                    else       ecurve2_sub(_MIPP_ ps[0],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);
    }
    ecp_memkill(_MIPP_ mem,4);

    MR_OUT
}

#endif

/*   Routines to implement comb 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 Elliptic Curve Digital Signature Standard (ECS) for example.
 *
 *   See "Handbook of Applied Cryptography"
 */

#ifndef MR_STATIC

BOOL ebrick2_init(_MIPD_ ebrick2 *B,big x,big y,big a2,big a6,int m,int a,int b,int c,int window,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           *
   * 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;
    epoint **table;
    epoint *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(136)

#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(epoint *));
    
    if (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;
    }
 
    if (m<0) m=-m;  /* if it is supersingular */

    w=epoint_init(_MIPPO_ );
    epoint2_set(_MIPP_ x,y,0,w);

    table[0]=epoint_init(_MIPPO_ );
    table[1]=epoint_init(_MIPPO_ );
    epoint2_copy(w,table[1]);
    for (j=0;j<t;j++)
        ecurve2_double(_MIPP_ w);

    k=1;
    for (i=2;i<(1<<window);i++)
    {
        table[i]=epoint_init(_MIPPO_ );
        if (i==(1<<k))
        {
            k++;
            epoint2_copy(w,table[i]);
            
            for (j=0;j<t;j++)
                ecurve2_double(_MIPP_ w);
            continue;
        }
        bp=1;
        for (j=0;j<k;j++)
        {
            if (i&bp)
                ecurve2_add(_MIPP_ table[1<<j],table[i]);
            bp<<=1;
        }
    }

    epoint_free(w);

/* create the table */

    len=MR_ROUNDUP(m,MIRACL);
    bptr=0;
    B->table=mr_alloc(_MIPP_ 2*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->w[j];
        for (j=0;j<len;j++)
            B->table[bptr++]=table[i]->Y->w[j];

        epoint_free(table[i]);
    }
        
    mr_free(table);  

    MR_OUT
    return TRUE;
}

void ebrick2_end(ebrick2 *B)
{
    mirkill(B->a2);
    mirkill(B->a6);
    mr_free(B->table);  
}

#else

/* use precomputated table in ROM - use romaker2.c to create the table, and ecdh2m*.c 
   for an example of use */

void ebrick2_init(ebrick2 *B,const mr_small* rom,big a2,big a6,int m,int a,int b,int c,int window,int nb)
{
    B->table=rom;
    B->a2=a2; /* just pass a pointer */
    B->a6=a6;
    B->m=m;
    B->a=a;
    B->b=b;
    B->c=c;
    B->window=window;  /* 2^4=16  stored values */
    B->max=nb;
}

#endif

int mul2_brick(_MIPD_ ebrick2 *B,big e,big x,big y)
{
    int i,j,t,d,m,len,maxsize,promptr;
    epoint *w,*z;
 
#ifdef MR_STATIC
    char mem[MR_ECP_RESERVE(2)];
#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 0;
    }
#endif

    if (logb2(_MIPP_ e) > B->max)
    {
        mr_berror(_MIPP_ MR_ERR_EXP_TOO_BIG);
        MR_OUT
        return 0;
    }
    if (!ecurve2_init(_MIPP_ B->m,B->a,B->b,B->c,B->a2,B->a6,FALSE,MR_BEST))
    {
        MR_OUT
        return 0;
    }

#ifdef MR_STATIC
    memset(mem,0,MR_ECP_RESERVE(2));
#else
    mem=ecp_memalloc(_MIPP_ 2);
#endif
    w=epoint_init_mem(_MIPP_ mem,0);
    z=epoint_init_mem(_MIPP_ mem,1);

    m=B->m;
    if (m<0) m=-m;

    len=MR_ROUNDUP(m,MIRACL);
    maxsize=2*(1<<B->window)*len;

    j=recode(_MIPP_ e,t,B->window,t-1);
    if (j>0)
    {
        promptr=2*j*len;
        init_point_from_rom(w,len,B->table,maxsize,&promptr);
    }

    for (i=t-2;i>=0;i--)
    {
        j=recode(_MIPP_ e,t,B->window,i);
        ecurve2_double(_MIPP_ w);
        if (j>0)
        {
            promptr=2*j*len;
            init_point_from_rom(z,len,B->table,maxsize,&promptr);
            ecurve2_add(_MIPP_ z,w);
        }
    }

    d=epoint2_get(_MIPP_ w,x,y);
#ifndef MR_STATIC
    ecp_memkill(_MIPP_ mem,2);
#else
    memset(mem,0,MR_ECP_RESERVE(2));
#endif
    MR_OUT
    return d;
}

#endif