mrecgf2m.c

miracl-大数运算库,大家使用有什么问题请多多提意见

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

    modmult2(_MIPP_ w[m-1],x[m-1],mr_mip->w6);
    if (size(mr_mip->w6)==0)
    {
        mr_berror(_MIPP_ MR_ERR_DIV_BY_ZERO);
        return FALSE;
    }

    inverse2(_MIPP_ mr_mip->w6,mr_mip->w6);  /* y=1/y */

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

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

int trace2(_MIPD_ big x)
{
    int i;
#ifdef MR_OS_THREADS
    miracl *mr_mip=get_mip();
#endif
    copy(x,mr_mip->w1);
    for (i=1;i<mr_mip->M;i++)
    {
        modsquare2(_MIPP_ mr_mip->w1,mr_mip->w1);
        add2(mr_mip->w1,x,mr_mip->w1);
    }   
    return (mr_mip->w1->w[0]&1);
}

void rand2(_MIPD_ big x)
{ /* random number */
    int i,k;
#ifdef MR_OS_THREADS
    miracl *mr_mip=get_mip();
#endif
    zero(x);
    k=1+mr_mip->M/MIRACL;        
    x->len=k;
    for (i=0;i<k;i++) x->w[i]=brand(_MIPPO_ );
    mr_lzero(x);
    reduce2(_MIPP_ x,x);    
}

int parity2(big x)
{ /* return LSB */
   if (x->len==0) return 0;
   return (int)(x->w[0]%2);
}

void halftrace2(_MIPD_ big b,big w)
{
    int i,M;
#ifdef MR_OS_THREADS
    miracl *mr_mip=get_mip();
#endif

    M=mr_mip->M;
    if (M%2==0) return;
   
    copy(b,mr_mip->w1);
    copy(b,w);
    
    for (i=1;i<=(M-1)/2;i++)
    { 
        modsquare2(_MIPP_ w,w);
        modsquare2(_MIPP_ w,w);
        add2(w,mr_mip->w1,w);   
    } 
}

BOOL quad2(_MIPD_ big b,big w)
{ /* Solves x^2 + x = b  for a root w  *
   * returns TRUE if a solution exists *
   * the "other" solution is w+1       */
    int i,M;
#ifdef MR_OS_THREADS
    miracl *mr_mip=get_mip();
#endif

    M=mr_mip->M;
    copy(b,mr_mip->w1);
    if (M%2==1) halftrace2(_MIPP_ b,w); /* M is odd, so its the Half-Trace */

    else
    {
        forever
        {
            rand2(_MIPP_ mr_mip->w2);
            zero(w);
            copy(mr_mip->w2,mr_mip->w3);
            for (i=1;i<M;i++)
            {
                modsquare2(_MIPP_ mr_mip->w3,mr_mip->w3);
                modmult2(_MIPP_ mr_mip->w3,mr_mip->w1,mr_mip->w4);
                modsquare2(_MIPP_ w,w);
                add2(w,mr_mip->w4,w);
                add2(mr_mip->w3,mr_mip->w2,mr_mip->w3);
            }    
            if (size(mr_mip->w3)!=0) break; 
        }
    }

    copy(w,mr_mip->w2);
    modsquare2(_MIPP_ mr_mip->w2,mr_mip->w2);
    add2(mr_mip->w2,w,mr_mip->w2);
    if (compare(mr_mip->w1,mr_mip->w2)==0) return TRUE;
    return FALSE;
}

void gf2m_dotprod(_MIPD_ int n,big *x,big *y,big w)
{ /* dot product - only one reduction! */
    int i;
#ifdef MR_OS_THREADS
    miracl *mr_mip=get_mip();
#endif
    mr_mip->check=OFF;
    zero(mr_mip->w5);

    for (i=0;i<n;i++)
    {
        multiply2(_MIPP_ x[i],y[i],mr_mip->w0);
        add2(mr_mip->w5,mr_mip->w0,mr_mip->w5);
    }

    reduce2(_MIPP_ mr_mip->w5,mr_mip->w5);
    copy(mr_mip->w5,w);

    mr_mip->check=ON;
}

