bigint.cpp

RSA对称、非对称加密解密算法

//下面让我们来实现大数类的主要成员函数：
/****************************************************************/
//file://大数运算库源文件：BigInt.cpp
//file://作者：[e-mail]
//file://修改: [e-mail](本拉登)
//file://版本：1.0 (2003.4.26) 1.1(2007.3.4)
//file://说明：适用于MFC
//file://需要改进的地方：在转化的过程中效率太低，可以考虑另外的方法
//file://在这个里面bug还有比较多的
//file://在输入输出转化的时候是有很大的问题
//file://在输入输出做了非常大的改动
/*******************测试工作*************************************
在测试的全过程中采用的是著名的数学专用软件Mathematica 5.0
测试第一阶段:小范围，小量测试
	以下为在测试中使用的程序
	数据的生成
		使用的是随机生成函数
		srand((unsigned) time(NULL));
		生成的是100以内(十进制)的数据，进行任意的加减乘除
	数据的检验
		使用Mathematica 5.0
		加法
			Close["D:\\usbkey\\test.txt"]
			Clear[i, result]
			For[i = 1; v = Read["D:\\usbkey\\test.txt", {Number, Number, Number}], 
			  i < 100, i++, result = v[[1]] + v[[2]] - v[[3]]; Print[result]]
		减法
			Close["D:\\usbkey\\test.txt"]
			Clear[i, result]
			For[i = 1; v = Read["D:\\usbkey\\test.txt", {Number, Number, Number}], 
			  i < 100, i++, result = Abs[v[[1]] - v[[2]]] - v[[3]]; Print[result]]
			  注：符号的问题并没有输出，所以测试的时候需要取绝对值，并且在加密中还
			  　　没有碰到有负数的情况
		乘法
			Close["D:\\usbkey\\test.txt"]
			Clear[i, result, v]
			For[i = 1; v = Read["D:\\usbkey\\test.txt", {Number, Number, Number}], 
			  i < 100, i++, result = v[[1]]*v[[2]] - v[[3]]; Print[result]]
		取模
			Close["D:\\usbkey\\test.txt"]
			Clear[i, result, v]
			For[i = 1; v = Read["D:\\usbkey\\test.txt", {Number, Number, Number}], 
			  i < 100, i++, result = Mod[v[[1]], v[[2]]] - v[[3]]; Print[result]]
		除法
			Close["D:\\usbkey\\test.txt"]
			Clear[i, result, v]
			For[i = 1; v = Read["D:\\usbkey\\test.txt", {Number, Number, Number}], 
			  i < 100, i++, result = (v[[1]] - Mod[v[[1]], v[[2]]])/v[[2]] - v[[3]]; 
			  Print[result]]
	  模乘方
			Close["D:\\usbkey\\RSA\\result.txt"]
			Clear[i, result, v]
			For[i = 1; v = Read["D:\\usbkey\\RSA\\result.txt", {Number, Number, Number,Number}], 
			  i < 100, i++, result = PowerMod[v[[1]],v[[2]],v[[3]]] - v[[4]]; Print[result]]

		  Close["D:\\usbkey\\RSA\\tmp.txt"]
			Clear[i, result, v]
			For[i = 1; v = Read["D:\\usbkey\\RSA\\tmp.txt", {Number, Number, Number}], 
			  i < 100, i++, result = PowerMod[v[[1]],v[[2]],v[[3]]]; Print[result]]

/****************************************************************/

#include "StdAfx.h"
#include "BigInt.h"
#include<stdlib.h>
#include<time.h>

CBigInt A64,Buff64,Seed64,M;
string a="6346136223846793005",b="18446744073709551616";

void PrintErr(int Errnum);
void CBigInt::Clear0()
{
	m_nSign=1;
	m_nLength=1;
	for(int i=0;i<BI_MAXLEN;i++)m_ulvalue[i]=0;
}

//file://初始化大数为0
CBigInt::CBigInt()
{
	m_nSign=1;
	m_nLength=1;
	base=100000000;//默认的进制为16进制
	for(int i=0;i<BI_MAXLEN;i++)m_ulvalue[i]=0;
}

