ecn2_opt.c

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

/*
 *   MIRACL E(F_p^2) support functions 
 *   mrecn2.c
 *
 *   Copyright (c) 2008 Shamus Software Ltd.
 */

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

static inline void zzn2_div2_i(zzn2 *w)
{
	moddiv2(w->a->w);
	w->a->len=2;
	moddiv2(w->b->w);
	w->b->len=2;
}

static inline void zzn2_tim2_i(zzn2 *w)
{
#ifdef MR_COUNT_OPS
fpa+=2; 
#endif

	modtim2(w->a->w);
	modtim2(w->b->w);
	w->a->len=2;
	w->b->len=2;
}

static inline void zzn2_tim3_i(zzn2 *w)
{
#ifdef MR_COUNT_OPS
fpa+=4; 
#endif

	modtim3(w->a->w);
	modtim3(w->b->w);
	w->a->len=2;
	w->b->len=2;
}

static inline void zzn2_copy_i(zzn2 *x,zzn2 *w)
{
    if (x==w) return;

    w->a->len=x->a->len;
    w->a->w[0]=x->a->w[0];
    w->a->w[1]=x->a->w[1];
    w->b->len=x->b->len;
    w->b->w[0]=x->b->w[0];
    w->b->w[1]=x->b->w[1];

}

static inline void zzn2_add_i(zzn2 *x,zzn2 *y,zzn2 *w)
{

#ifdef MR_COUNT_OPS
fpa+=2; 
#endif

    modadd(x->a->w,y->a->w,w->a->w);
	modadd(x->b->w,y->b->w,w->b->w);
	w->a->len=2;
	w->b->len=2;
}

static inline void zzn2_sub_i(zzn2 *x,zzn2 *y,zzn2 *w)
{
#ifdef MR_COUNT_OPS
fpa+=2; 
#endif
    modsub(x->a->w,y->a->w,w->a->w);
	modsub(x->b->w,y->b->w,w->b->w);
	w->a->len=2;
	w->b->len=2;
}

static inline void zzn2_timesi_i(zzn2 *u)
{
    mr_small w1[2];
	w1[0]=u->a->w[0];
	w1[1]=u->a->w[1];

    u->a->w[0]=u->b->w[0];
    u->a->w[1]=u->b->w[1];

	modneg(u->a->w);

	u->b->w[0]=w1[0];
	u->b->w[1]=w1[1];
}

static inline void zzn2_txx_i(zzn2 *u)
{
  /* multiply w by t^2 where x^2-t is irreducible polynomial for ZZn4
  
   for p=5 mod 8 t=sqrt(sqrt(-2)), qnr=-2
   for p=3 mod 8 t=sqrt(1+sqrt(-1)), qnr=-1
   for p=7 mod 8 and p=2,3 mod 5 t=sqrt(2+sqrt(-1)), qnr=-1 */
    zzn2 t;
	struct bigtype aa,bb;
	big a,b;
	mr_small w3[2],w4[2];
    a=&aa;
	b=&bb;
	a->len=2;
	b->len=2;
	a->w=w3;
	b->w=w4;
	t.a=a;
	t.b=b;
    zzn2_copy_i(u,&t);
    zzn2_timesi_i(u);
    zzn2_add_i(u,&t,u);
    zzn2_add_i(u,&t,u); 
    u->a->len=2;
	u->b->len=2;
}

static inline void zzn2_pmul_i(int i,zzn2 *x)
{
    modpmul(i,x->a->w);
    modpmul(i,x->b->w);
}

static inline void zzn2_sqr_i(zzn2 *x,zzn2 *w)
{
	static mr_small w1[2],w2[2];
#ifdef MR_COUNT_OPS
fpa+=3;
fpc+=2;
#endif
	modadd(x->a->w,x->b->w,w1);
    modsub(x->a->w,x->b->w,w2);
	modmult(x->a->w,x->b->w,w->b->w);
	modmult(w1,w2,w->a->w);   // routine that calculates (a+b)(a-b) ??
	modtim2(w->b->w);
	w->a->len=2;
	w->b->len=2;
}

