main.cpp

能够生成1024位的RSA算法密钥对

	}
    if (mshift) 
	{
		for (i = 0; i < mlen - 1; i++)
			m[i] = (m[i] << mshift) | (m[i + 1] >> (BIGNUM_INT_BITS - mshift));
		m[mlen - 1] = m[mlen - 1] << mshift;
    }

    alen = dividend[0];
    /* Ensure alen > mlen */
    if (alen <= mlen)
		alen = mlen + 1;

	/* Allocate a of size alen, copy dividend to a */

	a=new unsigned __int32[alen];

    for (j = 0; j < alen; j++)
		a[j] = 0;
    for (j = 1; j <= (int)dividend[0]; j++)
		a[alen - j] = dividend[j];
    /* Main computation */
    internal_mod(a, alen, m, mlen, quotient, mshift);

    /* Fixup result in case the modulus was shifted */
    if (mshift) 
	{
		for (i = alen - mlen - 1; i < alen - 1; i++)
		{
			a[i] = (a[i] << mshift) | (a[i + 1] >> (BIGNUM_INT_BITS - mshift));
		}
		a[alen - 1] = a[alen - 1] << mshift;
		internal_mod(a, alen, m, mlen, (unsigned __int32 *)quotient, 0);
		for (i = alen - 1; i >= alen - mlen; i--)
		{
			a[i] = (a[i] >> mshift) | (a[i - 1] << (BIGNUM_INT_BITS - mshift));
		}
    }
	
	//处理商
	for(i=alen;i>=1;i--)
	{
		if(quotient[i]!=0)
			break;
	}
	quotient[0]=i;

	//处理余数
	for(i=0;i<alen;i++)
	{
		if(a[i]!=0)
			break;
	}
	
	if(i==alen)//余数为零
	{
		delete[] a;
		delete[] m;
		return;
	}
	result[0]=alen-i;
	int k=1;
	for(j=alen-1;j>=i;j--)
	{
		result[k++]=a[j];
	}
		delete[] a;
		delete[] m;
}

void bignum_divmod(BIGNUM dividend, BIGNUM mod,unsigned __int32 * quotient,BIGNUM result)
{
    int mshift;
    int alen, mlen, i, j;
	
	if(quotient)
		memset(quotient,0,sizeof(BIGNUM));
	
	memset(result,0,sizeof(BIGNUM));

	if(CompareBigNum(dividend,mod)<0)
	{
		CopyBigNum(result,dividend);
		return;
	}
	/* Allocate m of size mlen, copy mod to m */
    /* We use big endian internally */
	unsigned __int32 *a,*m;
    mlen = mod[0];
	m=new unsigned __int32[mlen];
	memset(m,0,sizeof(unsigned __int32)*mlen);
	for (j = 0; j < mlen; j++)
		m[j] = mod[mlen - j];


    /* Shift m left to make msb bit set */
    for (mshift = 0; mshift < BIGNUM_INT_BITS-1; mshift++)
	{
		if ((m[mlen] << mshift) & BIGNUM_TOP_BIT)
			break;
	}
    if (mshift) 
	{
		for (i = 0; i < mlen - 1; i++)
			m[i] = (m[i] << mshift) | (m[i + 1] >> (BIGNUM_INT_BITS - mshift));
		m[mlen - 1] = m[mlen - 1] << mshift;
    }

    alen = dividend[0];
    /* Ensure alen > mlen */
    if (alen <= mlen)
		alen = mlen + 1;

	/* Allocate a of size alen, copy dividend to a */

	a=new unsigned __int32[alen];

    for (j = 0; j < alen; j++)
		a[j] = 0;
    for (j = 1; j <= (int)dividend[0]; j++)
		a[alen - j] = dividend[j];
    /* Main computation */
    internal_mod(a, alen, m, mlen, quotient, mshift);

    /* Fixup result in case the modulus was shifted */
    if (mshift) 
	{
		for (i = alen - mlen - 1; i < alen - 1; i++)
		{
			a[i] = (a[i] << mshift) | (a[i + 1] >> (BIGNUM_INT_BITS - mshift));
		}
		a[alen - 1] = a[alen - 1] << mshift;
		internal_mod(a, alen, m, mlen, NULL, 0);
		for (i = alen - 1; i >= alen - mlen; i--)
		{
			a[i] = (a[i] >> mshift) | (a[i - 1] << (BIGNUM_INT_BITS - mshift));
		}
    }
	
	//处理商
	if(quotient)
	{
		for(i=alen;i>=1;i--)
		{
			if(quotient[i]!=0)
				break;
		}
		quotient[0]=i;
	}

	//处理余数
	for(i=0;i<alen;i++)
	{
		if(a[i]!=0)
			break;
	}
	
	if(i==alen)//余数为零
	{
		delete[] a;
		delete[] m;
		return;
	}
	result[0]=alen-i;
	int k=1;
	for(j=alen-1;j>=i;j--)
	{
		result[k++]=a[j];
	}
		delete[] a;
		delete[] m;
}

