mrcurve.c

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

#ifndef MR_ALWAYS_BINARY
    if (mr_mip->base==mr_mip->base2)
    {
#endif
        if (mr_compare(mr_mip->w10,mr_mip->w13)>=0) bb=logb2(_MIPP_ mr_mip->w10)-1;
        else                                        bb=logb2(_MIPP_ mr_mip->w13)-1;

        while (bb>=0) /* for the simple NAF, this should be 1 */
        {
            if (mr_mip->user!=NULL) (*mr_mip->user)();
            ecurve_double(_MIPP_ pt);

            e1=h1=e2=h2=0;
            if (mr_testbit(_MIPP_ mr_mip->w9,bb)) e2=1;
            if (mr_testbit(_MIPP_ mr_mip->w10,bb)) h2=1;
            if (mr_testbit(_MIPP_ mr_mip->w12,bb)) e1=1;
            if (mr_testbit(_MIPP_ mr_mip->w13,bb)) h1=1;

            if (e1!=h1)
            {
                if (e2==h2)
                {
                    if (h1==1) ecurve_add(_MIPP_ p1,pt);
                    else       ecurve_sub(_MIPP_ p1,pt);
                }
                else
                {
                    if (h1==1)
                    {
                        if (h2==1) ecurve_add(_MIPP_ ps[0],pt);
                        else       ecurve_add(_MIPP_ ps[1],pt);
                    }
                    else
                    {
                        if (h2==1) ecurve_sub(_MIPP_ ps[1],pt);
                        else       ecurve_sub(_MIPP_ ps[0],pt);
                    }
                }
            }
            else if (e2!=h2)
            {
                if (h2==1) ecurve_add(_MIPP_ p2,pt);
                else       ecurve_sub(_MIPP_ p2,pt);
            }
            bb-=1;
        }
#ifndef MR_ALWAYS_BINARY
    }
    else
    {
         if (mr_compare(mr_mip->w10,mr_mip->w13)>=0)
              expb2(_MIPP_ logb2(_MIPP_ mr_mip->w10)-1,mr_mip->w11);
         else expb2(_MIPP_ logb2(_MIPP_ mr_mip->w13)-1,mr_mip->w11);

        while (size(mr_mip->w11) > 0)    /* for the NAF, this should be 1 */
        { /* add/subtract method */
            if (mr_mip->user!=NULL) (*mr_mip->user)();

            ecurve_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) ecurve_add(_MIPP_ p1,pt);
                    else       ecurve_sub(_MIPP_ p1,pt);
                }
                else
                {
                    if (h1==1)
                    {
                        if (h2==1) ecurve_add(_MIPP_ ps[0],pt);
                        else       ecurve_add(_MIPP_ ps[1],pt);
                    }
                    else
                    {
                        if (h2==1) ecurve_sub(_MIPP_ ps[1],pt);
                        else       ecurve_sub(_MIPP_ ps[0],pt);
                    }
                }
            }
            else if (e2!=h2)
            {
                if (h2==1) ecurve_add(_MIPP_ p2,pt);
                else       ecurve_sub(_MIPP_ p2,pt);
            }

            subdiv(_MIPP_ mr_mip->w11,2,mr_mip->w11);
        }
    }
#endif
    ecp_memkill(_MIPP_ mem,4);
    MR_OUT
}

#endif

#else

/*   Twisted Inverted Edwards curves 

 *   Assumes Twisted Inverted Edward's equation x^2+Ay^2 = x^2.y^2 + B
 *   Assumes points are not of order 2 or 4
*/

static void epoint_getrhs(_MIPD_ big x,big y)
{ 
  /* find RHS=(x^2-B)/(x^2-A) */
#ifdef MR_OS_THREADS
    miracl *mr_mip=get_mip();
#endif
 
    nres_modmult(_MIPP_ x,x,mr_mip->w6);
    nres_modsub(_MIPP_ mr_mip->w6,mr_mip->B,y);  
    nres_modsub(_MIPP_ mr_mip->w6,mr_mip->A,mr_mip->w6);

    nres_moddiv(y,mr_mip->w6,y);
}

#ifndef MR_NOSUPPORT_COMPRESSION