static inline void zzn2_dblsub_i(zzn2 *x,zzn2 *y,zzn2 *w)
{
#ifdef MR_COUNT_OPS
fpa+=4; 
#endif
    moddblsub(w->a->w,x->a->w,y->a->w);
	moddblsub(w->b->w,x->b->w,y->b->w);
	w->a->len=2;
	w->b->len=2;
}

static inline void zzn2_mul_i(zzn2 *x,zzn2 *y,zzn2 *w)
{
	static mr_small w1[2],w2[2],w5[2];
#ifdef MR_COUNT_OPS
fpa+=5;
fpc+=3;
#endif
/*#pragma omp parallel sections
{
	#pragma omp section */
	modmult(x->a->w,y->a->w,w1);
/*	#pragma omp section */
    modmult(x->b->w,y->b->w,w2);
/*}*/
	
	modadd(x->a->w,x->b->w,w5);
	modadd(y->a->w,y->b->w,w->b->w);
    modmult(w->b->w,w5,w->b->w);
    moddblsub(w->b->w,w1,w2);  /* w->b->w - w1 -w2 */

	modsub(w1,w2,w->a->w); 

	w->a->len=2;
	w->b->len=2; 
}

void zzn2_inv_i(_MIPD_ zzn2 *w)
{
#ifdef MR_OS_THREADS
    miracl *mr_mip=get_mip();
#endif

    if (mr_mip->ERNUM) return;
#ifdef MR_COUNT_OPS
fpc+=4;
fpa+=1;
#endif 
	MR_IN(163)
    modsqr(w->a->w,mr_mip->w1->w); 
    modsqr(w->b->w,mr_mip->w2->w); 
    modadd(mr_mip->w1->w,mr_mip->w2->w,mr_mip->w1->w);
	mr_mip->w1->len=2;

 /*   redc(_MIPP_ mr_mip->w1,mr_mip->w6); */
    copy(mr_mip->w1,mr_mip->w6);
  
    xgcd(_MIPP_ mr_mip->w6,mr_mip->modulus,mr_mip->w6,mr_mip->w6,mr_mip->w6);

/*    nres(_MIPP_ mr_mip->w6,mr_mip->w6); */

    modmult(w->a->w,mr_mip->w6->w,w->a->w);
	modneg(mr_mip->w6->w);
    modmult(w->b->w,mr_mip->w6->w,w->b->w);
    MR_OUT
}

BOOL nres_sqroot(_MIPD_ big x,big w)
{ /* w=sqrt(x) mod p. This depends on p being prime! */
    int i,t,js;
#ifdef MR_COUNT_OPS
fpc+=125; 
#endif   
#ifdef MR_OS_THREADS
    miracl *mr_mip=get_mip();
#endif
    if (mr_mip->ERNUM) return FALSE;

    copy(x,w);
    if (size(w)==0) return TRUE; 


	copy(w,mr_mip->w1);
    for (i=0;i<25;i++)
	{
		modsqr(w->w,w->w);
		modsqr(w->w,w->w);
		modsqr(w->w,w->w);
		modsqr(w->w,w->w);
		modsqr(w->w,w->w);
	}
	w->len=2;

	modsqr(w->w,mr_mip->w2->w);
	mr_mip->w2->len=2;
	if (compare(mr_mip->w1,mr_mip->w2)!=0) {zero(w);return FALSE;}

	
	return TRUE;

}

