#include "stdafx.h"
//#include "RSATest1.h"
#include "Rsawang1.h"

#ifdef _DEBUG
#define new DEBUG_NEW
#undef THIS_FILE
static char THIS_FILE[] = __FILE__;
#endif

/////////////////////////////////////////////////////////////////////////////
// CRsaA

IMPLEMENT_DYNCREATE(CRsaA, CCmdTarget)

CRsaA::CRsaA()
{
	InitInt();
		
}

CRsaA::~CRsaA()
{
}


BEGIN_MESSAGE_MAP(CRsaA, CCmdTarget)
	//{{AFX_MSG_MAP(CRsaA)
		// NOTE - the ClassWizard will add and remove mapping macros here.
	//}}AFX_MSG_MAP
		//ON_MESSAGE(WM_COMPUTING,OnComputing)
END_MESSAGE_MAP()

/////////////////////////////////////////////////////////////////////////////
// CRsaA message handlers

/*----------------------------------------------------------------------------
功能：進行相關大數的初始化
入口參數：無
返回值：無
----------------------------------------------------------------------------*/
void CRsaA::InitInt(void)
{
	SetZero(ZEROVALUE);						//對大數變量zerovalue清零
	memset(mZEROVALUE,0,MLENGTH);
	SetZero(ONEVALUE);                      //對大數變量ONEVALUE進行清零
	ONEVALUE[DATALENGTH-1]=1;				//ONEVALUE的最后一位為1
	SetZero(TWOVALUE);						//將TOWVALUE進行清零
    TWOVALUE[DATALENGTH-1]=2;				//TOWVALUE的最后一位為2
	SetZero(EIGHTVALUE);					//對EIGHTVALUE進行清零
    EIGHTVALUE[DATALENGTH-1]=8;				//最后一位為8
	return ;
}

/*---------------------------------------------------------------------------
功能：將一個大數A轉換為相應的字符串形式
入口參數：大數A
返回值：相對應的字符串
----------------------------------------------------------------------------*/
CString CRsaA::PrtInt(byteint A)
{
	register i=0;
	int m,n;
	while(i<DATALENGTH && A[i]==0)          //跳過大數開始的空白0
		i++;
	if(i<DATALENGTH)
		m=DATALENGTH-i;                     //求出有用的大數長度
	n=0;
											//注意到這里的i已經是數組中第一個非零元素的對應位置，
	CString str="";							//因此下面的循環就是從數組中
											//存放的數的最高位開始輸出。
	while(i<DATALENGTH)
	{
		str += (A[i++]+'0');
	}
	return str;
}

/*---------------------------------------------------------------------------
功能：大數A與大數B相乘，結果放入C中 A×B->C
入口參數：被乘數A和乘數B，結果C
返回值：無
----------------------------------------------------------------------------*/
void CRsaA::Multiply(byteint A,byteint B,byteint C)
{
	register i,j,w;
	int X,Y,Z;
	int Avalid=0;								//Avalid=validating bits of A
	int Bvalid=0;								//Avalid=validating bits of B
	while (A[Avalid]==0 && Avalid<DATALENGTH)
		Avalid++;								//計算Avalid
	while (B[Bvalid]==0 && Bvalid<DATALENGTH)
		Bvalid++;								//計算Bvalid

	SetZero(C);									//將C清零初始化
	
	for(i=DATALENGTH-1;i>=Avalid;i--)
		for(j=DATALENGTH-1;j>=Bvalid;j--)       //逐位進行相乘運算
		{
			X=A[i]*B[j];        
			Y=X/10;
			Z=X-10*Y;
			w=i+j-(DATALENGTH-1);
			C[w]=C[w]+Z;
			C[w-1]=C[w-1]+(C[w]/10)+Y;
			C[w]=C[w]-(C[w]/10)*10;
		}
	return;
}

/*---------------------------------------------------------------------------
功能：將指定的自定義的大數進行0初始化
入口參數：大數A名
返回值：無
----------------------------------------------------------------------------*/
void CRsaA::SetZero(byteint A)  
{
	memset(A,0,DATALENGTH);                    //調用系統函數進行初始化
}

