// RSA.cpp: implementation of the CRSA class.
//
//////////////////////////////////////////////////////////////////////

#include "stdafx.h"
#include "EncryptDecryptDlg.h"
#include "RSA.h"

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

//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////

CRSA::CRSA()
{

}

CRSA::~CRSA()
{

}

//對szMessage利用RSA算法進行測試   
CString   CRSA::Encrypt(CString   szMessage,   int   p,   int   q,int   e)   
{   
	int t,d,n,iMessage,EncryValues,a,b,gcd;   
	CString EncryMessage;   

	n   =   p*q;		//計算乘積   
	t   =   (p-1)*(q-1);	//用于與私鑰e互素,同時e的值要保存   

	ExtBinEuclid(&t,&e,&a,&b,&gcd);//獲取公鑰   
	if(gcd==1)   
		d=t-b;   

	//對信息進行加密   
	//將字符串信息進行數據類型轉化     
	iMessage   =   atoi(szMessage.GetBuffer(szMessage.GetLength()));   
	EncryValues   =   GetValues(iMessage,d,n);   
	EncryMessage.Format(_T("%d"),   EncryValues);   

	return EncryMessage;   
}  
 
CString CRSA::Decrypt(CString   szMessage,int   e,int   n)   
{   
	int EncryValues,iMessage;   
	CString EncryMessage;   

	iMessage   =   atoi(szMessage.GetBuffer(szMessage.GetLength()));   
	EncryValues   =   GetValues(iMessage,e,n);   
	EncryMessage.Format(_T("%d"),   EncryValues);  
	
	return EncryMessage;   
}  
 
//獲取與Itemp的素數   
int CRSA::GetSecretKey(int   p,   int   q)   
{   
	int IResult,Itemp;   
	Itemp   =   (p-1)*(q-1);   

	for(IResult=(int)(0.2*Itemp);IResult<Itemp;IResult++)   
		if(IsPrime(IResult))   
		return IResult;
		
	return Itemp;   
}   

//判別是否為素數   
BOOL   CRSA::IsPrime(int   x)   
{   
	int   k;   

	k=int(sqrt(x));   
	for(int i=2; i<=k;i++)   
	{   
		if(x%i==0)           
			break;   
	}   

	if(i>=k+1)                               
		return TRUE;   
	else   
		return FALSE;   
}   
    
/*   
求高次模運算   
輸入參數:u表示公開密鑰,V為n   
*/   
int   CRSA::GetValues(int iMessage,int   d,int   n)   
{   
	int s,t,u;   

	s=1;   
	t=iMessage;   
	u=d; 
	
	while(u)   
	{   
		if(u&1)   
			s=(s*t)%n;   

		u>>=1;   
		t=(t*t)%n;   
	}   

	return s;   
}   
    
/*   
求模逆元運算---歐幾里德拓展算法   
輸入參數:u表示t,V為公開密鑰   
*/   
void CRSA::ExtBinEuclid(int* u,int* v,int* u1,int* u2,int* u3)   
{   
	int k,t1,t2,t3;   
	if(*u < *v)   
		swap(*u, *v);   

	for(k=0; isEven(*u) && isEven(*v); ++k)   
	{   
		*u   >>=   1;   
		*v   >>=   1;   
	} 
	
	*u1   =   1;   
	*u2   =   0;   
	*u3   =   *u;  
	
	t1   =   *v;   
	t2   =   *u   -   1;   
	t3   =   *v;   

	do   
	{   
		do   
		{   
			if(isEven(*u3))   
			{   
				if(isOdd(*u1)||isOdd(*u2))   
				{   
					*u1   +=   *v;   
					*u2   +=   *u;   
				}  
				
				*u1   >>=   1;   
				*u2   >>=   1;   
				*u3   >>=   1;   
			}   

			if(isEven(t3)   ||   *u3   <   t3)   
			{   
				swap(*u1,t1);   
				swap(*u2,t2);   
				swap(*u3,t3);   
			}   

		}while(isEven(*u3)); 
		
		while(*u1   <   t1   ||   *u2   <   t2)   
		{   
			*u1   +=   *v;   
			*u2   +=   *u;   
		}   

		*u1   -=   t1;   
		*u2   -=   t2;   
		*u3   -=   t3;  
		
	}while(t3   >   0);   

	while(*u1   >=   *v   &&   *u2   >=   *u)   
	{   
		*u1   -=   *v;   
		*u2   -=   *u;   
	}   

	*u1   <<=   k;   
	*u2   <<=   k;   
	*u3   <<=   k;   
}   

BOOL CRSA::isEven(int x) 
{ 
    return !(bool)(x & 0x0001); 
}

BOOL CRSA::isOdd(int dN) 
{ 
	return (bool)(dN & 0x0001); 
} 

void CRSA::swap(int *p1,int *p2)
{
	int p;

	p = *p1;
	*p1 = *p2;
	*p2 = p;
}

void CRSA::swap(int& p1,int& p2)
{
	int p;
	
	p = p1;
	p1 = p2;
	p2 = p;
}