bigintcpp.cpp

RSA加密中的大整数运算

#include<stdio.h>
#include<math.h>
#include<iostream>
#include"BigInth.h"
#include<string>
using namespace std;
//预处理表格（用于模指数运算）

//428


BigInt PreTable[16];
BigInt pre_base[16];
//预处理表格（用于模乘运算）
BigInt TableModBase[36];
BigInt TableModMult[16];
// unsigned char HexArray[]=...
unsigned char HArray[]={'0','1','2','3','4','5','6','7','8','9','A','B','C','D','E','F'};
unsigned __int64 LMASK[]={0x0L,0x8000000000000000L,0xC000000000000000L,0xE000000000000000L,0xF000000000000000L};
unsigned __int64 RMASK[]={0x0L,0x0000000000000001L,0x0000000000000003L,0x0000000000000007L,0x000000000000000FL};
//a-f(61-66)0x110001-01100110
unsigned char hdigit(unsigned char c)
{
	unsigned char hi,lo;
	hi=c>>4;
	lo=c&0x0f;
	if(hi==0x04)return(lo+0x09);
	if(hi==0x06)return(lo+0x09);
	return lo;
}
	//431
BigInt operator +(const BigInt & p1,const unsigned __int64 & p2)
{
	int i;
	BigInt result;
	unsigned __int64 carry;

	i=0;
	result.iIdx=p1.iIdx;
	carry=p2;
	while(i<=p1.iIdx)
	{
		result.iVal[i]=p1.iVal[i]+carry;
		if(result.iVal[i]<carry)
			carry=1;
		else
			carry=0;
		i++;
	}
	if(result.iVal[result.iIdx+1]!=0)
		result.iIdx++;
	return result;
}

BigInt operator +(const BigInt & p1,const BigInt & p2)
{
	//operator+
	int i;
	short stop;
	BigInt result;
	unsigned __int64 carry;

	if(BIisZero(p1))
		return p2;
	if(BIisZero(p2))
		return p1;

	result.setZero();
	stop=p1.iIdx;
	if(stop<p2.iIdx)
		stop=p2.iIdx;
	result.iIdx=stop;

	carry=0;
	for(i=0;i<=stop;i++)
	{
		result.iVal[i]=p1.iVal[i]+p2.iVal[i]+carry;
		if(result.iVal[i]<p2.iVal[i])
			carry=1;
		else 
			carry=0;
	}
	if(carry==1)
	{
		stop++;
		result.iVal[stop]=1;
		result.iIdx=stop;
	}
	return result;
}
BigInt operator*(const BigInt &p1,const unsigned __int64 &p2)
{
	//operator*
	//result=p1*p2
	BigInt result;
	unsigned __int64 carry,dhigh,dlow;
	int i;

	if(BIisZero(p1))
		return result;
	if(p2==0)
		return result;

	result.iIdx=p1.iIdx+1;
	carry=0;
	for(i=0;i<=p1.iIdx;i++)
	{
		if(result.iVal[i]<carry)
			carry=1;
		else
			carry=0;
		BImul(p1.iVal[i],p2,dhigh,dlow);
		result.iVal[i]+=dlow;
		if(result.iVal[i]<dlow)
			carry++;
		carry+=dhigh;
		result.iVal[i+1]+=carry;
	}
	while(result.iVal[result.iIdx]==0)
	{
		result.iIdx--;
		if(result.iIdx==65535)break;
	}
	return result;
}