/*---------------------------------------------------------------------------
功能：將大數B拷貝到大數A中
入口參數：大數A，大數B
返回值：無
----------------------------------------------------------------------------*/
void CRsaA::IntCpy(byteint A,byteint B)
{
	memcpy(A,B,DATALENGTH);                    //調用系統函數完成拷貝
}

/*---------------------------------------------------------------------------
功能：A＋B的結果送C
入口參數：大數A,B,C
返回值：無
----------------------------------------------------------------------------*/
void CRsaA::Plus(byteint A,byteint B,byteint C)
{
	register i;//,w;
	int X,Y,Z,m,n,valid;
	m=IntValid(A);                 //計算A的長度         
	n=IntValid(B);                 //計算B的長度
	valid=(m>n)?m+1:n+1;           //計算時要以最長的數為準
	SetZero(C);                    //將C清零
	for(i=DATALENGTH-1;i>=DATALENGTH-valid;i--)
	{
		X=A[i]+B[i];               //按位相加
		Y=X/10;
		Z=X-10*Y;

		C[i]=C[i]+Z;               //計算進位
		C[i-1]=C[i-1]+Y;
	}
}

/*---------------------------------------------------------------------------
功能：大數SA減去大數SB，結果放入SC
入口參數：被減數SA，減數SB，差SC
返回值：無
----------------------------------------------------------------------------*/
void CRsaA::Substract(byteint SA,byteint SB,byteint SC)
{
	byteint buf;
	register i,j;
	int X;
	IntCpy(buf,SA);                  //將SA的內容拷貝到buf中
	SetZero(SC);                 //SC清零初始化
	for(i=DATALENGTH-1;i>=0;i--)	
	{
		if(buf[i]<SB[i])             //如果最低位不夠減
		{
			buf[i]=buf[i]+10;        //向高位借1
			if(buf[i-1]>0)           //如果高位夠減，直接減1
				(buf[i-1])--;    
			else                     //否則一直找到夠減的位
			{
				j=i-1;
				while(buf[j]==0)     //j不會出現越界，是因為保證了最高位不為0
					buf[j--]=9;
				buf[j]=buf[j]-1;
			}
		}
		X=buf[i]-SB[i];              //將各位減的結果存入SC中
		SC[i]=X;
	}
}

/*---------------------------------------------------------------------------
功能：比較兩個大數A和B的大小
入口參數：大數A和大數B
返回值：A>B:return 1 ; A=B:return 0 ; A<B:return -1
----------------------------------------------------------------------------*/
int CRsaA::IntCmp(byteint A,byteint B)
{
	int stat;
	stat=memcmp(A,B,DATALENGTH);    //系統函數
	if(stat==0)
		return 0;
	if(stat>0)
		return 1;
	return -1;
}

/*---------------------------------------------------------------------------
功能：得到一個大數的非零位數
入口參數：大數validtemp
返回值：大數中非零的位數
----------------------------------------------------------------------------*/
int CRsaA::IntValid(byteint validtemp)
{
	register i=0;
	while(validtemp[i]==0 && i<DATALENGTH)
		i++;
	return DATALENGTH-i;
}

