mrecn2.c

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

    t2.b = mr_mip->w11; 
    lam.a = mr_mip->w12; 
    lam.b = mr_mip->w13;    

    zzn2_copy(&(P->x),&t2);
    zzn2_sub(_MIPP_ &t2,&(Q->x),&t2);
    zzn2_inv(_MIPP_ &t2);   /* only one inverse required */
    zzn2_add(_MIPP_ &(P->x),&(Q->x),&(PP->x));
    zzn2_copy(&(PP->x),&(PM->x));

    zzn2_copy(&(P->y),&t1);
    zzn2_sub(_MIPP_ &t1,&(Q->y),&t1);
    zzn2_copy(&t1,&lam);
    zzn2_mul(_MIPP_ &lam,&t2,&lam);
    zzn2_copy(&lam,&t1);
    zzn2_sqr(_MIPP_ &t1,&t1);
    zzn2_sub(_MIPP_ &t1,&(PP->x),&(PP->x));
    zzn2_copy(&(Q->x),&(PP->y));
    zzn2_sub(_MIPP_ &(PP->y),&(PP->x),&(PP->y));
    zzn2_mul(_MIPP_ &(PP->y),&lam,&(PP->y));
    zzn2_sub(_MIPP_ &(PP->y),&(Q->y),&(PP->y));

    zzn2_copy(&(P->y),&t1);
    zzn2_add(_MIPP_ &t1,&(Q->y),&t1);
    zzn2_copy(&t1,&lam);
    zzn2_mul(_MIPP_ &lam,&t2,&lam);
    zzn2_copy(&lam,&t1);
    zzn2_sqr(_MIPP_ &t1,&t1);
    zzn2_sub(_MIPP_ &t1,&(PM->x),&(PM->x));
    zzn2_copy(&(Q->x),&(PM->y));
    zzn2_sub(_MIPP_ &(PM->y),&(PM->x),&(PM->y));
    zzn2_mul(_MIPP_ &(PM->y),&lam,&(PM->y));
    zzn2_add(_MIPP_ &(PM->y),&(Q->y),&(PM->y));

    PP->marker=MR_EPOINT_NORMALIZED;
    PM->marker=MR_EPOINT_NORMALIZED;

    return TRUE;
}

