mrmonty.c

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

    }
#endif
#ifdef MR_KCM
    }
#endif

    nres_double_modadd(_MIPP_ mr_mip->w0,mr_mip->w5,mr_mip->w6);  /* w6 =  a0.b0+a1.b1 */
    if (mr_mip->qnr==-2)
          nres_double_modadd(_MIPP_ mr_mip->w5,mr_mip->w5,mr_mip->w5);
    nres_double_modsub(_MIPP_ mr_mip->w0,mr_mip->w5,mr_mip->w0);  /* r = a0.b0+D.a1.b1 */
   
    nres_modadd(_MIPP_ a0,a1,mr_mip->w1);
    nres_modadd(_MIPP_ b0,b1,mr_mip->w2); 
    

#ifdef MR_COMBA
    if (mr_mip->ACTIVE)
    {
        comba_redc(_MIPP_ mr_mip->w0,r);
        comba_mult(_MIPP_ mr_mip->w1,mr_mip->w2,mr_mip->w0);
    }
    else
    {
#endif
#ifdef MR_KCM
    if (mr_mip->ACTIVE)
    {
        kcm_redc(_MIPP_ mr_mip->w0,r);
        kcm_mul(_MIPP_ mr_mip->w1,mr_mip->w2,mr_mip->w0);
    }
    else
    {
#endif
        redc(_MIPP_ mr_mip->w0,r);
        multiply(_MIPP_ mr_mip->w1,mr_mip->w2,mr_mip->w0);           /* w0=(a0+a1)*(b0+b1) */
#ifdef MR_COMBA
    }
#endif
#ifdef MR_KCM
    }
#endif
    nres_double_modsub(_MIPP_ mr_mip->w0,mr_mip->w6,mr_mip->w0); /* (a0+a1)*(b0+b1) - w6 */

#ifdef MR_COMBA
    if (mr_mip->ACTIVE)
    {
        comba_redc(_MIPP_ mr_mip->w0,i);
    }
    else
    {
#endif  
#ifdef MR_KCM
    if (mr_mip->ACTIVE)
    {
        kcm_redc(_MIPP_ mr_mip->w0,i);
    }
    else
    {
#endif      
        redc(_MIPP_ mr_mip->w0,i);
        MR_OUT
#ifdef MR_COMBA
    }
#endif
#ifdef MR_KCM
    }
#endif

    mr_mip->check=ON;

}

#endif

#ifndef MR_STATIC

void nres_dotprod(_MIPD_ int n,big *x,big *y,big w)
{
    int i;
#ifdef MR_OS_THREADS
    miracl *mr_mip=get_mip();
#endif

    if (mr_mip->ERNUM) return;
    MR_IN(120)
    mr_mip->check=OFF;
    zero(mr_mip->w7);
    for (i=0;i<n;i++)
    {
        multiply(_MIPP_ x[i],y[i],mr_mip->w0);
        mr_padd(_MIPP_ mr_mip->w7,mr_mip->w0,mr_mip->w7);
    }
    copy(mr_mip->pR,mr_mip->w6);
        /* w6 = p.R */
    divide(_MIPP_ mr_mip->w7,mr_mip->w6,mr_mip->w6);
    redc(_MIPP_ mr_mip->w7,w);

    mr_mip->check=ON;
    MR_OUT
}

#endif

void nres_negate(_MIPD_ big x, big w)
{
#ifdef MR_OS_THREADS
    miracl *mr_mip=get_mip();
#endif

#ifdef MR_COMBA
    if (mr_mip->ACTIVE)
    {
        comba_negate(_MIPP_ x,w);
        return;
    }    
    else
    {
#endif
        if (mr_mip->ERNUM) return;

        MR_IN(92)
        if (size(x)==0) zero(w);
        else mr_psub(_MIPP_ mr_mip->modulus,x,w);    
        MR_OUT

#ifdef MR_COMBA
    }
#endif

}

