bigint.cpp

RSA VC++实现

#include<stdio.h>
#include<math.h>
#include<string.h>
#include"BigInt.h"
#include<iostream>
using namespace std;
BigInt TableModBase[36];
unsigned char HArray[]={'0','1','2','3','4','5','6','7','8','9','A','B','C','D','E','F'};
unsigned_int64 RMASK[]={0x0L,0x0000000000000001L};
unsigned char hdigit(unsigned char c)//h for HEX
{
	unsigned char hi,lo;
	hi=c>>4;
	lo=c&0x0f;
	if(hi==0x04||hi==0x06)
		return(lo+0x09);
	return lo;
}

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

BigInt::~BigInt()
{

}

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

void BigInt::loadHEX(const byte* itext,int size_num)
{
	int seg,bgn,end,ttl;
	unsigned_int64 tmp;
	if(size_num!=0)
		ttl=size_num;
	else
		ttl=strlen((char *)itext);
	seg=(ttl-1)/LenMAXHEX;
	bgn=0;
	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]);
			bgn++;
		}
		iVal[i]=tmp;
		ttl=ttl-end;
	}
	iIdx=seg;
}

void BigInt::loadSTR(const byte* itext,int size_num)
{
	int seg,bgn,end,ttl;
	unsigned_int64 tmp;
	if(size_num!=0)
		ttl=size_num;
	else
		ttl=strlen((char *)itext);
	seg=(ttl-1)/LenMAXWRD;
	bgn=0;
	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];
			bgn++;
		}
		iVal[i]=tmp;
		ttl=ttl-end;
	}
	iIdx=seg;
}

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

int BIcompare(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 ++()
{
	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 --()
{
	unsigned_int64 carry;
	int i=0;
	carry=1;
	while(carry==1)
	{
		if(iVal[i]=0x0)
		{
			iVal[i]=FULL;
			carry=1;
		}
		else
		{
			iVal[i]--;
			carry=0;
		}
		i++;
	}
	if(iVal[iIdx==0])
		iIdx--;
	return *this;
}

BigInt& BigInt::operator <<=(const short &iBit)
{
	unsigned_int64 b1,b2,LM;
	short i,shift,ishift;
	if((iIdx==0)&&(iVal[0]==0))
		return *this;
	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;
	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;
}

BigInt& BigInt::operator >>=(const short &iBit)
{
	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;
}

byte* BigInt::outputHEX()
{
	unsigned char cs[8192];
	unsigned short k,l;
	for(int i=0;i<8192;i++)
		cs[i]='\0';
	l=0;
	for(i=iIdx;i>=0;i--)
	{
		for(int j=60;j>=0;j-=4)
		{
			k=(iVal[i]>>j)&0x0F;
			cs[l++]=HArray[k];
		}
	}
	return cs;
}

byte* BigInt::outputSTR()
{
	unsigned char cs[8192];
	int i,j,k;
	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;
	}
	return cs;
}

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

unsigned char BigInt::Get4BitBlockZero()
{
	unsigned char iwhich;
	unsigned_int64 m;
	if(iVal[iIdx]>0xFFFFFFFF)
	{
		m=0x0FFFFFFFFFFFFFFF;
		iwhich=0;
	}
	else
	{
		m=0x0FFFFFFF;
		iwhich=8;
	}
	while(iVal[iIdx]<m)
	{
		m>>=4;
		iwhich++;
	}
	return iwhich;
}

void BigInt::setUpperBlock(const short &which)
{
	unsigned_int64 m;
	short iwhich;
	for(int i=0;i<=iIdx;i++)
		iVal[i]=0;
	m=0x1000000000000000;
	if(which>0)
	{
		iwhich=(which-1)<<2;
		iVal[iIdx]=m>>iwhich;
	}
	else
	{
		iIdx++;
		iVal[iIdx]=1;
	}
}

bool BIisZero(BigInt &x)
{
	if(x.iIdx!=0)
		return false;
	if(x.iVal[0]!=0)
		return false;
	return true;
}

BigInt& BigInt::operator =(BigInt &p1)
{
	iIdx=p1.iIdx;
	for(int i=0;i<=iIdx;i++)
		iVal[i]=p1.iVal[i];
	return *this;
}

BigInt& BigInt::operator =(const unsigned_int64 &p1)
{
	iIdx=0;
	iVal[0]=p1;
	return *this;
}

inline bool operator>(BigInt &p1,BigInt &p2)
{
	short stop;
	stop=p1.iIdx;
	if(stop>p2.iIdx)
		return true;
	else if(stop<p2.iIdx)
		return false;
	else
	{
		while(stop>=0)
		{
			if(p1.iVal[stop]>p2.iVal[stop])
				return true;
			else if(p1.iVal[stop]<p2.iVal[stop])
				return false;
			else
			stop--;
		}
		return false;
	}
}

inline bool operator==(BigInt &p1,BigInt &p2)
{
	if(p1.iIdx!=p2.iIdx)
		return false;
	short stop=p1.iIdx;
	while(stop>=0)
	{
		if(p1.iVal[stop]!=p2.iVal[stop])
			return false;
		stop--;
	}
	return true;
}

inline bool operator!=(BigInt &p1,BigInt &p2)
{
	if(p1.iIdx!=p2.iIdx)
		return true;
	short stop=p1.iIdx;
	while(stop>=0)
	{
		if(p1.iVal[stop]!=p2.iVal[stop])
			return true;
		stop--;
	}
	return false;
}

BigInt operator+(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]<p1.iVal[i])
			carry=1;
		else
			carry=0;
		i++;
	}
	if(carry==1)
	{
		result.iVal[result.iIdx+1]=1;
		result.iIdx++;
	}
	return result;
}

