uvlong.cpp

椭圆曲线密码C实现的

#include "stdafx.h"
#include "uvlong.h"

//-------------------------------------------------------------------------------
void shl_cl(ULINT  x)
{
	ushort carry = 0;
	ushort N = x[0]; // necessary, since n can change
	
	for (int i = 1; i <= N+1; i+=1 )
	{
		ushort u = x[i];
		x[i] = ((u<<1)+carry);
		carry = u>>(BPU-1);
		if(x[i] != 0 )
		{
			x[0] = i;
		}
	}
	trim(x);
	
}

void shr_cl(ULINT  x)
{
	ushort carry = 0;
	ushort i=x[0];
	while (i>0)
	{	
		ushort u = x[i];
		x[i] = ((u>>1)+carry);
		carry = u<<(BPU-1);
		i -= 1;
	}
}

void clean_cl(ULINT  x)	
{ 
	for(int i = 0; i< CLINTMAXDIGIT+1; i++) x[i] = 0; 
}

void init_cl(ULINT  x,ushort v)
{
	clean_cl(x);
	if(x > 0)
	{
		x[0] = 1;
		x[1] = v;
	}
}

int copy_cl(ULINT   a, ULINT const b)
{
	clean_cl(a);
	if(b[0] > CLINTMAXDIGIT)
		return RSA_ERR_OF;
	
	for(int i = 0; i<= b[0]; i++)
	{
		a[i] = b[i] ;
	}
	
	return RSA_ERR_OK;
}

int add_cl(ULINT  const a,ULINT  const b,ULINT s)
{

	ushort	c = 0;
	ushort	const *ap,*bp;
	
	unsigned int	i = 1;
	unsigned int	t;
	unsigned int	B = (1<<(8*sizeof(ushort)));	//B为基数（一个unsigned short），
	
	ULINT	tmp;
	clean_cl(tmp);
	
	if( comp_cl(a,b) >= 0 )
	{
		ap = a;
		bp = b;
		SET_CLINTSIZE(tmp,a[0]);
	}else{
		ap = b;
		bp = a;
		SET_CLINTSIZE(tmp,b[0]);
	}
	
	do{ 
		t =  ap[i] + bp[i] + c;
		tmp[i] =  t&(B-1);
		c =  t/B;
		if(tmp[i] != 0 )
		{
			tmp[0] = i;
		}
	}while( ++i <= bp[0] );
	
	do{
		t = ap[i] + c;
		tmp[i] = t&(B-1);
		c = t/B;
		if(tmp[i] != 0 )
		{
			tmp[0] = i;
		}
	}while( ++i <= ap[0] );
	
	if(i > CLINTMAXDIGIT)
		return RSA_ERR_OF;
	tmp[i] = c;	
	if(tmp[i] != 0 )
	{
		tmp[0] = i;
	}
	copy_cl(s,tmp);
	return RSA_ERR_OK;
}

int sub_cl(ULINT const a,ULINT  const b,ULINT s)
{
	
	ushort	c = 1;
	ushort	const *ap,*bp;
	
	unsigned int	i = 1;
	unsigned int	t;
	unsigned int	B = (1<<(8*sizeof(ushort)));	//B为基数（一个unsigned short），
	
	ULINT	tmp;
	clean_cl(tmp);
	if( comp_cl(a,b) >= 0 )
	{
		ap = a;
		bp = b;
		SET_CLINTSIZE(tmp,a[0]);
	}else{
		ap = b;
		bp = a;
		SET_CLINTSIZE(tmp,b[0]);
	}
	
	do{
		if(c==1)
			t =  B + ap[i] - bp[i] ;
		else
			t =  B - 1 + ap[i] - bp[i] ;
		
		tmp[i] =  t & (B-1);
		c =  t/B;
		if(tmp[i] != 0)
		{
			tmp[0] = i;
		}
		
	}while( ++i <= bp[0]);
	
	do{
		if(c==1)
			t =  B + ap[i];
		else
			t =  B - 1 + ap[i];
		
		tmp[i] = (t&(B-1));
		c = t/B;		
		if(tmp[i]  != 0)
		{
			tmp[0] = i;
		}
	}while(++i <= ap[0]);		
	
	copy_cl(s,tmp);
	return RSA_ERR_OK;
}

