largeintegers.cpp

RSA大数运算库 RSA大数运算库

/* Lint class. Version 1.5

Copyright VF (C) 2004
implemented by Vagelis Fortunas Mytilini Greece
email:  [e-mail] December 2004

You are free to use this code as you wish.
In no event will the author be hold liable for any damages arising from the use of this software.

There is no zero divisor check, so you must be careful whith divisions

No complex operations allowed such r= a*x+b*y+c%z..... or  f=(a+b)*(c-d)/(...
because this class can't keep intermediate temporary results for any complex
operation e.g.(b*y)
You can use this type of complex operation:
a=((b*c+3+w+r+t)*h/r/r/2+3)%f

MAXLEN is the  allocated (malloc) number of binary dword digits per large integer.

BUFLEN is the buffer size in bytes allocated in stack for display only purpose.

Look at header file for more details about defined functions
This class is not thread safe.

*/

//############################################################################################

#pragma warning(disable:4100) // Disable this warning because argumens passed via registers
#include <stdio.h>//fopen
#include <stdlib.h>// malloc free
#include <string.h>//memcpy
#include <ctype.h>//isalpha, isdigit
#include<io.h> //_close _open
#include<FCNTL.H> //_O_BINARY
#include<SYS\STAT.H> //_S_IWRITE
#include "LargeIntegers.h"
// variables for improving speed (but costs for memory)
Lint LITmp1,LITmp,LITmp2;;//
Lint gcd,gcd1;//
Lint divy;//div
Lint divtmp;//div
Lint ybnt;//div
Lint gen;//for general purpose
Lint cres,cres1,restmp;// temporary results for complex operations
Lint r2,q3,b2km;//for Barret modular reduction
Lint mdxp,mdxp1;//for modular exponentiation
Lint sqr;//for squaring
LINT y,r;//for Miller-Rabbin test
unsigned int radix=10;
extern const unsigned int primes[];//look at primes.cpp
//############################################################################################
unsigned int sth,stl;//stamp counter of proccessor
unsigned int tth,ttl;//time counter (0,1 micro sec interval)
char sc[25];
//############################################################################################
__declspec(naked) void Bc(void)
	{//this func must called before each operation to store the counts in sth:stl	
		__asm
		{
			push eax
			push edx
			rdtsc// main action
			mov sth,edx
			mov stl,eax
			pop edx
			pop eax
			ret
		}
	}

//############################################################################################
__declspec(naked) void Ac(void)
	{//this func must called after operation to calc the counts difference stored in sth:stl	
		__asm
		{
			push eax
			push edx
			rdtsc// main action
			sub eax,stl//calculate the difference between this rdtsc and pevious Bc()
			sbb edx,sth
			//minus 92
			sub eax,92//(92 counts is the offset between the Bc and Ac func)
			sbb edx,0
			push 10
			push offset sc//loads the sc buffer with result
			push edx
			push eax
			call _ui64toa//convert the difference to string and stores it to sc
			add esp,16
			pop edx
			pop eax
			ret
		}
	}
//############################################################################################
__declspec(naked) void Bt(void)
	{//this func must called before each operation to count. the time stored in tth:ttl	
		__asm
		{
			//representing the number of 100-nanosecond intervals since January 1, 1601 (UTC).
			push eax
			push edx
gt0:		mov edx,ds:[2147352600]//read the timer from this address
			mov eax,ds:[2147352596]//read the timer from this address 
			cmp edx,ds:[2147352604]//read the timer from this address 
			jne gt0
			mov ttl,eax 
			mov tth,edx 
			pop edx
			pop eax
			ret
		}
	}

//############################################################################################
__declspec(naked) void At(void)
	{//this func must called after  operation to count the time stored in tth:ttl	
		__asm
		{
			push eax
			push edx			
gt0:		mov edx,ds:[2147352600]//read the timer from this address
			mov eax,ds:[2147352596]//read the timer from this address 
			cmp edx,ds:[2147352604]//read the timer from this address 
			jne gt0
			sub eax,ttl
			sbb edx,tth
			push ebx
			mov ebx,10
			div ebx//convert to microseconds
			pop ebx
			mov edx,0
			push 10
			push offset sc
			push edx
			push eax
			call _ui64toa//loads the sc buffer with result
			add esp,16
			pop edx
			pop eax
			ret
		}
	}
