main.cpp

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

    int i = 1;
	int alen=a[0];
	if(alen==0)
		return;
    while (i < alen && a[i] == 0)
		a[i++] = BIGNUM_INT_MASK;
    a[i]--;
	if(a[alen]==0)
		a[0]=alen-1;
}
/*-----------------------------------------------------------------------------
///////////////////////////////////////////////////////////////////////////////
//功能：实现2^32进制大数减法
//入口参数： a>=b
//         a----------被减数
//         b----------减数
//         c----------结果
//返回值：void
///////////////////////////////////////////////////////////////////////////////
-----------------------------------------------------------------------------*/
void bignum_substract(BIGNUM a, BIGNUM b, BIGNUM c)
{
	int alen = a[0], blen = b[0];
	
    int mlen = (alen > blen ? alen : blen);
    int i;
	unsigned __int32 carry;//借位标志
	

	unsigned __int64 minuend;//被减数
	unsigned __int64 subtrahend,difference;//减数和差

	memset(c,0,sizeof(BIGNUM));
	carry=0;
	//a<b,直接返回
	if(CompareBigNum(a,b)<0)
	{
		abort();
		return;
	}
	for(i=1;i<=mlen;i++)
	{
		if(i>blen)//长度对齐
			subtrahend=0;
		else
			subtrahend=b[i];
		
		subtrahend+=carry;//上一位的借位

		minuend=a[i];


		if(minuend<subtrahend)
		{
			carry=1;
			minuend+=0x100000000;
		}
		else
		{
			carry=0;
		}

		//minuend=minuend+0x100000000*carry;
		difference=minuend-subtrahend;
		c[i]=(unsigned __int32)difference;
	}
	for(i=mlen;i>=1;--i)
	{
		if(c[i]!=0)
		{
			c[0]=i;
			return;
		}
	}
		c[0]=0;

}
void bignum_substract_long(BIGNUM a, unsigned __int32 b, BIGNUM c)
{
	int alen = a[0];
    int i;

	unsigned __int32 carry;//借位标志
	unsigned __int64 minuend;//被减数
	unsigned __int64 subtrahend,difference;//减数和差

	carry=0;
	memset(c,0,sizeof(BIGNUM));

	for(i=1;i<=alen;i++)
	{
		if(i>1)//长度对齐
			subtrahend=0;
		else
			subtrahend=b;
		//构造减数，对应位数加上 上一位的借位
		subtrahend+=carry;//上一位的借位

		//构造被减数
		minuend=a[i];

		if(minuend<subtrahend)
		{
			carry=1;
			minuend=minuend+0x100000000;
		}
		else
			carry=0;

		//minuend=minuend+0x100000000*carry;
		
		difference=minuend-subtrahend;
		c[i]=(unsigned __int32)difference;
	}
	//计算剩余的位数
	for(i=alen;i>=1;--i)
	{
		if(c[i]!=0)
		{
			c[0]=i;
			return;
		}
	}
		c[0]=0;

}

/******************************************************************************/
/*                                                                            */
/*  Function:  Multiplication kernel function                                 */
/*             w/o overflow detection, w/o checking for leading zeros         */
/*             accumulator mode not supported                                 */
/*  Syntax:    void mult (BIGNUM aa_l, BIGNUM bb_l, BIGNUM p_l);                 */
/*  Input:     aa_l, bb_l (Factors)                                           */
/*  Output:    p_l (Product)                                                  */
/*  Returns:   -                                                              */
/*                                                                            */
/******************************************************************************/
void bignum_mul (BIGNUM A, BIGNUM B, BIGNUM c) /* Allow for double length result    */
{
	int alen = A[0], blen = B[0];

	unsigned __int64 product;

	unsigned __int32 carry=0;
	int i,j,k;
	
	//BIGNUM A;//被乘数
	//BIGNUM B;//乘数

	
	//CopyBigNum(A,a);
	//CopyBigNum(B,b);

	memset(c,0,sizeof(BIGNUM));
	if(A[0]==0||B[0]==0)
		return;
	/*else if((a[0]==1) && (a[1]==1))
	{
		CopyBigNum(c,b);
		return;
	}
	else if((b[0]==1)&&(b[1]==1))
	{
		CopyBigNum(c,a);
		return;
	}*/
	for(i=1;i<=alen;i++)
	{
		carry=0;
		for(j=1;j<=blen;j++)
		{
			k=i+j-1;

			product=A[i];
			product*=(unsigned __int64)B[j];
			product=product+c[k]+carry;
			//product=(unsigned __int64)c[k]+(unsigned __int64)A[i]*B[j]+carry;
			
			/*if(product>>32)
			{
				carry=(unsigned __int32)(product>>32);
			}
			else
				carry=0;
			*/
			carry=(unsigned __int32)(product>>32);

			c[k]=(unsigned __int32)product;

		}
		/***********************************************************
		if(carry)
		{
			c[k+1]=carry;
		}
		**********************************************************************/
		c[k+1]=carry;
	}
	if(carry>0)
	{
		c[0]=alen+blen;
	}
	else
		c[0]=alen+blen-1;
}