int comp_cl( ULINT const a,ULINT  const b)
{	
	if(a[0]>CLINTMAXDIGIT || b[0]>CLINTMAXDIGIT)
		return 0;	//不作处理

	int i = a[0];
	if( i < b[0])	i = b[0];

	while(i > 0){
		if ( a[i] > b[i] ) return +1;
		if ( a[i] < b[i] ) return -1;
		i--;
	};
	
	return 0;
}

int	trim( ULINT  a)
{
	int i;
	i = a[0];
	if(i>CLINTMAXDIGIT)
		return RSA_ERR_02;
	while(i> 0 && a[i]== 0){i--;}
	a[0] = i;
	
	return RSA_ERR_OK;	
}

int mul_cl( ULINT const a, ULINT  const b, ULINT mul, int keep)
{
	//  fast_mul( x, y, x.bits()+y.bits() );
	// *this = (x*y) % (2**keep)
	ULINT  pt;
	int i,limit = (keep+BPU-1)/BPU; // size of result in ushort
	clean_cl(pt);
	
	int	min = a[0]; if ( min > limit ) min = limit;
	
	for (i = 1; i <= min; i += 1)
	{
		ushort m = a[i];
		ushort c = 0; // carry
		int min = i+b[0]; if (min>limit) min = limit;
		for ( int j = i; j <= min; j+=1 )
		{
			// This is the critical loop
			// Machine dependent code could help here
			// c:a[j] = a[j] + c + m*y.a[j-i];
			ushort w, v = pt[j], p = b[j-i+1];
			v += c; c = ( v < c );
			w = ushort(lo(p)*lo(m)); v += w; c += ( v < w );
			w = ushort(lo(p)*hi(m)); c += hi(w); w = lh(w); v += w; c += ( v < w );
			w = ushort(hi(p)*lo(m)); c += hi(w); w = lh(w); v += w; c += ( v < w );
			c += hi(p) * hi(m);
			pt[j] = v;
		}
		
		while ( c && j<=limit )
		{
			pt[j] += c;
			c = pt[j] < c;
			j += 1;
		}
	}
	// eliminate unwanted bits
	keep %= BPU; if (keep) pt[limit] &= (1<<keep)-1;
	// calculate n
	while (limit && pt[limit] ==0 ) limit-=1;
	pt[0] = limit;
	copy_cl(mul,pt);
	return RSA_ERR_OK;

}

int div_cl( ULINT const a, ULINT  const b, ULINT div ,	ULINT  rem)
{
	ULINT s,r,d,m;	
	copy_cl(r,a);
	copy_cl(m,b);
	init_cl(s,1);
	clean_cl(d);
	
	trim(r);	
	trim(m);	
	
	if(IsZero(m))
		return RSA_ERR_02;

	while ( comp_cl(r,m) > 0 )
	{
		shl_cl(m);
		shl_cl(s);
	}
	
	while ( comp_cl(r,b) >= 0 )
	{	
		while ( comp_cl(r,m) < 0 )
		{
			shr_cl(m);
			shr_cl(s);
		}
		sub_cl(r, m ,r);
		add_cl(d, s ,d);	
	}
	copy_cl(div,d);
	copy_cl(rem,r);
	return RSA_ERR_OK;
}