//############################################################################################
void SetRadix(unsigned int r=10)// set radix
{
	radix=r;
	if (radix>36)radix=36;
	if (radix<=1)radix=10;	
}
//############################################################################################
int GetRandomBits(void* buffer,unsigned int bits)
{		
	int file;
	char filename[]="\\~VFtmp0001";
	unsigned int tm;
	tm=bits/16;
	if(bits%16>0)tm++;//round bits (if necessary) to next 16 bits value
	
	if((file=_open(filename,_O_TRUNC |_O_BINARY | _O_CREAT | _O_WRONLY,_S_IWRITE))!=-1)//open  file for write
	{	   
		char buf[16519];//not equal to any cluster size 

		for (unsigned int a=0;a<tm;a++)
		{	
			_write(file,buf,sizeof(buf));// actually this operation writes data to buffer
										//  NOT to disk


			Bc();			//Here is the main action(Counts needed for writing
			_commit(file);	//the data to the disc surface.)
			Ac();			//this value needs, in any case, debiasing.
					
			
			//    WARNING *  WARNING.   This, must be subject for many more tests.
			//  I do not recommend to use it without extended tests

			stl=stl & 0x3ffff;	//this kind of debiasing tested only on my PC
			stl=stl>>2;			//This debiasing keeps 16 bits after second bit
			//////////////////////////////////////////////////////////////////////////

			
			__asm
			{	//write the data to buffer (16 bits slices) 
				mov eax,stl
				mov ebx,a
				mov ecx,buffer
				mov [ecx+ebx*2],ax// 16 bits
			}			
		}
		_close(file);
		remove(filename);
		return 0;
	}
	return 1;
	
}
//############################################################################################
Lint::Lint(void)
{
	IntLen=1;
	this->DataBase=(PBU)malloc(MAXLEN*sizeof(BU));
	this->Data=this->DataBase;//Data points to the begin of integer
	sign=0;
	this->Data[0]=0;//without sign
}
//############################################################################################
Lint::~Lint(void)
{
	WipeOut();
	free(DataBase);	
}
//############################################################################################
Lint::Lint(BU l)//
{
	DataBase=(PBU)malloc(MAXLEN*sizeof(BU));
	Data=this->DataBase;//Data points to the begin of integer
	sign=0;
	IntLen=1;
	Data[0]=l;
}
//############################################################################################
Lint::Lint(int l)
{
	DataBase=(PBU)malloc(MAXLEN*sizeof(int));
	__asm
	{
		mov ecx,this
		mov edx,l
		mov eax,edx
		and eax,80000000h//we want only the sign
		jz nxt49
		neg edx
nxt49:	shr eax,31//put it to lsb
		mov [ecx]Lint.sign,eax//copy sign
		mov [ecx]Lint.IntLen,1//copy curlen
		mov eax,[ecx]Lint.DataBase
		mov [ecx]Lint.Data,eax
		mov [eax],edx//*this=l;
	}
}
//############################################################################################
Lint::Lint(Lint& source)//??0Lint@@QAE@PAV0@@Z
{
	DataBase=(PBU)malloc(MAXLEN*sizeof(BU));
	__asm
	{//copy the source to this
		mov ebx,this
		mov eax,source
		mov ecx,[eax]source.IntLen
		mov [ebx]this.IntLen,ecx//copy curlen first
		mov edx,[eax]source.sign
		mov [ebx]this.sign,edx//copy sign
		mov edx,[eax]source.Data
		sub edx,[eax]source.DataBase
		add edx,[ebx]this.DataBase
		mov [ebx]this.Data,edx//copy DataIndex
		mov esi,[eax]source.DataBase
		mov edi,[ebx]this.DataBase
		cld//  cld is for inc and std is for dec
		rep movsd//*this=source;
	}
}

