largeintegers.cpp

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

	   //normalize integers x*=mp divy*=mp	and set the values of n and t					
		mov mp,0
		mov esi,divy.Data//data	pointer
		mov	ebx, divy.IntLen//length value
		bt dword ptr[esi+ebx*4-4],31
		jc end111//compare to 1^32 / 2
		//////// find first the normalization(mp) factor/////
		bsr eax,dword ptr[esi+ebx*4-4]//scan for the position of the msb
		mov edx,31
		sub edx,eax//find how many positions must be shift left
		mov mp,edx//for later use

		//MULTIPLY x (rem)
		mov ecx,rem
		call Sl
		//multiply divy
		lea ecx,divy
		call Sl

end111:	
		//set the values of n and t
		mov edi,rem
		mov eax,[edi]Lint.IntLen
		dec eax
		mov n,eax//n= x.IntLen-1
		mov eax,divy.IntLen
		dec eax
		mov t,eax//t= divy.IntLen-1;

		//quot.ReallocDataZero(n-t+1);
		mov ecx,n
		sub ecx,t
		add ecx,1//n-t+1 digits		
		mov ebx,quot
		lea edx,[ebx]quot.IntLen
		mov ebx,[ebx]quot.Data
		mov [edx],ecx//
lp12:	mov dword ptr[ebx+ecx*4-4],0
		loop lp12

		//while(x >=ybnt) x= x-ybnt
		//ybnt=divy; and shift left n-t steps simultaneusly //ybnt=divy*b^(n-t)
		mov edi,divy.Data
		mov esi,ybnt.DataBase
		mov ybnt.Data,esi//initialize just in case
		mov ebx,n
		sub ebx,t
		lea edx,[esi+ebx*4]//shift left n-t steps
		mov ecx,divy.IntLen//
		mov ybnt.IntLen,ecx
		add ybnt.IntLen,ebx//curlen= divy.IntLen+n-t
cpy0:	mov eax,[edi+ecx*4-4]
		mov[edx+ecx*4-4],eax// ybnt=divy;
		loop cpy0
		//zeroize rest dwords of ybnt from n-t-1 to 0
		mov ecx,ebx		
		jecxz whl1//if n-t==0
set0:	mov dword ptr[esi+ecx*4-4],0
		loop set0
whl1:		
		//while ybnt<=x quot->Data[n-t]+=1;x-=ybnt
		lea edx,ybnt
		mov ecx,rem
whl12:	call CompareU
		cmp eax,2
		jnc blb1//if ybnt>x goto the next block of code
		//else quot->Data[n-t]+=1;x-=ybnt;repeat until ybnt>x
		mov ebx,n
		sub ebx,t
		mov eax,quot
		mov eax,[eax]quot.Data
		inc dword ptr[eax+ebx*4]// quot->Data[n-t]+=1		
		//x-=ybnt;		
		call Sub2
		jmp whl12
blb1:
	
///////////////////////////begin of big loop//////for (i=n;i>=t+1;i--)
		mov	ecx,divy.Data
		mov ebx,t		
		mov eax,dword ptr[ecx+ebx*4]// divy.Data[t]
		mov yt,eax
		mov eax,dword ptr[ecx+ebx*4-4]// divy.Data[t-1]
		mov yt1,eax
		mov eax,n
		mov i,eax
		inc ebx
		cmp eax,ebx
		jnae endbglp
biglpp:	//for (i=n;i>=t+1;i--)		
		
		mov	edi,i
		//move to variables the xi,xi1,xi2,*qit1 (to increase speed)
		mov ecx,edi
		sub ecx,t
		mov eax,quot
		mov eax,[eax]quot.Data
		lea esi,[eax+ecx*4-4]//find *qit1 (q(i-t-1))
		mov qit1,esi
		mov ecx,rem
		mov	ebx,[ecx]Lint.Data
		mov ecx,[ecx]Lint.IntLen
		mov eax,[ebx+edi*4]
		mov	xi,eax
		mov eax,[ebx+edi*4-4]
		mov	xi1,eax
		mov eax,[ebx+edi*4-8]
		mov	xi2,eax
		// if i...>= curlen then xi...=0
		cmp edi,ecx
		jb jb1
		mov xi,0//x.Data[i]=0
		dec ecx
		cmp edi,ecx
		jb jb1
		mov xi1,0//x.Data[i-1]=0
		dec ecx
		cmp edi,ecx
		jb jb1
		mov xi2,0//x.Data[i-2]=0		