BOOL ecn2_add3(_MIPD_ ecn2 *Q,ecn2 *P,zzn2 *lam,zzn2 *ex1,zzn2 *ex2)
{ /* P+=Q */
    BOOL Doubling=FALSE;
    BOOL twist;
    int iA;
    zzn2 t1,t2,t3;
    zzn2 Yzzz;
 
#ifdef MR_OS_THREADS
    miracl *mr_mip=get_mip();
#endif

    t1.a = mr_mip->w8;
    t1.b = mr_mip->w9; 
    t2.a = mr_mip->w10; 
    t2.b = mr_mip->w11; 
    t3.a = mr_mip->w12; 
    t3.b = mr_mip->w13; 
    Yzzz.a = mr_mip->w3;
    Yzzz.b = mr_mip->w4;

    twist=mr_mip->TWIST;
    if (mr_mip->ERNUM) return FALSE;

    if (P->marker==MR_EPOINT_INFINITY)
    {
        ecn2_copy(Q,P);
        return Doubling;
    }
    if (Q->marker==MR_EPOINT_INFINITY) return Doubling;

    MR_IN(205)

    if (Q!=P && Q->marker==MR_EPOINT_GENERAL)
    { /* Sorry, this code is optimized for mixed addition only */
        mr_berror(_MIPP_ MR_ERR_BAD_PARAMETERS);
        MR_OUT
        return Doubling;
    }
#ifndef MR_AFFINE_ONLY
    if (mr_mip->coord==MR_AFFINE)
    {
#endif
        if (!zzn2_compare(&(P->x),&(Q->x)))
        {
            zzn2_copy(&(P->y),&t1);
            zzn2_sub(_MIPP_ &t1,&(Q->y),&t1);
            zzn2_copy(&(P->x),&t2);
            zzn2_sub(_MIPP_ &t2,&(Q->x),&t2);
            zzn2_copy(&t1,lam);
            zzn2_inv(_MIPP_ &t2);
            zzn2_mul(_MIPP_ lam,&t2,lam);

            zzn2_add(_MIPP_ &(P->x),&(Q->x),&(P->x));
            zzn2_copy(lam,&t1);
            zzn2_sqr(_MIPP_ &t1,&t1);
            zzn2_sub(_MIPP_ &t1,&(P->x),&(P->x));
           
            zzn2_copy(&(Q->x),&(P->y));
            zzn2_sub(_MIPP_ &(P->y),&(P->x),&(P->y));
            zzn2_mul(_MIPP_ &(P->y),lam,&(P->y));
            zzn2_sub(_MIPP_ &(P->y),&(Q->y),&(P->y));
        }
        else
        {   
            if (!zzn2_compare(&(P->y),&(Q->y)) || zzn2_iszero(&(P->y)))
            {
                ecn2_zero(P);
                zzn2_from_int(_MIPP_ 1,lam);
                MR_OUT
                return Doubling;
            }
            zzn2_copy(&(P->x),&t1);
            zzn2_copy(&(P->x),&t2);
            zzn2_copy(&(P->x),lam);
            zzn2_sqr(_MIPP_ lam,lam);
            zzn2_add(_MIPP_ lam,lam,&t3);
            zzn2_add(_MIPP_ lam,&t3,lam);

            if (mr_abs(mr_mip->Asize)<MR_TOOBIG) zzn2_from_int(_MIPP_ mr_mip->Asize,&t3);
            else zzn2_from_zzn(mr_mip->A,&t3);
        
            if (twist)
            {
                zzn2_txx(_MIPP_ &t3);
                zzn2_txx(_MIPP_ &t3);
            }
            zzn2_add(_MIPP_ lam,&t3,lam);
            zzn2_add(_MIPP_ &(P->y),&(P->y),&t3);
            zzn2_inv(_MIPP_ &t3);
            zzn2_mul(_MIPP_ lam,&t3,lam);

            zzn2_add(_MIPP_ &t2,&(P->x),&t2);
            zzn2_copy(lam,&(P->x));
            zzn2_sqr(_MIPP_ &(P->x),&(P->x));
            zzn2_sub(_MIPP_ &(P->x),&t2,&(P->x));
            zzn2_sub(_MIPP_ &t1,&(P->x),&t1);
            zzn2_mul(_MIPP_ &t1,lam,&t1);
            zzn2_sub(_MIPP_ &t1,&(P->y),&(P->y));
        }

        P->marker=MR_EPOINT_NORMALIZED;
        MR_OUT
        return Doubling;
#ifndef MR_AFFINE_ONLY
    }

    if (Q==P) Doubling=TRUE;

    zzn2_copy(&(Q->x),&t3);
    zzn2_copy(&(Q->y),&Yzzz);

    if (!Doubling)
    {
        if (P->marker!=MR_EPOINT_NORMALIZED)
        {
            zzn2_sqr(_MIPP_ &(P->z),&t1); /* 1S */
            zzn2_mul(_MIPP_ &t3,&t1,&t3);         /* 1M */
            zzn2_mul(_MIPP_ &t1,&(P->z),&t1);     /* 1M */
            zzn2_mul(_MIPP_ &Yzzz,&t1,&Yzzz);     /* 1M */
        }
        if (zzn2_compare(&t3,&(P->x)))
        {
            if (!zzn2_compare(&Yzzz,&(P->y)) || zzn2_iszero(&(P->y)))
            {
                ecn2_zero(P);
                zzn2_from_int(_MIPP_ 1,lam);
                MR_OUT
                return Doubling;
            }
            else Doubling=TRUE;
        }
    }
    if (!Doubling)
    { /* Addition */
        zzn2_sub(_MIPP_ &t3,&(P->x),&t3);
        zzn2_sub(_MIPP_ &Yzzz,&(P->y),lam);
        if (P->marker==MR_EPOINT_NORMALIZED) zzn2_copy(&t3,&(P->z));
        else zzn2_mul(_MIPP_ &(P->z),&t3,&(P->z)); /* 1M */
        zzn2_sqr(_MIPP_ &t3,&t1);                  /* 1S */
        zzn2_mul(_MIPP_ &t1,&t3,&Yzzz);            /* 1M */
        zzn2_mul(_MIPP_ &t1,&(P->x),&t1);          /* 1M */
        zzn2_copy(&t1,&t3);
        zzn2_add(_MIPP_ &t3,&t3,&t3);
        zzn2_sqr(_MIPP_ lam,&(P->x));              /* 1S */
        zzn2_sub(_MIPP_ &(P->x),&t3,&(P->x));
        zzn2_sub(_MIPP_ &(P->x),&Yzzz,&(P->x));
        zzn2_sub(_MIPP_ &t1,&(P->x),&t1);
        zzn2_mul(_MIPP_ &t1,lam,&t1);              /* 1M */
        zzn2_mul(_MIPP_ &Yzzz,&(P->y),&Yzzz);      /* 1M */
        zzn2_sub(_MIPP_ &t1,&Yzzz,&(P->y));

/*
        zzn2_sub(_MIPP_ &(P->x),&t3,&t1);     
        zzn2_sub(_MIPP_ &(P->y),&Yzzz,lam); 
        if (P->marker==MR_EPOINT_NORMALIZED) zzn2_copy(&t1,&(P->z));
        else zzn2_mul(_MIPP_ &(P->z),&t1,&(P->z)); 
        zzn2_sqr(_MIPP_ &t1,&t2);             
        zzn2_add(_MIPP_ &(P->x),&t3,&t3);     
        zzn2_mul(_MIPP_ &t3,&t2,&t3);         
        zzn2_sqr(_MIPP_ lam,&(P->x));        
        zzn2_sub(_MIPP_ &(P->x),&t3,&(P->x));

        zzn2_mul(_MIPP_ &t2,&t1,&t2);         
        zzn2_add(_MIPP_ &(P->x),&(P->x),&t1);
        zzn2_sub(_MIPP_ &t3,&t1,&t3);
        zzn2_mul(_MIPP_ &t3,lam,&t3);         

        zzn2_add(_MIPP_ &(P->y),&Yzzz,&t1);

        zzn2_mul(_MIPP_ &t2,&t1,&t2);         
        zzn2_sub(_MIPP_ &t3,&t2,&(P->y));
        zzn2_div2(_MIPP_ &(P->y));
*/
    }
    else
    { /* doubling */
        zzn2_sqr(_MIPP_ &(P->y),&t3);  /* 1S */

        iA=mr_mip->Asize;
        if (iA!=0)
        {
            if (P->marker==MR_EPOINT_NORMALIZED) zzn2_from_int(_MIPP_ 1,&t1);
            else zzn2_sqr(_MIPP_ &(P->z),&t1);  /* 1S */
            if (ex2!=NULL) zzn2_copy(&t1,ex2);

            if (iA==-3)
            {
                if (twist) zzn2_txx(_MIPP_ &t1);
                zzn2_sub(_MIPP_ &(P->x),&t1,lam);
                zzn2_add(_MIPP_ &t1,&(P->x),&t1);
                zzn2_mul(_MIPP_ lam,&t1,lam);        /* 1M */
                zzn2_add(_MIPP_ lam,lam,&t2);
                zzn2_add(_MIPP_ lam,&t2,lam);
            }
            else
            {
                zzn2_sqr(_MIPP_ &(P->x),lam);  /* 1S */
                zzn2_add(_MIPP_ lam,lam,&t2);         
                zzn2_add(_MIPP_ lam,&t2,lam);      
          
                if (twist) zzn2_txx(_MIPP_ &t1);    
                zzn2_sqr(_MIPP_ &t1,&t1);          /* 1S */ 
             
                if (iA!=1)
                { /* optimized for iA=1 case */
                    if (iA<MR_TOOBIG) zzn2_imul(_MIPP_ &t1,iA,&t1);
                    else zzn2_smul(_MIPP_ &t1,mr_mip->A,&t1);
                }
                zzn2_add(_MIPP_ lam,&t1,lam);
            }
        }
        else
        {
            zzn2_sqr(_MIPP_ &(P->x),lam);  /* 1S */
            zzn2_add(_MIPP_ lam,lam,&t2);
            zzn2_add(_MIPP_ lam,&t2,lam);
        }
        zzn2_mul(_MIPP_ &(P->x),&t3,&t1);    /* 1M */
        zzn2_add(_MIPP_ &t1,&t1,&t1);
        zzn2_add(_MIPP_ &t1,&t1,&t1);
        zzn2_sqr(_MIPP_ lam,&(P->x));        /* 1S */
        zzn2_add(_MIPP_ &t1,&t1,&t2);
        zzn2_sub(_MIPP_ &(P->x),&t2,&(P->x));
        if (P->marker==MR_EPOINT_NORMALIZED) zzn2_copy(&(P->y),&(P->z));
        else zzn2_mul(_MIPP_ &(P->z),&(P->y),&(P->z));   /* 1M */
        zzn2_add(_MIPP_ &(P->z),&(P->z),&(P->z));
        zzn2_add(_MIPP_ &t3,&t3,&t3);
        if (ex1!=NULL) zzn2_copy(&t3,ex1);
        zzn2_sqr(_MIPP_ &t3,&t3);                  /* 1S */
        zzn2_add(_MIPP_ &t3,&t3,&t3);
        zzn2_sub(_MIPP_ &t1,&(P->x),&t1);
        zzn2_mul(_MIPP_ lam,&t1,&(P->y));          /* 1M */  
        zzn2_sub(_MIPP_ &(P->y),&t3,&(P->y));
    }

    P->marker=MR_EPOINT_GENERAL;
    MR_OUT
    return Doubling;
#endif
}