/*---------------------------------------------------------------------------
功能：計算大數A÷B的結果，余數放在C中，商在D中
入口參數：被除數A，除數B，余數C，商D
返回值：無
----------------------------------------------------------------------------*/
void CRsaA::SetMode(byteint A,byteint B,byteint C,byteint D)
{
	register i,j,k;
	int valid_1,valid_2,valid,sbits,cmpval;
	byteint buf1,buf2;
    
	SetZero(buf1);  SetZero(buf2);
	SetZero(D);                       //將大數D進行清零初始化
    IntCpy(C,A);                      //將被除數A拷貝到C中
	valid_2=IntValid(B);              //計算B(除數)的位數,
	while((cmpval=IntCmp(C,B))>0)     //變除法為減法,每減一次就判斷是否有C>B,如果滿足就繼續減。
	{
		valid_1=IntValid(C);          //計算C(被除數)的位數,因為它的位數在循環過程中是變化的
		                              //做減法后(C-B)仍然存放在C中
		valid=valid_1-valid_2;        //C的長度與B的長度的差（該值最小為0）
		if(valid>0)                   //如果被除數比除數的位數多
		{
			i=DATALENGTH-valid_1;     //被除數前導零的個數
			j=DATALENGTH-valid_2;     //除數前導零的個數，作下標指示器
			sbits=0;
			for(k=j;k<DATALENGTH;k++)
			{
				if(C[i]>B[j])         //從C和B的最高位開始依次比較對應位的大小，判斷是否夠減
					break;
				if(C[i]<B[j])
				{
					sbits=1;          //如果不夠減，那么C就退一位，再做減法
					break;
				}
				i++;j++;              //當C和B的最高位相等時,就比較二者的次高位
			}
			valid=valid-sbits;
			SetZero(buf1);            //buf1清零
			for(i=valid;i<DATALENGTH;i++)
			{
				j=i-valid;
				buf1[j]=B[i];         //buf1中存放的是B左移若干位之后得到的值
				                      //如果夠減,則B左移后最高位與C的最高位對齊,
				                      //否則與C的次高位對齊
			}
		}
		else
			IntCpy(buf1,B);           //當C和B的位數相同時,就直接把B放入緩沖區buf1中

		D[DATALENGTH-1-valid]++;      //這里保存的是在某一位上所做的減法的次數，每做一次就加1
		Substract(C,buf1,buf2);       //不論C的長度與B的長度的差是否大于0，都要做減法，直到C<=B
		IntCpy(C,buf2);
	}
	if(cmpval==0)                     //兩個數相等
	{
		SetZero(C);                   //余數為0
		D[DATALENGTH-1]++;            //商為1
	}
}

/*---------------------------------------------------------------------------
功能：隨機地產生一個大數奇數，長度為num，最高位不是0，存放在RandomA中
入口參數：大數A，長度num
返回值：無
----------------------------------------------------------------------------*/
void CRsaA::IntRandom(byteint RandomA,int num)
{
	int i;
	SetZero(RandomA);                     //將RandomA清零
	
	while(!(RandomA[DATALENGTH-1]%2))     //判斷條件保證RandomA的最后一位數是奇數
		RandomA[DATALENGTH-1]=rand()%10;  //如果最后一位是偶數，則從新產生最后一位
    while(!(RandomA[DATALENGTH-num]))     //判斷條件保證RandomA最高位不是0
		RandomA[DATALENGTH-num]=rand()%10;//如果最高位是0,則從新產生最高位

	i=DATALENGTH-2;
	while(i>=DATALENGTH-num+1)            //循環產生從次低位開始到次高位的所有位上的數
		RandomA[i--]=rand()%10;
}

/*---------------------------------------------------------------------------
功能：將質數類型B拷貝到A中，實現類型轉換
入口參數：大數A，質數類型B
返回值：無
----------------------------------------------------------------------------*/
//功能：將數B拷貝到大數A，實現類型轉換
void CRsaA::LoadInt(byteint A,mtype B)
{
	register i,j;
	SetZero(A);                  //A進行清零初始化
	i=DATALENGTH-1;
	j=MLENGTH-1;
	while(j>0)                   //循環拷貝各位數字
	{
		A[i--]=B[j--];
	}
}

/*---------------------------------------------------------------------------
功能：該函數用來從集合[1,b-1]中產生若干個用于檢測的數，存放在Model[]中
入口參數：無
返回值：無
----------------------------------------------------------------------------*/
void CRsaA::Mdata()
{
	register i,j;                     //Randomly choose a set of 100 numbers in [1,b-1]
	int k=MLENGTH-2;
	
	memset(Model,0,TESTNUM*MLENGTH);  //這個函數在這里用來將整個數組清零，進行初始化
	srand( (unsigned)time( NULL ) );  //進行隨機函數的初始化
	for(i=0;i<TESTNUM;i++)            //TESTNUM為需要產生的個數
	{
		for(j=MLENGTH-1;j>=k;j--)
		{
			Model[i][j]=rand()%10;    //注意這里與測試素數的程序中的區別，
		}
		if((memcmp(Model[i],mZEROVALUE,MLENGTH))==0)  
			i--;
		k--;                          //保證所產生的數不為0
		if (k<0) k=MLENGTH-2;
	}
	
}

