largeint.cpp

rsa算法/// ////

			sal ecx,dword ptr 2;
			
			sub eax,len; //求初始偏移。
			
			mov ebx,dword ptr 4; //偏移倍率
			mul ebx;		
			
			lea ebx,label0;
			add eax,ebx;
			clc;
			jmp eax;
	labelloop:
			popf;
	label0:
			rcr dword ptr [esi + ecx - 1*4],1;
			//label1:
			rcr dword ptr [esi + ecx - 2*4],1;
			//label2:
			rcr dword ptr [esi + ecx - 3*4],1;
			//label3:
			rcr dword ptr [esi + ecx - 4*4],1;
			//label4:
			rcr dword ptr [esi + ecx - 5*4],1;
			//label5:
			rcr dword ptr [esi + ecx - 6*4],1;
			//label6:
			rcr dword ptr [esi + ecx - 7*4],1;
			//label7:
			rcr dword ptr [esi + ecx - 8*4],1;
			//label8:
			rcr dword ptr [esi + ecx - 9*4],1;
			//label9:
			rcr dword ptr [esi + ecx - 10*4],1;
			//label10:
			rcr dword ptr [esi + ecx - 11*4],1;
			//label11:
			rcr dword ptr [esi + ecx - 12*4],1;
			//label12:
			rcr dword ptr [esi + ecx - 13*4],1;
			//label13:
			rcr dword ptr [esi + ecx - 14*4],1;
			//label14:
			rcr dword ptr [esi + ecx - 15*4],1;
			//label15:
			rcr dword ptr [esi + ecx - 16*4],1;
			//label16:
			pushf;
			sub ecx,dword ptr 64;
			jnz labelloop;
			popf;
			popad;
		}
		for( T_DWORD i = n._len-1; i > 0; i--)
		{
			if( n._data[i] == 0 ) //末尾是0
			{
				n._len--;
			}
			else break;
		}
	}
	
	void CLargeInt::RCL(CLargeInt& n)
	{
		T_DWORD	len = n._len; //len绝对不能<1，否则会出错。
		T_DWORD	*p1 = 0;
		
		n._data[len] = 0;
		n._len++;
		
		len++;
		p1 = n._data;
		
		__asm
		{
			pushad;		
			
			//载入计算地址
			mov esi,p1;
			
			mov eax,len;
			mov ecx,eax;
			
			sal eax,dword ptr 2;
			add esi,eax;
			
			add ecx,dword ptr 15;
			and ecx,dword ptr 0xFFFFFFF0;
			
			mov eax,ecx;
			sal ecx,dword ptr 2;
			
			neg ecx;
			
			sub eax,len; //求初始偏移。
			jz label0;
			
			mov ebx,dword ptr 4; //偏移倍率
			mul ebx;		
			
			lea ebx,label1;
			sub ebx,4;
			add eax,ebx;
			clc;
			jmp eax;
	labelloop:
			popf;
	label0:
			rcl dword ptr [esi + ecx + 0*4],1;
	label1:
			rcl dword ptr [esi + ecx + 1*4],1;
			//label2:
			rcl dword ptr [esi + ecx + 2*4],1;
			//label3:
			rcl dword ptr [esi + ecx + 3*4],1;
			//label4:
			rcl dword ptr [esi + ecx + 4*4],1;
			//label5:
			rcl dword ptr [esi + ecx + 5*4],1;
			//label6:
			rcl dword ptr [esi + ecx + 6*4],1;
			//label7:
			rcl dword ptr [esi + ecx + 7*4],1;
			//label8:
			rcl dword ptr [esi + ecx + 8*4],1;
			//label9:
			rcl dword ptr [esi + ecx + 9*4],1;
			//label10:
			rcl dword ptr [esi + ecx + 10*4],1;
			//label11:
			rcl dword ptr [esi + ecx + 11*4],1;
			//label12:
			rcl dword ptr [esi + ecx + 12*4],1;
			//label13:
			rcl dword ptr [esi + ecx + 13*4],1;
			//label14:
			rcl dword ptr [esi + ecx + 14*4],1;
			//label15:
			rcl dword ptr [esi + ecx + 15*4],1;
			//label16:
			pushf;
			add ecx,dword ptr 64;
			jnz labelloop;
			popf;
			popad;
		}
		for( T_DWORD i = n._len-1; i > 0; i--)
		{
			if( n._data[i] == 0 ) //末尾是0
			{
				n._len--;
			}
			else break;
		}
	}
	
	void CLargeInt::Mul(const CLargeInt& faciend,const CLargeInt& multiplier,CLargeInt& product)
	{
		CLargeInt temp;
		product._len = (faciend._len + multiplier._len);
		memset(product._data,0,product._len * 4	);
		
		for( T_DWORD i = 0; i <	multiplier._len; i++)
		{
			Mul(faciend,multiplier._data[i],temp);
			Add(product,temp,product,i);
		}
		for( i = product._len-1; i > 0;	i--)
		{
			if( product._data[i] ==	0 ) //末尾是0
			{
				product._len--;
			}
			else break;
		}
	}
	
	void CLargeInt::Div(const CLargeInt& dividend,T_DWORD divisor,CLargeInt& quotient,T_DWORD& residual)
	{
		T_DWORD	len; //len绝对不能<1，否则会出错。
		T_DWORD	*p1 = 0;
		T_DWORD	*p2 = 0;
		
		T_DWORD	*pr = &residual;
		
		len = dividend._len;
		quotient._len =	dividend._len;
		p1 = dividend._data;
		p2 = quotient._data;
		
		__asm
		{
			pushad;		
			
			//载入计算地址
			mov esi,p1;
			mov edi,p2;
			
			mov eax,len;
			mov ecx,eax;
			
			add ecx,dword ptr 7;
			and ecx,dword ptr 0xFFFFFFF8;
			
			mov eax,ecx;
			sal ecx,dword ptr 2;
			
			sub eax,len; //求初始偏移。
			
			mov ebx,dword ptr 0x0A;	//偏移倍率
			mul ebx;		
			
			lea edx,label0;
			add eax,edx;
			
			xor edx,edx;
			
			mov ebx,divisor;
			
			clc;
			jmp eax;
	labelloop:
			
	label0:
			mov eax,[esi + ecx - 1*4];
			div ebx;
			mov [edi + ecx - 1*4],eax;
			//label1:
			mov eax,[esi + ecx - 2*4];
			div ebx;
			mov [edi + ecx - 2*4],eax;
			//label2:
			mov eax,[esi + ecx - 3*4];
			div ebx;
			mov [edi + ecx - 3*4],eax;
			//label3:
			mov eax,[esi + ecx - 4*4];
			div ebx;
			mov [edi + ecx - 4*4],eax;
			//label4:
			mov eax,[esi + ecx - 5*4];
			div ebx;
			mov [edi + ecx - 5*4],eax;
			//label5:
			mov eax,[esi + ecx - 6*4];
			div ebx;
			mov [edi + ecx - 6*4],eax;
			//label6:
			mov eax,[esi + ecx - 7*4];
			div ebx;
			mov [edi + ecx - 7*4],eax;
			//label7:
			mov eax,[esi + ecx - 8*4];
			div ebx;
			mov [edi + ecx - 8*4],eax;
			//label8:
			sub ecx,dword ptr 32;
			jnz labelloop;
			
			//运行到这里说明已经计算完毕，最后保存余数。
			mov ecx,pr;
			mov [ecx],edx;
			popad;
		}
		
		for( T_DWORD i = quotient._len-1; i > 0; i--)
		{
			if( quotient._data[i] == 0 ) //末尾是0
			{
				quotient._len--;
			}
			else break;
		}
	}
	
	void CLargeInt::Div(const CLargeInt& dividend,const CLargeInt& divisor,CLargeInt& quotient,CLargeInt& residual)
	{
		if( dividend._len < divisor._len )
		{
			quotient._len =	1;
			quotient._data[0] = 0;
			Copy(dividend,residual);
		}
		else
		{
			if( divisor._len == 1)
			{			
				Div(dividend,divisor._data[0],quotient,residual._data[0]);
				residual._len =	1;
			}
			else
			{
				CLargeInt d,r;
				
				//满位算法
				T_DWORD	head = divisor._data[divisor._len-1];
				__asm
				{
					pushad;
					mov eax,head;
					bsr ecx,eax;
					mov edx,dword ptr 31;
					sub edx,ecx;
					mov ecx,edx;
					mov eax,dword ptr 0x01;
					sal eax,cl;
					mov head,eax;
					popad;
				}
				
				Mul(dividend,head,d);
				Mul(divisor,head,r);
				
				quotient._len =	d._len - r._len	+ 1;
				quotient._data[quotient._len - 1] = 0;
				
				T_DWORD	newhead	= r._data[r._len - 1];
				//以上处理的目的是使得被除数最高位的1移动到DWORD的最高位。
				//处理之后可以极大减少商的上下限之间的差距。
				
				T_DWORD	highpart = 0;
				T_DWORD	lowpart	 = 0;
				T_DWORD	max = 0,min = 0;
				T_DWORD	offset = 0;
				CLargeInt temp;
				for( T_DWORD i = d._len-1; i >=	r._len-1; i-- )
				{				
					offset = i - (r._len - 1);	
					lowpart	= d._data[i];
					
					__asm
					{//这段汇编代码的作用是求商的上下限。min & max
						pushad;
						mov edx,highpart;
						mov eax,lowpart;
						mov ecx,newhead;
						div ecx;
						mov max,eax;
						
						inc ecx;
						jz _mov;
						mov edx,highpart;
						mov eax,lowpart;
						div ecx;
						mov edx,eax;
	_mov:
						mov min,edx;
						popad;
					}
					
					if( max	== 0 )
					{
						highpart = d._data[i];
						quotient._data[offset] = 0;
					}
					else
					{
						Mul(r,max,temp);
						if( max	!= min )
						{
							while( !LargerEqual(d,temp,offset) )
							{//这里使用的其实是试商法，
								//由于max和min的差距已经很小，所以这里不再折半试商。
								max--;
								Sub(temp,r,temp);
							}
						}	
						
						quotient._data[offset] = max; //保存商。
						Sub(d,temp,d,offset); //求本阶的余数。
						highpart = d._data[i]; //载入余数。
					}
				}
				
				//清除高位的0。
				for( i = quotient._len-1; i > 0; i--)
				{
					if( quotient._data[i] == 0 ) //末尾是0
					{
						quotient._len--;
					}
					else break;
				}
				//除法完成，计算余数：
				Div(d,head,residual,newhead);
				
				if( newhead != 0 ) 
				{
					//余数不为0，说明出错。
					__asm int 3;
				}
			}
			
		}
	}
	
	void CLargeInt::ExpMod(const CLargeInt&	source,const CLargeInt&	exponent,const CLargeInt& modulo,CLargeInt& result)
	{
		CLargeInt n,e,r(1),temp,temp1;
		Copy(source,n);
		Copy(exponent,e);
		
		while( e._len >	1 || e._data[e._len - 1] > 1 )
		{
			if( e._data[0] &1 ) 
			{
				Mul(r,n,temp);
				Div(temp,modulo,temp1,r);
			}
			RCR(e);
			Mul(n,n,temp);
			Div(temp,modulo,temp1,n);
		}
		Mul(r,n,temp);
		Div(temp,modulo,temp1,result);
	}
	
	bool CLargeInt::RabinMillerTest(const CLargeInt& source,const CLargeInt& base)
	{
		CLargeInt m,temp(1);
		
		Sub(source,temp,m);
		
		T_DWORD	count =	0;
		while(!(m._data[0] & 0x01) ) 
		{
			count++;
			RCR(m);
		}
		/*
		这里注释掉的是旧的算法，可以用后面的等效算法取代。
		改变的算法使得计算ExpMod的次数由 count 减少到 1
		虽然理论上计算次数大大减少了，但是实际效果似乎只是减少了50%左右的运算量。
		
		  for( T_DWORD i = 0; i< count;	i++)
		  {
		  CLargeInt mod;
		  ExpMod(base,m,source,mod);
		  if( mod._data[0] == 1	&& mod._len == 1 ) 
		  {
		  return true;
		  }
		  else
		  {
		  Sub(source,mod,temp);
		  if(  temp._data[0] ==	1 && temp._len == 1) 
		  {
		  return true;
		  }
		  }
		  RCL(m);		
		  }
		*/
		
		CLargeInt mod;
		ExpMod(base,m,source,mod);
		if( mod._data[0] == 1 && mod._len == 1 ) 
		{
			return true;
		}
		else
		{
			Sub(source,mod,temp);
			if(  temp._data[0] == 1	&& temp._len ==	1) 
			{
				return true;
			}
		}
		for( T_DWORD i = 1; i< count; i++)
		{
			CLargeInt next,t;
			Mul(mod,mod,next);
			Div(next,source,t,mod);
			if( mod._data[0] == 1 && mod._len == 1 ) 
			{
				return true;
			}
			else
			{
				Sub(source,mod,temp);
				if(  temp._data[0] == 1	&& temp._len ==	1) 
				{
					return true;
				}
			}			
		}
		
		return false;
	}
	
	bool CLargeInt::RSACreate( const CLargeInt &p,const CLargeInt &	q,const	CLargeInt &e,CLargeInt &d,CLargeInt &n)
	{//由已知的P,Q,E计算N,D，完成RSA密钥生成。
		Mul(p,q,n);
		CLargeInt a(e),b(n);
		Sub(b,p,b);
		Sub(b,q,b);
		Add(b,1,b);
		
		if( !Coprime(b,e) ) return false;
		//求D的算法，通过辗转相除，最终求得需要的D值。
		CLargeInt k1,c1;
		Div(b,a,k1,c1);
		if( c1._len == 1 && c1._data[0]	== 0 ) return false;
		if( c1._len == 1 && c1._data[0]	== 1 ) 
		{ 
			CLargeInt temp;
			Sub(e,1,temp);
			Mul(temp,k1,d);
			Add(d,1,d);
			return true; 
		}
		
		CLargeInt k2,c2,ka2;
		Div(a,c1,k2,c2);
		if( c2._len == 1 && c2._data[0]	== 0 ) return false;
		Mul(k1,k2,ka2);
		Add(ka2,1,ka2);
		if( c2._len == 1 && c2._data[0]	== 1 ) { Copy(ka2,d); return true; }
		
		
		CLargeInt k3,c3,ka3;
		Div(c1,c2,k3,c3);
		if( c3._len == 1 && c3._data[0]	== 0 ) return false;
		Mul(k3,ka2,ka3);
		Add(ka3,k1,ka3);
		if( c3._len == 1 && c3._data[0]	== 1 ) 
		{ 
			Copy(ka3,d);
			
			CLargeInt temp,temp1,temp2;
			Mul(d,e,temp);
			Div(temp,b,temp1,temp2);
			Add(temp2,1,temp2);
			if( Equal(temp2,b) )
			{
				Mul(d,d,temp1);
				Div(temp1,b,temp2,d);
				Mul(d,e,temp1);
				Div(temp1,b,temp2,d);
			}
			return true; 
		}
		
		CLargeInt kn_2(k2),cn_2(c2),ka_2(ka2);
		CLargeInt kn_1(k3),cn_1(c3),ka_1(ka3);
		
		CLargeInt kn,cn,kan;
		do {
			Div(cn_2,cn_1,kn,cn);
			Mul(kn,ka_1,kan);
			Add(kan,ka_2,kan);
			
			if( cn._len == 1 && cn._data[0]	== 0 ) return false;
			if( cn._len == 1 && cn._data[0]	== 1 ) 
			{
				Copy(kan,d);
				
				CLargeInt temp,temp1,temp2;
				Mul(d,e,temp);
				Div(temp,b,temp1,temp2);
				Add(temp2,1,temp2);
				if( Equal(temp2,b) )
				{
					Mul(d,d,temp1);
					Div(temp1,b,temp2,d);
					Mul(d,e,temp1);
					Div(temp1,b,temp2,d);
				}
				return true; 
			}
			Copy(kn_1,kn_2);
			Copy(cn_1,cn_2);
			Copy(ka_1,ka_2);
			
			Copy(kn,kn_1);
			Copy(cn,cn_1);
			Copy(kan,ka_1);
			
		} while(true);
	}
	
	void CLargeInt::RSAEncode( const CLargeInt &n,const CLargeInt &d,const CLargeInt &m,CLargeInt &c)
	{
		ExpMod(m,d,n,c);
	}
	
	void CLargeInt::RSADecode( const CLargeInt &n,const CLargeInt &e,const CLargeInt &c,CLargeInt &m)
	{
		ExpMod(c,e,n,m);
	}
	
	typedef	unsigned __int64 ULONGLONG;
	inline ULONGLONG GetCycleCount()
	{
		__asm RDTSC
	}
	#include <windows.h>
	void CLargeInt::CreateRandom(CLargeInt &n,T_DWORD bitcount)
	{
		n._len = (bitcount + 31)/32;
		for( T_DWORD i = 0; i <	n._len;	i++ )
		{
			T_DWORD	byte[4];
			
			for( int b = 0;	b < 4; b++)
			{
				for( int j = 0;	j < 4 ;	j++)
				{
					Sleep(0);
				}
				byte[b]	= GetCycleCount()& 0xFF;
			}
			
			n._data[i] = (byte[0] << 24)
				| (byte[1] << 16)
				| (byte[2] << 8)
				| (byte[3] << 0);
		}
		n._data[0] |= 1;
		n._data[n._len - 1] |= 0x80000000;
		if( (bitcount &	31) )
		{
			n._data[n._len - 1] >>=	32 - (bitcount & 31);
		}	
	}
	
	bool CLargeInt::Coprime(const CLargeInt	&source,const CLargeInt	&target)
	{
		CLargeInt m(source),n(target),temp;
		while(true)
		{
			Div(m,n,temp,m);
			if( m._len == 1	&& m._data[0] == 1 ) return true;
			else if( m._len	== 1 &&	m._data[0] == 0	) return false;
			
			Div(n,m,temp,n);
			if( n._len == 1	&& n._data[0] == 1 ) return true;
			else if( n._len	== 1 &&	n._data[0] == 0	) return false;
		}
	}
}