BOOL epoint_x(_MIPD_ big x)
{ /* test if x is associated with a point on the   *
   * currently active curve                        */
    int j;

#ifdef MR_OS_THREADS
    miracl *mr_mip=get_mip();
#endif
    if (mr_mip->ERNUM) return FALSE;

    MR_IN(147)
    
    if (x==NULL) return FALSE;

    nres(_MIPP_ x,mr_mip->w2);
    epoint_getrhs(_MIPP_ mr_mip->w2,mr_mip->w7);

    if (size(mr_mip->w7)==0)
    {
        MR_OUT
        return TRUE;
    }

    redc(_MIPP_ mr_mip->w7,mr_mip->w4);
    j=jack(_MIPP_ mr_mip->w4,mr_mip->modulus);

    MR_OUT
    if (j==1) return TRUE;
    return FALSE;
}

#endif

BOOL epoint_set(_MIPD_ big x,big y,int cb,epoint *p)
{ /* initialise a point on active ecurve            *
   * if x or y == NULL, set to point at infinity    *
   * if x==y, a y co-ordinate is calculated - if    *
   * possible - and cb suggests LSB 0/1  of y       *
   * (which "decompresses" y). Otherwise, check     *
   * validity of given (x,y) point, ignoring cb.    *
   * Returns TRUE for valid point, otherwise FALSE. */
  
    BOOL valid;

#ifdef MR_OS_THREADS
    miracl *mr_mip=get_mip();
#endif
    if (mr_mip->ERNUM) return FALSE;

    MR_IN(97)

    if (x==NULL || y==NULL)
    {
        copy(mr_mip->one,p->X);
        zero(p->Y); 
        p->marker=MR_EPOINT_INFINITY;
        MR_OUT
        return TRUE;
    }

/* find RHS */

    nres(_MIPP_ x,p->X);

    epoint_getrhs(_MIPP_ p->X,mr_mip->w7);

    valid=FALSE;

    if (x!=y)
    { /* compare with y^2 */
        nres(_MIPP_ y,p->Y);
        nres_modmult(_MIPP_ p->Y,p->Y,mr_mip->w1);
        
        if (mr_compare(mr_mip->w1,mr_mip->w7)==0) valid=TRUE;
    }
    else
    { /* no y supplied - calculate one. Find square root */
#ifndef MR_NOSUPPORT_COMPRESSION

        valid=nres_sqroot(_MIPP_ mr_mip->w7,p->Y);
    /* check LSB - have we got the right root? */
        redc(_MIPP_ p->Y,mr_mip->w1);
        if (remain(_MIPP_ mr_mip->w1,2)!=cb) 
            mr_psub(_MIPP_ mr_mip->modulus,p->Y,p->Y);

#else
    mr_berror(_MIPP_ MR_ERR_NOT_SUPPORTED);
    MR_OUT
    return FALSE;
#endif
    } 
    if (valid)
    {
        p->marker=MR_EPOINT_NORMALIZED;
        MR_OUT
        return TRUE;
    }

    MR_OUT
    return FALSE;
}

#ifndef MR_STATIC

void epoint_getxyz(_MIPD_ epoint *p,big x,big y,big z)
{ /* get (x,y,z) coordinates */
#ifdef MR_OS_THREADS
    miracl *mr_mip=get_mip();
#endif

    MR_IN(143)
    convert(_MIPP_ 1,mr_mip->w1);
    if (p->marker==MR_EPOINT_INFINITY)
    {
        if (x!=NULL) copy(mr_mip->w1,x);
        if (y!=NULL) zero(y);
        if (z!=NULL) zero(z);
        MR_OUT
        return;
    }
    if (x!=NULL) redc(_MIPP_ p->X,x);
    if (y!=NULL) redc(_MIPP_ p->Y,y);
    if (z!=NULL) redc(_MIPP_ p->Z,z);

    MR_OUT
    return;
}

#endif