BigInt operator+(BigInt &p1,BigInt &p2)
{
	int i;
	short stop;
	BigInt result;
	unsigned_int64 carry;
	if(BIisZero(p1))
		return p2;
	if(BIisZero(p2))
		return p1;
	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-(BigInt &p1,BigInt &p2)
{
	int i;
	BigInt result;
	unsigned_int64 carry;
	if(BIisZero(p2))
		return p1;
	else
	{
		carry=0;
		for(i=0;i<=p1.iIdx;i++)
		{
			if(p1.iVal[i]>=p2.iVal[i])
			{
				result.iVal[i]=p1.iVal[i]-p2.iVal[i];
				if(result.iVal[i]==0x0&&carry==0x1)
				{
					result.iVal[i]=FULL;
				}
				else
				{
					result.iVal[i]-=carry;
					carry=0;
				}
			}
			else
			{
				result.iVal[i]=FULL-p2.iVal[i]+p1.iVal[i]+RMASK[1]-carry;
				carry=RMASK[1];
			}
		}
		result.iIdx=p1.iIdx;
		while((result.iIdx>0)&&(result.iVal[result.iIdx]==0))
			result.iIdx--;
	}
	return result;
}

BigInt operator*(BigInt &p1,const unsigned_int64 &p2)
{
	BigInt result;
	unsigned_int64 carry,high,low;
	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,high,low);
		result.iVal[i]+=low;
		if(result.iVal[i]<low)
			carry++;
		carry+=high;
		result.iVal[i+1]=carry;
	}
	while(result.iVal[result.iIdx]==0)
		result.iIdx--;
	return result;
}


BigInt operator*(BigInt &p1,BigInt &p2)
{
	BigInt result;
	unsigned_int64 carry,high,low;
	int i;
	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(int j=0;j<=p1.iIdx;j++)
			{
				BImul(p1.iVal[j],p2.iVal[i],high,low);
				result.iVal[i+j]+=carry;
				if(result.iVal[i+j]<carry)
					carry=1;
				else
					carry=0;
				result.iVal[i+j]+=low;
				if(result.iVal[i+j]<low)
					carry++;
				carry+=high;
			}
		}
		result.iVal[i+p1.iIdx+1]+=carry;
	}
	while(result.iVal[result.iIdx]==0)
		result.iIdx--;
	return result;
}