void nres_div2(_MIPD_ big x,big w)
{
#ifdef MR_OS_THREADS
    miracl *mr_mip=get_mip();
#endif

    MR_IN(198)
    copy(x,mr_mip->w1);
    if (remain(_MIPP_ mr_mip->w1,2)!=0)
        add(_MIPP_ mr_mip->w1,mr_mip->modulus,mr_mip->w1);
    subdiv(_MIPP_ mr_mip->w1,2,mr_mip->w1);
    copy(mr_mip->w1,w);

    MR_OUT
}

void nres_div3(_MIPD_ big x,big w)
{
#ifdef MR_OS_THREADS
    miracl *mr_mip=get_mip();
#endif

    MR_IN(199)
    copy(x,mr_mip->w1);
    while (remain(_MIPP_ mr_mip->w1,3)!=0)
        add(_MIPP_ mr_mip->w1,mr_mip->modulus,mr_mip->w1);
    subdiv(_MIPP_ mr_mip->w1,3,mr_mip->w1);
    copy(mr_mip->w1,w);

    MR_OUT
}

void nres_div5(_MIPD_ big x,big w)
{
#ifdef MR_OS_THREADS
    miracl *mr_mip=get_mip();
#endif

    MR_IN(208)
    copy(x,mr_mip->w1);
    while (remain(_MIPP_ mr_mip->w1,5)!=0)
        add(_MIPP_ mr_mip->w1,mr_mip->modulus,mr_mip->w1);
    subdiv(_MIPP_ mr_mip->w1,5,mr_mip->w1);
    copy(mr_mip->w1,w);

    MR_OUT
}

/* mod pR addition and subtraction */
#ifndef MR_NO_LAZY_REDUCTION

void nres_double_modadd(_MIPD_ big x,big y,big w)
{
#ifdef MR_OS_THREADS
    miracl *mr_mip=get_mip();
#endif
#ifdef MR_COMBA

    if (mr_mip->ACTIVE)
    {
        comba_double_add(_MIPP_ x,y,w);
        return;
    }
    else
    {
#endif 

        if (mr_mip->ERNUM) return;
        MR_IN(153)

        mr_padd(_MIPP_ x,y,w);
        if (mr_compare(w,mr_mip->pR)>=0)
            mr_psub(_MIPP_ w,mr_mip->pR,w);

        MR_OUT
#ifdef MR_COMBA
    }
#endif
}

void nres_double_modsub(_MIPD_ big x,big y,big w)
{
#ifdef MR_OS_THREADS
    miracl *mr_mip=get_mip();
#endif
#ifdef MR_COMBA

    if (mr_mip->ACTIVE)
    {
        comba_double_sub(_MIPP_ x,y,w);
        return;
    }
    else
    {
#endif 

        if (mr_mip->ERNUM) return;
        MR_IN(154)

        if (mr_compare(x,y)>=0)
            mr_psub(_MIPP_ x,y,w);
        else
        {
            mr_psub(_MIPP_ y,x,w);
            mr_psub(_MIPP_ mr_mip->pR,w,w);
        }

        MR_OUT
#ifdef MR_COMBA
    }
#endif
}

#endif

void nres_modadd(_MIPD_ big x,big y,big w)
{ /* modular addition */
#ifdef MR_OS_THREADS
    miracl *mr_mip=get_mip();
#endif
#ifdef MR_COUNT_OPS
fpa++; 
#endif
#ifdef MR_COMBA

    if (mr_mip->ACTIVE)
    {
        comba_add(_MIPP_ x,y,w);
        return;
    }
    else
    {
#endif
        if (mr_mip->ERNUM) return;

        MR_IN(90)
        mr_padd(_MIPP_ x,y,w);
        if (mr_compare(w,mr_mip->modulus)>=0) mr_psub(_MIPP_ w,mr_mip->modulus,w);

        MR_OUT
#ifdef MR_COMBA
    }
#endif
}

