ecdsa.cpp

椭圆曲线签名算法

				TempNum=TempNum-10;
				rest2=1;
			}
			else
				rest2=0;
			result.AddHead(char(TempNum));
			tempa=tempa->Prev;
		}
		if(rest2)
			result.AddHead(char(rest2));
		if(temp.Head!=NULL)
		{
			temp.End=temp.Head;
			temp.Head=NULL;
		}
		tempb=NULL;
	}
	AdjustBigNum(result);
	if (!flag)
	{
		result.Head->Num=char(int(result.Head->Num)*(-1));
	}
	
	return result;
}
/************************************************************************/
/* 将除法转化为减法来处理,基本思想如下:
						div=0;
						while(a>=0)
						{
							a-=b;
							div++;
						}
						div--;	
这种方式直接处理效率很低,后来改进为得到商的各位数字,将除数扩大处理,
速度提高了很多,现在可以对整数的整除均可以进行
																		*/
/************************************************************************/
BigInteger BigInteger::operator / (BigInteger BigNum2)//对/号进行重载
{
	BigInteger BigNum1,result(0);
	bool flag=true;
	BigNum1=*this;
	if (int(BigNum1.Head->Num)*int(BigNum2.Head->Num)<0) 
	{
		flag=false;
	}
	if (int(BigNum1.Head->Num)<0)
	{
		BigNum1.Head->Num=char(int(BigNum1.Head->Num)*(-1));
	}
	if (int(BigNum2.Head->Num)<0)
	{
		BigNum2.Head->Num=char(int(BigNum2.Head->Num)*(-1));
	}

	int cmp=Compare(BigNum1,BigNum2);
	if (cmp==-1)
	{
		result.AddEnd(0);
	}
	else if (cmp==0)
	{
		result.AddEnd(1);
	}
	else
	{
		int n,t,i=0,k,sub;//BigNum1,BigNum2的长度
		Node *p1=BigNum1.Head;
		Node *p2=BigNum2.Head;
		while (p1)
		{
			n++;
			p1=p1->Next;
		}
		while (p2)
		{
			t++;
			p2=p2->Next;
		}
		sub=n-t;
		BigInteger Bm1,Bm2=BigNum2;
		BigInteger temp0(0),temp1(1),expand,temp2,temp3,temp;
		/************************************************************************/
		/* 对此情形的整除采用每步获取商的各位数字的形式得到,余数小于0时退出    */
		/************************************************************************/
		while((!(Compare(BigNum1,Bm2)==-1)))
		{
			Bm1=BigNum1;//保存每步的被除数
			expand=temp1;
			n=t=0;
			p1=BigNum1.Head;
			p2=BigNum2.Head;
			while (p1)
			{
				n++;
				p1=p1->Next;
			}
			while (p2)
			{
				t++;
				p2=p2->Next;
			}
			temp2=Transform(10); 
			temp3=Transform(n-t-1);
			//先将除数扩大10^(n-t-1)倍,商再扩大这么多倍即可得到除数的最高位后添0的数值
			if (n-t-1>0) 
			{ 
				expand=temp2^temp3;
				BigNum2=BigNum2*expand;
			}
			k=0;
			while(int(BigNum1.Head->Num)>=0)
			{
				BigNum1=BigNum1-BigNum2;
				k++;
			}
			k--;
			temp=expand*Transform(k);
			result=result+temp;
			BigNum1=Bm1-BigNum2*Transform(k);//每步的余数代替被除数
			BigNum2=Bm2;//恢复除数
		}
	}
	AdjustBigNum(result);	
	if (!flag)
	{
		result.Head->Num=char(int(result.Head->Num)*(-1));
	}
	return result;	
}