//############################################################################################
Lint::Lint(const char* str)
{
	DataBase=(PBU)malloc(MAXLEN*sizeof(BU));//only one byte
	Data=DataBase;//Data points to the begin of integer
	Data[0]=0;
	sign=0;
	IntLen=1;
	bool tmpsign=false;//temporary sign
	unsigned char* index=(unsigned char*)str;
	if (*str == '-'){tmpsign=true;index++;}//negative number
me:	if (*index=='0'){index++;goto me;}//cut all leading zeroes
	while((isdigit(*index)&&(*index<(radix+'0')))||(isalpha(*index)&&(radix>10)&&(*index<(radix+'A'))))
	{
		if (radix<=10)LITmp1=*index-'0';
		else
		{
			if (*index>'9')
				LITmp1=*index-'A'+10;
			else LITmp1=*index-'0';
		}

		Mul2(radix,&gen);
		Add1(&gen, &LITmp1, this);
		++index;
	}
	NormalizeLength();
	if (tmpsign &&(Data[0]!=0 ||IntLen>1 )) sign=1;//negative number
}
//############################################################################################
int Lint::FromBuffer(void* itemdata,BU items,BU itemsize)
{
	if (MAXLEN*sizeof(BU)< items*itemsize)return 1;//buffer is biger than LINT    
	BU tmplen;
	tmplen=items*itemsize;//length of buffer in bytes(8bit)
	if (!tmplen) return 2;//invalid size or items
	IntLen= tmplen/sizeof(BU);
	if (tmplen%sizeof(BU)>0) IntLen++;//increase
	Data[IntLen-1]=0; //make the last dword zero.
	if(!memcpy(Data,itemdata,tmplen)) return 3;//cant copy	
	sign=0;//sign is always positive
	NormalizeLength();//cut leading zeroes
	return 0;
}
//############################################################################################
int Lint::ToBuffer(void* buffer,PBU bufsize)
{
	*bufsize=IntLen*sizeof(BU);//length of buffer in bytes(8bit)
	if(!memcpy(buffer,Data,*bufsize))
	{
		*bufsize=0;
		return 1;//cant copy
	}
	return 0;
}
//############################################################################################
int Lint::FromFile(char* filename)
{		
	FILE *stream;
	int nr_of_error=0;
	BU filelen;
	if((stream=fopen(filename,"rb"))!=0)
	{				
		setvbuf(stream,0,_IONBF,0);//allow no buffering
		fseek(stream,0,SEEK_END);//for read size only
		filelen=(BU)ftell(stream);		
		if (MAXLEN*sizeof(BU)< filelen){nr_of_error=1;goto er;}//file is biger than LINT can take   
		if (!filelen){nr_of_error=2;goto er;}//empty file
		IntLen= filelen/sizeof(BU);
		if (filelen%sizeof(BU)>0) IntLen++;//increase
		Data[IntLen-1]=0; //make the last dword zero.		
		fseek(stream,0,SEEK_SET);
		if (fread(Data,1,filelen,stream)!=filelen)nr_of_error=3;
er:		fclose(stream);
		return nr_of_error;
	}
	return 4;// file does not e
}
//############################################################################################
int Lint::ToFile(char* filename)
{		
	FILE *stream;
	int nr_of_error=0;
	if((stream=fopen(filename,"wb"))!=0)
	{				
		setvbuf(stream,0,_IONBF,0);//allow no buffering(not no HD cashing)
		if(fwrite(Data,sizeof(BU),IntLen,stream)!=IntLen)nr_of_error=1;//cant write
		fclose(stream);
		return nr_of_error;
	}
	return 2;//cant open file
}
//############################################################################################
Lint& Lint::operator >> (BU pp){Sr(pp);return *this;}
//############################################################################################
Lint& Lint::operator << (BU pp){Sl(pp);	return *this;}
//############################################################################################
bool Lint::operator ==(Lint& cc){return(CompareS(&cc)==0);}
//############################################################################################
bool Lint::operator >=(Lint& cc){BU zz;zz=CompareS(&cc);return((zz==0)||(zz==1));}
//############################################################################################
bool Lint::operator <=(Lint& cc){BU zz;zz=CompareS(&cc);return((zz==0)||(zz==2));}
//############################################################################################
bool Lint::operator >(Lint& cc){return(CompareS(&cc)==1);}
//############################################################################################
bool Lint::operator <(Lint& cc){return(CompareS(&cc)==2);}
//############################################################################################
bool Lint::operator !=(Lint& cc){return(CompareS(&cc)!=0);}
//############################################################################################
bool Lint::operator ==(BU cc){gen=cc;return(CompareS(&gen)==0);}
//############################################################################################
bool Lint::operator >=(BU cc){BU zz;gen=cc;zz=CompareS(&gen);return((zz==0)||(zz==1));}
//############################################################################################
bool Lint::operator <=(BU cc){BU zz;gen=cc;zz=CompareS(&gen);return((zz==0)||(zz==2));}
//############################################################################################
bool Lint::operator >(BU cc){gen=cc;return(CompareS(&gen)==1);}
//############################################################################################
bool Lint::operator <(BU cc){gen=cc;return(CompareS(&gen)==2);}
//############################################################################################
bool Lint::operator !=(BU cc){gen=cc;return(CompareS(&gen)!=0);}
//############################################################################################
bool Lint::operator ==(int cc){gen=cc;return(CompareS(&gen)==0);}
//############################################################################################
bool Lint::operator >=(int cc){BU zz;gen=cc;zz=CompareS(&gen);return((zz==0)||(zz==1));}
//############################################################################################
bool Lint::operator <=(int cc){BU zz;gen=cc;zz=CompareS(&gen);return((zz==0)||(zz==2));}
//############################################################################################
bool Lint::operator >(int cc){gen=cc;return(CompareS(&gen)==1);}
//############################################################################################
bool Lint::operator <(int cc){gen=cc;return(CompareS(&gen)==2);}
//############################################################################################
bool Lint::operator !=(int cc){gen=cc;return(CompareS(&gen)!=0);}
//############################################################################################
Lint& Lint::operator + (Lint& pp)
{
	Add1(this,&pp,&restmp);
	cres=restmp;
	return cres;
}
//############################################################################################
Lint& Lint::operator - (Lint& ss)
{
	Sub1(this,&ss,&restmp);
	cres=restmp;
	return cres;
}
//############################################################################################
Lint& Lint::operator * (Lint& mm)
{
	Mul1(&mm,&restmp);
	cres=restmp;
	return cres;
}
//############################################################################################
Lint& Lint::operator / (Lint& dd)
{
	Div1(&dd,&restmp,&gen);
	cres=restmp;
	return cres;

}
//############################################################################################
Lint& Lint::operator % (Lint& mm)
{
	Div1(&mm,&gen,&restmp);
	cres=restmp;
	return cres;
}
//############################################################################################
Lint& Lint::operator + (BU pp)
{
	gen=pp;
	Add1(this,&gen,&restmp);
	cres=restmp;
	return cres;

}
//############################################################################################
Lint& Lint::operator - (BU ss)
{
	gen=ss;
	Sub1(this,&gen,&restmp);
	cres=restmp;
	return cres;
}
//############################################################################################
Lint& Lint::operator * (BU mm)
{
	Mul2(mm,&restmp);
	cres=restmp;
	return cres;
}
//############################################################################################
Lint& Lint::operator / (BU dd)
{
	Div2(dd,&restmp,&gen);
	cres=restmp;
	return cres;
}
//############################################################################################
Lint& Lint::operator % (BU mm)
{
	Div2(mm,&gen,&restmp);
	cres=restmp;
	return cres;
}
//############################################################################################
Lint& Lint::operator + (int pp)
{
	gen=pp;
	Add1(this,&gen,&restmp);
	cres=restmp;