//file://初始化大数为0
CBigInt::CBigInt(My_int64 mybase)
{
	m_nSign=1;
	m_nLength=1;
	base=mybase;
	for(int i=0;i<BI_MAXLEN;i++)m_ulvalue[i]=0;
}

//file://采用缺省的解构函数
CBigInt::~CBigInt()
{
}

//file://大数比较，如果大数A位数比大数B多，当然A>B
//file://如果位数相同，则从高位开始比较，直到分出大小
int CBigInt::Cmp(CBigInt& A)
{
	if(m_nLength>A.m_nLength)
		return 1;
	if(m_nLength<A.m_nLength)
		return -1;
	for(int i=m_nLength-1;i>=0;i--)
	{
		if(m_ulvalue[i]>A.m_ulvalue[i])
			return 1;
		if(m_ulvalue[i]<A.m_ulvalue[i])
			return -1;
	}
	return 0;
}
int CBigInt::Cmp(unsigned long A)
{
	if(this->m_nLength>=2)
		return 1;
	else
	{
		if(this->m_ulvalue[0]>A)
			return 1;
		if(this->m_ulvalue[0]<A)
			return -1;
		return 0;
	}
}


//file://照搬参数的各属性
CBigInt& CBigInt::Mov(CBigInt& A)
{
	//符号要不要跟着改，先改着
	m_nSign=A.m_nSign;
	m_nLength=A.m_nLength;
	base=A.base;
	for(int i=0;i<BI_MAXLEN;i++)
		m_ulvalue[i]=A.m_ulvalue[i];
	return *this;
}
/*
CBigInt& CBigInt::Mov(My_int64 A)
{
	
	if(A>=base)
	{
		m_nLength=2;
		m_ulvalue[0]=(unsigned long)A%base;
		m_ulvalue[1]=(unsigned long)A/base;
	}
	else
	{
		m_nLength=1;
		m_ulvalue[0]=(unsigned long)A;
	}
	return *this;
}
*/
CBigInt& CBigInt::Mov(unsigned int A)
{
	this->Clear0();
	this->m_nLength=1;
	this->m_ulvalue[0]=(unsigned long) A;
	return *this;
}