BigInteger BigInteger::operator % (BigInteger BigNum2)//对%号进行重载
{
	BigInteger BigNum1,temp,temp1(-1),result;
	BigNum1=*this;
	//为负则化为正处理,'+'只能对两个正整数有效
	while (int(BigNum1.Head->Num)<0)
	{
		BigNum1=BigNum1*temp1;//转正
		BigNum1=BigNum2-BigNum1;
	}	
	temp=BigNum1/BigNum2;
	result=BigNum1-(temp*BigNum2);
	AdjustBigNum(result);
	return result;	
}
/************************************************************************/
/*底数和指数都是正数,可以按模重复平方法的思路计算,只是计算过程中不用取余*/
/************************************************************************/
BigInteger BigInteger::operator ^ (BigInteger BigNum2)
{
	int count=0;
	BigInteger result(1),temp,temp2(2);
	BigInteger &BigNum1=*this;
	int b[200];
	//将BigNum2转换为二进制
	while(int(BigNum2.Head->Num))
	{
		temp=BigNum2%temp2;
		b[count++]=int(temp.Head->Num);
		BigNum2=BigNum2/temp2;
	}
	//按模重复平方法计算
	for(int i=count-1;i>=0;i--)
	{
		result=result*result;
		if(b[i])
			result=result*BigNum1;
	}
	return result;
}

BigInteger BigInteger::operator = (BigInteger BigNum)//对=号进行重载
{
	if(this==&BigNum)
		return *this;
	this->~BigInteger();
	Node *p;
	TempNode=Head=End=NULL;
	p=BigNum.Head;
	while(p)
	{
		AddEnd(p->Num);
		p=p->Next;
	}
	return *this;
}

CString disp(BigInteger BigNum)//输出链表
{
	CString str;
	char s[2]={'\0','\0'};
	Node *p=BigNum.Head;
	while(p)
	{
		str+=itoa(int(p->Num),s,10);
		p=p->Next;
	}
	str+="\r\n";
	return str;
}
//a mod n 的逆,存在则返回逆，否则返回0
BigInteger Inv(BigInteger a,BigInteger n)
{
	BigInteger b1(0),b2(1),d1(n),d2(a%n),temp,temp0(0);
	if (int(a.Head->Num)<0)
	{
		a=a+n;
	}
	while (int(d2.Head->Num))
	{
		temp=b2;
		b2=b1-(b2*(d1/d2));	 
		b1=temp;
		temp=d2;
		d2=d1-((d1/d2)*d2);
		d1=temp;
	}
	while (int(b1.Head->Num)<0)
	{
		b1.Head->Num=char(int(b1.Head->Num)*(-1));
		b1=n-b1;
	}
	if (d1.Head==d1.End&&int(d1.Head->Num==1))
	{
		return b1%n;
	}
	else
		return temp0;
	
}
//大整数的比较:a>b则返回1,相等返回0,a<b返回-1,只针对非负整数
int Compare(BigInteger BigNum1,BigInteger BigNum2)
{
	int result=0;//初始化为相等
	Node *temp1,*temp2;
	temp1=BigNum1.End;
	temp2=BigNum2.End;
	while (temp1&&temp2)
	{
		if (int(temp1->Num)>int(temp2->Num))
		{
			result=1;
		}
		if (int(temp1->Num)<int(temp2->Num))
		{
			result=-1;
		}
		temp1=temp1->Prev;
		temp2=temp2->Prev; 
	}
	if (temp1)
	{
		result=1;
	}
	if (temp2)
	{
		result=-1;
	}
	return result;
}
//如果BigNum==0返回1，否则返回0
int Compare(BigInteger BigNum)
{
	if (int(BigNum.Head->Num))
	{
		return 0;
	}
	else
		return 1;
}
//随机产生一个n位的大整数
BigInteger Rand(int n)
{
	BigInteger result,temp1(1);
	int number;
	srand(unsigned(GetTickCount()+seed));	
	number=rand();//随机产生种子
	seed=number;
	srand(number);//用种子初始化随机发生器
	number=1+rand()%9;//产生1-9的数字作为第一位
	result.AddEnd(char(number));
	n--;
	while (n)
	{
		number=rand();
		srand(number+seed);
		number=rand()%10;
		result.AddEnd(char(number));
		n--;
	}
	seed=seed/2;
	//调整使最后一位为奇数，利于后面产生素数
	if(int(result.End->Num)%2==0)
		result=result+temp1;

	return result;
}
/************************************************************************/
/*     随机产生大整数Bignum以内的大整数,即0--BigNum-1之间
		方法: 随机生成一个相同位数的大整数,再求模                       */