BOOL zzn2_sqrt(_MIPD_ zzn2 *u,zzn2 *w)
{ /* sqrt(a+ib) = sqrt(a+sqrt(a*a-n*b*b)/2)+ib/(2*sqrt(a+sqrt(a*a-n*b*b)/2))
     where i*i=n */
#ifdef MR_OS_THREADS
    miracl *mr_mip=get_mip();
#endif
#ifdef MR_COUNT_OPS
fpc+=2;
fpa+=1;
#endif 
    if (mr_mip->ERNUM) return FALSE;

    zzn2_copy(u,w);
    if (zzn2_iszero(w)) return TRUE;

    MR_IN(204)  

	modsqr(w->b->w,mr_mip->w7->w);
	modsqr(w->a->w,mr_mip->w1->w);
	modadd(mr_mip->w1->w,mr_mip->w7->w,mr_mip->w7->w);
	mr_mip->w7->len=2;

//    nres_modmult(_MIPP_ w->b,w->b,mr_mip->w7);
//    nres_modmult(_MIPP_ w->a,w->a,mr_mip->w1);
//    nres_modadd(_MIPP_ mr_mip->w7,mr_mip->w1,mr_mip->w7);

    if (!nres_sqroot(_MIPP_ mr_mip->w7,mr_mip->w7)) /* s=w7 */
    {
        zzn2_zero(w);
        MR_OUT
        return FALSE;
    }
#ifdef MR_COUNT_OPS
fpa+=1;
#endif 
    modadd(w->a->w,mr_mip->w7->w,mr_mip->w15->w);
	moddiv2(mr_mip->w15->w);
	mr_mip->w15->len=2;

//    nres_modadd(_MIPP_ w->a,mr_mip->w7,mr_mip->w15);
//    nres_div2(_MIPP_ mr_mip->w15,mr_mip->w15);

    if (!nres_sqroot(_MIPP_ mr_mip->w15,mr_mip->w15))
    {
#ifdef MR_COUNT_OPS
fpa+=1;
#endif 
    modsub(w->a->w,mr_mip->w7->w,mr_mip->w15->w);
	moddiv2(mr_mip->w15->w);
	mr_mip->w15->len=2;


   //     nres_modsub(_MIPP_ w->a,mr_mip->w7,mr_mip->w15);
   //     nres_div2(_MIPP_ mr_mip->w15,mr_mip->w15);
        if (!nres_sqroot(_MIPP_ mr_mip->w15,mr_mip->w15))
        {
            zzn2_zero(w);
            MR_OUT
            return FALSE;
        }
//		else printf("BBBBBBBBBBBBBBBBBB\n");
    }
//	else printf("AAAAAAAAAAAAAAAAAAA\n");
#ifdef MR_COUNT_OPS
fpa+=1;
#endif 
    copy(mr_mip->w15,w->a);
    modadd(mr_mip->w15->w,mr_mip->w15->w,mr_mip->w15->w);
    nres_moddiv(_MIPP_ w->b,mr_mip->w15,w->b);

    MR_OUT
    return TRUE;
}

/*
BOOL zzn2_multi_inverse(_MIPD_ int m,zzn2 *x,zzn2 *w)
{ 
    int i;
    zzn2 t1,t2;
#ifdef MR_OS_THREADS
    miracl *mr_mip=get_mip();
#endif
    if (m==0) return TRUE;
    if (m<0) return FALSE;
    MR_IN(214)

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

    if (m==1)
    {
        zzn2_copy_i(&x[0],&w[0]);
        zzn2_inv_i(_MIPP_ &w[0]);

        MR_OUT
        return TRUE;
    }

    zzn2_from_int(_MIPP_ 1,&w[0]);
    zzn2_copy_i(&x[0],&w[1]);

    for (i=2;i<m;i++)
    {
        if (zzn2_isunity(_MIPP_ &x[i-1]))
            zzn2_copy_i(&w[i-1],&w[i]);
        else
            zzn2_mul_i(&w[i-1],&x[i-1],&w[i]); 
    }

    t1.a=mr_mip->w8;
    t1.b=mr_mip->w9;
    t2.a=mr_mip->w10;
    t2.b=mr_mip->w11;

    zzn2_mul_i(&w[m-1],&x[m-1],&t1);
    if (zzn2_iszero(&t1))
    {
        mr_berror(_MIPP_ MR_ERR_DIV_BY_ZERO);
        MR_OUT
        return FALSE;
    }

    zzn2_inv_i(_MIPP_ &t1);

    zzn2_copy_i(&x[m-1],&t2);
    zzn2_mul_i(&w[m-1],&t1,&w[m-1]);

    for (i=m-2;;i--)
    {
        if (i==0)
        {
            zzn2_mul_i(&t2,&t1,&w[0]);
            break;
        }
        zzn2_mul_i(&w[i],&t2,&w[i]);
        zzn2_mul_i(&w[i],&t1,&w[i]);
        if (!zzn2_isunity(_MIPP_ &x[i])) zzn2_mul_i(&t2,&x[i],&t2);
    }

    MR_OUT 
    return TRUE;   
}

*/

BOOL ecn2_iszero(ecn2 *a)
{
    if (a->marker==MR_EPOINT_INFINITY) return TRUE;
    return FALSE;
}