//file://大数相加
//file://调用形式：N.Add(A)，返回值：N+A
//file://若两大数符号相同，其值相加，否则改变参数符号再调用大数相减函数
/******************************************************************
例如：
     A  B  C
+       D  E
--------------
= S  F  G  H

其中 若C+E<=0xffffffff，则H=C+E，carry(进位标志)=0
     若C+E>0xffffffff，则H=C+E-0x100000000，carry=1

     若B+D+carry<=0xfffffff，则G=B+D，carry=0      
     若B+D+carry>0xfffffff，则G=B+D+carry-0x10000000，carry=1

     若carry=0，则F=A，S=0
     若carry=1，A<0xfffffff，则F=A+1，S=0
     若carry=1，A=0xfffffff，则F=0，S=1
/*****************************************************************/
CBigInt CBigInt::Add(CBigInt& A)
{
	CBigInt X(base);
	if(m_nSign==A.m_nSign)
	{
		X.Mov(*this);
		unsigned long carry=0;
		My_int64 sum=0;
		if(X.m_nLength<A.m_nLength)
			X.m_nLength=A.m_nLength;
		for(int i=0;i<X.m_nLength;i++)
		{
			sum=A.m_ulvalue[i];
			sum=sum+X.m_ulvalue[i]+carry;
			X.m_ulvalue[i]=(unsigned long)sum%base;
			carry=(unsigned long)sum/base;
		}
		if(X.m_nLength<BI_MAXLEN)
		{
			X.m_ulvalue[X.m_nLength]=carry;
			X.m_nLength+=carry;
		}
		else
		{
			//错误处理，超出规定位数，重新定义位数
			//string& Err_Exceed_Digit;
			//Err_Exceed_Digit="";
			//Err_Exceed_Digit."Digits execd the largest number ,please redefine the BI_MAXLEN";
			//PrintErr(Err_Exceed_Digit);
			PrintErr(1);
		}
		return X;
	}
	else
	{
		X.Mov(A);
		X.m_nSign=1-X.m_nSign;
		return Sub(X);
	}
}
CBigInt CBigInt::Add(long A)
{
	My_int64 tmp,carry=A;
	for(int i=0;i<m_nLength;i++)
	{
		tmp=m_ulvalue[i]+carry;
		m_ulvalue[i]=(unsigned long)tmp%base;
		carry=tmp/base;
		if(carry==0)
			break;
	}
	if(carry!=0)
	{
		m_ulvalue[m_nLength]=(unsigned long)carry;
		m_nLength++;
	}
	return *this;
}
//file://大数相减
//file://调用形式：N.Sub(A)，返回值：N-A
//file://若两大数符号相同，其值相减，否则改变参数符号再调用大数相加函数
/******************************************************************
例如：
     A  B  C
-       D  E
--------------
=    F  G  H

其中 若C>=E，则H=C-E，carry(借位标志)=0
     若C<E，则H=C-E+0x100000000，carry=1

     若B-carry>=D，则G=B-carry-D，carry=0      
     若B-carry<D，则G=B-carry-D+0x10000000，carry=1

     若carry=0，则F=A
     若carry=1，A>1，则F=A-1
     若carry=1，A=1，则F=0
/*****************************************************************/
CBigInt CBigInt::Sub(CBigInt& A)
{
	CBigInt X(base);
	if(m_nSign==A.m_nSign)
	{
		X.Mov(*this);
		int cmp=X.Cmp(A);
		if(cmp==0){X.Mov(0);return X;}
		int len,carry=0;
		My_int64 num;
		unsigned long *s,*d;
		if(cmp>0)
		{
			s=X.m_ulvalue;
			d=A.m_ulvalue;
			len=X.m_nLength;
		}
		if(cmp<0)
		{
			s=A.m_ulvalue;
			d=X.m_ulvalue;
			len=A.m_nLength;
			X.m_nSign=1-X.m_nSign;
		}
		for(int i=0;i<len;i++)
		{
			if((s[i]-carry)>=d[i])
			{
				X.m_ulvalue[i]=s[i]-carry-d[i];
				carry=0;
			}
			else
			{
				num=base+s[i];
				X.m_ulvalue[i]=(unsigned long)(num-carry-d[i]);
				carry=1;
			}
		}
		while(X.m_ulvalue[len-1]==0)len--;
		X.m_nLength=len;
		return X;
	}
	else
	{
		X.Mov(A);
		X.m_nSign=1-X.m_nSign;
		return Add(X);
	}
}
CBigInt CBigInt::Sub(long A)
{
	My_int64 tmp,carry=A;
	for(int i=0;i<m_nLength;i++)
	{
		tmp=m_ulvalue[i]-carry;
		m_ulvalue[i]=(unsigned long)tmp%base;
		carry=tmp/base;
		if(carry==0)
			break;
	}
	if(carry!=0)
	{
		m_ulvalue[m_nLength]-=(unsigned long)carry;
		if(m_ulvalue[m_nLength]==0)
		{
			m_nLength--;
		}
	}		
	return *this;
}
//file://大数相乘
//file://调用形式：N.Mul(A)，返回值：N*A
/******************************************************************
例如：
        A  B  C
*          D  E
----------------
=    S  F  G  H
+ T  I  J  K
----------------
= U  V  L  M  N

其中，SFGH=ABC*E，TIJK=ABC*D

而对于：
     A  B  C
*          E
-------------
= S  F  G  H    

其中，若C*E<=0xffffffff，则H=C*E，carry(进位标志)=0
     若C*E>0xffffffff，则H=(C*E)&0xffffffff
       carry=(C*E)/0xffffffff
     若B*E+carry<=0xffffffff，则G=B*E+carry，carry=0
     若B*E+carry>0xffffffff，则G=(B*E+carry)&0xffffffff
       carry=(B*E+carry)/0xffffffff
     若A*E+carry<=0xffffffff，则F=A*E+carry，carry=0
     若A*E+carry>0xffffffff，则F=(A*E+carry)&0xffffffff
       carry=(A*E+carry)/0xffffffff
     S=carry
*****************************************************************/
CBigInt CBigInt::Mul(CBigInt& A)
{
	CBigInt X(base),Y(base);
	My_int64 mul;
	int k;
	unsigned long carry;
	for(int i=0;i<A.m_nLength;i++)
	{
		Y.Clear0();
		Y.m_nLength=m_nLength;
		carry=0;
		for(int j=0;j<m_nLength;j++)
		{
			mul=m_ulvalue[j];
			mul=mul*A.m_ulvalue[i]+carry;
			Y.m_ulvalue[j]=mul%base;
			carry=mul/base;
		}
		if(carry&&(Y.m_nLength<BI_MAXLEN))
		{
			Y.m_nLength++;
			Y.m_ulvalue[Y.m_nLength-1]=carry;
		}
		if(Y.m_nLength<BI_MAXLEN-i)
		{
			Y.m_nLength+=i;
			for(k=Y.m_nLength-1;k>=i;k--)
				Y.m_ulvalue[k]=Y.m_ulvalue[k-i];
			for(k=0;k<i;k++)
				Y.m_ulvalue[k]=0;
		}
		//X.Add(Y);
		X.Mov(X.Add(Y));//他这样写有什么用途，为什么要这么写
	}
	if(m_nSign+A.m_nSign==1)
		X.m_nSign=0;
	else
		X.m_nSign=1;
	return X;
}

