bigint.cpp

来自「本程序实现DSA数字签名 是学习和研究密码学的良好资源 欢迎下载」· C++ 代码 · 共 632 行 · 第 1/2 页

    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;
	}
}

/*
//赋M为默认除数，即加/解密中的模n
monty::monty( const CBigInt &M )
{
//	m = M;
//	N = 0; 
//	R = 1; 
//	while ( R < M ) 
//	{ 
//		R += R; 
//		N += 1; 
//	}
//	R1 = modinv( R-m, m );
//	n1 = R - modinv( m, R );
	m.Mov(M);
	N.Mov(0);
	R.Mov(1);
	while (R.Cmp(M)<0)
	{
		R.Mov(R.Add(R));
		N.Mov(N.Add(1));
	}
	R1.Mov(modinv(R.Sub(m),m);
	n1.Mov(R.Sub(m,R);
}


void monty::mul(CBigInt &x, const CBigInt &y )
{
//	T.value->fast_mul(*x.value,*y.value,N*2);	//T=x*y;
//	k.value->fast_mul(*T.value,*n1.value,N);	//k=(T*n1)%R;
//	x.value->fast_mul(*k.value,*m.value,N*2);	//x=(T+k*m)/R; 
//	x +=T;
//	x.value->shr( N );
//	if (x>=m) x -= m;
	T.Mov(x.Mul(y));
	k.Mov(T.Mul(n1));
	k.Mov(k.Mod(R));
	x.Mov(T.Add(k.Mul(m)));
	x.Mov(x.Div(R));
}

//返回值= (x^e)%(this->m)
CBigInt monty::exp( const CBigInt &x, const CBigInt &e )
{
//	vlong result = R-m;
//	vlong t = ( x * R ) % m;
//	unsigned bits = e.value->bits();
	CBigInt result,t;
	result.Mov(R.Sub(m));
	t.Mov(x.Mul(R));
	t.Mov(t.Mod(m));
	unsigned i = 0;
	while (1)
	{
		if ( e.value->bit(i) )
		mul( result, t);
		i += 1;
		if ( i == bits ) break;
		mul( t, t );
	}
	return ( result * R1 ) % m;
}

/*
class monty 	
{
	CBigInt R,R1,m,n1;
	CBigInt T,k; 		//工作寄存器
	unsigned N;		//R的位（bit）数
	void mul( CBigInt &x, const CBigInt &y );
public:
	CBigInt exp( const CBigInt &x, const CBigInt &e );
	monty( const CBigInt &M );
};


//返回值= (x^e)%m
CBigInt modexp( const CBigInt & x, CBigInt & e, const CBigInt & m )
{
	monty me(m);
	return me.exp( x,e );
}

*/