BOOL prepare_basis(_MIPD_ int m,int a,int b,int c,BOOL check)
{
    int i,k,sh;
#ifdef MR_OS_THREADS
    miracl *mr_mip=get_mip();
#endif
    if (mr_mip->ERNUM) return FALSE;

    if (b==0) c=0;
    if (m==mr_mip->M && a==mr_mip->AA && b==mr_mip->BB && c==mr_mip->CC)
        return TRUE;   /* its already prepared... */

    MR_IN(138)
    if (m <=0 || a<=0 || a>=m || b>=a) 
    {
        mr_berror(_MIPP_ MR_ERR_BAD_MODULUS);
        MR_OUT
        return FALSE;
    }
    
    mr_mip->M=m;
    mr_mip->AA=a;
    mr_mip->BB=0;
    mr_mip->CC=0;
    zero(mr_mip->modulus);

    k=1+m/MIRACL;

    if (k>mr_mip->nib)
    {
        mr_berror(_MIPP_ MR_ERR_OVERFLOW);
        MR_OUT
        return FALSE;
    }

    mr_mip->modulus->len=k;
    sh=m%MIRACL;
    mr_mip->modulus->w[k-1]=((mr_small)1<<sh);
    mr_mip->modulus->w[0]^=1;
    mr_mip->modulus->w[a/MIRACL]^=((mr_small)1<<(a%MIRACL));
    if (b!=0)
    {
         mr_mip->BB=b;
         mr_mip->CC=c;
         mr_mip->modulus->w[b/MIRACL]^=((mr_small)1<<(b%MIRACL));
         mr_mip->modulus->w[c/MIRACL]^=((mr_small)1<<(c%MIRACL));
    }

    if (!check)
    {
        MR_OUT
        return TRUE;
    }

/* check for irreducibility of basis */

    zero(mr_mip->w4);
    mr_mip->w4->len=1;
    mr_mip->w4->w[0]=2;       /* f(t) = t */
    for (i=1;i<=m/2;i++)
    {
        modsquare2(_MIPP_ mr_mip->w4,mr_mip->w4);
        incr2(mr_mip->w4,2,mr_mip->w5);
        gcd2(_MIPP_ mr_mip->w5,mr_mip->modulus,mr_mip->w6);
        if (size(mr_mip->w6)!=1)
        {
            mr_berror(_MIPP_ MR_ERR_NOT_IRREDUC);
            MR_OUT
            return FALSE;
        }
    }
                   
    MR_OUT
    return TRUE;
}

/* Initialise with Trinomial or Pentanomial      *
 * t^m  + t^a + 1 OR t^m + t^a +t^b + t^c + 1    *
 * Set b=0 for pentanomial. a2 is usually 0 or 1 *
 * m negative indicates a super-singular curve   */

BOOL ecurve2_init(_MIPD_ int m,int a,int b,int c,big a2,big a6,BOOL check,int type)
{
#ifdef MR_OS_THREADS
    miracl *mr_mip=get_mip();
#endif
    int i;

/* catch some nonsense conditions */

    if (mr_mip->ERNUM) return FALSE;

    mr_mip->SS=FALSE;
    if (m<0)
    { /* its a supersingular curve! */
        mr_mip->SS=TRUE;
      /*   type=MR_AFFINE;      always AFFINE */
        m=-m;
        if (size(a2)!=1) return FALSE;
        if (size(a6) >1) return FALSE;
    }
    if (size(a2)<0) return FALSE;
    if (size(a6)<0) return FALSE;
    MR_IN(123)

    if (!prepare_basis(_MIPP_ m,a,b,c,check))
    { /* unable to set the basis */
        MR_OUT
        return FALSE;
    }    

    mr_mip->Asize=size(a2);    
    mr_mip->Bsize=size(a6);

    if (mr_mip->Asize==MR_TOOBIG)
        copy(a2,mr_mip->A);

    if (mr_mip->Bsize==MR_TOOBIG)
        copy(a6,mr_mip->B);

 /* Use C to store B^(2^M-2) - required for projective doubling */
    if (!mr_mip->SS)
    {
        copy(a6,mr_mip->C);
        for (i=1;i<m-1;i++) modsquare2(_MIPP_ mr_mip->C,mr_mip->C);
    }
#ifndef MR_AFFINE_ONLY
    mr_mip->coord=type;
#else
    if (type==MR_PROJECTIVE)
        mr_berror(_MIPP_ MR_ERR_NOT_SUPPORTED);
#endif
    MR_OUT
    return TRUE;
}    