int  modexp_cl( const ULINT x, const ULINT e,const ULINT mod,ULINT result)
{

	int  j=0,i = e[0]*BPU;
	if(i == 0)
		return RSA_ERR_02;
	
	while ( i && ((e[((i-1)/BPU)+1] & (1<<(i-1)%BPU)) == 0) ) 
		i -= 1;	
	
	unsigned char *c=new unsigned char[i];
	memset(c,0x00,i);
	while ( j<i )
	{
		if((e[(j/BPU)+1] & (1<<j%BPU)) > 0)
		{
			c[j] = 1;
		}else{
			c[j] = 0;
		}
		j ++;
	}
	
	ULINT	z;
	init_cl(z,1);
	
	ULINT	div;
	for( j = i-1;j >= 0;j--)
	{
		mul_cl(z,z,z,2*z[0]*16);
		div_cl(z,mod,div,z);
		if(c[j]>0)
		{
			mul_cl(z,x,z,(z[0]+x[0])*16);
			div_cl(z,mod,div,z);
		}
	}
	delete []c;
	copy_cl(result,z);
	return RSA_ERR_OK;
}

int  gcd_cl( const ULINT  X, const ULINT  Y ,ULINT result)
{
	ULINT x, y;
	copy_cl(x,X);
	copy_cl(y,Y);
	
	ULINT t,div;
	init_cl(t,0);
	while (1)
	{
		if(comp_cl(y,t) == 0)
		{
			copy_cl(result,x);
			break; 
		}
		div_cl(x,y,div,x);
		
		if(comp_cl(x,t) == 0)
		{
			copy_cl(result,y);
			break; 
		}
		div_cl(y,x,div,y);
	}
	trim(result);
	return RSA_ERR_OK;
}

int IsZero(const ULINT a)
{
	int i = a[0];
	while(i>0)
	{
		if(a[i]>0 )
			return 0;
		i--;
	}
	return 1;
}
//------------------------------------------------------------------------

uvlong::uvlong()
{
	m_share = 0;
	clean_cl(m_clint);	
}

uvlong::uvlong ( unsigned int	x )
{
	m_share = 0;
	int y = x;
	if(y<0){ x = (y^0xffffffff)+1; }
	
	clean_cl(m_clint);
	for(int i = 1;i<=2;i++)
	{
		m_clint[i] = (x>>(BPU*(i-1))) & 0x0ffff;
		if(m_clint[i]>0)
			m_clint[0] = i;
	}
	
}

uvlong::~uvlong()
{

}

uvlong::operator unsigned()
{
	int x= ( m_clint[0] > 2) ? 2 : m_clint[0];
	
	unsigned int n=0;
	for(int i = 1 ; i <= x ; i++ )
	{
		n += (m_clint[i]<<(BPU*(i-1)));
	}
	return n;
}

uvlong& uvlong::Append( const ushort& x )
{
	if( m_clint[0] < CLINTMAXDIGIT )
	{			
		m_clint[0]	+=	1;
		m_clint[m_clint[0]]	=	x;
	}
	
	return *this;
}

int uvlong::GetBits() const
{
	int x = m_clint[0]*BPU;
	while (x && test(x-1)==0) x -= 1;
	return x;
	
}

int uvlong::test(unsigned int i) const
{
	return (m_clint[(i/BPU)+1] & (1<<(i%BPU)) ) != 0; 
}

uvlong& uvlong::modexp( const uvlong & m, const uvlong & e, const uvlong & mod )
{
	modexp_cl(m.m_clint, e.m_clint, mod.m_clint, m_clint);
	return *this;
}

void uvlong::ReArray()
{
	unsigned j=0, i = m_clint[0];
	unsigned char * p ;
	
	while(m_clint[i] == 0 && i >= 1){
		i--;
	}
	if(i > 0)
	{
		p =  (unsigned char *)&m_clint[i];
		if(m_clint[i] > 0xff){ p++; }
		while(j<8)
		{
			if(*p & (1<<j)){ break; }
			j++;
		}
		*p = (*p)>>j;	
	}	
	m_clint[0] = i;
}

uvlong& uvlong::gcd(const uvlong &a, const uvlong &b)
{
	gcd_cl(a.m_clint, b.m_clint, m_clint);
	return *this;
}