mrecgf2m.c

大数运算库

            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 */
#ifndef MR_GENERIC_MT
    miracl *mr_mip=get_mip();
#endif

    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
    return TRUE;
}

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;
#ifndef MR_GENERIC_MT
    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 */
#ifndef MR_GENERIC_MT
    miracl *mr_mip=get_mip();
#endif

    if (p->marker==MR_EPOINT_INFINITY)
    { /* 2 times infinity == infinity! */
        return;
    }

    if (mr_mip->coord==MR_AFFINE)
    {
        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);
        add2(mr_mip->w8,p->X,mr_mip->w8);   /* w8 is slope m */

        modsquare2(_MIPP_ mr_mip->w8,mr_mip->w6);  /* w6 =m^2 */
        add2(mr_mip->w6,mr_mip->w8,mr_mip->w1);
        if (mr_mip->Asize==MR_TOOBIG)
            add2(mr_mip->w1,mr_mip->A,mr_mip->w1); 
        else
            incr2(mr_mip->w1,mr_mip->Asize,mr_mip->w1); /* w1 = x3 */

        add2(p->X,mr_mip->w1,mr_mip->w6);
        modmult2(_MIPP_ mr_mip->w6,mr_mip->w8,mr_mip->w6);
        copy(mr_mip->w1,p->X);
        add2(mr_mip->w6,mr_mip->w1,mr_mip->w6);
        add2(p->Y,mr_mip->w6,p->Y);
        return;
    }

    if (size(p->X)==0)
    { /* set to infinity */
        epoint2_set(_MIPP_ NULL,NULL,0,p);
        return;
    }

    if (p->marker!=MR_EPOINT_NORMALIZED)
    {
        modmult2(_MIPP_ p->Y,p->Z,p->Y);             /* t2 = t2 * t3 */
        modsquare2(_MIPP_ p->Z,p->Z);                /* t3 = t3^2 */
        modmult2(_MIPP_ mr_mip->C,p->Z,mr_mip->w4);  /* t4 = c * t3 */ 
        modmult2(_MIPP_ p->Z,p->X,p->Z);             /* t3 = t3 * t1 */
    }
    else
    {
        copy(mr_mip->C,mr_mip->w4);
        copy(p->X,p->Z);
    }
    add2(p->Y,p->Z,p->Y);                 /* t2 = t2 + t3 */
    add2(mr_mip->w4,p->X,mr_mip->w4);     /* t4 = t4 + t1 */
    modsquare2(_MIPP_ mr_mip->w4,mr_mip->w4);    /* t4 = t4^2 */ 
    modsquare2(_MIPP_ mr_mip->w4,mr_mip->w4);    /* t4 = t4^2 */
    modsquare2(_MIPP_ p->X,mr_mip->w1);          /* t1 = t1^2 */
    add2(p->Y,mr_mip->w1,p->Y);           /* t2 = t2 + t1 */
    modmult2(_MIPP_ p->Y,mr_mip->w4,p->Y);       /* t2 = t2 * t4 */
    modsquare2(_MIPP_ mr_mip->w1,mr_mip->w1);    /* t1 = t1^2 */
    modmult2(_MIPP_ mr_mip->w1,p->Z,mr_mip->w1); /* t1 = t1 * t3 */
    add2(p->Y,mr_mip->w1,p->Y);           /* t2 = t2 + t1 */
    copy(mr_mip->w4,p->X);

    p->marker=MR_EPOINT_GENERAL;
}

static BOOL ecurve2_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 */
 
#ifndef MR_GENERIC_MT
    miracl *mr_mip=get_mip();