void nres_modsub(_MIPD_ big x,big y,big w)
{ /* modular subtraction */

#ifdef MR_OS_THREADS
    miracl *mr_mip=get_mip();
#endif
#ifdef MR_COUNT_OPS
fpa++;
#endif
#ifdef MR_COMBA
    if (mr_mip->ACTIVE)
    {
        comba_sub(_MIPP_ x,y,w);
        return;
    }
    else
    {
#endif
        if (mr_mip->ERNUM) return;

        MR_IN(91)

        if (mr_compare(x,y)>=0)
            mr_psub(_MIPP_ x,y,w);
        else
        {
            mr_psub(_MIPP_ y,x,w);
            mr_psub(_MIPP_ mr_mip->modulus,w,w);
        }

        MR_OUT
#ifdef MR_COMBA
    }
#endif

}

int nres_moddiv(_MIPD_ big x,big y,big w)
{ /* Modular division using n-residues w=x/y mod n */
    int gcd;
#ifdef MR_OS_THREADS
    miracl *mr_mip=get_mip();
#endif
    if (mr_mip->ERNUM) return 0;

    MR_IN(85)

    if (x==y)
    { /* Illegal parameter usage */
        mr_berror(_MIPP_ MR_ERR_BAD_PARAMETERS);
        MR_OUT
        
        return 0;
    }
    redc(_MIPP_ y,mr_mip->w6);
    gcd=invmodp(_MIPP_ mr_mip->w6,mr_mip->modulus,mr_mip->w6);
   
    if (gcd!=1) zero(w);
    else
    {
        nres(_MIPP_ mr_mip->w6,mr_mip->w6);
        nres_modmult(_MIPP_ x,mr_mip->w6,w);
    /*    mad(_MIPP_ x,mr_mip->w6,x,mr_mip->modulus,mr_mip->modulus,w); */
    }
    MR_OUT
    return gcd;
}

void nres_premult(_MIPD_ big x,int k,big w)
{ /* multiply n-residue by small ordinary integer */
#ifdef MR_OS_THREADS
    miracl *mr_mip=get_mip();
#endif
    int sign=0;
    if (k==0) 
    {
        zero(w);
        return;
    }
    if (k<0)
    {
        k=-k;
        sign=1;
    }
    if (mr_mip->ERNUM) return;

    MR_IN(102)

    if (k<=6)
    {
        switch (k)
        {
        case 1: copy(x,w);
                break;
        case 2: nres_modadd(_MIPP_ x,x,w);
                break;    
        case 3:
                nres_modadd(_MIPP_ x,x,mr_mip->w0);
                nres_modadd(_MIPP_ x,mr_mip->w0,w);
                break;
        case 4:
                nres_modadd(_MIPP_ x,x,w);
                nres_modadd(_MIPP_ w,w,w);
                break;    
        case 5:
                nres_modadd(_MIPP_ x,x,mr_mip->w0);
                nres_modadd(_MIPP_ mr_mip->w0,mr_mip->w0,mr_mip->w0);
                nres_modadd(_MIPP_ x,mr_mip->w0,w);
                break;
        case 6:
                nres_modadd(_MIPP_ x,x,w);
                nres_modadd(_MIPP_ w,w,mr_mip->w0);
                nres_modadd(_MIPP_ w,mr_mip->w0,w);
                break;
        }
        if (sign==1) nres_negate(_MIPP_ w,w);
        MR_OUT
        return;
    }

    premult(_MIPP_ x,k,mr_mip->w0);
    divide(_MIPP_ mr_mip->w0,mr_mip->modulus,mr_mip->modulus);
    
    if (sign==1) nres_negate(_MIPP_ mr_mip->w0,w);
    else copy(mr_mip->w0,w);

    MR_OUT
}