/*---------------------------------------------------------------------------
功能：該函數用來將十進制的大整數轉換成二進制的數
入口參數：需轉換的大數B，二進制結果flag[400]
返回值：無
----------------------------------------------------------------------------*/
void CRsaA::TransBi(byteint B,signed char flag[400])
{
	byteint buf;
	byteint result;
	byteint temp;
	register i;
	SetZero(buf);  SetZero(result);  SetZero(temp);
	memset(flag,0,400);                     //將flag數組清零

	i=399;
	IntCpy(buf,B);                          //將B拷貝到buf中
	while(IntCmp(buf,ZEROVALUE)==1)         //如果buf內容為0
	{
		SetMode(buf,TWOVALUE,temp,result);  //將buf進行大數的模2運算，商在result中，余數temp
		flag[i]=temp[DATALENGTH-1];         
		IntCpy(buf,result);                 //對商繼續進行模2運算
		i--;
	}
	flag[i]=-1;                             //設置一個標志位，表明二進制數的開始
}

/*---------------------------------------------------------------------------
功能：該函數用來進行模冪算法，A為底數，模為c，二進制的指數B存放在數組flag中
入口參數：底數A，模C，結果D，二進制質數flag[400]
返回值：A^B=1(mod C),返回1；A^B=p-1(mod C),返回2；否則返回0
----------------------------------------------------------------------------*/
int CRsaA::PowerMode(byteint A,byteint C,byteint D,signed char flag[400])
{
	byteint buf;
	byteint result;
	byteint temp,P;
	register i;
	SetZero(D);   SetZero(buf); SetZero(result); SetZero(temp); SetZero(P);  //將D清零

	IntCpy(temp,A);                       //將A的值拷貝到temp中
	if(flag[399]==1)                      //最低位為1，拷貝本身，flag[i]只有1或者0兩種情況
		IntCpy(result,A);
	else								  //最低位為0，則冪為1
		IntCpy(result,ONEVALUE);
	i=398;
	while(flag[i]!=-1)                    //判斷是否已經到達指數盡頭
	{
		Multiply(temp,temp,buf);          //temp*temp->buf 
		SetMode(buf,C,temp,P);            //buf%c余數->temp,商->p
		if(flag[i]!=0)                    //如果該位不是0，則將其和前一步低一位的結果進行乘法運算
		{                                 //否則，將其作為該位的模，在高一位的運算中，只要進行一次
			Multiply(temp,result,buf);    //平方運算，就可以得到高一位的模
			SetMode(buf,C,result,P);
		}
		i--;
	}                                     //result中存放的是最終結果
	IntCpy(buf,C);
	IntCpy(D,result);
	Substract(buf,ONEVALUE,temp);
	if(IntCmp(result,ONEVALUE)==0)        //p mod n=1，判斷是否有A^B=1(mod C)
		return 1;
	if(IntCmp(result,temp)==0)            //p mod n=-1[p-1=-1(mod p)]，判斷是否有A^B=p-1(mod C)
		return 2;
	return 0;
}

/*---------------------------------------------------------------------------
功能：產生一個質數
入口參數：大數Prm
返回值：產生成功，返回0
----------------------------------------------------------------------------*/
int CRsaA::Prime(byteint Prm)
{
	int i,k,ok;
	signed char flag[400];
	byteint A,B,D,buf1,buf2;
	SetZero(A); SetZero(B); SetZero(D); SetZero(buf1); SetZero(buf2);
	
	while(1)                                 //一直循環直到找到一個素數為止
	{
		int pass=0;
		srand( (unsigned)time( NULL ) );     //初始化srand
		IntRandom(B,MLENGTH);                //隨機產生一個大數B  try b if prime,B是一個奇數

		IntCpy(Prm,B);                       //將B拷貝到prm中 C=N result prime
		Substract(B,ONEVALUE,buf1);          //將B-ONEVALUE的結果放到buf1中