// bmrsa.cpp : Defines the entry point for the console application.
//


#include <string.h>
#include <stdio.h>
#include <time.h>
#include "bignum.h"
#define MAXPRIMECOUNT 1000 // 尋找素數的最大次數
unsigned int nSmallPrimes[MAXPRIMECOUNT][2]; // 小素數數組
unsigned int nPrimeCount = 0; // 尋找素數的次數

// 尋找小素數
void MakeSmallPrimes()
{
   unsigned int n;
   unsigned int j;
   nPrimeCount = 3;
   // 首先定義幾個小素數
   nSmallPrimes[0][0] = 2;
   nSmallPrimes[1][0] = 3;
   nSmallPrimes[2][0] = 5;
   nSmallPrimes[0][1] = 4;
   nSmallPrimes[1][1] = 9;
   nSmallPrimes[2][1] = 25;
   // 開始尋找素數
   for (n=7; nPrimeCount < MAXPRIMECOUNT; n+=2)
   {
      for (j=0; nSmallPrimes[j][1] < n; j++)
      {
         if (j>= nPrimeCount) // 如果大于當前素數組標號，則返回
         {
            return;
         }
         if (n % nSmallPrimes[j][0]==0)  // 如果不是素數，則退出循環
         {
            break;
         }
      }
	  // 找到素數，設置素數
      if (nSmallPrimes[j][1] > n)
      {
         nSmallPrimes[nPrimeCount][0] = n;
         nSmallPrimes[nPrimeCount++][1] = n*n;
      }
   }
}

// 生成隨機大數
CBigNum GenerateBigRandomNumber(unsigned short nBytes)
{
   CBigNum Result=0U; // 初始化大數
   int i;
   clock_t ctStart;
   unsigned long ctr=0;
   
   // 設置時間間隔
   clock_t ctInterval = CLOCKS_PER_SEC / 50 + 1; 

   for (i=0; i<nBytes*2; i++)
   {
      ctStart = clock();
	  // 等到大于時間間隔再開始
      while (clock() - ctStart < ctInterval)
         ctr++;

      ctr = (ctr % 33) & 0xF;

      Result <<= 4U; // 大數左移4位
      Result |= ctr; // 做或運算
   }
   putchar('\n');
   return Result; // 返回大數
}

CBigNum FindABigPrime(unsigned short nBytes)
{
	CBigNum nBig, nBig2;
	DWORD j;
	DWORD nTestCount = 0;
	DWORD nLehmanCount = 0; 
	clock_t ctStartTime = clock(); // 記錄開始時間
	DWORD nOffset=0;
	bool bPrime=false; // 素數標志位
	
	// 開始尋找對應位數的大素數
	for (nBig = GenerateBigRandomNumber(nBytes) | 1U; !bPrime; nBig+=2U, nOffset+=2)
	{
		nTestCount++;
		for (j=0; j<nPrimeCount; j++)
		{
			// 如果不是大素數，則退出循環
			if (nBig % nSmallPrimes[j][0] == 0)
			{
				break;
			}
		}
		
		if (j<nPrimeCount)
			continue;
		nLehmanCount++;
		nBig2 = (nBig - 1U) / 2U;
		// 設置一些隨機的素數
		DWORD arnLehmanPrimes[] = { 89, 5179, 25981, 25439, 25013, 25667, 27397 };
		// 初始化大數組
		CBigNum LehmanResults[sizeof(arnLehmanPrimes) / sizeof(arnLehmanPrimes[0])];
		nBig2 = nBig - 1U;
		bPrime = true;
		for (j=0; j<sizeof(arnLehmanPrimes) / sizeof(arnLehmanPrimes[0]); j++)
		{
			// 開始生成大素數
			LehmanResults[j] = 
				CBigNum(arnLehmanPrimes[j]).PowMod(nBig2, nBig, CLOCKS_PER_SEC);
			if (LehmanResults[j] == nBig2)
			{
			}
			else if (LehmanResults[j] == 1U)
			{
			}
			else // 不是大素數
			{	
				bPrime = false;
				break;
			}
		}
		// 找到大素數
		if (bPrime) 
		{
			break;
		}
	}	
	return nBig; // 返回大素數
}