int epoint_get(_MIPD_ epoint* p,big x,big y)
{ /* Get point co-ordinates in affine, normal form       *
   * (converted from projective, Montgomery form)        *
   * if x==y, supplies x only. Return value is Least     *
   * Significant Bit of y (useful for point compression) */

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

    if (p->marker==MR_EPOINT_INFINITY)
    {
        zero(y);
        convert(_MIPP_ 1,x);
        return 0;
    }
    if (mr_mip->ERNUM) return 0;

    MR_IN(98)

    if (!epoint_norm(_MIPP_ p)) 
    { /* not possible ! */
        MR_OUT
        return (-1);
    }

    redc(_MIPP_ p->X,x);
    redc(_MIPP_ p->Y,mr_mip->w1);

    if (x!=y) copy(mr_mip->w1,y);
    lsb=remain(_MIPP_ mr_mip->w1,2); 
    MR_OUT
    return lsb;
}

BOOL epoint_norm(_MIPD_ epoint *p)
{ /* normalise a point */
    
#ifdef MR_OS_THREADS
    miracl *mr_mip=get_mip();
#endif

    if (p->marker!=MR_EPOINT_GENERAL) return TRUE;

    if (mr_mip->ERNUM) return FALSE;

    MR_IN(117)

    copy(mr_mip->one,mr_mip->w8);

    if (nres_moddiv(_MIPP_ mr_mip->w8,p->Z,mr_mip->w8)>1) /* 1/Z  */
    {
        epoint_set(_MIPP_ NULL,NULL,0,p);
        mr_berror(_MIPP_ MR_ERR_COMPOSITE_MODULUS); 
        MR_OUT
        return FALSE;
    }
    
    nres_modmult(_MIPP_ p->X,mr_mip->w8,p->X);            /* X/Z */
    nres_modmult(_MIPP_ p->Y,mr_mip->w8,p->Y);            /* Y/Z */

    copy(mr_mip->one,p->Z);
   
    p->marker=MR_EPOINT_NORMALIZED;
    MR_OUT

    return TRUE;
}

void ecurve_double(_MIPD_ epoint *p)
{ /* double epoint on active ecurve */

#ifdef MR_OS_THREADS
    miracl *mr_mip=get_mip();
#endif
    if (mr_mip->ERNUM) return;

    if (p->marker==MR_EPOINT_INFINITY) 
    { /* 2 times infinity == infinity ! */
        return;
    }
    nres_modadd(_MIPP_ p->X,p->Y,mr_mip->w1);

    nres_modmult(_MIPP_ p->X,p->X,p->X);                 /* A=X1^2        */
    nres_modmult(_MIPP_ p->Y,p->Y,p->Y);                 /* B=Y1^2        */
    nres_modmult(_MIPP_ mr_mip->w1,mr_mip->w1,mr_mip->w1);          /* (X+Y)^2       */
    nres_modsub(_MIPP_ mr_mip->w1,p->X,mr_mip->w1);
    nres_modsub(_MIPP_ mr_mip->w1,p->Y,mr_mip->w1);           /* E=(X+Y)^2-A-B   */

    if (mr_abs(mr_mip->Asize)==MR_TOOBIG)                      /* U = aB        */
        nres_modmult(_MIPP_ p->Y,mr_mip->A,p->Y);
    else
        nres_premult(_MIPP_ p->Y,mr_mip->Asize,p->Y);   

    if (p->marker!=MR_EPOINT_NORMALIZED)
        nres_modmult(_MIPP_ p->Z,p->Z,p->Z);
    else
        copy(mr_mip->one,p->Z);

    nres_modadd(_MIPP_ p->Z,p->Z,p->Z);
    if (mr_abs(mr_mip->Bsize)==MR_TOOBIG)                           /* 2dZ^2 */
        nres_modmult(_MIPP_ p->Z,mr_mip->B,p->Z);
    else
        nres_premult(_MIPP_ p->Z,mr_mip->Bsize,p->Z);  
  
    nres_modadd(_MIPP_ p->X,p->Y,mr_mip->w2);           /* C=A+U         */
    nres_modsub(_MIPP_ p->X,p->Y,mr_mip->w3);           /* D=A-U         */

    nres_modmult(_MIPP_ mr_mip->w2,mr_mip->w3,p->X);                /* X=C.D */

    nres_modsub(_MIPP_ mr_mip->w2,p->Z,mr_mip->w2);           /* C-2dZ^2 */
    nres_modmult(_MIPP_ mr_mip->w2,mr_mip->w1,p->Y);                /* Y=E.(C-2dZ^2) */
    nres_modmult(_MIPP_ mr_mip->w3,mr_mip->w1,p->Z);                /* Z=D.E */

    p->marker=MR_EPOINT_GENERAL;
    return;
}
   
