mrecn2.c

比较新的功能强大的rsa算法源代码,方便使用.

    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_PRE_2 (14+4*MR_MAX_M_T_S)

static void ecn2_pre(_MIPD_ int sz,BOOL norm,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_MAX_M_T_S],e[MR_MAX_M_T_S];
    char mem[MR_BIG_RESERVE(MR_PRE_2)];       
 	memset(mem, 0, MR_BIG_RESERVE(MR_PRE_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);
    zzn2_sqr(_MIPP_ &W,&A);
    zzn2_sub(_MIPP_ &A,&(PT[0].x),&A);
    zzn2_sub(_MIPP_ &A,&(PT[0].x),&A);
    zzn2_sub(_MIPP_ &(PT[0].x),&A,&B);
    zzn2_mul(_MIPP_ &B,&W,&B);
    zzn2_sub(_MIPP_ &B,&(PT[0].y),&B);

    zzn2_sub(_MIPP_ &B,&(PT[0].y),&T);
    zzn2_mul(_MIPP_ &T,&d[1],&T);

    zzn2_sqr(_MIPP_ &T,&(PT[1].x));
    zzn2_sub(_MIPP_ &(PT[1].x),&A,&(PT[1].x));
    zzn2_sub(_MIPP_ &(PT[1].x),&(PT[0].x),&(PT[1].x));

    zzn2_sub(_MIPP_ &A,&(PT[1].x),&(PT[1].y));
    zzn2_mul(_MIPP_ &(PT[1].y),&T,&(PT[1].y));
    zzn2_sub(_MIPP_ &(PT[1].y),&B,&(PT[1].y));

    for (i=2;i<sz;i++)
    {
        zzn2_sub(_MIPP_ &(PT[i-1].y),&B,&T);
        zzn2_mul(_MIPP_ &T,&d[i],&T);

        zzn2_sqr(_MIPP_ &T,&(PT[i].x));
        zzn2_sub(_MIPP_ &(PT[i].x),&A,&(PT[i].x));
        zzn2_sub(_MIPP_ &(PT[i].x),&(PT[i-1].x),&(PT[i].x));

        zzn2_sub(_MIPP_ &A,&(PT[i].x),&(PT[i].y));
        zzn2_mul(_MIPP_ &(PT[i].y),&T,&(PT[i].y));
        zzn2_sub(_MIPP_ &(PT[i].y),&B,&(PT[i].y));
    }
    for (i=0;i<sz;i++) PT[i].marker=MR_EPOINT_NORMALIZED;

#ifndef MR_STATIC
    memkill(_MIPP_ mem, 14+4*sz);
    mr_free(d); mr_free(e);
#else
    memset(mem, 0, MR_BIG_RESERVE(MR_PRE_2));
#endif
}

#ifndef MR_DOUBLE_BIG
#define MR_MUL_RESERVE (1+4*MR_ECC_STORE_N2)
#else
#define MR_MUL_RESERVE (2+4*MR_ECC_STORE_N2)
#endif

int ecn2_mul(_MIPD_ big k,ecn2 *P)
{
    int i,j,nb,n,nbs,nzs,nadds;
    big h;
    ecn2 T[MR_ECC_STORE_N2];
#ifdef MR_OS_THREADS
    miracl *mr_mip=get_mip();
#endif

#ifndef MR_STATIC
    char *mem = memalloc(_MIPP_ MR_MUL_RESERVE);
#else
    char mem[MR_BIG_RESERVE(MR_MUL_RESERVE)];
    memset(mem, 0, MR_BIG_RESERVE(MR_MUL_RESERVE));
#endif

    j=0;
#ifndef MR_DOUBLE_BIG
    h=mirvar_mem(_MIPP_ mem, j++);
#else
    h=mirvar_mem(_MIPP_ mem, j); j+=2;
#endif
    for (i=0;i<MR_ECC_STORE_N2;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++);
    }

    MR_IN(207)

    ecn2_norm(_MIPP_ P);

	nadds=0;
    premult(_MIPP_ k,3,h);
    ecn2_copy(P,&T[0]);
    ecn2_pre(_MIPP_ MR_ECC_STORE_N2,TRUE,T);
    nb=logb2(_MIPP_ h);

    ecn2_zero(P);

    for (i=nb-1;i>=1;)
    {
        if (mr_mip->user!=NULL) (*mr_mip->user)();
        n=mr_naf_window(_MIPP_ k,h,i,&nbs,&nzs,MR_ECC_STORE_N2);
 
        for (j=0;j<nbs;j++) ecn2_add(_MIPP_ P,P);
       
        if (n>0) {nadds++; ecn2_add(_MIPP_ &T[n/2],P);}
        if (n<0) {nadds++; ecn2_sub(_MIPP_ &T[(-n)/2],P);}
        i-=nbs;
        if (nzs)
        {
            for (j=0;j<nzs;j++) ecn2_add(_MIPP_ P,P);
            i-=nzs;
        }
    }

    ecn2_norm(_MIPP_ P);
    MR_OUT

#ifndef MR_STATIC
    memkill(_MIPP_ mem, MR_MUL_RESERVE);
#else
    memset(mem, 0, MR_BIG_RESERVE(MR_MUL_RESERVE));
#endif
	return nadds;
}

/* Double addition, using Joint Sparse Form */
/* R=aP+bQ */

#define MR_MUL2_JSF_RESERVE 20

int ecn2_mul2_jsf(_MIPD_ big a,ecn2 *P,big b,ecn2 *Q,ecn2 *R)
{
    int e1,h1,e2,h2,bb,nadds;
    ecn2 P1,P2,PS,PD;
    big c,d,e,f;
#ifdef MR_OS_THREADS