jb1:
		//if (x.Data[i]==divy.Data[t]) then quot->Data[i-t-1]=4294967295 else	load quot->Data[i-t-1] with (xib+xi-1)/yt
		mov edx,xi
		cmp	edx,yt//compare with divy.Data[t]
		jne	neq
		mov	dword ptr[esi],4294967295//load	quot.Data[i-t-1] with ffffffff
		jmp	nxt		
neq:	//perform xi:xi-1 /	yt
		mov	eax,xi1//load	x.Data[i-1]
		div	dword ptr[yt]//perform xi-1 /yt
		mov	dword ptr[esi],eax//load	quot.Data[i-t-1] with result
nxt:			
		/////////////////////////while (qt1*(ytb+yt1)>xib2+xi1b+xi2) q(i-t-1) -- ///////////
		///// now multiply (yt:yt-1) by q(i-t-1) and save it to ltmp
		mov	eax,yt1//take first dword yt-1
		mul	dword ptr[esi]//multiply 
		mov	ebx,eax//save	the	result 
		mov	ecx,edx// save temporarily edx
		mov	eax,yt//take second dword yt		
		mul	dword ptr[esi]//multiply 
		add	eax,ecx// from previous	mult
		adc	edx,0//and the carry to	edx
		//if ltmp>rtmp set carry flag
		mov	ecx,xi2//xi-2
		sub	ecx,ebx
		mov	ecx,xi1//xi-1
		sbb	ecx,eax
		mov	ecx,xi//xi
		sbb	ecx,edx
		jnc	endw
		//q(i-t-1)= q(i-t-1)-1
		dec	dword ptr[esi]//q(i-t-1)= q(i-t-1)-1
		jmp	nxt
endw:	//////////end of while (qt1*(ytb+yt1)>xib2+xi1b+xi2) q(i-t-1) -- ///////////
		
		//x=x- quot.Data[i-t-1]*yb^(i-t-1)///////////////////////////
		mov	esi,divtmp.Data
		mov	ebx,ybnt.Data
		mov eax,n
		sub	eax,i
		add eax,1
		lea	ebx,[ebx+eax*4]//shift left	i-t-1 steps divy.Data
		mov ecx,ybnt.IntLen
		sub ecx,eax
		mov divtmp.IntLen,ecx//new IntLen for divtmp
		inc divtmp.IntLen//plus one for mult
		mov	edx,0
		mov edi,qit1
		mov saveesp,esp
		mov esp,ebx// ybnt.Data		
		////////////mul	///////////////////////
arxm:	mov	eax,[esp]		
		mov	ebx,edx// save temporarily edx
		mul dword ptr[edi]//multiply 
		add	eax,ebx// from previous	mult
		adc	edx,0//and the carry to	edx
		mov	[esi],eax//save	the	result 
		add	esi,4//increase	pointer
		add esp,4
		loop arxm
		mov [esi],edx//save	the	result 
		mov esp,saveesp
		//divtmp.NormalizeLength();
		mov	esi,divtmp.Data//data	pointer
nrm:	mov	ecx,divtmp.IntLen//length	value	
		test dword ptr[esi+ecx*4-4],4294967295
		jnz	end15//need	no normalizing		
		sub	divtmp.IntLen,1//normalize length of divtmp		
		jnz	nrm//if len is above 0
		inc	divtmp.IntLen//if 0 then curlen=1
end15:	//x-=divtmp
		lea edx,divtmp
		mov ecx,rem//pass "this" pointer
		call Sub2
		////////////end of x=x- quot.Data[i-t-1]*yb^(i-t-1)///////////////////////////
				
		//if(x>0)jump to	the	end25////////////////////////////////////
		test [ecx]Lint.sign,4294967295
		jz end25
		////////////x=x+ yb^(i-t-1)///////////////////////////
		mov	ebx,ybnt.Data
		mov eax,n
		sub	eax,i
		add eax,1
		lea	ebx,[ebx+eax*4]//shift left	i-t-1 steps divy.Data
		mov esi,ybnt.Data//save temporarily
		mov edi,ybnt.IntLen//save temporarily
		mov ybnt.Data,ebx
		sub ybnt.IntLen,eax
		//x+=ybnt;
		lea edx,ybnt
		mov ecx,rem
		call Add2
		mov ybnt.IntLen,edi//restore
		mov ybnt.Data,esi//restore
		//quot.Data[i-t-1]--;
		mov	eax,qit1
		dec	dword ptr[eax]//quot.Data[i-t-1]--;