void bignum_mul_long (BIGNUM a, unsigned __int32 b, BIGNUM c) /* Allow for double length result    */
{
	int alen = a[0];

	unsigned __int64 temp;

	unsigned __int32 carry=0;//进位标志
	int i(0);

	memset(c,0,sizeof(BIGNUM));
	
	if(a[0]==0||b==0)
		return;


	for(i=1;i<=alen;i++)
	{
		temp=(unsigned __int64)c[i]+(unsigned __int64)a[i]*b+carry;
		carry=(unsigned __int32)(temp>>32);
		c[i]=(unsigned __int32)temp;
	}
	c[i]=carry;

	if(carry)
	{
		c[0]=i;
	}
	else
		c[0]=alen;

}



/*-----------------------------------------------------------------------------
///////////////////////////////////////////////////////////////////////////////
//功能：实现10进制大数除法(变为减法)division
//入口参数： 
//         dividend----------被除数(dividend)
//         B----------除数(divisor )
//         result-----商(quotient)
//         remainder-余数
//返回值：void(BIGNUM a, BIGNUM b, BIGNUM c)
///////////////////////////////////////////////////////////////////////////////
-----------------------------------------------------------------------------*/
void bigdiv(BIGNUM dividend,BIGNUM divisor,BIGNUM result,BIGNUM remainder)
{
	BIGNUM TempDivisor,buf2;
	int iCmpResult=0;

	memset(TempDivisor,0,sizeof(BIGNUM));
	memset(buf2,0,sizeof(BIGNUM));
	memset(result,0,sizeof(BIGNUM));
	memset(remainder,0,sizeof(BIGNUM));
	
	CopyBigNum(remainder,dividend);//将被除数dividend拷贝到余数remainder中

	int iDividendLength;//被除数的有效长度
	int jDivisorLength;//除数的有效长度
	int i,j,k;
	int iDifference;
	int iBit;//被除数第一位小于除数的第一位，必须退位

	jDivisorLength=divisor[0];//除数的有效长度
	//j=DATALENGTH-jDivisorLength;//除数的前缀零的个数
	while((iCmpResult=CompareBigNum(remainder,divisor))>0)//被除数大于除数的时候，一直循环
	{
		iDividendLength=remainder[0];//被除数的有效长度(因为是动态的)
		j=jDivisorLength;//除数最高位

		iDifference=iDividendLength-jDivisorLength;//被除数的长度与除数的长度的差（该值最小为0）
		
		if(iDifference>0)//除法变为减法，构造减数
		{
			i=iDividendLength;//被除数的最高位
			iBit=0;
			for(k=j;k>=1;--k)
			{

				if(remainder[i]>divisor[j])//从被除数和除数的最高位开始依次比较对应位的大小，判断是否够减
				{
					break;
				}
				if(remainder[i]<divisor[j])
				{
					iBit=1;		//如果不够减，那么被除数就退一位，再做减法
					break;
				}
				--i;
				--j;
			}
			iDifference-=iBit;
			memset(TempDivisor,0,sizeof(BIGNUM));
			/************************************************
			for(i=iDifference;i<DATALENGTH;i++)
			{
				//TempDivisor中存放的是divisor左移若干位之后得到的值
				//1：如果够减,则除数左移后最高位与被除数的最高位对齐,
				//2：否则与被除数的次高位对齐
				TempDivisor[i-iDifference]=divisor[i];//除法为减法，
			}
			**********************************************/
			for(i=divisor[0];i>=1;--i)
			{
				//TempDivisor中存放的是divisor左移若干位之后得到的值
				//1：如果够减,则除数左移后最高位与被除数的最高位对齐,
				//2：否则与被除数的次高位对齐
				TempDivisor[i+iDifference]=divisor[i];//除法为减法，
			}
			TempDivisor[0]=iDifference+divisor[0];
		}
		else
			CopyBigNum(TempDivisor,divisor);

		result[iDifference+1]++;
		bignum_substract(remainder,TempDivisor,buf2);
		CopyBigNum(remainder,buf2);

	}
	if(iCmpResult==0)                     //两个数相等
	{
		memset(remainder,0,sizeof(BIGNUM));//余数为0
		result[1]++;       //商加1
	}
	for(i=dividend[0];i>=1;--i)
	{
		if(result[i]!=0)
		{
			result[0]=i;
			return;
		}
	}
		result[0]=0;
}
static void internal_add_shifted(unsigned __int32 *number,
				 unsigned n, int shift)
{
    int word = 1 + (shift / BIGNUM_INT_BITS);
    int bshift = shift % BIGNUM_INT_BITS;
    unsigned __int64 addend;

    addend = (unsigned __int64)n << bshift;

    while (addend) {
	addend += number[word];
	number[word] = (unsigned __int32) addend & BIGNUM_INT_MASK;
	addend >>= BIGNUM_INT_BITS;
	word++;
    }
}