void nres_modmult(_MIPD_ big x,big y,big w)
{ /* Modular multiplication using n-residues w=x*y mod n */
#ifdef MR_OS_THREADS
    miracl *mr_mip=get_mip();
#endif
    if ((x==NULL || x->len==0) && x==w) return;
    if ((y==NULL || y->len==0) && y==w) return;
    if (y==NULL || x==NULL || x->len==0 || y->len==0)
    {
        zero(w);
        return;
    }
#ifdef MR_COUNT_OPS
fpc++;
#endif
#ifdef MR_COMBA
    if (mr_mip->ACTIVE)
    {
        if (x==y) comba_square(_MIPP_ x,mr_mip->w0);
        else      comba_mult(_MIPP_ x,y,mr_mip->w0);
        comba_redc(_MIPP_ mr_mip->w0,w);
    }
    else
    {
#endif
#ifdef MR_KCM
    if (mr_mip->ACTIVE)
    {
        if (x==y) kcm_sqr(_MIPP_ x,mr_mip->w0);
        else      kcm_mul(_MIPP_ x,y,mr_mip->w0);
        kcm_redc(_MIPP_ mr_mip->w0,w);
    }
    else
    { 
#endif
#ifdef MR_PENTIUM
    if (mr_mip->ACTIVE)
    {
        if (x==y) fastmodsquare(_MIPP_ x,w);
        else      fastmodmult(_MIPP_ x,y,w);
    }
    else
    { 
#endif
        if (mr_mip->ERNUM) return;

        MR_IN(83)

        mr_mip->check=OFF;
        multiply(_MIPP_ x,y,mr_mip->w0);
        redc(_MIPP_ mr_mip->w0,w);
        mr_mip->check=ON;
        MR_OUT
#ifdef MR_COMBA
}
#endif
#ifdef MR_KCM
}
#endif
#ifdef MR_PENTIUM
}
#endif

}

/* Montgomery's trick for finding multiple   *
 * simultaneous modular inverses             *
 * Based on the observation that             *
 *           1/x = yz*(1/xyz)                *
 *           1/y = xz*(1/xyz)                *
 *           1/z = xy*(1/xyz)                *
 * Why are all of Peter Montgomery's clever  *
 * algorithms always described as "tricks" ??*/

BOOL nres_double_inverse(_MIPD_ big x,big y,big w,big z)
{ /* find y=1/x mod n and z=1/w mod n */
  /* 1/x = w/xw, and 1/w = x/xw       */
#ifdef MR_OS_THREADS
    miracl *mr_mip=get_mip();
#endif
    MR_IN(145)

    nres_modmult(_MIPP_ x,w,mr_mip->w6);  /* xw */

    if (size(mr_mip->w6)==0)
    {
        mr_berror(_MIPP_ MR_ERR_DIV_BY_ZERO);
        MR_OUT
        return FALSE;
    }
    redc(_MIPP_ mr_mip->w6,mr_mip->w6);
    redc(_MIPP_ mr_mip->w6,mr_mip->w6);
    invmodp(_MIPP_ mr_mip->w6,mr_mip->modulus,mr_mip->w6);

    nres_modmult(_MIPP_ w,mr_mip->w6,mr_mip->w5);
    nres_modmult(_MIPP_ x,mr_mip->w6,z);
    copy(mr_mip->w5,y);

    MR_OUT
    return TRUE;
}