BOOL epoint2_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/x     *
   * (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(125)

    if (x==NULL || y==NULL)
    {
        convert(_MIPP_ 1,p->X);
        convert(_MIPP_ 1,p->Y);
        p->marker=MR_EPOINT_INFINITY;
        MR_OUT
        return TRUE;
    }

    valid=FALSE;       

    if (mr_mip->SS)
    { /* Super-singular - calculate x^3+x+B */
        copy (x,p->X);
        modsquare2(_MIPP_ p->X,mr_mip->w5);           /* w5=x^2 */
        modmult2(_MIPP_ mr_mip->w5,p->X,mr_mip->w5);  /* w5=x^3 */
        add2(mr_mip->w5,p->X,mr_mip->w5);             
        incr2(mr_mip->w5,mr_mip->Bsize,mr_mip->w5);  /* w5=x^3+x+B */
        if (x!=y)
        { /* compare with y^2+y */
            copy(y,p->Y);
            modsquare2(_MIPP_ p->Y,mr_mip->w1);
            add2(mr_mip->w1,p->Y,mr_mip->w1);
            if (compare(mr_mip->w1,mr_mip->w5)==0) valid=TRUE;
        }
        else
        { /* no y supplied - calculate one. Solve quadratic */
            valid=quad2(_MIPP_ mr_mip->w5,mr_mip->w5);
            incr2(mr_mip->w5,cb^parity2(mr_mip->w5),p->Y);
        }
    } 
    else
    { /* calculate x^3+Ax^2+B */
        copy(x,p->X);

        modsquare2(_MIPP_ p->X,mr_mip->w6);           /* w6=x^2 */
        modmult2(_MIPP_ mr_mip->w6,p->X,mr_mip->w5);  /* w5=x^3 */

        if (mr_mip->Asize==MR_TOOBIG)
            copy(mr_mip->A,mr_mip->w1);
        else
            convert(_MIPP_ mr_mip->Asize,mr_mip->w1);
        modmult2(_MIPP_ mr_mip->w6,mr_mip->w1,mr_mip->w0);
        add2(mr_mip->w5,mr_mip->w0,mr_mip->w5);

        if (mr_mip->Bsize==MR_TOOBIG)
            add2(mr_mip->w5,mr_mip->B,mr_mip->w5);    /* w5=x^3+Ax^2+B */
        else
            incr2(mr_mip->w5,mr_mip->Bsize,mr_mip->w5); 
        if (x!=y)
        { /* compare with y^2+xy */
            copy(y,p->Y);
            modsquare2(_MIPP_ p->Y,mr_mip->w2);
            modmult2(_MIPP_ p->Y,p->X,mr_mip->w1);
            add2(mr_mip->w1,mr_mip->w2,mr_mip->w1);
            if (compare(mr_mip->w1,mr_mip->w5)==0) valid=TRUE;
        }
        else
        { /* no y supplied - calculate one. Solve quadratic */
            if (size(p->X)==0) 
            {
                if (mr_mip->Bsize==MR_TOOBIG) 
                    copy(mr_mip->B,mr_mip->w1);
                else convert(_MIPP_ mr_mip->Bsize,mr_mip->w1); 

                sqroot2(_MIPP_ mr_mip->w1,p->Y);
                valid=TRUE;
            }
            else
            {
                inverse2(_MIPP_ mr_mip->w6,mr_mip->w6);  /* 1/x^2 */
                modmult2(_MIPP_ mr_mip->w5,mr_mip->w6,mr_mip->w5);
                valid=quad2(_MIPP_ mr_mip->w5,mr_mip->w5);     
                incr2(mr_mip->w5,cb^parity2(mr_mip->w5),mr_mip->w5);
                modmult2(_MIPP_ mr_mip->w5,p->X,p->Y);
            }
        }
    }
    if (valid)
    {
        p->marker=MR_EPOINT_NORMALIZED;
        MR_OUT
        return TRUE;
    }
    MR_OUT
    return FALSE;
}

BOOL epoint2_norm(_MIPD_ epoint *p)
{ /* normalise a point */
#ifdef MR_OS_THREADS
    miracl *mr_mip=get_mip();
#endif
#ifndef MR_AFFINE_ONLY
    if (mr_mip->coord==MR_AFFINE) return TRUE;
    if (p->marker!=MR_EPOINT_GENERAL) return TRUE;

    if (mr_mip->ERNUM) return FALSE;

    MR_IN(126)

    if (!inverse2(_MIPP_ p->Z,mr_mip->w8))
    {
        MR_OUT
        return FALSE;
    }

    modsquare2(_MIPP_ mr_mip->w8,mr_mip->w1);          /* 1/ZZ */
    modmult2(_MIPP_ p->X,mr_mip->w1,p->X);             /* X/ZZ */
    modmult2(_MIPP_ mr_mip->w1,mr_mip->w8,mr_mip->w1); /* 1/ZZZ */ 
    modmult2(_MIPP_ p->Y,mr_mip->w1,p->Y);             /* Y/ZZZ */
    convert(_MIPP_ 1,p->Z);

    p->marker=MR_EPOINT_NORMALIZED;
    MR_OUT
#endif
    return TRUE;
}