#endif
    if (mr_mip->coord==MR_AFFINE)
    {
        add2(p->Y,pa->Y,mr_mip->w8);
        add2(p->X,pa->X,mr_mip->w6);
        if (size(mr_mip->w6)==0)
        {  /* divide by zero */
            if (size(mr_mip->w8)==0)
            { /* should have doubled! */
                return FALSE;
            }
            else
            { /* point at infinity */
                epoint2_set(_MIPP_ NULL,NULL,0,pa);
                return TRUE;
            }
        }
        inverse2(_MIPP_ mr_mip->w6,mr_mip->w5);

        modmult2(_MIPP_ mr_mip->w8,mr_mip->w5,mr_mip->w8); /* w8=m */
        modsquare2(_MIPP_ mr_mip->w8,mr_mip->w5);          /* m^2  */

        if (mr_mip->SS)
        {
             add2(pa->X,p->X,pa->X);
             add2(pa->X,mr_mip->w5,pa->X);

             add2(pa->X,p->X,pa->Y);
             modmult2(_MIPP_ pa->Y,mr_mip->w8,pa->Y);
             add2(pa->Y,p->Y,pa->Y);
             incr2(pa->Y,1,pa->Y);
        }
        else
        {
            add2(mr_mip->w5,mr_mip->w8,mr_mip->w5);
            add2(mr_mip->w5,mr_mip->w6,mr_mip->w5);
            if (mr_mip->Asize==MR_TOOBIG)
                add2(mr_mip->w5,mr_mip->A,mr_mip->w5);
            else
                incr2(mr_mip->w5,mr_mip->Asize,mr_mip->w5); /* w5=x3 */
        
            add2(pa->X,mr_mip->w5,mr_mip->w6);
            modmult2(_MIPP_ mr_mip->w6,mr_mip->w8,mr_mip->w6);
            copy(mr_mip->w5,pa->X);
            add2(mr_mip->w6,mr_mip->w5,mr_mip->w6);
            add2(pa->Y,mr_mip->w6,pa->Y);
        }
        pa->marker=MR_EPOINT_NORMALIZED;
        return TRUE;
    }

    if (p->marker!=MR_EPOINT_NORMALIZED)
    {
        modsquare2(_MIPP_ p->Z,mr_mip->w6);           /* t7 = t6^2    */
        modmult2(_MIPP_ pa->X,mr_mip->w6,mr_mip->w1); /* t1 = t1 * t7 */
        modmult2(_MIPP_ mr_mip->w6,p->Z,mr_mip->w6);  /* t7 = t7 * t6 */
        modmult2(_MIPP_ pa->Y,mr_mip->w6,mr_mip->w2); /* t2 = t2 * t7 */ 
    }
    else
    {
        copy(pa->X,mr_mip->w1);
        copy(pa->Y,mr_mip->w2);
    }
    if (pa->marker==MR_EPOINT_NORMALIZED)
        convert(_MIPP_ 1,mr_mip->w6);
    else
        modsquare2(_MIPP_ pa->Z,mr_mip->w6);           /* t7 = t3^2    */
    modmult2(_MIPP_ mr_mip->w6,p->X,mr_mip->w8);       /* t8 = t4 * t7 */
    add2(mr_mip->w1,mr_mip->w8,mr_mip->w1);     /* t1 = t1 + t8 */
    if (pa->marker!=MR_EPOINT_NORMALIZED)
        modmult2(_MIPP_ mr_mip->w6,pa->Z,mr_mip->w6);  /* t7 = t7 * t3 */
    modmult2(_MIPP_ mr_mip->w6,p->Y,mr_mip->w8);       /* t8 = t7 * t5 */
    add2(mr_mip->w2,mr_mip->w8,mr_mip->w2);     /* t2 = t2 + t8 */
    if (size(mr_mip->w1)==0)
    {
        if (size(mr_mip->w2)==0)
        { /* should have doubled! */
            return FALSE;
        }
        else
        { /* point at infinity */
            epoint2_set(_MIPP_ NULL,NULL,0,pa);
            return TRUE;
        }
    }
    modmult2(_MIPP_ p->X,mr_mip->w2,mr_mip->w4);      /* t4 = t2 * t4 */
    if (pa->marker!=MR_EPOINT_NORMALIZED)
        modmult2(_MIPP_ pa->Z,mr_mip->w1,mr_mip->w3);  /* t3 = t3 * t1 */
    else 
        copy(mr_mip->w1,mr_mip->w3);
    modmult2(_MIPP_ p->Y,mr_mip->w3,mr_mip->w5);      /* t5 = t5 * t3 */
    add2(mr_mip->w4,mr_mip->w5,mr_mip->w4);           /* t4 = t4 + t5 */
    modsquare2(_MIPP_ mr_mip->w3,mr_mip->w5);         /* t5 = t3^2    */
    modmult2(_MIPP_ mr_mip->w4,mr_mip->w5,mr_mip->w6); /* t7 = t4 * t5 */

    if (p->marker!=MR_EPOINT_NORMALIZED) 
        modmult2(_MIPP_ mr_mip->w3,p->Z,mr_mip->w3);  /* t3 = t3 * t6 */
    add2(mr_mip->w2,mr_mip->w3,mr_mip->w4);    /* t4 = t2 + t3 */
    modmult2(_MIPP_ mr_mip->w2,mr_mip->w4,mr_mip->w2);/* t2 = t2 * t4 */
    modsquare2(_MIPP_ mr_mip->w1,mr_mip->w5);         /* t5 = t1^2    */
    modmult2(_MIPP_ mr_mip->w1,mr_mip->w5,mr_mip->w1);/* t1 = t1 * t5 */
    if (mr_mip->Asize>0)
    {
        modsquare2(_MIPP_ mr_mip->w3,mr_mip->w8);     /* t8 = t3^2    */
        if (mr_mip->Asize>1)
        {
            if (mr_mip->Asize==MR_TOOBIG)
                copy(mr_mip->A,mr_mip->w5);
            else 
                convert(_MIPP_ mr_mip->Asize,mr_mip->w5);
            modmult2(_MIPP_ mr_mip->w8,mr_mip->w5,mr_mip->w8);
        }
        add2(mr_mip->w1,mr_mip->w8,mr_mip->w1);/* t1 = t1 + t8 */
    }
    add2(mr_mip->w1,mr_mip->w2,pa->X);         /* t1 = t1 + t2 */
    modmult2(_MIPP_ mr_mip->w4,pa->X,mr_mip->w4);/* t4 = t4 * t1 */
    add2(mr_mip->w4,mr_mip->w6,pa->Y);         /* t2 = t4 + t7 */
    copy(mr_mip->w3,pa->Z);

    pa->marker=MR_EPOINT_GENERAL;
    return TRUE;
}

