main.cpp

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

		{
			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_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
	}
}
/*
 * Compute the residue of a bignum, modulo a (max 16-bit) short.
 */
unsigned short bignum_mod_short(BIGNUM number, unsigned short modulus)
{
    unsigned __int64 mod, r;
    int i;

    r = 0;
    mod = modulus;
    for (i = number[0]; i > 0; i--)
		r = (r * (BIGNUM_TOP_BIT % mod) * 2 + number[i] % mod) % mod;
    return (unsigned short) r;
}
//蒙哥马利模乘乘模运算C=A*B*r^(-k) % N
//k为N在r进制下的位数
//于是我们可以得出r为任何值的蒙哥马利算法：
/*
N[0]*N[0]' %r =1，q=(C'[0]+A*B[0])*(r-N[0]') %r
r=2^32
m=r-N[0]'
C'=0
FOR i FROM 0 TO k
q=(C'[0]+A*B[0])*m %r
C'=(C'+A*B+q*N)/r
IF C'>=N C'=C'-N
RETURN C'*/

//r=2^32进制
void Montgomery_r(BIGNUM A,BIGNUM B,BIGNUM N,BIGNUM remainder)
{
	unsigned i=0,j=0;
	BIGNUM product,temp;
	//BIGNUM A;//被乘数
	//BIGNUM B;//乘数
	BIGNUM C;//每次模余的和
	unsigned __int32 B0;
	unsigned __int32 C0;
	
	unsigned __int32 q;
	unsigned __int32 m;
	
	unsigned int iDataLength;
	unsigned __int64 b1;
	

	//CopyBigNum(A,A1);
	//CopyBigNum(B,B1);
	memset(C,0,sizeof(BIGNUM));//C'=0


	//*************************************************************************
	//求N_0;符合N[0]*N[0]' %r =1;
	//N0=n%2^32=N[1],r=2^32;N0x-ry=1=>ax-(2^32)*y=1
	unsigned __int64 r;
	unsigned __int32 N0,N_0;//N0=n%(2^32);
	unsigned __int32 x,y;
	N0=N[1];
	r=0x100000000;//b=2^32
	GetEuclidEquation2(N0,r,N_0,y);//N[0]*N[0]' %r =1
	//N_0=x;
	/************************************************************************/
	//N_0=N_;
	B0=B[1];//B0=B%(2^32+1)
	m=0xFFFFFFFF-N_0+1;//2^32-N_0;

	iDataLength=N[0];//N的r进制的位数
	for(i=1;i<=iDataLength;i++)
	{
		C0=C[1];//C0=C%(2^32+1);
		//q=(C'[0]+A[i]*B[0])*m %r
		
		b1=(i<=A[0] ? A[i]*B0:0);//保证A的长度和N对齐
		if((b1>>32)>=1)
			b1=(unsigned __int32)b1;//b1=A[i]*B[0] %r
		b1=C0+b1;
		if((b1>>32)>=1)
			b1=(unsigned __int32)b1;//b1=(C'[0]+A[i]*B[0]) %r
		b1=b1*m;
		if((b1>>32)>=1)
			b1=(unsigned __int32)b1;//(C'[0]+A[i]*B[0])*m %r
		q=(unsigned __int32)b1;

		//C'=(C'+A[i]*B+q*N)/r
		bignum_mul_long(B,A[i],product);//A[i]*B
		bignum_add(C,product,temp);//C=C+A[i]*B
		CopyBigNum(C,temp);

		bignum_mul_long(N,q,product);//q*N
		bignum_add(C,product,temp);//C=(C'+A[i]*B+q*N)
		CopyBigNum(C,temp);

		for(j=2;j<=C[0];++j)//C=C/r
		{
			C[j-1]=C[j];
		}
		C[C[0]]=0;
		C[0]--;
		
	}

	if(CompareBigNum(C,N)>=0)//IF C'>=N C'=C'-N
	{
			bignum_substract(C,N,remainder);
			return;
			//CopyBigNum(C,temp);
	}
	CopyBigNum(remainder,C);


}
//二进制
//A*B*2^(-k) mod m --->k为m的比特位数
void Montgomery_2(BIGNUM A,BIGNUM B,BIGNUM m,BIGNUM remainder)
{
	unsigned i=0;
	BIGNUM product,temp;
	//BIGNUM A;//被乘数
	//BIGNUM B;//乘数
	BIGNUM C;//每次模余的和

	//CopyBigNum(A,multiplicand);
	//CopyBigNum(B,multiplicator);
	memset(C,0,sizeof(BIGNUM));//C'=0
	unsigned int iBitCount=GetBigNumBitCount(m);//
	unsigned int iCarry=0;//是否能整除
	for(i=0;i<iBitCount;i++)
	{
		//bignum_mul_long(multiplicator,multiplicand[i],product);//A[i]*B+C
		if(bignum_get_bit(A,i))//A[i]=1;
		{
			CopyBigNum(product,B);
			bignum_add(C,product,temp);
			CopyBigNum(C,temp);
		}
		if(bignum_get_bit(C,0))//C为奇数
		{
			iCarry=1;
			bignum_add(C,m,temp);
			CopyBigNum(C,temp);
		}
		//if(i==iBitCount-1)
		//	break;
		bignum_rightshift2(C,1,temp);//C=C/2
		CopyBigNum(C,temp);
	}
	if(CompareBigNum(C,m)>=0)//IF C'>=N C'=C'-N
	{
			bignum_substract(C,m,temp);
			CopyBigNum(C,temp);
	}
	CopyBigNum(remainder,C);
}
//选择与模数n互素的基数R=2^k，n满足2k－1≤n<2k， n应为奇数。
//并且选择R'及n’，满足0< R'<n, 0< n’<n,使得 RR'-nn’＝1。
//对于0≤m<Rn的任意整数,Montgomery给出求模乘法mR^(-1) mod n 的快速算法M(m):
/*
M(m)
{
k = ( m * n’ ) mod R;
x = (m + k*n ) / R;
    if (x>=n) x -= n;
      return x;
}
*/
void Montgomery4(BIGNUM m,BIGNUM R,BIGNUM n_,BIGNUM n,BIGNUM remainder)
{
	BIGNUM product,k,temp,quotient;
	/*if(CompareBigNum(m,n)>0)
	{
		bignum_mod(m,n,temp);
		CopyBigNum(m,temp);
	}*/
	bignum_mul(m,n_,product);//m*n'
	bignum_mod(product,R,k);//k=(m*n')%R

	bignum_mul(k,n,product);//(k*n)
	bignum_add(m,product,temp);//m+(k*n)
	bignum_div(temp,R,quotient,remainder);
	CopyBigNum(remainder,quotient);
	if(CompareBigNum(remainder,n)>=0)
	{
		bignum_substract(remainder,n,temp);
		CopyBigNum(remainder,temp);
		return;
	}
	
}
//乘模运算C=A*B % N
//A*B=A*(Sum[i=0 to n](B[i]*0x100000000^i))
//A*B % N = (Sum[i=0 to n]((A*B[i])*0x100000000^i)) % N
//void mulmode(BIGNUM A,BIGNUM B,BIGNUM divisor,BIGNUM remainder)
void mulmode(BIGNUM multiplicand,BIGNUM multiplicator,BIGNUM divisor,BIGNUM remainder)
{
	unsigned i=0,j=0;
	BIGNUM product,quotient,temp,tempRemainder;
	BIGNUM A;//被乘数
	BIGNUM B;//乘数
	BIGNUM C;//每次模余的和

	memset(C,0,sizeof(BIGNUM));
	
	CopyBigNum(A,multiplicand);
	CopyBigNum(B,multiplicator);
	for(i=1;i<=B[0];i++)
	{
		//C=C+A*B[i]*0x100000000^(i-1)%N
		bignum_mul_long(A,B[i],product);
		//k=product[0];

		
		for(j=product[0];j>=1 && i>1;--j)
		{
			product[j+i-1]=product[j];//每个数向右移n-1位(低位在前，高位在后)
		}
		for(j=1;j<i-1 ;j++)
		{
			product[j]=0;
		}
		product[0]+=i-1;

		bignum_div(product,divisor,quotient,tempRemainder);
		bignum_add(C,tempRemainder,temp);
		
		if(CompareBigNum(temp,divisor)>=0)
		{
			bignum_div(temp,divisor,quotient,tempRemainder);
			CopyBigNum(C,tempRemainder);
		}
		else
			CopyBigNum(C,temp);
		
	}
	CopyBigNum(remainder,C);
	//bignum_div(C,divisor,quotient,tempRemainder);
	//CopyBigNum(remainder,tempRemainder);//余数

}