BigInt operator/(BigInt &p1,BigInt &p2)
{
	BigInt d;
	return BIdivision(p1,p2,d);
}

BigInt operator%(BigInt &p1,BigInt &p2)
{
	BigInt result,mb;
	result=p1;
	if(BIcompare(result,p2)>0)
	{
		mb=p2;
		MakeThemClose(result,mb);
		while(BIcompare(result,mb)>0)
			mb<<=1;
		while(BIcompare(result,p2)>0)
		{
			while(BIcompare(result,mb)<0)
				mb>>=1;
			result=result-mb;
		}
	}
	if(BIcompare(result,p2)==0)
		result.setZero();
	return result;
}

void BIswap(BigInt &p1,BigInt &p2)
{
	BigInt tmp;
	tmp=p1;
	p1=p2;
	p2=tmp;
}

BigInt BIdivision(BigInt &p1,BigInt &p2,BigInt &pr)
{
	BigInt q,r,pb;
	int test;
	test=BIcompare(p1,p2);
	if(test>0)
	{
		r=p1;
		pb=p2;
		MakeThemClose(r,pb);
		while(BIcompare(r,pb)>0)
			pb<<=1;
		while(BIcompare(r,pb)<0)
			pb>>=1;
		while((BIcompare(r,p2)>0)||(BIcompare(p2,pb)<=0))
		{
			if(BIcompare(r,pb)>=0)
			{
				r=r-pb;
				q<<=1;
				q++;
			}
			else
				q<<=1;
			pb>>=1;
		}
		pr=r;
	}
	else if(test==0)
	{
		q++;
		pr.setZero();
	}
	else
	{
		q.setZero();
		pr=p1;
	}
	return q;
}

void MakeModBaseTable(BigInt &pp)
{
	TableModBase[0]=pp;
	for(int i=1;i<36;i++)
	{
		TableModBase[i]=TableModBase[i-1];
		TableModBase[i]<<=2;
	}
}

BigInt BImodmul(BigInt &p1,BigInt &p2,BigInt &pp)
{
	BigInt a,b,c,result;
	short i,j,kbit,kbit2;
	if(BIisZero(p1))
		return result;
	if(BIisZero(p2))
		return result;
	if(TableModBase[0]!=pp)
		MakeModBaseTable(pp);
	a=p1%pp;
	b=p2%pp;
	kbit2=FindZeroBit(pp.iVal[pp.iIdx]);
	for(i=b.iIdx;i>=0;i--)
	{
		result<<=64;
		if(b.iVal[i]!=0)
		{
			c=a*b.iVal[i];
			result=result+c;
		}
		if(BIcompare(result,pp)>=0)
		{
			kbit=kbit2-FindZeroBit(result.iVal[result.iIdx]);
			if(result.iIdx>pp.iIdx)
				kbit+=64;
			kbit>>=1;
			for(j=kbit;j>=0;j--)
			{
				while(BIcompare(result,TableModBase[j])>=0)//这里有BUG,RESULT默认的情况下iIdx已增加1，但增加的这位却为0 ，
					result=result-TableModBase[j];	//虽不影响大小，但却影响大数间的比较，详细见大数比较,所以修改比较函数
				
			}
		}
	}
	return result;
}

BigInt BIinverse(BigInt &p1,BigInt &p2)
{
	BigInt y,g0,g1,g2,v0,v1,v2;
	g0=p2;
	g1=p1;
	v1++;
	while(!BIisZero(g1))
	{
		y=BIdivision(g0,g1,g2);
		g0=g1;
		g1=g2;
		v2=y*v1;
		while(BIcompare(v0,v2)<0)
			v0=v0+p2;
		v0=v0-v2;
		BIswap(v0,v1);
	}
	return v0;
}