//p448
BigInt operator*(const BigInt & p1,const BigInt & p2)
{
	//operator*
	//result=p1*p2
	BigInt result;
	unsigned __int64 carry,dhigh,dlow;
	int i,j;

	//carry=dhigh
	if(BIisZero(p1))
		return result;
	if(BIisZero(p2))
		return result;

	result.iIdx=p1.iIdx+p2.iIdx+1;
	if(result.iIdx>TOTALBOXS)
		result.iIdx=TOTALBOXS;
	for(i=0;i<=p2.iIdx;i++)
	{
		carry=0;
		if(p2.iVal[i]!=0)
		{
			for(j=0;j<=p1.iIdx;j++)
			{
				BImul(p1.iVal[j],p2.iVal[i],dhigh,dlow);
				result.iVal[i+j]+=carry;
				if(result.iVal[i+j]<carry)
					carry=1;
				else
					carry=0;
				result.iVal[i+j]+=dlow;
				if(result.iVal[i+j]<dlow)
					carry++;
				carry+=dhigh;
			}
		}
		result.iVal[i+p1.iIdx+1]+=carry;
	}
	while(result.iVal[result.iIdx]==0)
	{
		result.iIdx--;
		if(result.iIdx==65535)
		{
			result.iIdx=0;
			break;
		}
	}
	return result;
}

inline bool operator!=(const BigInt & p1,const BigInt & p2)
{
	//operator!=
	if(p1.iIdx!=p2.iIdx)
		return true;
	for(int i=0;i<=p1.iIdx;i++)
	{
		if(p1.iVal[i]!=p2.iVal[i])
			return true;
	}
	return false;
}



BigInt::BigInt()
{
	iIdx=0;
	for(int i=0;i<TOTALBOXS;i++)
		iVal[i]=0;
}

BigInt::~BigInt()
{}

void BigInt::setZero(void)
{
	iIdx=0;
	for(int i=0;i<TOTALBOXS;i++)
		iVal[i]=0;
}

void BigInt::setFull(void)
{
	iIdx=65;
	for(int i=0;i<TOTALBOXS;i++)
		iVal[i]=FULL;
}

void BigInt::loadDEC(const string itext)
{
	int seg,bgn,end,ttl;
	char lstr[9];
	BigInt a,b;
//	short k;

	ttl=itext.length();
	seg=(itext.length()-1)/LenMAXDEC;
	bgn=1;
	b.iIdx=0;
	for(int i=seg;i>=0;i--)
	{
		end=ttl%LenMAXDEC;
		if(end==0)end=LenMAXDEC;
		//Change to HEX
		for(int j=0;j<9;j++)
			lstr[j]='0';
		for(j=1;j<=end;j++)
			lstr[9-j]=itext[bgn+end-j-1];
		b.iVal[0]=_atoi64(lstr);
		if(bgn==1)
			a=b;
		
		//432
		else
		{
			//MAXDEC 1000000000
			a=a*MAXDEC;
			a=a+b;
		}
		bgn=bgn+end;
		ttl=ttl-end;
	}
		iIdx=a.iIdx;
		for(i=0;i<=iIdx;i++)
			iVal[i]=a.iVal[i];
	
}

void BigInt::loadHEX(const string itext)
{
	int seg,bgn,end,ttl;
	unsigned __int64 tmp;

	ttl=itext.length();
	seg=(itext.length()-1)/LenMAXHEX;
	bgn=1;
	for(int i=seg;i>=0;i--)
	{
		end=ttl%LenMAXHEX;
		if(end==0)end=LenMAXHEX;
		tmp=0;
		for(int j=1;j<=end;j++)
		{
			tmp<<=4;
			tmp=tmp|hdigit(itext[bgn-1]);
			bgn++;
		}
		iVal[i]=tmp;
		ttl=ttl-end;
	}
	iIdx=seg;
}

//432

void BigInt::loadSTR(const string itext)
{
   int seg,bgn,end,ttl;
   unsigned __int64 tmp;
   ttl=itext.length();
   seg=(itext.length()-1)/LenMAXWRD;
   bgn=1;
   for(int i=seg;i>=0;i--)
   {
	   end=ttl%LenMAXWRD;
	   if(end==0)end=LenMAXWRD;
	   tmp=0;
	   for(int j=1;j<=end;j++)
	   {
		   tmp<<=8;
		   tmp=tmp|(unsigned char)itext[bgn-1];
		   bgn++;
	   }
	   iVal[i]=tmp;
	   ttl=ttl-end;
   }
   iIdx=seg;
}

//433