static BOOL ecurve_padd(_MIPD_ epoint *p,epoint *pa)
{ /* primitive add two epoints on the active ecurve - pa+=p;   *
   * note that if p is normalized, its Z coordinate isn't used */
 
#ifdef MR_OS_THREADS
    miracl *mr_mip=get_mip();
#endif

    if (p->marker==MR_EPOINT_INFINITY) return TRUE;
    if (pa->marker==MR_EPOINT_INFINITY)
    {
        epoint_copy(p,pa);
        return TRUE;
    }

    nres_modadd(_MIPP_ p->X,p->Y,mr_mip->w1);
    nres_modadd(_MIPP_ pa->X,pa->Y,mr_mip->w2);
    nres_modmult(_MIPP_ mr_mip->w1,mr_mip->w2,mr_mip->w1);  /* I=(X1+Y1)(X2+Y2) */
    if (p->marker!=MR_EPOINT_NORMALIZED) 
    {
        if (pa->marker==MR_EPOINT_NORMALIZED)
            copy(p->Z,pa->Z);
        else nres_modmult(_MIPP_ p->Z,pa->Z,pa->Z);    /* z = A = Z1*Z2 */
    }
    else
    {
        if (pa->marker==MR_EPOINT_NORMALIZED) copy(mr_mip->one,pa->Z);
    }

    nres_modmult(_MIPP_ pa->Z,pa->Z,mr_mip->w2);       /* w2 = B = dA^2   */
    if (mr_abs(mr_mip->Bsize)==MR_TOOBIG)                   
        nres_modmult(_MIPP_ mr_mip->w2,mr_mip->B,mr_mip->w2);
    else
        nres_premult(_MIPP_ mr_mip->w2,mr_mip->Bsize,mr_mip->w2);
    nres_modmult(_MIPP_ p->X,pa->X,pa->X);             /* x = C = X1*X2 */
    nres_modmult(_MIPP_ p->Y,pa->Y,pa->Y);             /* y = D = Y1*Y2 */
    nres_modmult(_MIPP_ pa->X,pa->Y,mr_mip->w3);       /* w3 = E = C*D     */

    nres_modsub(_MIPP_ mr_mip->w1,pa->X,mr_mip->w1);
    nres_modsub(_MIPP_ mr_mip->w1,pa->Y,mr_mip->w1);   /* I=(X1+Y1)(X2+Y2)-C-D =X1*Y2+Y1*X2 */

    if (mr_abs(mr_mip->Asize)==MR_TOOBIG)                   /*   */
        nres_modmult(_MIPP_ pa->Y,mr_mip->A,pa->Y);
    else
        nres_premult(_MIPP_ pa->Y,mr_mip->Asize,pa->Y);
    nres_modsub(_MIPP_ pa->X,pa->Y,pa->X);   /* X = H = C-aD */

    nres_modmult(_MIPP_ pa->Z,pa->X,pa->Z);
    nres_modmult(_MIPP_ pa->Z,mr_mip->w1,pa->Z);

    nres_modsub(_MIPP_ mr_mip->w3,mr_mip->w2,pa->Y);
    nres_modmult(_MIPP_ pa->Y,mr_mip->w1,pa->Y);

    nres_modadd(_MIPP_ mr_mip->w3,mr_mip->w2,mr_mip->w3);
    nres_modmult(_MIPP_ pa->X,mr_mip->w3,pa->X);

    if (size(pa->Z)==0)
    {
        copy(mr_mip->one,pa->X);
        zero(pa->Y);
        pa->marker=MR_EPOINT_INFINITY;
    }
    else pa->marker=MR_EPOINT_GENERAL;

    return TRUE;      
}

void epoint_copy(epoint *a,epoint *b)
{   
    if (a==b || b==NULL) return;

    copy(a->X,b->X);
    copy(a->Y,b->Y);
    copy(a->Z,b->Z);

    b->marker=a->marker;
    return;
}