mrcurve.c

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

/*
 *   MIRACL elliptic curve routines
 *   mrcurve.c
 *
 *   Assumes Weierstrass equation y^2 = x^3 + Ax + B
 *   See IEEE P1363 Draft Standard 
 *
 *   (See below for Edwards coordinates implementation)
 *
 *   Uses Montgomery's representation internally
 *
 *   Works particularly well with fixed length Comba multiplier
 *   e.g. #define MR_COMBA 5 for 5x32 = 160 bit modulus
 *        on 32-bit computer
 *
 *   Copyright (c) 1997-2009 Shamus Software Ltd.
 */

#include <stdlib.h> 
#include "miracl.h"
#ifdef MR_STATIC
#include <string.h>
#endif

#ifndef MR_EDWARDS

static void epoint_getrhs(_MIPD_ big x,big y)
{ /* x and y must be different */

  /* find x^3+Ax+B */
#ifdef MR_OS_THREADS
    miracl *mr_mip=get_mip();
#endif
    nres_modmult(_MIPP_ x,x,y);

    nres_modmult(_MIPP_ y,x,y);
    if (mr_abs(mr_mip->Asize)==MR_TOOBIG)
        nres_modmult(_MIPP_ x,mr_mip->A,mr_mip->w1);
    else
        nres_premult(_MIPP_ x,mr_mip->Asize,mr_mip->w1);
    nres_modadd(_MIPP_ y,mr_mip->w1,y);
    if (mr_abs(mr_mip->Bsize)==MR_TOOBIG)
        nres_modadd(_MIPP_ y,mr_mip->B,y);
    else
    {
        convert(_MIPP_ mr_mip->Bsize,mr_mip->w1);
        nres(_MIPP_ mr_mip->w1,mr_mip->w1);
        nres_modadd(_MIPP_ y,mr_mip->w1,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->w3);

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

    redc(_MIPP_ mr_mip->w3,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);
        copy(mr_mip->one,p->Y);
        p->marker=MR_EPOINT_INFINITY;
        MR_OUT
        return TRUE;
    }

/* find x^3+Ax+B */

    nres(_MIPP_ x,p->X);

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

    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->w3)==0) valid=TRUE;
    }
    else
    { /* no y supplied - calculate one. Find square root */
#ifndef MR_NOSUPPORT_COMPRESSION

        valid=nres_sqroot(_MIPP_ mr_mip->w3,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)
    {
#ifndef MR_AFFINE_ONLY
        if (mr_mip->coord==MR_AFFINE)
        { /* (0,1) or (0,0) = O */
#endif
            if (x!=NULL) zero(x);
            if (mr_mip->Bsize==0)
            {
                if (y!=NULL) copy(mr_mip->w1,y);
            }
            else
            {
                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);
        MR_OUT
        return;
    }
    if (x!=NULL) redc(_MIPP_ p->X,x);
    if (y!=NULL) redc(_MIPP_ 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) redc(_MIPP_ mr_mip->w1,z);
            else redc(_MIPP_ p->Z,z);
        }
    }
#endif
    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(x);
        zero(y);
        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

#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(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_ mr_mip->w8,mr_mip->w8,mr_mip->w1);/* 1/ZZ */
    nres_modmult(_MIPP_ p->X,mr_mip->w1,p->X);            /* X/ZZ */
    nres_modmult(_MIPP_ mr_mip->w1,mr_mip->w8,mr_mip->w1);/* 1/ZZZ */
    nres_modmult(_MIPP_ p->Y,mr_mip->w1,p->Y);            /* Y/ZZZ */

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

#endif

    return TRUE;
}

BOOL epoint_multi_norm(_MIPD_ int m,big *work,epoint **p)
{ /* Normalise an array of points of length m<MR_MAX_M_T_S - requires a workspace array of length m */

#ifdef MR_OS_THREADS
    miracl *mr_mip=get_mip();
#endif
 
#ifndef MR_AFFINE_ONLY
    int i;
    big w[MR_MAX_M_T_S];
    if (mr_mip->coord==MR_AFFINE) return TRUE;
    if (mr_mip->ERNUM) return FALSE;   
    if (m>MR_MAX_M_T_S) return FALSE;

    MR_IN(190)

    for (i=0;i<m;i++)
    {
        if (p[i]->marker==MR_EPOINT_NORMALIZED) w[i]=mr_mip->one;
        else w[i]=p[i]->Z;
    }
  
    if (!nres_multi_inverse(_MIPP_ m,w,work)) 
    {
       MR_OUT
       return FALSE;
    }

    for (i=0;i<m;i++)
    {
        copy(mr_mip->one,p[i]->Z);
        p[i]->marker=MR_EPOINT_NORMALIZED;
        nres_modmult(_MIPP_ work[i],work[i],mr_mip->w1);
        nres_modmult(_MIPP_ p[i]->X,mr_mip->w1,p[i]->X);    /* X/ZZ */
        nres_modmult(_MIPP_ mr_mip->w1,work[i],mr_mip->w1);
        nres_modmult(_MIPP_ p[i]->Y,mr_mip->w1,p[i]->Y);    /* Y/ZZZ */
    }    
    MR_OUT
#endif
    return TRUE;   
}

/* adds b+=a, d+=c, and slopes in s1 and s2 */

#ifndef MR_NO_ECC_MULTIADD
#ifndef MR_STATIC