int BIcompare(const BigInt & p1,const BigInt & p2)
{
	short i,j;
	i=p1.iIdx;
	j=p2.iIdx;
	if(i>j)
		return 1;
	else if(i<j)
		return -1;
	else 
	{
		while(i>=0)
		{
		
		if(p1.iVal[i]>p2.iVal[i])
			return 1;
		else if(p1.iVal[i]<p2.iVal[i])
			return -1;
		i--;
	}
	return 0;
	}
}

////////////////////////////////
//从440页开始到458页
/////////////////////////////////

//p434
int BIcompare(const BigInt &p1,const unsigned __int64 &p2)
{
	if(p1.iIdx>0)
		return 1;
	else
	{
		if(p1.iVal[0]>p2)
			return 1;
		else if(p1.iVal[0]<p2)
			return -1;
		else 
			return 0;
	}
}

BigInt &BigInt::operator++(int)
{
	unsigned __int64 tmp,carry;
	int i;

	i=0;
	carry=1;
	while(carry==1)
	{
		tmp=iVal[i]+carry;
		if(tmp<iVal[i])
			carry=1;
		else
			carry=0;
		iVal[i]=tmp;
		i++;
	}
	if(iVal[iIdx+1]!=0)
		iIdx++;
	return *this;
}

BigInt &BigInt::operator--(int)
{
//	unsigned __int64 tmp,carry;
	unsigned __int64 carry;
	int i;

	i=0;
	carry=1;
	while(carry==1)
	{
		if(iVal[i]==0x0)
		{
			iVal[i]=FULL;
			carry=1;
		}
		else
		{
			iVal[i]--;
			carry=0;
		}
	}
	if(iVal[iIdx]==0)
	{
		iIdx--;
		if(iIdx==65535)iIdx=0;
	}
	return *this;
}

//p435
void BigInt::ShiftAdd(const unsigned __int64 p1)
{
	int i;
	unsigned __int64 carry;
	iVal[iIdx+1]=iVal[iIdx]>>60;

	for(i=iIdx;i>0;i--)
		iVal[i]=(iVal[i]<<4)|(iVal[i-1]>>60);

	iVal[0]=(iVal[0]<<4);
	carry=p1;
	i=0;
	while(carry!=0)
	{
		iVal[i]=iVal[i]+carry;
		if(iVal[i]<carry)
			carry=1;
		else
			carry=0;
		i++;
	}
	if(iVal[iIdx+1]!=0)
		iIdx++;
}
	
//p436
BigInt & BigInt::operator<<=(const short & iBit)
{
	//LM=0x80000+.0xC0000+,0xE0000+,0xF0000+,...<0xFFFFF+};
	//0+is 000,F+if FFFF
	unsigned __int64 b1,b2,LM;
	short i,shift,ishift;

	if((iIdx==0)&(iVal[0]==0))
		return *this;

	//lest shift over TOTALBITS bits
	ishift=iBit;
	while(ishift>=TOTALBITS)
	{
		for(i=iIdx;i>=0;i--)
			iVal[i+1]=iVal[i];
		iVal[0]=0;
		iIdx++;
		ishift-=TOTALBITS;
	}
	if(ishift==0)
		return *this;

	//left shift less than TOTALBITS bits
	b1=0x0;
	shift=TOTALBITS-ishift;
	LM=FULL<<shift;
	for(i=0;i<=iIdx;i++)
	{
		b2=iVal[i]&LM;
		iVal[i]=(iVal[i]<<ishift)|b1;
		if(b2==0x0)
			b1=0x0;
		else
			b1=b2>>shift;
	}
	if(iIdx!=TOTALBOXS-1)
	{
		if(b1!=0x0)
		{
			iIdx++;
			iVal[iIdx]=b1;
		}
	}
	else
	{
		for(i=TOTALBOXS-1;i>=0;i--)
			if(iVal[i]!=0)
			{
				iIdx=i;
				break;
			}
			if((i==-1)&&(iIdx!=0))
				iIdx=0;
	}
	return *this;
}