// 生成公鑰和私鑰
void GenKeyPair(CBigNum &PublicMod, CBigNum &PublicKey, CBigNum &PrivateKey, CBigNum &P, CBigNum &Q, unsigned int nByteCount = 32)
{
   if (0U==(P | Q))
   {
      P=FindABigPrime(nByteCount); // 生成nByteCount位的大素數
      Q=FindABigPrime(nByteCount); // 生成nByteCount位的大素數
      PublicKey=GenerateBigRandomNumber(nByteCount) | 1U;
   } else {
      PublicKey |= 1U;
   }
   PrivateKey = (P-1U) * (Q-1U); // 初始化私鑰
   while (PublicKey > PrivateKey)
      PublicKey=GenerateBigRandomNumber(nByteCount-1) | 1U;
   while(CBigNum::gcd(PublicKey,PrivateKey) != 1U) // 生成公鑰
      PublicKey+=2; // 累加直至互素
   PrivateKey = PublicKey.Inverse(PrivateKey); // 生成私鑰

   PublicMod = P*Q; // 公鑰n的生成
}





// 生成特定格式的公鑰和私鑰
void GenerateKeys(CBigNumString &PublicMod, CBigNumString &PublicKey, CBigNumString &PrivateKey, unsigned short nBytes)
{
	CBigNum PubMod, PubKey, PriKey, PriP, PriQ;
	MakeSmallPrimes();
    GenKeyPair(PubMod, PubKey, PriKey, PriP, PriQ, nBytes); // 生成公鑰和私鑰
	// 將公鑰和私鑰轉換成16進制形式
	PublicMod = PubMod.ToHexString(); 
	PublicKey = PubKey.ToHexString();
	PrivateKey = PriKey.ToHexString();
}

CBigNumString strMod, strPubKey, strPriKey; // 初始化大數字符變量

// RSA加密函數
void RSAEncrypt(char *publickey,char *publicmod, char *output, unsigned int *outputlen, char *input, unsigned int inputlen)
{
	CBigNum Transform;
	CBigNum PubMod, PubKey;
	CBigNumString strTransform;
	// 將公鑰轉換成大數
	PubMod = CBigNum::FromHexString(publicmod);
	PubKey = CBigNum::FromHexString(publickey); 
    
	// 轉換輸入的明文
	Transform = Transform.FromByteString(input);
	// 使用RSA加密明文
	Transform = Transform.PowMod(PubKey,PubMod);
	// 將密文轉換成16進制的字符
	strTransform = Transform.ToHexString();
	
	// 輸出密文長度
	*outputlen = strlen((const char*)strTransform)+1;
	// 輸出密文
	memcpy(output,(const char*)strTransform,(*outputlen)+1);
}

// RSA解密
void RSADecrypt(char *output, unsigned int *outputlen, char *input, unsigned int inputlen)
{
	CBigNum Transform;
	CBigNum PubMod,PriKey;
	CBigNumString strTransform;
	// 將私鑰轉換成大數
	PubMod = CBigNum::FromHexString((const char*)strMod);
	PriKey = CBigNum::FromHexString((const char*)strPriKey);
    // 轉換輸入的密文
	Transform = Transform.FromHexString(input);
	// 使用RSA對密文進行解密
	Transform = Transform.PowMod(PriKey,PubMod);
    // 將解密文轉換成字節字符串
	strTransform = Transform.ToByteString();
    
	// 輸出解密文長度
	*outputlen = strlen((const char*)strTransform)+1;
	// 輸出解密文
	memcpy(output,(const char*)strTransform,(*outputlen)+1);


}



int main(int argc, char* argv[])
{
	
	char pubkey[300]; // 公鑰
	char pubmod[300]; // 公鑰
	char encrypt_text[300]; // 輸出的密文
	char decrypt_text[300]; // 輸出的解密文
	unsigned int pubkeylen;
	unsigned int encrypt_len;
	unsigned int decrypt_len;
	char plain_text[50];
	strcpy(plain_text,"Welcome to RSA world!");	
	// 產生公鑰和私鑰
	GenerateKeys(strMod,strPubKey,strPriKey,64);
	// 設置公鑰字符串
	// 這里轉換成char型的是為了在網絡上傳輸方便
	memcpy(pubkey,(const char*)strPubKey,strlen((const char*)strPubKey)+1);
	memcpy(pubmod,(const char*)strMod,strlen((const char*)strMod)+1);
	
    // 使用RSA進行加密
	RSAEncrypt(pubkey,pubmod,encrypt_text,&encrypt_len,plain_text,sizeof(plain_text));
    // 使用RSA進行解密
	RSADecrypt(decrypt_text,&decrypt_len,encrypt_text,encrypt_len);
	printf("公鑰n :  %s\n",pubmod);
	printf("公鑰e :  %s\n",pubkey);
	printf("\n現在可以把公鑰傳輸給明文所有者進行加密\n\n");
    printf("加密前的明文:\n");
	printf("%s\n\n\n",plain_text);
	printf("加密后的密文:\n");
	printf("%s\n\n\n",encrypt_text);
	printf("解密后的輸出:\n");
	printf("%s\n\n\n",decrypt_text);
	getchar();
	return 0;
}