void bignum_div(BIGNUM dividend,BIGNUM divisor,BIGNUM quotient,BIGNUM remainder)
{
	unsigned __int32 i,blen,len;
	int iCmpResult=0;
	unsigned __int64 num;
	//unsigned __int32 div;
	unsigned __int32 hi,lo,w,q,r;
	BIGNUM tempdividend,X,Z,temp;


	if(CompareBigNum(dividend,divisor)<0)
	{
		memset(quotient,0,sizeof(BIGNUM));
		CopyBigNum(remainder,dividend);
		return;
	}
	//memset(tempdividend,0,sizeof(BIGNUM));
	CopyBigNum(tempdividend,dividend);
	memset(X,0,sizeof(BIGNUM));
	memset(Z,0,sizeof(BIGNUM));
	
	blen=divisor[0];//被除数的位数
	while((iCmpResult=CompareBigNum(tempdividend,divisor))>0)
	{
		i=tempdividend[0];//被除数动态减小，所以长度必须重新算
		len=i-blen;
		hi=tempdividend[i];
		
		w=divisor[blen];
		if(hi>w)//说明divisor[i]<0xFFFFFFFF
		{
			//q=hi/(w+1);
			//r=hi%(w+1);

			lo=hi;
			hi=0;
			DIVMOD_WORD(hi,lo,w,q,r);
			
		}
		else if(i>blen)
		{
			len-=1;//被除数第一位等于小于除数的第一位，必须退位
			//************************************************
			if(w==0xffffffff||(w+1==0xffffffff))
			{

				q=hi;

			}
			else
			{
				num=hi;
				lo=tempdividend[i-1];
				num=(num<<32)+tempdividend[i-1];
				q=(unsigned __int32)(num/(w+1));
			}
			/*num=tempdividend[i];
			num=(num<<32)+tempdividend[i-1];
			if(divisor[blen]==0xffffffff)
				div=(unsigned __int32)(num>>32);
			else 
				div=num/(divisor[blen]+1);*/
			/***********************************************/
			//hi=tempdividend[i];
			//lo=tempdividend[i-1];
			//w=divisor[blen]+1;
			//DIVMOD_WORD(hi,lo,w,q,r);
			//div=q;


			//例如十进制的98/9 =>div=10
		}
		else
		{
			//bignum_add(X,ONEVALUE,temp);
			//CopyBigNum(X,temp);
			bignum_Increment(X);//X=X+1
			bignum_substract(tempdividend,divisor,temp);
			CopyBigNum(tempdividend,temp);//tempdividend=tempdividend-divisor
			break;
		}
		//div必定小于等于0xffffffff
		memset(Z,0,sizeof(BIGNUM));
		Z[0]=1+len;
		Z[1+len]=q;
		
		//移位Z=Z*0x1,0000,0000^len
		/******************************************************************
		CopyBigNum2(Z,div);
		for(k=Z[0];k>=1 && len>1;--k)
		{
			Z[k+len]=Z[k];//每个数向右移len位(低位在前，高位在后)
		}
		for(k=1;k<=len;k++)
		{
			Z[k]=0;
		}
		Z[0]+=i-1;
		**********************************************************************/

		/**********************************************************************
		CopyBigNum2(Z,div);
		Z[0]+=len;
		for(k=Z[0];k>len;k--)
			Z[k]=Z[k-len];
		for(k=1;k<=len;k++)
			Z[k]=0;
		****************************************/
		bignum_add(X,Z,temp);
		CopyBigNum(X,temp);//X=X+Z;
		
		bignum_mul(Z,divisor,temp);
		CopyBigNum(Z,temp);//Z=divisor*Z;
		
		bignum_substract(tempdividend,Z,temp);
		CopyBigNum(tempdividend,temp);//tempdividend=tempdividend-divisor*Z
	}
	
	
	CopyBigNum(remainder,tempdividend);

	if(iCmpResult==0)                     //能整除相等,余数和除数相等
	{
		memset(remainder,0,sizeof(BIGNUM));//余数为0
		
		X[1]++;       //商加1
	}
	
	for(i=dividend[0];i>=1;--i)
	{
		if(X[i]!=0)
		{
			X[0]=i;
			break;
		}
	}
	CopyBigNum(quotient,X);
}
//试商法
//A=A-X*B
void bignum_div_long(BIGNUM dividend,unsigned __int32 divisor,BIGNUM quotient,BIGNUM remainder)
{
	unsigned __int32 i,blen,k,len;
	int iCmpResult=0;
	unsigned __int64 num;
	unsigned __int64 div;
	//unsigned __int32 high,low,q,r;
	BIGNUM tempdividend,X,Z,temp;

	//memset(tempdividend,0,sizeof(BIGNUM));
	CopyBigNum(tempdividend,dividend);
	memset(X,0,sizeof(BIGNUM));
	memset(Z,0,sizeof(BIGNUM));
	
	blen=1;//除数的位数
	while((iCmpResult=CompareBigNum2(tempdividend,divisor))>0)
	{
		i=tempdividend[0];//被除数动态减小，所以长度必须重新算
		len=i-blen;
		if(tempdividend[i]>divisor)//说明divisor[j]<0xFFFFFFFF
		{
			div=tempdividend[i]/(divisor+1);
		}
		else if(i>blen)
		{
			len-=1;//被除数第一位等于小于除数的第一位，必须退位
			num=tempdividend[i];
			num=(num<<32)+tempdividend[i-1];

			//high=tempdividend[i];
			//low=tempdividend[i-1];

			if(divisor==0xffffffff)
				div=(unsigned __int32)(num>>32);
			else 
				div=num/divisor;

			//例如十进制的98/9 =>div=10
		}
		else
		{
			//bignum_add(X,ONEVALUE,temp);
			//CopyBigNum(X,temp);
			bignum_Increment(X);//X=X+1
			break;
		}
		

		CopyBigNum2(Z,div);
		//移位Z=Z*0x1,0000,0000^len
		/******************************************************************
		for(k=Z[0];k>=1 && len>1;--k)
		{
			Z[k+len]=Z[k];//每个数向右移len位(低位在前，高位在后)
		}
		for(k=1;k<=len;k++)
		{
			Z[k]=0;
		}
		Z[0]+=i-1;
		**********************************************************************/

		//**********************************************************************
		Z[0]+=len;
		for(k=Z[0];k>len;k--)
			Z[k]=Z[k-len];
		for(k=1;k<=len;k++)
			Z[k]=0;
		//****************************************/
		bignum_add(X,Z,temp);
		CopyBigNum(X,temp);//X=X+Z;
		
		bignum_mul_long(Z,divisor,temp);
		CopyBigNum(Z,temp);//Z=divisor*Z;
		
		bignum_substract(tempdividend,Z,temp);
		CopyBigNum(tempdividend,temp);//tempdividend=tempdividend-divisor*Z
	}
	

	if(iCmpResult==0)                     //能整除相等,余数和除数相等
	{
		memset(remainder,0,sizeof(BIGNUM));//余数为0
		X[1]++;       //商加1
	}
	for(i=dividend[0];i>=1;--i)
	{
		if(X[i]!=0)
		{
			X[0]=i;
			break;
		}
	}
	CopyBigNum(quotient,X);
	CopyBigNum(remainder,tempdividend);
}
//试商法
//A=A-X*B
void bignum_mod(BIGNUM dividend,BIGNUM divisor,BIGNUM remainder)
{
	unsigned __int32 alen,blen,len;
	int iCmpResult=0;
	unsigned __int64 num;
	unsigned __int32 div;
	unsigned __int32 hi,lo,w,q,r;
	BIGNUM tempdividend,Z,temp;

	if(CompareBigNum(dividend,divisor)<0)
	{
		CopyBigNum(remainder,dividend);
		return;
	}
	//memset(tempdividend,0,sizeof(BIGNUM));
	CopyBigNum(tempdividend,dividend);
	memset(Z,0,sizeof(BIGNUM));
	
	blen=divisor[0];//被除数的位数
	while((iCmpResult=CompareBigNum(tempdividend,divisor))>0)
	{
		alen=tempdividend[0];//被除数动态减小，所以长度必须重新算
		len=alen-blen;
		hi=tempdividend[alen];
		w=divisor[blen];
		if(hi>w)//说明divisor[j]<0xFFFFFFFF
		{
			div=hi/(w+1);
		}
		else if(alen>blen)
		{
			len-=1;//被除数第一位等于小于除数的第一位，必须退位
			
			//************************************************
			if(w==0xffffffff||(w+1==0xffffffff))
			{
				div=hi;
			}
			else
			{
				num=hi;
				num=(num<<32)+tempdividend[alen-1];
				div=(unsigned __int32)(num/(w+1));
			}
			/*num=tempdividend[i];
			num=(num<<32)+tempdividend[i-1];
			if(divisor[blen]==0xffffffff)
				div=(unsigned __int32)(num>>32);
			else 
				div=num/(divisor[blen]+1);*/
			/***********************************************/
			//hi=tempdividend[i];
			//lo=tempdividend[i-1];
			//w=divisor[blen]+1;
			//DIVMOD_WORD(hi,lo,w,q,r);
			//div=q;


			//例如十进制的98/9 =>div=10
		}
		else
		{
			//bignum_add(X,ONEVALUE,temp);
			//CopyBigNum(X,temp);
			bignum_substract(tempdividend,divisor,temp);
			CopyBigNum(tempdividend,temp);//tempdividend=tempdividend-divisor
			break;
		}
		//div必定小于等于0xffffffff
		memset(Z,0,sizeof(BIGNUM));
		Z[0]=1+len;
		Z[1+len]=div;
		
		//移位Z=Z*0x1,0000,0000^len
		/******************************************************************
		CopyBigNum2(Z,div);
		for(k=Z[0];k>=1 && len>1;--k)
		{
			Z[k+len]=Z[k];//每个数向右移len位(低位在前，高位在后)
		}
		for(k=1;k<=len;k++)