void BImul(const unsigned_int64 &p1,const unsigned_int64 &p2,unsigned_int64 &high,																unsigned_int64 &low)
{
	unsigned_int64 aH,aL,bH,bL;
	unsigned_int64 m,m1,m2;
	aH=p1>>32;
	aL=p1&0xFFFFFFFF;
	bH=p2>>32;
	bL=p2&0xFFFFFFFF;
	high=aH*bH;
	low=aL*bL;
	m1=aH*bL;
	m2=aL*bH;
	high+=(m1>>32);
	high+=(m2>>32);
	m=(m1&0xFFFFFFFF)+(m2&0xFFFFFFFF);
	high+=(m>>32);
	m=m<<32;
	low+=m;
	if(low<m)
		high++;
}

void MakeThemClose(BigInt &p1,BigInt &p2)
{
	short shift,Sa,Sb;
	shift=TOTALBITS*(p1.iIdx-p2.iIdx);
	if(shift!=0)
	{
		Sa=FindZeroBit(p1.iVal[p1.iIdx]);
		Sb=FindZeroBit(p2.iVal[p2.iIdx]);
		if(Sb>Sa)
			shift=shift+Sb-Sa;
		else
			shift=shift+Sa-Sb;
		shift=shift-1;
		p2<<=shift;
	}
}

short FindZeroBit(const unsigned_int64 &p1)
{
	unsigned_int64 cc,t;
	short Fbit=3;
	t=p1;
	cc=FULL>>4;
	while(t<cc)
	{
		cc>>=4;
		Fbit+=4;
	}
	cc=FULL>>Fbit;
	while((cc&t)!=t)
	{
		Fbit--;
		cc=FULL>>Fbit;
	}
	return Fbit;
}

BigInt MontMult(BigInt &p1,BigInt &p2,BigInt &pp)
{
	BigInt m,base,result;
	BigInt pre_b[16],pre_p[16];
	unsigned short mp,u;
	int bblock;
	base=0x10;
	base.iIdx=0;
	pre_b[0].setZero();
	pre_b[1]=p2;
	pre_p[0].setZero();
	pre_p[1]=pp;
	for(int i=2;i<16;i++)
	{
		pre_b[i]=pre_b[i-1]+p2;
		pre_p[i]=pre_p[i-1]+pp;
	}
	m=BIinverse(pp,base);
	mp=0x10-m.iVal[0];
	bblock=16*pp.iIdx+15;//这里就是pp，而不是p1
	bblock-=pp.Get4BitBlockZero();
	for(int j=0;j<=bblock;j++)
	{
		u=(result.Get4BitBlock(0)+p1.Get4BitBlock(j)*p2.Get4BitBlock(0))*mp;//以下原理都正确
		u=u&0x0F;
		result=result+pre_b[p1.Get4BitBlock(j)];
		result=result+pre_p[u];
		result>>=4;
	}
	if(BIcompare(result,pp)>=0)
		result=result-pp;
	return result;
}

BigInt MontExpo(BigInt &p1,BigInt &p2,BigInt &pp)
{
	BigInt zb,zR,zxp,result;
	int bblock,kbit;
	unsigned_int64 m;
	short k,l;
	bblock=pp.Get4BitBlockZero();
	zR=pp;
	zR.setUpperBlock(bblock);
	zb=BImodmul(zR,zR,pp);//正确
	zxp=MontMult(p1,zb,pp);//哈哈，搞定
	result=zR%pp;//%运算正确
	short temp=FindZeroBit(p2.iVal[p2.iIdx]);
	kbit=63-temp;
	kbit+=64*p2.iIdx;
	for(int j=kbit;j>=0;j--)
	{
		k=j%64;
		l=j/64;
		m=p2.iVal[l]>>k;
		result=MontMult(result,result,pp);
		if((m&0x01)==0x01)
			result=MontMult(result,zxp,pp);
	}
	zxp.setZero();
	zxp.iVal[0]=1;
	result=MontMult(result,zxp,pp);
	return result;
}