//p437
BigInt &BigInt::operator>>=(const short &iBit)
{
	//Rm=0x0+0001,0x0+0003,0x0+0007,0x0+000F,...,0xFFFFF+};
	unsigned __int64 b1,b2,RM;
	short i,shift,ishift;

	if((iIdx==0)&(iVal[0]==0))
		return *this;

	ishift=iBit;
	while(ishift>=TOTALBITS)
	{
		for(i=0;i<iIdx;i++)
			iVal[i]=iVal[i+1];
		iVal[iIdx]=0;
		iIdx--;
		ishift-=TOTALBITS;
	}
	if(ishift==0)
		return *this;

	b1=0x0;
	shift=TOTALBITS-ishift;
	RM=FULL>>shift;
	for(i=iIdx;i>=0;i--)
	{
		b2=iVal[i]&RM;
		iVal[i]=iVal[i]>>ishift|b1;
		if(b2==0x0)
			b1=0x0;
		else
			b1=b2<<shift;
	}
	if((iVal[iIdx]==0)&&(iIdx>0))
		iIdx--;
	return *this;
}
//438
string BigInt::outputDEC(void)
{
	BigInt a,b,c,tempb;
	tempb=*this;
	int i;
//	string aa;

//	aa=" ";
	a.iIdx=tempb.iIdx;
	for(i=tempb.iIdx;i>=0;i--)
		a.iVal[i]=tempb.iVal[i];
	b.iIdx=0;
	b.iVal[0]=MAXDEC2;
	tempb.iIdx=0;
	while(BIcompare(a,MAXDEC2)>0)
	{
		a=BIdivision(a,b,c);
		tempb.iVal[tempb.iIdx++]=c.iVal[0];
	}
	tempb.iVal[tempb.iIdx]=a.iVal[0];
	//output the value
	char buffer[1000000]="\0";
	char temp[100];
	for(i=tempb.iIdx;i>=0;i--)
	{
	//	aa=aa+IntToStr((__int64)iVal[i]);
       _i64toa((__int64)tempb.iVal[i],temp,10);                               //改
		strcat(buffer,temp);
	
//	string buffer;
//	_i64toa((__int64)iVal[i],(char *)buffer,10);
	}

basic_string<char> aa =buffer;
	return aa;
}

string BigInt::outputHEX(void)
{
	//unsigned char cs[640];
	BigInt temp;
	temp=*this;
//	string cs;
 char cs[8192];
//	string aa;
	unsigned short k,l;

	for(int i=0;i<8192;i++)
		cs[i]='\0';
	l=0;
	for(i=temp.iIdx;i>=0;i--)
	{
		for(int j=60;j>=0;j-=4)
		{
			k=(temp.iVal[i]>>j) & 0x0F;
			cs[l++]=HArray[k];
		}
	}
	//cd[l]='\0';
	//aa.sprintf(cs);                                //改
 //  aa=string(cs);

//	strcpy(aa,cs);

 //basic_string<char> aa =cs;
	string aa=cs;
	return aa;
}

//p439
string BigInt::outputSTR(void)
{
 char cs[8192];
	int i,j,k;
//	string cs;

	for(i=0;i<8192;i++)
		cs[i]='\0';
	j=0;

	cs[j]=(iVal[iIdx]>>56) & 0xff;
	if(cs[j]!='\0')   j++;
	cs[j]=(iVal[iIdx]>>48) & 0xff;
	if(cs[j]!='\0')   j++;
	cs[j]=(iVal[iIdx]>>40) & 0xff;
	if(cs[j]!='\0')   j++;
	cs[j]=(iVal[iIdx]>>32) & 0xff;
	if(cs[j]!='\0')   j++;
	cs[j]=(iVal[iIdx]>>24) & 0xff;
	if(cs[j]!='\0')   j++;
	cs[j]=(iVal[iIdx]>>16) & 0xff;
	if(cs[j]!='\0')   j++;
	cs[j]=(iVal[iIdx]>>8) & 0xff;
	if(cs[j]!='\0')   j++;
	cs[j]=(iVal[iIdx]) & 0xff;//???????????????
	if(cs[j]!='\0')   j++;

	for(i=iIdx-1;i>=0;i--)
	{
		for(k=56;k>=0;k-=8)
			cs[j++]=(iVal[i]>>k) & 0xff;
	}
	//cs[j]='\0';
//	aa.sprintf(cs);                         //改
	
//	aa=(string)cs;

	//sprintf(cs);
	string aa=cs;
	return aa;
}