void epoint2_copy(epoint *a,epoint *b)
{   
    if (a==b) return;
    copy(a->X,b->X);
    copy(a->Y,b->Y);
    if (a->marker==MR_EPOINT_GENERAL) copy(a->Z,b->Z);
    b->marker=a->marker;
    return;
}

BOOL epoint2_comp(_MIPD_ epoint *a,epoint *b)
{
    int ia,ib;
#ifndef MR_GENERIC_MT
    miracl *mr_mip=get_mip();
#endif
    if (mr_mip->ERNUM) return FALSE;
    if (a==b) return TRUE;

    if (a->marker==MR_EPOINT_INFINITY)
    {
        if (b->marker==MR_EPOINT_INFINITY) return TRUE;
        else return FALSE;
    } 
    if (b->marker==MR_EPOINT_INFINITY)
        return FALSE;

    MR_IN(128)

    ia=epoint2_get(_MIPP_ a,mr_mip->w9,mr_mip->w9);
    ib=epoint2_get(_MIPP_ b,mr_mip->w10,mr_mip->w10);

    MR_OUT
    if (ia==ib && compare(mr_mip->w9,mr_mip->w10)==0) return TRUE;
    return FALSE;
}

big ecurve2_add(_MIPD_ epoint *p,epoint *pa)
{  /* pa=pa+p; */
   /* An ephemeral pointe to the line slope is returned *
    * only if curve is super-singular                   */
#ifndef MR_GENERIC_MT
    miracl *mr_mip=get_mip();
#endif
    if (mr_mip->ERNUM) return NULL;

    MR_IN(129)

    if (p==pa) 
    {
        ecurve2_double(_MIPP_ pa);
        MR_OUT
        return mr_mip->w8;
    }
    if (pa->marker==MR_EPOINT_INFINITY)
    {
        epoint2_copy(p,pa);
        MR_OUT 
        return NULL;
    }
    if (p->marker==MR_EPOINT_INFINITY) 
    {
        MR_OUT
        return NULL;
    }
    if (!ecurve2_padd(_MIPP_ p,pa)) ecurve2_double(_MIPP_ pa);
    MR_OUT
    return mr_mip->w8;
}