end25:	////////////end of x=x+ quot.Data[i-t-1]*yb^(i-t-1)//////////////
		// end if(x>0)jump to the end25////////////////////////////////////		
		
		dec dword ptr[i]//for (i=n;i>=t+1;i--) end loop
		mov eax,i
		mov ebx,t
		cmp ebx,eax
		jnae biglpp
///////////////////////////end of big loop//////for (i=n;i>=t+1;i--)
endbglp:			
		//shift right rem, mp bits
		mov ecx,rem
		mov edx,mp
		call Sr
		
	//quot->NormalizeLength();
		mov esi,quot
		mov ebx,[esi]quot.Data
clp17:	mov	eax,[esi]quot.IntLen//length	value	
		mov eax,[ebx+eax*4-4]
		test eax,4294967295
		jnz end17//need no normalizing		
		lea eax,[esi]quot.IntLen
		dec dword ptr[eax]//normalize length of divy
		test dword ptr[eax],4294967295//if curlen is above 0
		jnz clp17
		inc dword ptr[eax]//if 0 then curlen=1
end17:

		////rem.sign=x.sign  quot sign depends of rem and A2
		//// test sign and restore original signs
		mov ecx,rem
		mov eax,thissign
		mov [ecx]Lint.sign,eax//rem.sign=this.sign
		mov ecx,[esp]//this
		mov [ecx]Lint.sign,eax//restore this.sign
		mov ecx,[esp+4]//A2
		mov eax,A2sign
		mov [ecx]Lint.sign,eax//restore A2.sign
		mov esi,quot
		
		mov eax,0
		cmp eax,thissign// test sign (this)
		rcl eax,1
		mov ecx,0
		cmp ecx,A2sign// test sign
		rcl ecx,1
		//cmp eax,ecx//theese all are the xor function (compatibility with 486)
//		jne xr1
//		mov eax,0
//		jmp xr2
//xr1:	mov eax,1/////////// minus if one is minus
//xr2:	mov [esi]quot.sign,eax//set sign
		xor eax,ecx
		mov [esi]quot.sign,eax//set sign
		
		//zero must have allways positive sign
		mov ecx,quot//quot
		call ZeroSign
		mov ecx,rem
		call ZeroSign//rem		