/************************************************************************/
BigInteger Rand(BigInteger BigNum)
{
	Node *p=BigNum.Head;
	BigInteger result;
	int length=0;//BigNum的位数
	int num;
	while (p)
	{
		length++;
		p=p->Next;
	}
	srand(unsigned(GetTickCount()));	
	randmize=rand()%1500;//随机产生种子
	srand(randmize);
	for(int i=1;i<=length;i++)
	{
		srand(randmize);//用种子初始化随机发生器
		randmize+=rand()%197;//保证种子不同
		num=rand()%10;
		result.AddEnd(num);
	}
	AdjustBigNum(result);
	result=result%BigNum;
	return result;
}
//将long型变量转化为大整数BigInteger型
BigInteger Transform(long n)
{
	BigInteger result;
	int temp;
	bool flag;
	if (n<0)
	{
		flag=false;
		n=-n;
	}
	while(n)
	{
		temp=n%10;//从个位开始依次取各位的数字
		result.AddHead(char(temp));
		n=n/10;
	}
	if (!flag) 
	{
		result.Head->Num=char(int(result.Head->Num)*(-1));//n为负数则转化为负的大整数
	}
	return result;
}


//大整数a^m%n运算,用模重复平方法求解
BigInteger Calculate_exp(BigInteger a,BigInteger m,BigInteger n)
{
	int i;
	int count=0;
	BigInteger d(1),temp,temp2(2);
	int b[400];
	//计算m转换为二进制
	while(int(m.Head->Num))
	{
		temp=m%temp2;
		b[count++]=int(temp.Head->Num);
		m=m/temp2;
	}
	//按模重复平方法计算
	for(i=count-1;i>=0;i--)
	{
		d=d*d%n;
		if(b[i])
			d=d*(a%n)%n;
	}
	return d;
}
/************************************************************************/
/*素性检验之前的筛选,即除以100以内的小素数								*/
/************************************************************************/
bool Select(BigInteger BigNum,int n)
{
	int a[]={3,5,7,11,13,17,19,23,29,31,34,37,41,43,47,51,57,59,61,67,71,73,79,83,89,91,97};
	if (int(BigNum.End->Num)%2==0) 
	{
		return false;
	}
	int i=0;
	BigInteger temp;
	while (i<27&&i<n) 
	{
		temp=Transform(a[i++]);
		if (Compare(BigNum%temp)) 
		{
			return false;
		}
	}
	return true;
}
/************************************************************************/
/* Rabin_Miller素性检验													*/
/************************************************************************/
bool M_Rabin(BigInteger n,int k)
{
	BigInteger t,b,r;
	long s=0,i=3;
	BigInteger nn,temp,temp0(0),temp1(1),temp2(2);
	nn=n-temp1;
	t=n-temp1;
	if (Compare(n,temp2)==0||Compare(n,temp1+temp2)==0) 
	{
		return true;
	}
	if (Compare(n,temp1)==0||Compare(n,temp2+temp2)==0)
	{
		return false;
	}
	temp=nn%temp2;
	while (Compare(temp))
	{
		t=nn/temp2;
		nn=nn/temp2;
		s++;
		temp=nn%temp2;
	}
	nn=n-temp1;
	while (k)
	{
		b=temp2+Rand(n-temp2-temp2);//随机选取2<=b<=n-2
		r=Calculate_exp(b,t,n);
		if (Compare(r,temp1)&&Compare(r,nn))
		{
			r=Calculate_exp(r,temp2,n);
			i++;
			while (Compare(r,nn)&&i<s+2) 
			{
				r=Calculate_exp(r,temp2,n);
				i++;
			}
			if (Compare(r,nn))
			{
				return false;
			}
		}
		i=3;
		k--;
	}
	return true;
}
//生成m位的伪随机大素数
BigInteger Produce_Prime(int m)
{
	BigInteger result=Rand(m),temp2(2);
	while (1)
	{
		if (!Select(result,2*m)) 
		{
			result=result+temp2;
		}
		else
		{
			if (!M_Rabin(result,5))
			{
				result=result+temp2;
			}
			else
				return result;
		}
	}	
}
//将一串数字转化为大整数
BigInteger CStringToBignum(CString sub)
{
	int length=sub.GetLength();
	BigInteger result;
	TCHAR c;
	int num;
	for(int i=0;i<length;i++)
	{
		c=sub[i];
		num=c-'0';
		result.AddEnd(num);
	}
	return result;
}
/////////////////////////////////////////////////////////////////////////////
// CECDSAApp message handlers