void epoint2_negate(_MIPD_ epoint *p)
{ /* negate a point */
#ifndef MR_GENERIC_MT
    miracl *mr_mip=get_mip();
#endif
    if (mr_mip->ERNUM) return;
    if (p->marker==MR_EPOINT_INFINITY) return;
    MR_IN(130)
    if (p->marker==MR_EPOINT_GENERAL)
    {
        modmult2(_MIPP_ p->X,p->Z,mr_mip->w1);
        add2(p->Y,mr_mip->w1,p->Y);
    }
    else 
    {
        if (mr_mip->SS)  incr2(p->Y,1,p->Y);
        else             add2(p->Y,p->X,p->Y);
                        
    }
    MR_OUT
}

big ecurve2_sub(_MIPD_ epoint *p,epoint *pa)
{
    big r;
#ifndef MR_GENERIC_MT
    miracl *mr_mip=get_mip();
#endif
    if (mr_mip->ERNUM) return NULL;

    MR_IN(131)

    if (p==pa)
    {
        epoint2_set(_MIPP_ NULL,NULL,0,pa);
        MR_OUT
        return NULL;
    } 
    if (p->marker==MR_EPOINT_INFINITY) 
    {
        MR_OUT
        return NULL;
    }

    epoint2_negate(_MIPP_ p);
    r=ecurve2_add(_MIPP_ p,pa);
    epoint2_negate(_MIPP_ p);

    MR_OUT
    return r;
}

void ecurve2_multi_add(_MIPD_ int m,epoint **x,epoint **w)
{ /* adds m points together simultaneously, w[i]+=x[i] */
    int i,*flag;
    big *A,*B,*C;
    char *mem;
#ifndef MR_GENERIC_MT
    miracl *mr_mip=get_mip();
#endif
    if (mr_mip->ERNUM) return;

    MR_IN(132)
    if (mr_mip->coord==MR_AFFINE && !mr_mip->SS)
    {
        A=(big *)mr_alloc(_MIPP_ m,sizeof(big));
        B=(big *)mr_alloc(_MIPP_ m,sizeof(big));
        C=(big *)mr_alloc(_MIPP_ m,sizeof(big));
        flag=(int *)mr_alloc(_MIPP_ m,sizeof(int));

        convert(_MIPP_ 1,mr_mip->w3);  /* unity */
        mem=memalloc(_MIPP_ 3*m);

        for (i=0;i<m;i++)
        {
            A[i]=mirvar_mem(_MIPP_ mem,3*i);
            B[i]=mirvar_mem(_MIPP_ mem,3*i+1);
            C[i]=mirvar_mem(_MIPP_ mem,3*i+2);
            flag[i]=0;
            if (compare(x[i]->X,w[i]->X)==0 && compare(x[i]->Y,w[i]->Y)==0)
            { /* doubling */
                if (x[i]->marker==MR_EPOINT_INFINITY || size(x[i]->Y)==0)
                {
                    flag[i]=1;     /* result is infinity */
                    copy(mr_mip->w3,B[i]);
                    continue;
                }
                modsquare2(_MIPP_ x[i]->X,A[i]);
                add2(A[i],x[i]->Y,A[i]);
                copy(x[i]->X,B[i]);
            }
            else
            {
                if (x[i]->marker==MR_EPOINT_INFINITY)
                {
                    flag[i]=2;                    /* w[i] unchanged */
                    copy(mr_mip->w3,B[i]);
                    continue;
                }
                if (w[i]->marker==MR_EPOINT_INFINITY)