void epoint2_getxyz(_MIPD_ epoint* p,big x,big y,big z)
{
#ifdef MR_OS_THREADS
    miracl *mr_mip=get_mip();
#endif
    convert(_MIPP_ 1,mr_mip->w1);
    if (p->marker==MR_EPOINT_INFINITY)
    {
#ifndef MR_AFFINE_ONLY
        if (mr_mip->coord==MR_AFFINE)
        { /* (0,0) = O */
#endif
            if (x!=NULL) zero(x);
            if (y!=NULL) zero(y);
#ifndef MR_AFFINE_ONLY
        }

        if (mr_mip->coord==MR_PROJECTIVE)
        { /* (1,1,0) = O */
            if (x!=NULL) copy(mr_mip->w1,x);
            if (y!=NULL) copy(mr_mip->w1,y);
        }
#endif
        if (z!=NULL) zero(z);
        return;
    }
    if (x!=NULL) copy(p->X,x);
    if (y!=NULL) copy(p->Y,y);
#ifndef MR_AFFINE_ONLY
    if (mr_mip->coord==MR_AFFINE)
    {
#endif
        if (z!=NULL) zero(z);
#ifndef MR_AFFINE_ONLY
    }

    if (mr_mip->coord==MR_PROJECTIVE)
    {
        if (z!=NULL)
        {
            if (p->marker!=MR_EPOINT_GENERAL) copy(mr_mip->w1,z);
            else copy(p->Z,z);
        }
    }
#endif
    return;
}

int epoint2_get(_MIPD_ epoint* p,big x,big y)
{ /* Get point co-ordinates in affine, normal form       *
   * (converted from projective form). If x==y, supplies *
   * x only. Return value is LSB of y/x (useful for      *
   * point compression)                                  */
    int lsb;
#ifdef MR_OS_THREADS
    miracl *mr_mip=get_mip();
#endif
    
    if (p->marker==MR_EPOINT_INFINITY)
    {
        zero(x);
        zero(y);
        return 0;
    }
    if (mr_mip->ERNUM) return 0;

    MR_IN(127)

    epoint2_norm(_MIPP_ p);

    copy(p->X,x);
    copy(p->Y,mr_mip->w5);

    if (x!=y) copy(mr_mip->w5,y);
    if (size(x)==0)
    {
        MR_OUT
        return 0;
    }
    if (mr_mip->SS)
    {
        lsb=parity2(p->Y);
    }
    else
    {
        inverse2(_MIPP_ x,mr_mip->w5);
        modmult2(_MIPP_ mr_mip->w5,p->Y,mr_mip->w5);

        lsb=parity2(mr_mip->w5);
    }
    MR_OUT
    return lsb;
}

static void ecurve2_double(_MIPD_ epoint *p)
{ /* double epoint on active curve */
#ifdef MR_OS_THREADS
    miracl *mr_mip=get_mip();
#endif

    if (p->marker==MR_EPOINT_INFINITY)
    { /* 2 times infinity == infinity! */
        return;
    }
#ifndef MR_AFFINE_ONLY
    if (mr_mip->coord==MR_AFFINE)
    {
#endif
        if (mr_mip->SS)
        { /* super-singular */
            modsquare2(_MIPP_ p->X,p->X);
            incr2(p->X,1,mr_mip->w8);
            modsquare2(_MIPP_ p->X,p->X);
            modsquare2(_MIPP_ p->Y,p->Y);
            modsquare2(_MIPP_ p->Y,p->Y);
            add2(p->Y,p->X,p->Y);   /* y=x^4+y^4   */
            incr2(p->X,1,p->X);     /* x=x^4+1     */
            return;
        }    

        if (size(p->X)==0)
        { /* set to point at infinity */
            epoint2_set(_MIPP_ NULL,NULL,0,p);
            return;
        }
   
        inverse2(_MIPP_ p->X,mr_mip->w8);
  
        modmult2(_MIPP_ mr_mip->w8,p->Y,mr_mip->w8);