/* Dahmen, Okeya and Schepers "Affine Precomputation with Sole Inversion in Elliptic Curve Cryptography" */
/* Precomputes table into T. Assumes first P has been copied to P[0], then calculates 3P, 5P, 7P etc. into T */

#define MR_DOS_2 (14+4*MR_ECC_STORE_N2_PRECOMP)

static void ecn2_dos(_MIPD_ int sz,ecn2 *PT)
{
    BOOL twist;
    int i,j;
    zzn2 A,B,C,D,E,T,W;

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

#ifndef MR_STATIC
    zzn2 *d=(zzn2 *)mr_alloc(_MIPP_ sz,sizeof(zzn2));
    zzn2 *e=(zzn2 *)mr_alloc(_MIPP_ sz,sizeof(zzn2));
    char *mem = memalloc(_MIPP_ 14+4*sz);
#else
    zzn2 d[MR_ECC_STORE_N2_PRECOMP],e[MR_ECC_STORE_N2_PRECOMP];
    char mem[MR_BIG_RESERVE(MR_DOS_2)];       
 	memset(mem, 0, MR_BIG_RESERVE(MR_DOS_2));   
#endif

    twist=mr_mip->TWIST;
    j=0;

    A.a= mirvar_mem(_MIPP_ mem, j++);
    A.b= mirvar_mem(_MIPP_ mem, j++);
    B.a= mirvar_mem(_MIPP_ mem, j++);
    B.b= mirvar_mem(_MIPP_ mem, j++);
    C.a= mirvar_mem(_MIPP_ mem, j++);
    C.b= mirvar_mem(_MIPP_ mem, j++);
    D.a= mirvar_mem(_MIPP_ mem, j++);
    D.b= mirvar_mem(_MIPP_ mem, j++);
    E.a= mirvar_mem(_MIPP_ mem, j++);
    E.b= mirvar_mem(_MIPP_ mem, j++);
    T.a= mirvar_mem(_MIPP_ mem, j++);
    T.b= mirvar_mem(_MIPP_ mem, j++);
    W.a= mirvar_mem(_MIPP_ mem, j++);
    W.b= mirvar_mem(_MIPP_ mem, j++);

    for (i=0;i<sz;i++)
    {
        d[i].a= mirvar_mem(_MIPP_ mem, j++);
        d[i].b= mirvar_mem(_MIPP_ mem, j++);
        e[i].a= mirvar_mem(_MIPP_ mem, j++);
        e[i].b= mirvar_mem(_MIPP_ mem, j++);
    }

    zzn2_add(_MIPP_ &(PT[0].y),&(PT[0].y),&d[0]);   /* 1. d_0=2.y */
    zzn2_sqr(_MIPP_ &d[0],&C);                      /* 2. C=d_0^2 */

    zzn2_sqr(_MIPP_ &(PT[0].x),&T);
    zzn2_add(_MIPP_ &T,&T,&A);
    zzn2_add(_MIPP_ &T,&A,&T);
           
    if (mr_abs(mr_mip->Asize)<MR_TOOBIG) zzn2_from_int(_MIPP_ mr_mip->Asize,&A);
    else zzn2_from_zzn(mr_mip->A,&A);
        
    if (twist)
    {
        zzn2_txx(_MIPP_ &A);
        zzn2_txx(_MIPP_ &A);
    }
    zzn2_add(_MIPP_ &A,&T,&A);             /* 3. A=3x^2+a */
    zzn2_copy(&A,&W);

    zzn2_add(_MIPP_ &C,&C,&B);
    zzn2_add(_MIPP_ &B,&C,&B);
    zzn2_mul(_MIPP_ &B,&(PT[0].x),&B);     /* 4. B=3C.x */

    zzn2_sqr(_MIPP_ &A,&d[1]);
    zzn2_sub(_MIPP_ &d[1],&B,&d[1]);       /* 5. d_1=A^2-B */

    zzn2_sqr(_MIPP_ &d[1],&E);             /* 6. E=d_1^2 */
    
    zzn2_mul(_MIPP_ &B,&E,&B);             /* 7. B=E.B */

    zzn2_sqr(_MIPP_ &C,&C);                /* 8. C=C^2 */

    zzn2_mul(_MIPP_ &E,&d[1],&D);          /* 9. D=E.d_1 */

    zzn2_mul(_MIPP_ &A,&d[1],&A);
    zzn2_add(_MIPP_ &A,&C,&A);
    zzn2_negate(_MIPP_ &A,&A);             /* 10. A=-d_1*A-C */

    zzn2_add(_MIPP_ &D,&D,&T);
    zzn2_sqr(_MIPP_ &A,&d[2]);
    zzn2_sub(_MIPP_ &d[2],&T,&d[2]);
    zzn2_sub(_MIPP_ &d[2],&B,&d[2]);       /* 11. d_2=A^2-2D-B */

    if (sz>3)
    {
        zzn2_sqr(_MIPP_ &d[2],&E);             /* 12. E=d_2^2 */

        zzn2_add(_MIPP_ &T,&D,&T);
        zzn2_add(_MIPP_ &T,&B,&T);
        zzn2_mul(_MIPP_ &T,&E,&B);             /* 13. B=E(B+3D) */
        
        zzn2_add(_MIPP_ &A,&A,&T);
        zzn2_add(_MIPP_ &C,&T,&C);
        zzn2_mul(_MIPP_ &C,&D,&C);             /* 14. C=D(2A+C) */

        zzn2_mul(_MIPP_ &d[2],&E,&D);          /* 15. D=E.d_2 */

        zzn2_mul(_MIPP_ &A,&d[2],&A);
        zzn2_add(_MIPP_ &A,&C,&A);
        zzn2_negate(_MIPP_ &A,&A);             /* 16. A=-d_2*A-C */

 
        zzn2_sqr(_MIPP_ &A,&d[3]);
        zzn2_sub(_MIPP_ &d[3],&D,&d[3]);
        zzn2_sub(_MIPP_ &d[3],&B,&d[3]);       /* 17. d_3=A^2-D-B */

        for (i=4;i<sz;i++)
        {
            zzn2_sqr(_MIPP_ &d[i-1],&E);       /* 19. E=d(i-1)^2 */
            zzn2_mul(_MIPP_ &B,&E,&B);         /* 20. B=E.B */
            zzn2_mul(_MIPP_ &C,&D,&C);         /* 21. C=D.C */
            zzn2_mul(_MIPP_ &E,&d[i-1],&D);    /* 22. D=E.d(i-1) */

            zzn2_mul(_MIPP_ &A,&d[i-1],&A);
            zzn2_add(_MIPP_ &A,&C,&A);
            zzn2_negate(_MIPP_ &A,&A);         /* 23. A=-d(i-1)*A-C */

            zzn2_sqr(_MIPP_ &A,&d[i]);
            zzn2_sub(_MIPP_ &d[i],&D,&d[i]);
            zzn2_sub(_MIPP_ &d[i],&B,&d[i]);   /* 24. d(i)=A^2-D-B */
        }
    }

    zzn2_copy(&d[0],&e[0]);
    for (i=1;i<sz;i++)
        zzn2_mul(_MIPP_ &e[i-1],&d[i],&e[i]);
       
    zzn2_copy(&e[sz-1],&A);
    zzn2_inv(_MIPP_ &A);

    for (i=sz-1;i>0;i--)
    {
        zzn2_copy(&d[i],&B);
        zzn2_mul(_MIPP_ &e[i-1],&A,&d[i]);  
        zzn2_mul(_MIPP_ &A,&B,&A);
    }
    zzn2_copy(&A,&d[0]);

    for (i=1;i<sz;i++)
    {
        zzn2_sqr(_MIPP_ &e[i-1],&T);
        zzn2_mul(_MIPP_ &d[i],&T,&d[i]); /** */
    }

    zzn2_mul(_MIPP_ &W,&d[0],&W);