bignumber.cpp

基于RSA算法对文档进行加解密的VC++实现,效果较好.

			for(i=Z.m_nLength-1;i>=len;i--)Z.m_ulValue[i]=Z.m_ulValue[i-len];
			//Z的低len 长度补 0
			for(i=0;i<len;i++)Z.m_ulValue[i]=0;
		}
		X.Mov(X.Add(Z)); //执行X=X+(A[p]/B[q]-1)*0x100000000**(p-q)
        Y.Mov(Y.Sub(A.Mul(Z))); //执行 A=A-X*B
    }
    return X;
}

CBigNumber CBigNumber::Div(unsigned long A)
{
    CBigNumber X;
    X.Mov(*this);
    if(X.m_nLength==1){X.m_ulValue[0]=X.m_ulValue[0]/A;return X;}
    unsigned __int64 div,mul;
    unsigned long carry=0;
    for(int i=X.m_nLength-1;i>=0;i--)
    {
        div=carry;//存放余数
        div=(div<<32)+X.m_ulValue[i];//上次的余数左移32位加上这次的被除数
        X.m_ulValue[i]=(unsigned long)(div/A);//执行除运算
        mul=(div/A)*A;//商乘以除数
        carry=(unsigned long)(div-mul);//计算这次的余数
    }
    if(X.m_ulValue[X.m_nLength-1]==0)X.m_nLength--;
    return X;
}

/****************************************************************************************
大数求模
调用形式：N.Mod(A)
返回值：N%A
****************************************************************************************/
CBigNumber CBigNumber::Mod(CBigNumber A)
{
    CBigNumber X,Y;
	unsigned __int64 div,num;
    unsigned long carry=0;
	unsigned i,len;
    X.Mov(*this);
    while(X.Cmp(A)>=0)
    {
		div=X.m_ulValue[X.m_nLength-1];//被除数最高位
		num=A.m_ulValue[A.m_nLength-1];//除数最高位
		len=X.m_nLength-A.m_nLength;
		if((div==num)&&(len==0)){X.Mov(X.Sub(A));break;}
		if((div<=num)&&len){len--;div=(div<<32)+X.m_ulValue[X.m_nLength-2];}
		div=div/(num+1);
		Y.Mov(div);//预除下 商给了Y
		Y.Mov(A.Mul(Y));//预除下的商 乘以 除数
		if(len)//Y 左移len 位
		{
			Y.m_nLength+=len;
			for(i=Y.m_nLength-1;i>=len;i--)Y.m_ulValue[i]=Y.m_ulValue[i-len];
			for(i=0;i<len;i++)Y.m_ulValue[i]=0;
		}
        X.Mov(X.Sub(Y));//X＝X－Y
    }
    return X;
}

unsigned long CBigNumber::Mod(unsigned long A)
{
    if(m_nLength==1)return(m_ulValue[0]%A);
    unsigned __int64 div;
    unsigned long carry=0;
    for(int i=m_nLength-1;i>=0;i--)
    {
        div=m_ulValue[i];
		div+=carry*0x100000000;
        carry=(unsigned long)(div%A);
    }
    return carry;
}

/****************************************************************************************
从字符串按10进制或16进制格式输入到大数
调用格式：N.Get(str,len) len为字节数
返回值：N被赋值为相应大数
****************************************************************************************/
void CBigNumber::Get(unsigned char *str, UINT  len)//转成实在的数字
{
	   CBigNumber X,Y;

	   int i;
	   X.Mov(0);

	   for(i=0;i<len ;i++)
	   {
		   X.Mov(X.Mul(256));
		   X.Mov(X.Add(str[i]));
	   }

	 m_nLength=X.m_nLength;

	 if (m_nLength>1)
	 {
		 for(unsigned long  i=0;i<m_nLength;i++)
		  m_ulValue[i]=X.m_ulValue[i];
		 
	 }
	 else
	 {   
		m_nLength=1;
        m_ulValue[0]=X.m_ulValue[0];   	

	 }
	 for(i=m_nLength;i<BI_MAXLEN;i++)
		{
			m_ulValue[i]=0;			
		}
}