void ecn2_copy(ecn2 *a,ecn2 *b)
{
    zzn2_copy_i(&(a->x),&(b->x));
    zzn2_copy_i(&(a->y),&(b->y));
#ifndef MR_AFFINE_ONLY
    if (a->marker==MR_EPOINT_GENERAL) zzn2_copy_i(&(a->z),&(b->z));
#endif
    b->marker=a->marker;
}

void ecn2_zero(ecn2 *a)
{
    zzn2_zero(&(a->x)); zzn2_zero(&(a->y)); 
#ifndef MR_AFFINE_ONLY
    if (a->marker==MR_EPOINT_GENERAL) zzn2_zero(&(a->z));
#endif
    a->marker=MR_EPOINT_INFINITY;
}

BOOL ecn2_compare(_MIPD_ ecn2 *a,ecn2 *b)
{
#ifdef MR_OS_THREADS
    miracl *mr_mip=get_mip();
#endif
    if (mr_mip->ERNUM) return FALSE;

    MR_IN(193)
    ecn2_norm(_MIPP_ a);
    ecn2_norm(_MIPP_ b);
    MR_OUT
    if (zzn2_compare(&(a->x),&(b->x)) && zzn2_compare(&(a->y),&(b->y)) && a->marker==b->marker) return TRUE;
    return FALSE;
}

void ecn2_norm(_MIPD_ ecn2 *a)
{
    zzn2 t;
#ifdef MR_OS_THREADS
    miracl *mr_mip=get_mip();
#endif
#ifndef MR_AFFINE_ONLY
    if (mr_mip->ERNUM) return;
    if (a->marker!=MR_EPOINT_GENERAL) return;

    MR_IN(194)

    zzn2_inv_i(_MIPP_ &(a->z));

    t.a=mr_mip->w3;
    t.b=mr_mip->w4;
    zzn2_copy_i(&(a->z),&t);

    zzn2_sqr_i( &(a->z),&(a->z));
    zzn2_mul_i( &(a->x),&(a->z),&(a->x));
    zzn2_mul_i( &(a->z),&t,&(a->z));
    zzn2_mul_i( &(a->y),&(a->z),&(a->y));
    zzn2_from_int(_MIPP_ 1,&(a->z));
    a->marker=MR_EPOINT_NORMALIZED;

    MR_OUT
#endif
}

void ecn2_get(_MIPD_ ecn2 *e,zzn2 *x,zzn2 *y,zzn2 *z)
{
    zzn2_copy_i(&(e->x),x);
    zzn2_copy_i(&(e->y),y);
#ifndef MR_AFFINE_ONLY
    if (e->marker==MR_EPOINT_GENERAL) zzn2_copy_i(&(e->z),z);
	else                              zzn2_from_zzn(mr_mip->one,z);
#endif
}

void ecn2_getxy(ecn2 *e,zzn2 *x,zzn2 *y)
{
    zzn2_copy_i(&(e->x),x);
    zzn2_copy_i(&(e->y),y);
}

void ecn2_getx(ecn2 *e,zzn2 *x)
{
    zzn2_copy_i(&(e->x),x);
}

inline void zzn2_conj_i(zzn2 *x,zzn2 *w)
{
    zzn2_copy_i(x,w);
	modneg(w->b->w);
}

void ecn2_psi(_MIPD_ zzn2 *psi,ecn2 *P)
{
	ecn2_norm(_MIPP_ P);
	zzn2_conj_i(&(P->x),&(P->x));
	zzn2_conj_i(&(P->y),&(P->y));
	zzn2_mul_i(&(P->x),&psi[0],&(P->x));
	zzn2_mul_i(&(P->y),&psi[1],&(P->y));

}

#ifndef MR_AFFINE_ONLY
void ecn2_getz(_MIPD_ ecn2 *e,zzn2 *z)
{
    if (e->marker==MR_EPOINT_GENERAL) zzn2_copy_i(&(e->z),z);
	else                              zzn2_from_zzn(mr_mip->one,z);
}
#endif

void ecn2_rhs(_MIPD_ zzn2 *x,zzn2 *rhs)
{ /* calculate RHS of elliptic curve equation */