//幂模运算D=C^E % N
/*************************************************************************
void powermode(BIGNUM base,BIGNUM power,BIGNUM divisor,BIGNUM remainder)
{
	int i;
	int iBitCount=0;

	char *pszBinary;
	
	if(base[0]==0)
	{
		remainder[0]=0;
		return;
	}
	iBitCount=GetBigNumBitCount(power);
	pszBinary=new char[iBitCount+1];
	
	if(pszBinary==NULL)
	{
		remainder[0]=0;
		return;
	}
	BigNumToBinary(power,pszBinary,iBitCount+1);//把幂(指数)转为二进制
	//printf("二进制=%s\n",pszBinary);
	BIGNUM product,temp,quotient;
	memset(product,0,sizeof(BIGNUM));
	//D=1
	product[0]=1;
	product[1]=1;

	for(i=0;i<iBitCount;i++)
	{
		//D=D*D % N
		if(i>0)
		{
			bignum_mul(product,product,temp);
			CopyBigNum(product,temp);
			//bignum_div(product,divisor,quotient,remainder);
			bignum_mod(product,divisor,remainder);

			CopyBigNum(product,remainder);
			
			//mulmode(product,product,divisor,remainder);
			//CopyBigNum(product,remainder);
		}
					
		if(pszBinary[i]=='1')
		{

			//D=D*C % N
			bignum_mul(product,base,temp);
			CopyBigNum(product,temp);
			//bignum_div(product,divisor,quotient,remainder);
			bignum_mod(product,divisor,remainder);
			//mulmode(product,base,divisor,remainder);

			CopyBigNum(product,remainder);
		}
		if(product[0]==0)
			break;
	}
	CopyBigNum(remainder,product);
	delete[] pszBinary;
}
******************************************************************************/
void powermode(BIGNUM base,BIGNUM power,BIGNUM divisor,BIGNUM remainder)
{
	int i;
	int iBitCount=0;
	unsigned char byte;
	if(base[0]==0)
	{
		remainder[0]=0;
		return;
	}
	iBitCount=GetBigNumBitCount(power);

	BIGNUM product,temp,quotient;
	memset(product,0,sizeof(BIGNUM));
	//D=1
	product[0]=1;
	product[1]=1;

	for(i=iBitCount-1;i>=0;i--)
	{

			byte=(unsigned char)(power[i/32+1]>>(i%32))&0x1;
			//if(CompareBigNum(product,ONEVALUE)>0)
			if(product[1]>1)
			{
				bignum_mul(product,product,temp);
				CopyBigNum(product,temp);

				//bignum_mod(product,divisor,remainder);
				bignum_divmod(product,divisor,NULL,remainder);
				CopyBigNum(product,remainder);
			}
			if(byte==1) 
			{

				//D=D*C % N
				//if(CompareBigNum(product,ONEVALUE)==0)
				if(product[0]==1 &&(product[1]==1))
				{
					CopyBigNum(product,base);//因为base<divisor
					continue;
				}
				else
				{
					bignum_mul(product,base,temp);
					CopyBigNum(product,temp);
					//bignum_mod(product,divisor,remainder);
					bignum_divmod(product,divisor,NULL,remainder);
					CopyBigNum(product,remainder);
				}
			}
			if(product[0]==0)
			{
				//CopyBigNum(remainder,product);
				return;
			}

			
	}
	return;
	//CopyBigNum(remainder,product);
	
}