/****************************************************************************************
将大数按10进制或16进制格式输出为字符串
调用格式：N.Put(str)
返回值：无，大数N转换为字符串str
****************************************************************************************/
void CBigNumber::Put(CString &str)
{   
	unsigned long  ch;
    CBigNumber X;
    X.Mov(*this);
	CString  string_copy;
   while(X.m_ulValue[X.m_nLength-1]>0)	
    {
        ch=X.Mod(256);
		string_copy.Format("%ld",ch);

		str=string_copy+str;
        X.Mov(X.Div(256));       
    }
}
void CBigNumber::Putchar(CString &str)
{  
	unsigned char ch;
	CBigNumber X;
  	CString  string_copy;   
    X.Mov(*this);
	
    while(X.m_ulValue[X.m_nLength-1]>0)
    {
		
		ch = X.m_ulValue[0]&0xff;
		str =(CString)ch+str;
        X.Mov(X.Div(256));    
    }

}
/****************************************************************************************
求不定方程ax-by=1的最小整数解
调用方式：N.Euc(A)
返回值：X,满足：NX mod A=1
****************************************************************************************/
CBigNumber CBigNumber::Euc(CBigNumber A)
{
	CBigNumber M,E,X,Y,I,J;
    int x,y;
	M.Mov(A);//M 是被除数
	E.Mov(*this);//E 是除数
	X.Mov(0);
	Y.Mov(1);
	x=y=1;
	while((E.m_nLength!=1)||(E.m_ulValue[0]!=0))
	{
		I.Mov(M.Div(E));// 比如49 /11，I 是商
		J.Mov(M.Mod(E));// 比如49 %11，J 是余数
		
		M.Mov(E);//除数给了被除数
		E.Mov(J);//余数给了除数
		
		J.Mov(Y);
		Y.Mov(Y.Mul(I));//总的商，给了Y
		if(x==y)
		{
		    if(X.Cmp(Y)>=0)//X >＝ Y
				Y.Mov(X.Sub(Y));//Y = X - Y

			else{Y.Mov(Y.Sub(X));  y=0;}//Y=Y-X
		}
		else{Y.Mov(X.Add(Y));x=1-x;y=1-y;}
		X.Mov(J);// X 是这一步算出来之前的总的商
	}
	if(x==0)X.Mov(A.Sub(X));
	return X;
}

/****************************************************************************************
用蒙哥马利法进行幂模运算
调用方式：N.Mon(A,B)
返回值：X=N^A MOD B
****************************************************************************************/

CBigNumber CBigNumber::Mon(CBigNumber A, CBigNumber B)
{
    CBigNumber X,Y,Z;
    X.Mov(1);
    Y.Mov(*this);
    Z.Mov(A);
    while((Z.m_nLength!=1)||Z.m_ulValue[0])//指数不为0时
	{

        if(Z.m_ulValue[0]&1)//当指数为奇数时
		{
             Z.Mov(Z.Sub(1));
             X.Mov(X.Mul(Y));
             X.Mov(X.Mod(B));
		}
        else                 //当指数为偶数时
		{
             Z.Mov(Z.Div(2));//指数除以2
             Y.Mov(Y.Mul(Y));
             Y.Mov(Y.Mod(B));
		}
	}
    return X;
}

/****************************************************************************************
拉宾米勒算法测试素数
调用方式：N.Rab()
返回值：若N为素数，返回1，否则返回0
****************************************************************************************/
int CBigNumber::Rab()
{
    unsigned i,j,pass;
    for(i=0;i<550;i++){if(Mod(PrimeTable[i])==0)return 0;}
    CBigNumber S,A,I,K;
    K.Mov(*this);
	K.m_ulValue[0]--;
    for(i=0;i<15;i++)
    {
        pass=0;
        A.Mov(rand()*rand());
		S.Mov(K);
        while((S.m_ulValue[0]&1)==0)//此数是奇数时才测试
		{
			//n－1 除以2
            for(j=0;j<S.m_nLength;j++)
			{
			    S.m_ulValue[j]=S.m_ulValue[j]>>1;
			    if(S.m_ulValue[j+1]&1)S.m_ulValue[j]=S.m_ulValue[j]|0x80000000;
			}
		    if(S.m_ulValue[S.m_nLength-1]==0)S.m_nLength--;
			// 计算a^t%n 是否等于 1
		
			I.Mov(A.Mon(S,*this));
			if(I.Cmp(K)==0){pass=1;break;}
		}
		if((I.m_nLength==1)&&(I.m_ulValue[0]==1))pass=1;
		if(pass==0)return 0;
	}
    return 1;
}

/****************************************************************************************
产生随机素数
调用方法：N.GetPrime(bits)
返回值：N被赋值为一个bits位（0x100000000进制长度）的素数
****************************************************************************************/
void CBigNumber::GetPrime(int bits)
{
    unsigned i;
    m_nLength=bits;
begin:
	for(i=0;i<m_nLength;i++)m_ulValue[i]=rand()*0x10000+rand();//先随机产生一个大数，每一个数随机产生两次
    m_ulValue[0]=m_ulValue[0]|1;//保证是奇数
	//大数整体左移一位,乘以 2
	for(i=m_nLength-1;i>0;i--)
	{
		m_ulValue[i]=m_ulValue[i]<<1;
		if(m_ulValue[i-1]&0x80000000)m_ulValue[i]++;
	}
	m_ulValue[0]=m_ulValue[0]<<1;
	m_ulValue[0]++;
	
    for(i=0;i<550;i++){if(Mod(PrimeTable[i])==0)goto begin;}
    CBigNumber S,A,I,K;
    K.Mov(*this);
	K.m_ulValue[0]--;
    for(i=0;i<15;i++)
	{
        A.Mov(rand()*rand());
	    S.Mov(K.Div(2));
	
	    I.Mov(A.Mon(S,*this));
	    if(((I.m_nLength!=1)||(I.m_ulValue[0]!=1))&&(I.Cmp(K)!=0))goto begin;
	}
}