CBigInt CBigInt::Mul(long A)
{
	My_int64 tmp,carry=0;
	for(int i=0;i<m_nLength;i++)
	{
		tmp=m_ulvalue[i]*A+carry;
		m_ulvalue[i]=tmp%base;
		carry=tmp/base;
	}
	if(carry!=0)
	{
		m_ulvalue[m_nLength]=(unsigned long )carry;
		m_nLength++;
	}
	return *this;
}
//file://大数相除
//file://调用形式：N.Div(A)，返回值：N/A
//file://除法的关键在于“试商”，然后就变成了乘法和减法
//file://这里将被除数与除数的试商转化成了被除数最高位与除数最高位的试商
CBigInt CBigInt::Div(CBigInt& A)
{
	CBigInt X(base),Y(base),Z(base);
	int len;
	My_int64 num,div;
	unsigned long carry=0;
	Y.Mov(*this);
	while(Y.Cmp(A)>0)
	{
		if(Y.m_ulvalue[Y.m_nLength-1]>A.m_ulvalue[A.m_nLength-1])
		{
			len=Y.m_nLength-A.m_nLength;
			div=Y.m_ulvalue[Y.m_nLength-1]/(A.m_ulvalue[A.m_nLength-1]+1);
		}
		else
			if(Y.m_nLength>A.m_nLength)
			{
				len=Y.m_nLength-A.m_nLength-1;
				num=Y.m_ulvalue[Y.m_nLength-1];
				num=num*base+Y.m_ulvalue[Y.m_nLength-2];
				if(A.m_ulvalue[A.m_nLength-1]==(base-1))
					div=num/base;
				else div=num/(A.m_ulvalue[A.m_nLength-1]+1);
			}
			else
			{
				//X.Add(1);
				X.Mov(X.Add(1));
				break;
			}
			Z.Mov(div);
			Z.m_nLength+=len;
			for(int 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));
			//X.Add(Z);
			Z.Mov(Z.Mul(A));
			//Z.Mul(A);
			Y.Mov(Y.Sub(Z));
			//Y.Sub(Z);
	}
	if(Y.Cmp(A)==0)
		X.Mov(X.Add(1));
		//X.Add(1);
	if(m_nSign+A.m_nSign==1)
		X.m_nSign=0;
	else 
		X.m_nSign=1;
	return X;
}
CBigInt CBigInt::Div(long A,long& mod)
{
	unsigned long carry=0;
	int myi;
	My_int64 tmp;
	CBigInt result(this->base);
	result.m_nLength=this->m_nLength;
	for(myi=this->m_nLength-1;myi>=0;myi--)
	{
		tmp=carry*this->base+this->m_ulvalue[myi];
		result.m_ulvalue[myi]=tmp/A;