static void internal_mod(unsigned __int32 *a, int alen,unsigned __int32 *m, int mlen,unsigned __int32 * quot, int qshift)
{
    unsigned __int32 m0, m1;
    unsigned int h;
    int i, k;

    m0 = m[0];
    if (mlen > 1)
		m1 = m[1];
    else
		m1 = 0;

	/*if(a[0]==0)
		i=1;
	else
		i=0;*/

    for (!a[0] ? i=1:i=0; i <= alen - mlen; i++) 
	{
		unsigned __int64 t;
		unsigned int q, r, c, ai1;


		if (i == 0) 
		{
			h = 0;
		} 
		else 
		{
			h = a[i - 1];
			a[i - 1] = 0;
		}

		if (i == alen - 1)
			ai1 = 0;
		else
			ai1 = a[i + 1];
		
		/* Find q = h:a[i] / m0 */
		if (h >= m0) 
		{
			/*
			 * Special case.
			 * 
			 * To illustrate it, suppose a BignumInt is 8 bits, and
			 * we are dividing (say) A1:23:45:67 by A1:B2:C3. Then
			 * our initial division will be 0xA123 / 0xA1, which
			 * will give a quotient of 0x100 and a divide overflow.
			 * However, the invariants in this division algorithm
			 * are not violated, since the full number A1:23:... is
			 * _less_ than the quotient prefix A1:B2:... and so the
			 * following correction loop would have sorted it out.
			 * 
			 * In this situation we set q to be the largest
			 * quotient we _can_ stomach (0xFF, of course).
			 */
				q = BIGNUM_INT_MASK;//#define BIGNUM_INT_MASK  0xFFFFFFFFUL
		} 
		else 
		{
	    /* Macro doesn't want an array subscript expression passed
	     * into it (see definition), so use a temporary. */
			unsigned __int32 tmplo = a[i];
			DIVMOD_WORD(h, tmplo, m0,q, r);
			if(!q)
				continue;
			/* Refine our estimate of q by looking at
			 h:a[i]:a[i+1] / m0:m1 */
			//t = MUL_WORD(m1, q);
			t=(unsigned __int64)m1*q;
			if (t > ((unsigned __int64) r << BIGNUM_INT_BITS) + ai1) 
			{
				q--;
				t -= m1;
				r = (r + m0) & BIGNUM_INT_MASK;     /* overflow? */
				if (r >= (unsigned __int64) m0 && t > ((unsigned __int64) r << BIGNUM_INT_BITS) + ai1) 
					q--;
			}
		}

		/* Subtract q * m from a[i...] */
		c = 0;
		for (k = mlen - 1; k >= 0; k--) {
			t = MUL_WORD(q, m[k]);
			t += c;
			c = (unsigned)(t >> BIGNUM_INT_BITS);
			if ((unsigned __int32) t > a[i + k])
			c++;
			a[i + k] -= (unsigned __int32) t;
		}

		/* Add back m in case of borrow */
		if (c != h) 
		{
			t = 0;
			for (k = mlen - 1; k >= 0; k--) 
			{
				t += m[k];
				t += a[i + k];
				a[i + k] = (unsigned __int32) t;
				t = t >> BIGNUM_INT_BITS;
			}
			q--;
		}
		if (quot)
			internal_add_shifted(quot, q, qshift + BIGNUM_INT_BITS * (alen - mlen - i));
    }
}

static void bignum_divmodbak(BIGNUM dividend, BIGNUM mod, BIGNUM quotient,BIGNUM result)
{
    int mshift;
    int alen, mlen, i, j;
	

	memset(quotient,0,sizeof(BIGNUM));
	memset(result,0,sizeof(BIGNUM));
	/* 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;