endz:	mov eax,0//return 0;		
		pop ecx
		pop edx//restore
		popf
		pop ebx
		pop esi
		pop edi	
		mov esp,ebp
		pop ebp
		ret 8
	}
}
//############################################################################################
__declspec(naked)int Lint::Div2(BU A2,Lint* quot,Lint* rem)//
{	
	__asm
    {
		push edi//save all registers
		push esi
		push ebx
		push ecx
		push edx
		
		mov ebx,[esp+24]//quot
		mov edx,[esp+28]//rem
		//fix the signs
		mov eax,[ecx]Lint.sign//this.sign
		mov [ebx]quot.sign,eax//quot.sign=this.sign
		mov [edx]rem.sign,eax//rem.sign=quot.sign		
		//initialize vars and pointers
		mov esi,[ebx]quot.Data
		mov edi,[ecx]Lint.Data
		mov ecx,[ecx]Lint.IntLen
		mov [ebx]quot.IntLen,ecx//set new curlen//reallocdatazero
		mov edx,0//
		//division
ddd:	mov eax,[edi+ecx*4-4]
		div dword ptr[esp]//edx or A2
		mov [esi+ecx*4-4],eax
		loop ddd		
		//rem =edx
		mov ecx, [esp+28]//rem
		mov dword ptr[ecx]rem.IntLen,1//set rem curlen=1( realloc)
		mov eax,[ecx]rem.Data
		mov [eax],edx//rem =edx
		//normalize quot
		mov eax,[ebx]quot.IntLen// quot length 
		test dword ptr[esi+eax*4-4],4294967295//
		jnz endff//need no normalizing
		sub [ebx]quot.IntLen,1//normalize length of prod
		jnz endff//if len is above 0
		inc [ebx]quot.IntLen//if 0 then curlen=1		
		
endff:	mov eax,0//return 0;
		pop edx//restore
		pop ecx
		pop ebx
		pop esi
		pop edi
		ret 8//		
	}	
}
//############################################################################################
__declspec(naked)int Lint::Add1(Lint*  A1, Lint* A2, Lint* sum)
{	
	PBU	mindata;
	PBU	maxdata;
	BU minlen;//minimum	length
	BU maxlen;//maximum	length
	
	__asm
	{
		push ebp
		mov ebp,esp
		sub esp,__LOCAL_SIZE//as  many bytes as local variables
		push edi//save registers
		push esi
		push ebx
		push ecx
		push edx
	}
	
	if (A1->sign==0)
	{
		if (A2->sign>0)
		{
			A2->sign=0;
			Sub1(A1,A2,sum);
			A2->sign=1;//restore
			goto endadd;
		}
	}
	else//A1.sign>0
	{
		if (A2->sign==0)
		{
			A1->sign=0;
			Sub1(A2,A1,sum);
			A1->sign=1;//restore
			goto endadd;
		}
		else 
		{
			A2->sign=0;
			A1->sign=0;
			Add1(A1,A2,sum);
			sum->sign=1;//negative
			A2->sign=1;//restore
			A1->sign=1;//restore			
			goto endadd;
		}
	}

	if (A1->IntLen>A2->IntLen)
	{
		minlen=A2->IntLen;
		maxlen=A1->IntLen;
		mindata=A2->Data;
		maxdata=A1->Data;		
	}
	else 
	{
		minlen=A1->IntLen;
		maxlen=A2->IntLen;
		mindata=A1->Data;
		maxdata=A2->Data;
	}
	__asm
	{	
		//sum->ReallocDataZero(maxlen+1)			
		mov ebx,sum
		mov ecx,maxlen
		add ecx,1//is the length of the sum
		mov edi,[ebx]sum.Data
		mov [ebx]sum.IntLen,ecx////set new curlen
		mov eax,0// fill memory and return 0;
		cld//  cld is for inc and std is for dec
		rep stosd//fill data with zeros
		//here begins the addition
		mov	edx,[ebx]sum.Data// from now up to the end edx points to sum.Data	
		mov	ecx, minlen	
		mov	esi, mindata
		mov	ebx,maxdata
		mov edi,0//for index purpose
		clc//clear carry
		////////////add	min	integer	first///////////////////////
arx:	mov	eax,[esi+edi*4]//mov eax,mindata
		adc	eax,[ebx+edi*4]//add
		mov	[edx+edi*4],eax//mov sum,eax
		inc edi//increase index
		loop arx
		///////////////proccess	the	rest bytes////////////////////
		mov	ecx, maxlen
		pushf//save	carry etc
		sub	ecx, minlen			
		popf//load carry		
		jecxz lastact
		jnc restwoc	// if not carry just copy the rest bytes(for fastener code)
		
rest:	mov	eax,[ebx+edi*4]//mov ebx,maxdata
		adc	eax,0//add
		mov	[edx+edi*4],eax//mov sum,eax			
		inc edi
		loop rest
		jmp lastact
//////////////////////////////////////////////////////////////
restwoc:mov eax,[ebx+edi*4]
		mov [edx+edi*4],eax
		inc edi
		loop restwoc
		clc
//////////////////////////////////////////////////////////////////
lastact:mov eax,0//last action  add carry(if exists) to sum
		adc	eax,0//add only carry
		mov [edx+edi*4],eax// save carry to the msb of sumdata
		// here ends the addition
	}		
	sum->NormalizeLength();
endadd:
	__asm
	{
		mov eax,0
		pop edx//restore
		pop ecx
		pop ebx
		pop esi
		pop edi	
		mov esp,ebp
		pop ebp
		ret //
	}
}
//############################################################################################
__declspec(naked)int Lint::Add2(Lint* A2)
{	
	__asm