bigint.cpp

RSA算法的演示程序,分组加密功能,可以对任意长度的字符串进行加密解密

		if( len )
		{
			Z.m_nLength += len;
			for( i=Z.m_nLength-1; i>=len; i-- )
				Z.m_ulValue[i] = Z.m_ulValue[i-len];
			for( i=0; i<len; i++ )
				Z.m_ulValue[i]=0;
		}
		X.Mov(X.Add(Z));
        Y.Mov(Y.Sub(A.Mul(Z)));
    }
    return X;
}

CBigInt CBigInt::Div( unsigned long A )
{
    CBigInt 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];
        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
****************************************************************************************/
CBigInt CBigInt::Mod( CBigInt& A )
{
    CBigInt 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.Mov(A.Mul(Y));
		if( 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));
    }
    return X;
}

unsigned long CBigInt::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,sys)
返回值：N被赋值为相应大数
sys暂时只能为10或16
****************************************************************************************/
void CBigInt::Get( CString& str, unsigned int system )
{
    int len = str.GetLength(), k;
    Mov(0);
    for(int i=0; i<len; i++ )
    {
       Mov( Mul(system) );
       if( (str[i]>='0') && (str[i]<='9') )
		   k = str[i]-48;
       else if( (str[i]>='A') && (str[i]<='F') )
		   k = str[i]-55;
       else if( (str[i]>='a') && (str[i]<='f') )
		   k=str[i]-87;
       else 
		   k=0;
       Mov( Add(k) );
    }
}

/****************************************************************************************
将大数按10进制或16进制格式输出为字符串
调用格式：N.Put(str,sys)
返回值：无，参数str被赋值为N的sys进制字符串
sys暂时只能为10或16
****************************************************************************************/
void CBigInt::Put( CString& str, unsigned int system )
{
    if( (m_nLength==1) && (m_ulValue[0]==0) )
	{
		str="0";
		return;
	}
	str="";
    CString t = "0123456789ABCDEF";
    int a;
    char ch;
    CBigInt X;
    X.Mov(*this);
    while( X.m_ulValue[X.m_nLength-1] > 0 )
    {
        a = X.Mod( system );
        ch = t[a];
        str.Insert( 0, ch );
        X.Mov( X.Div( system ) );
    }
}

/****************************************************************************************
求不定方程ax-by=1的最小整数解
调用方式：N.Euc(A)
返回值：X,满足：NX mod A=1
****************************************************************************************/
CBigInt CBigInt::Euc( CBigInt& A )
{
	CBigInt M,E,X,Y,I,J;
    int x,y;
	M.Mov(A);
	E.Mov(*this);
	X.Mov(0);
	Y.Mov(1);
	x=y=1;
	while( (E.m_nLength!=1) || (E.m_ulValue[0]!=0) )
	{
		I.Mov(M.Div(E));
		J.Mov(M.Mod(E));
		M.Mov(E);
		E.Mov(J);
		J.Mov(Y);
		Y.Mov(Y.Mul(I));
		if( x == y )
		{
		    if( X.Cmp(Y) >= 0 )
				Y.Mov(X.Sub(Y));
			else
			{
				Y.Mov(Y.Sub(X));
				y=0;
			}
		}
		else
		{
			Y.Mov(X.Add(Y));
			x=1-x;
			y=1-y;
		}
		X.Mov(J);
	}
	if( x==0 )
		X.Mov(A.Sub(X));
	return X;
}

/****************************************************************************************
求乘方的模
调用方式：N.RsaTrans(A,B)
返回值：X=N^A MOD B
****************************************************************************************/
CBigInt CBigInt::RsaTrans( CBigInt& A, CBigInt& B )
{
    CBigInt X,Y;
	int i,j,k;
	unsigned n;
	unsigned long num;
	k = A.m_nLength * 32 - 32;
	num = A.m_ulValue[A.m_nLength-1];
	while( num )
	{
		num = num>>1;
		k++;
	}
	X.Mov(*this);
	for( i=k-2; i>=0; i-- )
	{
		Y.Mov(X.Mul(X.m_ulValue[X.m_nLength-1]));
		Y.Mov(Y.Mod(B));
        for( n=1; n<X.m_nLength; n++ )
		{          
			for( j=Y.m_nLength; j>0; j-- )
				Y.m_ulValue[j] = Y.m_ulValue[j-1];
			Y.m_ulValue[0] = 0;
			Y.m_nLength ++;
			Y.Mov(Y.Add(X.Mul(X.m_ulValue[X.m_nLength-n-1])));
			Y.Mov(Y.Mod(B));
		}
		X.Mov(Y);
		if( (A.m_ulValue[i>>5]>>(i&31))&1 )
		{
		    Y.Mov(Mul(X.m_ulValue[X.m_nLength-1]));
		    Y.Mov(Y.Mod(B));
            for( n=1; n<X.m_nLength; n++ )
			{          
			    for( j=Y.m_nLength; j>0; j-- )
					Y.m_ulValue[j] = Y.m_ulValue[j-1];
			    Y.m_ulValue[0] = 0;
			    Y.m_nLength ++;
			    Y.Mov(Y.Add(Mul(X.m_ulValue[X.m_nLength-n-1])));
			    Y.Mov(Y.Mod(B));
			}
		    X.Mov(Y);
		}
	}
    return X;
}

/****************************************************************************************
拉宾米勒算法测试素数
调用方式：N.Rab()
返回值：若N为素数，返回1，否则返回0
****************************************************************************************/
int CBigInt::Rab()
{
    unsigned i,j,pass;
    for( i=0; i<550; i++ )
	{
		if( Mod(PrimeTable[i]) == 0 )
			return 0;
	}
    CBigInt S,A,I,K;
    K.Mov(*this);
	K.m_ulValue[0] --;
    for( i=0; i<5; i++ )
    {
        pass = 0;
        A.Mov( rand() * rand() );
		S.Mov( K );
        while( (S.m_ulValue[0]&1) == 0 )
		{
            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 --;
			I.Mov(A.RsaTrans(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 CBigInt::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;
	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;
	}
    CBigInt S,A,I,K;
    K.Mov(*this);
	K.m_ulValue[0] --;
    for( i=0; i<5; i++ )
	{
        A.Mov( rand() * rand() );
	    S.Mov( K.Div(2) );
	    I.Mov( A.RsaTrans(S,*this) );
	    if( ( (I.m_nLength!=1)||(I.m_ulValue[0]!=1) ) && (I.Cmp(K)!=0) )
			goto begin;
	}
}