void ecurve_double_add(_MIPD_ epoint *a,epoint*b,epoint *c,epoint *d,big *s1,big *s2)
{
#ifdef MR_OS_THREADS
    miracl *mr_mip=get_mip();
#endif
    if (mr_mip->ERNUM) return;    

    MR_IN(144);

#ifndef MR_AFFINE_ONLY

    if (mr_mip->coord==MR_AFFINE)
    {
#endif
        if (a->marker==MR_EPOINT_INFINITY || size(a->Y)==0)
        {
            *s1=NULL;
            ecurve_add(_MIPP_ c,d);
            *s2=mr_mip->w8;
            MR_OUT
            return;
        }
        if (b->marker==MR_EPOINT_INFINITY || size(b->Y)==0)
        {
            *s1=NULL;
            epoint_copy(a,b);
            ecurve_add(_MIPP_ c,d);
            *s2=mr_mip->w8;
            MR_OUT
            return;
        }
        if (c->marker==MR_EPOINT_INFINITY || size(c->Y)==0)
        {
            ecurve_add(_MIPP_ a,b);
            *s1=mr_mip->w8;
            *s2=NULL;
            MR_OUT
            return;
        }
        if (d->marker==MR_EPOINT_INFINITY || size(d->Y)==0)
        {
            epoint_copy(c,d);
            ecurve_add(_MIPP_ a,b);
            *s1=mr_mip->w8;
            *s2=NULL;
            MR_OUT
            return;
        }

        if (a==b || (mr_compare(a->X,b->X)==0 && mr_compare(a->Y,b->Y)==0))
        {
            nres_modmult(_MIPP_ a->X,a->X,mr_mip->w8);
            nres_premult(_MIPP_ mr_mip->w8,3,mr_mip->w8); /* 3x^2 */
            if (mr_abs(mr_mip->Asize)==MR_TOOBIG)
                nres_modadd(_MIPP_ mr_mip->w8,mr_mip->A,mr_mip->w8);
            else
            {
                convert(_MIPP_ mr_mip->Asize,mr_mip->w2);
                nres(_MIPP_ mr_mip->w2,mr_mip->w2);
                nres_modadd(_MIPP_ mr_mip->w8,mr_mip->w2,mr_mip->w8);
            }
            nres_premult(_MIPP_ a->Y,2,mr_mip->w10);
        }
        else
        {
            if (mr_compare(a->X,b->X)==0)
            {
                epoint_set(_MIPP_ NULL,NULL,0,b);
                *s1=NULL;
                ecurve_add(_MIPP_ c,d);
                *s2=mr_mip->w8;
                MR_OUT
                return;
            }
            nres_modsub(_MIPP_ a->Y,b->Y,mr_mip->w8);
            nres_modsub(_MIPP_ a->X,b->X,mr_mip->w10);
        }

        if (c==d || (mr_compare(c->X,d->X)==0 && mr_compare(c->Y,d->Y)==0))
        {
            nres_modmult(_MIPP_ c->X,c->X,mr_mip->w9);
            nres_premult(_MIPP_ mr_mip->w9,3,mr_mip->w9); /* 3x^2 */
            if (mr_abs(mr_mip->Asize)==MR_TOOBIG)
                nres_modadd(_MIPP_ mr_mip->w9,mr_mip->A,mr_mip->w9);
            else
            {
                convert(_MIPP_ mr_mip->Asize,mr_mip->w2);
                nres(_MIPP_ mr_mip->w2,mr_mip->w2);
                nres_modadd(_MIPP_ mr_mip->w9,mr_mip->w2,mr_mip->w9);
            }
            nres_premult(_MIPP_ c->Y,2,mr_mip->w11);
        }
        else
        {
            if (mr_compare(c->X,d->X)==0)
            {
                epoint_set(_MIPP_ NULL,NULL,0,d);
                *s2=NULL;
                ecurve_add(_MIPP_ a,b);
                *s1=mr_mip->w8;
                MR_OUT
                return;
            }
            nres_modsub(_MIPP_ c->Y,d->Y,mr_mip->w9);
            nres_modsub(_MIPP_ c->X,d->X,mr_mip->w11);
        }

        nres_double_inverse(_MIPP_ mr_mip->w10,mr_mip->w10,mr_mip->w11,mr_mip->w11);
        nres_modmult(_MIPP_ mr_mip->w8,mr_mip->w10,mr_mip->w8);
        nres_modmult(_MIPP_ mr_mip->w9,mr_mip->w11,mr_mip->w9);

        nres_modmult(_MIPP_ mr_mip->w8,mr_mip->w8,mr_mip->w2); /* m^2 */
        nres_modsub(_MIPP_ mr_mip->w2,a->X,mr_mip->w1);
        nres_modsub(_MIPP_ mr_mip->w1,b->X,mr_mip->w1);

        nres_modsub(_MIPP_ b->X,mr_mip->w1,mr_mip->w2);
        nres_modmult(_MIPP_ mr_mip->w2,mr_mip->w8,mr_mip->w2);
        nres_modsub(_MIPP_ mr_mip->w2,b->Y,b->Y);
        copy(mr_mip->w1,b->X);
        b->marker=MR_EPOINT_GENERAL;

        nres_modmult(_MIPP_ mr_mip->w9,mr_mip->w9,mr_mip->w2); /* m^2 */
        nres_modsub(_MIPP_ mr_mip->w2,c->X,mr_mip->w1);
        nres_modsub(_MIPP_ mr_mip->w1,d->X,mr_mip->w1);

        nres_modsub(_MIPP_ d->X,mr_mip->w1,mr_mip->w2);
        nres_modmult(_MIPP_ mr_mip->w2,mr_mip->w9,mr_mip->w2);
        nres_modsub(_MIPP_ mr_mip->w2,d->Y,d->Y);
        copy(mr_mip->w1,d->X);
        d->marker=MR_EPOINT_GENERAL;