mrec2m.c

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

/*
 *   MIRACL routines for implementation of Elliptic Curve Cryptography over GF(2^m) 
 *   mrec2m.c
 *
 *   Curve equation is Y^2 + XY = X^3 + A.X^2 + B
 *   where A is 0 or 1
 *
 *   For algorithms used, see IEEE P1363 Standard, Appendix A
 *   unless otherwise stated.
 *
 *   New from version 5.1.1 - changed from IEEE to Lopez-Dahab coordinates
 *   See "A note on Lopez-Dahab coordinates" - Tanja Lange (eprint archive)
 *   (x,y,z) = (x/z,y/(z*z),1)
 *
 *   For supersingular curves Ordinary Projective coordinates are used.
 *   (x,y,z) = (x/z,y/z,1)
 *
 *   READ COMMENTS CAREFULLY FOR VARIOUS OPTIMIZATION SUGGESTIONS
 *
 *   No assembly language used.
 *
 *   Space can be saved by removing unneeded functions and 
 *   deleting unrequired functionality 
 *
 *   Copyright (c) 2000-2007 Shamus Software Ltd.
 */

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

#ifndef MR_NOFULLWIDTH
                     /* This does not make sense using floating-point! */

/* 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

/* catch some nonsense conditions */

    if (mr_mip->ERNUM) return FALSE;

#ifndef MR_NOKOBLITZ
    mr_mip->KOBLITZ=FALSE;
#endif

#ifndef MR_NO_SS
    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;
    }
#else
    if (m<0) return FALSE;
#endif
    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);

#ifndef MR_NOKOBLITZ
#ifndef MR_NO_SS
    if (!mr_mip->SS && mr_mip->Bsize==1)
#else
    if (mr_mip->Bsize==1)
#endif
    {
        if (mr_mip->Asize==0 || mr_mip->Asize==1)
        {
            mr_mip->KOBLITZ=TRUE;
        }
    }
#endif

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

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

#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
    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;       

#ifndef MR_NO_SS
    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 (mr_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 */
#endif
        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 (mr_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);
            }
        }
#ifndef MR_NO_SS
    }
#endif
    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;
    }

#ifndef MR_NO_SS
    if (mr_mip->SS)
    {
        modmult2(_MIPP_ p->X,mr_mip->w8,p->X);
        modmult2(_MIPP_ p->Y,mr_mip->w8,p->Y); 
    }
    else
    {
#endif
        modmult2(_MIPP_ p->X,mr_mip->w8,p->X);               /* X/Z */
        modsquare2(_MIPP_ mr_mip->w8,mr_mip->w8);            /* 1/ZZ */ 
        modmult2(_MIPP_ p->Y,mr_mip->w8,p->Y);               /* Y/ZZ */
#ifndef MR_NO_SS
    }
#endif

    convert(_MIPP_ 1,p->Z);

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

#ifndef MR_STATIC

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

#endif

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;
    }
#ifndef MR_NO_SS
    if (mr_mip->SS)
    {
        lsb=parity2(p->Y);
    }
    else
    {
#endif
        inverse2(_MIPP_ x,mr_mip->w5);
        modmult2(_MIPP_ mr_mip->w5,p->Y,mr_mip->w5);

        lsb=parity2(mr_mip->w5);
#ifndef MR_NO_SS
    }
#endif
    MR_OUT
    return lsb;
}

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

#ifndef MR_NO_SS
        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;
        }    
#endif
        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;
#ifndef MR_AFFINE_ONLY
    }

#ifndef MR_NO_SS
    if (mr_mip->SS)
    { /* super-singular */

        modsquare2(_MIPP_ p->X,p->X);
        modsquare2(_MIPP_ p->X,p->X);
        modsquare2(_MIPP_ p->Y,p->Y);
        modsquare2(_MIPP_ p->Y,p->Y);
        if (p->marker!=MR_EPOINT_NORMALIZED)
        {
            modsquare2(_MIPP_ p->Z,p->Z);
            modsquare2(_MIPP_ p->Z,p->Z);           /* z^4 */
            add2(p->Y,p->X,p->Y);                   /* y^4+x^4 */ 
            add2(p->X,p->Z,p->X);                   /* z^4+z^4 */
        }
        else
        {
            add2(p->Y,p->X,p->Y);
            incr2(p->X,1,p->X);
        }
 
        return;
    }   
#endif    

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

    modsquare2(_MIPP_ p->X,mr_mip->w1);    /* S=X^2 */
    add2(p->Y,mr_mip->w1,p->Y);            /* U=S+Y */

    if (p->marker!=MR_EPOINT_NORMALIZED) 
    {
        modmult2(_MIPP_ p->X,p->Z,mr_mip->w4); /* T=X*Z */
        modsquare2(_MIPP_ mr_mip->w4,p->Z);    /* Z=T*T */
    }
    else 
    {
        copy(p->X,mr_mip->w4);
        copy(mr_mip->w1,p->Z);
    }

    modmult2(_MIPP_ mr_mip->w4,p->Y,mr_mip->w4); /* T=U*T */

    modsquare2(_MIPP_ p->Y,p->Y);     /* U*U */
    add2(p->Y,mr_mip->w4,p->X);       /* U*U+T */
    if (mr_mip->Asize>0)              /* X=U*U+T+AZ */
    {
        if (mr_mip->Asize>1)
        {
            if (mr_mip->Asize==MR_TOOBIG)
                copy(mr_mip->A,p->Y);
            else 
                convert(_MIPP_ mr_mip->Asize,p->Y);
            modmult2(_MIPP_ p->Y,p->Z,p->Y);
            add2(p->X,p->Y,p->X);
        }
        else
            add2(p->X,p->Z,p->X);
    }

    add2(mr_mip->w4,p->Z,mr_mip->w4);         /* Z+T */
    modmult2(_MIPP_ p->X,mr_mip->w4,p->Y);
    modsquare2(_MIPP_ mr_mip->w1,mr_mip->w1); /* S*S */
    modmult2(_MIPP_ mr_mip->w1,p->Z,mr_mip->w1);
    add2(p->Y,mr_mip->w1,p->Y);

    p->marker=MR_EPOINT_GENERAL;
#endif
}

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 */