//p440
short BigInt::Get8BitBlock(const short & unUseHeader,const short & BitIndex)
{
	//BitIndex must over ZERO
	//Header over Zero
	short Header,ots;
	unsigned __int64 m;

	ots=-1;
	Header=unUseHeader+4*BitIndex;
	while(Header>0)
	{
		Header-=64;
		ots++;
	}
	Header=-Header;

	m=iVal[iIdx-ots]>>Header;
	if(Header>60)
	{
		Header=64-Header;
		m=m&(iVal[iIdx]<<Header);
	}
	return m & 0x0F;
}

unsigned char BigInt::Get4BitBlock(const short & which)
{
	short iwhich,idx;
	idx=which>>4;
	return (iVal[idx]>>iwhich)& 0x0F;
}

unsigned char BigInt::Get8BitBlock(const short & which)
{
	//-15-14-13-...-2-1-0--
	//Total 16's 4-bits Block in 64bit Integet

	short iwhich,idx;
	unsigned short m;

	idx=which>>4;
	iwhich=(which & 0xF)<<2;
	if(iwhich!=0)
	{
		m=iVal[idx]>>(iwhich-4);
	}
	else
	{
		m=(iVal[idx]&0xF)<<4;
		if(idx>0)
			m=m|(iVal[idx-1]>>60);
	}
	return (m&0xFF);
}

//p441
unsigned short BigInt::Get12BitBlock(const short & which)
{
	short iwhich,idx;
	unsigned short m;

	idx=which>>4;
	iwhich=(which & 0xF)<<2;
	if(iwhich==0)
	{
		m=(iVal[idx]&0xF)<<8;
		if(idx>0)
			m=m|(iVal[idx-1]>>56);
	}
	else if(iwhich==4)
	{
		m=(iVal[idx]&0xF)<<4;
		if(idx>0)
			m=m|(iVal[idx-1]>>60);
	}
	else
	{
		m=iVal[idx]>>(iwhich-8);
	}
	return(m&0x0FFF);
}

unsigned char BigInt::Get4BitBlockZero()
{
	//-15-14-13-...-2-1-0--
	//Total 16's 4-bits Block in 64bit Integet
	unsigned char iwhich;
	unsigned __int64 m;
	 
	if(iVal[iIdx]>0xFFFFFFFF)
	{
		m=0x0FFFFFFFFFFF;
		iwhich=0;
	}
	else
	{
		m=0x0FFFFFFF;
		iwhich=8;
	}
	while(iVal[iIdx]<m)
	{
		m>>=4;
		iwhich++;
	}
	return iwhich;
}

//p442
unsigned __int64 BigInt::First64Bits()
{
	unsigned __int64 m;
	int i=0;
	
	m=iVal[iIdx];
	if(iIdx==0)
		return m;

	while(m&LMASK[2]!=LMASK[2])
	{
		m<<1;//????????????????/////
		i++;
	}
	return(m|iVal[iIdx-1]>>(64-i));
}

unsigned __int64 BigInt::First32Bits()
{
	unsigned __int64 m;
	int i=0;

	m=iVal[iIdx];
	if(iIdx==0)
	{
		if(m>0xFFFFFFFF)
			return(m>>32);
		else 
			return m;
	}
	while(m & LMASK[2]!=LMASK[2])
	{
		m<<1;//??????????????????/
		i++;
	}
	return (m|iVal[iIdx-1]>>(64-i)>>32);
}

//p443
void BigInt::setUpperBlock(const short & which)