/******************************************************************************/
/*                                                                            */
/*  函数:  实现2^32进制大数的幂模(调用2^32进制的蒙哥马利算法)                 */
/*  语法:  powermode_r(BIGNUM base,BIGNUM power,BIGNUM N,BIGNUM remainder)    */
/*  输入:                                                                     */
/*         base：2^32进制大数                                                 */
/*         power: 2^32进制大数                                                */
/*         N: 2^32进制大数                                                    */
/*         remainder: 2^32进制大数                                            */
/*  输出:                                                                     */
/*         remainder：                                                        */
/*  返回:  void                                                               */
/*  算法：                                                                    */
/*                                                                            */
/*		设R=(2^32)**k %N，R'=(2^32)**(-k) %N，E=Sum[i=0 to n](E*2**i)：       */
/*		A'=A*R %N                                                             */
/*		X=A'                                                                  */
/*		FOR i FROM n-1 TO 0                                                   */
/*			X=X*X*R' %N                                                       */
/*			IF E=1 X=X*A'*R' %N                                               */
/*		X=X*1*R' %N                                                           */
/*		RETURN X                                                              */
/******************************************************************************/
//r=2^32进制
void powermode_r(BIGNUM base,BIGNUM power,BIGNUM N,BIGNUM remainder)
{
	int i;
	int iBitCount=0;
	unsigned char byte;
	BIGNUM R,r,R2;
	BIGNUM A,X,temp,temp2,temp3;
	iBitCount=GetBigNumBitCount(power);
	if(base[0]==0)
	{
		remainder[0]=0;
		return;
	}
	memset(R,0,sizeof(BIGNUM));
	memset(R2,0,sizeof(BIGNUM));
	if(base[0]==1)
	{
		R[0]=1;
		R[1]=1;
		R2[0]=1;
		R2[1]=1;
	}
	else
	{
		R[0]=base[0]+1;
		R[R[0]]=1;//R=(2^32)^(base[0]+1)

		//unsigned long t1=0;
		//unsigned long t2=0;
		//t1= GetTickCount();
		//*********************************************************************
		//求R2=R*R的方法1
		bignum_substract(R,N,r);
		bignum_mul(r,r,R2);
		//unsigned long t3=0;
		//unsigned long t4=0;
		//***************************************
		//计算模除的方法1
		//t3= GetTickCount();
		bignum_mod(R2,N,X);
		//t4= GetTickCount();
		//t4-=t3;
		//printf("==========1)计算模除R2/N耗时%lu\n\n",t4);
		//***************************************
		//计算模除的方法2（改进后的模除算法）
		//t3= GetTickCount();
		//bignum_divmod(R2,N,NULL,temp);
		//t4= GetTickCount();
		//t4-=t3;
		//printf("==========2)计算模除R2/N耗时%lu\n\n",t4);


		CopyBigNum(R2,X);	
		//t2= GetTickCount();
		//t2-=t1;
		//printf("＝＝(方法1)计算R2耗时%lu\n",t2);
		//*********************************************************************
		//求R2=R*R的方法2
		/*t1= GetTickCount();
		R2[0]=2*R[0]-1;
		R2[R2[0]]=1;//R2=R*R
		bignum_mod(R2,N,X);
		CopyBigNum(R2,X);	
		t2= GetTickCount();
		t2-=t1;
		printf("＝＝(方法2)计算R2耗时%lu\n",t2);
		***************************************************/
	}

	Montgomery_r(base,R2,N,A);//A=A*R*R%N