BOOL nres_multi_inverse(_MIPD_ int m,big *x,big *w)
{ /* find w[i]=1/x[i] mod n, for i=0 to m-1 *
   * x and w MUST be distinct               */
    int i;
#ifdef MR_OS_THREADS
    miracl *mr_mip=get_mip();
#endif
    if (m==0) return TRUE;
    if (m<0) return FALSE;
    MR_IN(118)

    if (x==w)
    {
        mr_berror(_MIPP_ MR_ERR_BAD_PARAMETERS);
        MR_OUT
        return FALSE;
    }

    if (m==1)
    {
        copy(mr_mip->one,w[0]);
        nres_moddiv(_MIPP_ w[0],x[0],w[0]);
        MR_OUT
        return TRUE;
    }

    convert(_MIPP_ 1,w[0]);
    copy(x[0],w[1]);
    for (i=2;i<m;i++)
        nres_modmult(_MIPP_ w[i-1],x[i-1],w[i]); 

    nres_modmult(_MIPP_ w[m-1],x[m-1],mr_mip->w6);  /* y=x[0]*x[1]*x[2]....x[m-1] */
    if (size(mr_mip->w6)==0)
    {
        mr_berror(_MIPP_ MR_ERR_DIV_BY_ZERO);
        MR_OUT
        return FALSE;
    }

    redc(_MIPP_ mr_mip->w6,mr_mip->w6);
    redc(_MIPP_ mr_mip->w6,mr_mip->w6);

    invmodp(_MIPP_ mr_mip->w6,mr_mip->modulus,mr_mip->w6);

/* Now y=1/y */

    copy(x[m-1],mr_mip->w5);
    nres_modmult(_MIPP_ w[m-1],mr_mip->w6,w[m-1]);

    for (i=m-2;;i--)
    {
        if (i==0)
        {
            nres_modmult(_MIPP_ mr_mip->w5,mr_mip->w6,w[0]);
            break;
        }
        nres_modmult(_MIPP_ w[i],mr_mip->w5,w[i]);
        nres_modmult(_MIPP_ w[i],mr_mip->w6,w[i]);
        nres_modmult(_MIPP_ mr_mip->w5,x[i],mr_mip->w5);
    }

    MR_OUT 
    return TRUE;   
}

/* initialise elliptic curve */

void ecurve_init(_MIPD_ big a,big b,big p,int type)
{ /* Initialize the active ecurve    *
   * Asize indicate size of A        *
   * Bsize indicate size of B        */
    int as;
#ifdef MR_OS_THREADS
    miracl *mr_mip=get_mip();
#endif
    if (mr_mip->ERNUM) return;

    MR_IN(93)

#ifndef MR_NO_SS
    mr_mip->SS=FALSE;       /* no special support for super-singular curves */ 
#endif

    prepare_monty(_MIPP_ p);

    mr_mip->Asize=size(a);
    if (mr_abs(mr_mip->Asize)==MR_TOOBIG)
    {
        if (mr_mip->Asize>=0)
        { /* big positive number - check it isn't minus something small */
           copy(a,mr_mip->w1);
           divide(_MIPP_ mr_mip->w1,p,p);
           subtract(_MIPP_ p,mr_mip->w1,mr_mip->w1);
           as=size(mr_mip->w1);
           if (as<MR_TOOBIG) mr_mip->Asize=-as;
        }
    }
    nres(_MIPP_ a,mr_mip->A);

    mr_mip->Bsize=size(b);
    if (mr_abs(mr_mip->Bsize)==MR_TOOBIG) 
    {
        if (mr_mip->Bsize>=0)
        { /* big positive number - check it isn't minus something small */
           copy(b,mr_mip->w1);
           divide(_MIPP_ mr_mip->w1,p,p);
           subtract(_MIPP_ p,mr_mip->w1,mr_mip->w1);
           as=size(mr_mip->w1);
           if (as<MR_TOOBIG) mr_mip->Bsize=-as;
        }
    }

    nres(_MIPP_ b,mr_mip->B);
#ifdef MR_EDWARDS
    mr_mip->coord=MR_PROJECTIVE; /* only type supported for Edwards curves */
#else
#ifndef MR_AFFINE_ONLY
    if (type==MR_BEST) mr_mip->coord=MR_PROJECTIVE;
    else mr_mip->coord=type;
#else
    if (type==MR_PROJECTIVE)
        mr_berror(_MIPP_ MR_ERR_NOT_SUPPORTED);
#endif
#endif
    MR_OUT
    return;
}