大整数运算.txt

大整数运算的实现

// Information Security Term Project
// Public-Key Cryptography (RSA Implementation)
// Student: NTUIM-11 B90705048 Huang, Shu-chun
//                               < RSA SYSTEM >
//                   B90705033 Liao, chen-fu
//                               < Big-Number Operations >

#include <iostream>
#include <string>
#include <fstream>
#include <ctime>
#include <sstream>
#include <algorithm>
#include <vector>

using namespace std;

string gcd(string, string);
// Euclid's algorithm: finding the greatest common divisor
string mInverse(string, string);
// extended Euclid's algorithm: finding the multiplicative inverse
void RSAkey();
// RSA reference keys generation
string RSA(string, string, string);
// RSA encryption/decryption function
bool primality(string, int);
// testing for primality

string operator +(string, string);
string operator -(string, string);
string operator *(string, string);
string division(string, string);
string operator /(string, string);
string operator %(string, string);
bool operator >(string, string);
int max(string*, string*);

int main()
{

	// program title
	cout << "Information Security Term Project (RSA SYSTEM)\n";

	char RSAagain = 'y'; // execute program again

	while (RSAagain == 'y')
	{
		char inFileName[25] = {0}, // input file name
			 outFileName[25] = {0}; // output file name

		cout << "\nEnter input file name: ";
		cin >> inFileName;

		ifstream inFile;
		inFile.open(inFileName); // open an original file

		if (!inFile) // cannot open original file
			cout << "\nInput File not Found!!\a\n" << endl;
		else
		{
			cout << "Enter output file name: ";
			cin >> outFileName;
			ofstream outFile(outFileName); // make a new file

			clock_t startTime, // execution start-time
					endTime; // execution end-time
			double duration; // program execution time

			int RSAsel = 0; // encrypt/decrypt selection
			cout << "Select (1)Encryption (2)Decryption "
				 << "(3)Primality Test : ";
			cin >> RSAsel;

			char ch; // temporary character
			int chCode; // integer code of the temporary character

			string key, // RSA key value (e or d)
				   n; // RSA n value

			if (RSAsel == 1) // RSA encryption
			{
				cout << "\n<< RSA Encryption >>" << endl;

				RSAkey(); // show reference keys

				cout << "\nEnter a reasonable value of e: ";
				cin >> key;
				cout << "Enter a reasonable value of n: ";
				cin >> n;

				cout << "RSA Encypting..." << endl;
				startTime = clock();

				int eCount = 0; // count encrypted bytes

				while (inFile.peek() != EOF) // encryption loop
				{
					stringstream s1; // for string conversion use
					string code; // for calculation use
					inFile.get(ch); // read a character
					chCode = ch; // convert character to integer
					s1 << chCode;
					s1 >> code; // convert integer to string
					code = RSA(code, key, n); // encryption
					outFile << code << " "; // write a string
					cout << "\r" << ++eCount; // show encrypted bytes
				}

				endTime = clock();
				cout << " bytes\nEncryption Done!" << endl;
			}
			else if (RSAsel == 2) // RSA decryption
			{
				cout << "\n<< RSA Decryption >>" << endl;

				cout << "\nEnter a reasonable value of d: ";
				cin >> key;
				cout << "Enter a reasonable value of n: ";
				cin >> n;

				cout << "RSA Decrypting...\n";
				startTime = clock();

				int dCount = 0; // count encrypted bytes

				while (inFile.peek() != EOF) // decryption loop
				{
					stringstream s2; // for string conversion use
					string code; // for calculation use
					inFile >> code; // read a string
					inFile.ignore(1, EOF); // skip the space
					code = RSA(code, key, n); // decryption
					s2 << code;
					s2 >> chCode; // convert string to integer
					ch = chCode; // convert integer to character
					outFile << ch; // write a character
					cout << "\r" << ++dCount; // show decrypted bytes
				}

				endTime = clock();
				cout << " bytes\nDecryption Done!" << endl;
			}
			else if (RSAsel == 3) // primality test
			{
				cout << "\n<< Primality Test >>" << endl;

				int times = 0; // test rounds
				bool primeNumber; // inconclusive or composite

				cout << "\nPlease enter candidate integer n : ";
				cin >> n;
				cout << "How many rounds do you want to test? : ";
				cin >> times;
				
				cout << "Primality Testing...\n";
				startTime = clock();

				if (n == "1") // special case: n = 1
					cout << "\nNumber 1 is not a prime!\n" << endl;
				else if (n == "2") // special case: n = 2
					cout << "\nNumber 2 is a prime!\n" << endl;
				else // common case: n > 2
				{
					primeNumber = primality(n, times); // testing

					if (primeNumber) // n may or may not be a prime
						cout << "\nInconclusive.\n" << endl;
					else // n is composite (not a prime)
						cout << "\nComposite.\n" << endl;
				}

				endTime = clock();
			}
			else // do nothing
			{
				startTime = clock();
				cout << "\n<< Do nothing... >>\n" << endl;
				endTime = clock();
			}

			duration = double(endTime - startTime) / CLOCKS_PER_SEC;
			cout << "Execution: " << duration << " seconds\n\n";
			// show the execution time

			inFile.close(); // close the original file
			outFile.close(); // close the new file
		}

		cout << "Execute again?(y/N): ";
		cin >> RSAagain;
	}

	cout << endl;
	
	
	return 0; // indicate that program ended successfully
}

string gcd(string a, string b) // Euclid's algorithm
{
	string A = a,
		   B = b,
		   R = "0";

	while (B != "0")
	{
		R = A % B;
		A = B;
		B = R;
	}

	return A; // greatest common divisor
}

string mInverse(string a, string b) // extended Euclid's algorithm
{
	string A1 = "1", A2 = "0", A3 = a,
		   B1 = "0", B2 = "1", B3 = b,
		   T1 = "0", T2 = "0", T3 = "0",
		   Q = "0";
	
	while (B3 != "0" && B3 != "1")
	{
		Q = A3 / B3;

		T1 = A1 - Q*B1;
		T2 = A2 - Q*B2;
		T3 = A3 - Q*B3;
		A1 = B1; A2 = B2; A3 = B3;
		B1 = T1; B2 = T2; B3 = T3;
	}

	if ("0" > B2)
		B2 = B2 + a; // let the value of d be positive

	if (B3 == "0")
		return "0"; // no inverse
	else
		return B2; // the multiplicative inverse
}

void RSAkey() // RSA keys generation (for reference)
{
	string p, q, n, phi, e, d;

	p = "97";
	q = "83";
	// RSA core prime numbers

	n = p * q;
	phi = (p - "1") * (q - "1");

	srand(time(0)); // roll the die

	do // finding a random and reasonable e value (public key)
	{
		stringstream s;
		s << rand() % 256;
		s >> e;
	}
	while (gcd(e, phi) != "1");
	
	d = mInverse(phi, e); // (private key)

	cout << "\nHere is a pair of reference RSA keys (REMEMBER!!):\n";
	cout << "Public key {e,n} = {" << e << ", " << n << "}\n";
	cout << "Private key {d,n} = {" << d << ", " << n << "}" << "\n";
	// show the reference keys to user
}

// RSA encryption/decryption
string RSA(string oriCode, string key, string n)
{
	string newCode = "1",
		   tempCode = oriCode, // original code
		   power = "1";

	// this quick algorithm is designed by AllenHuang
	while (key > "0")
	{
		if (power * "2" > key)
		{
			newCode = (newCode * tempCode) % n;
			tempCode = oriCode;
			key = key - power;
			power = "1";
		}
		else
		{
			tempCode = (tempCode * tempCode) % n;
			power = power * "2";
		}
	}

	return newCode; // new code after calculation
}

bool primality(string n, int times) // primality test
{
	// even number test (Allen's extra test)
	switch (n[n.length()-1])
	{
		case '0': case '2': case '4': case '6': case '8':
			return false; // even number greater than 2 => composite
		default:
			break;
	}

	// n-1 = 2^k * q (k > 0, q odd)
	int k = 0;
	string q,
		   a, // 1 < a < n-1, random number
		   temp = n - "1"; // n-1
	
	// calculate k & q
	while (temp[temp.length()-1] != '1' &&
		   temp[temp.length()-1] != '3' &&
		   temp[temp.length()-1] != '5' &&
		   temp[temp.length()-1] != '7' &&
		   temp[temp.length()-1] != '9')
	{
		temp = temp / "2";
		k++;
	}
	q = temp;

	// get a random number a
	srand(time(0)); // roll the die
	stringstream s;
	s << rand() % 256;
	s >> a;

	if (RSA(a, q, n) == "1")
		return true; // inconclusive
	else
		return false; // composite
}

string operator +(string x, string y)
{
	string xx, yy, end;

	if (x[0] == '-' && y[0] != '-')
	{
		xx.assign(x, 1, x.length()-1);
		return (y - xx);
	}
	else if (x[0] != '-' && y[0] == '-')
	{
		yy.assign(y, 1, y.length()-1);
		return (x - yy);
	}
	else if (x[0] == '-' && y[0] == '-')
	{
		xx.assign(x, 1, x.length()-1);
		yy.assign(y, 1, y.length()-1);
		return "-" + (xx + yy);
	}

	reverse(x.begin(), x.end());
	reverse(y.begin(), y.end());

	int i, sum, carry = 0;
	char* z = new char[max(&x, &y)+1];

	for (i = 0; i < x.length(); i++)
	{
		sum = (x[i] + y[i] - 96 + carry) % 10;
		carry = (x[i] + y[i] - 96 + carry) / 10;
		itoa(sum, &z[i], 10);
	}

	end = z;

	if (carry != 0)
		end.append("1");

	reverse(end.begin(), end.end());
	return end;
}

string operator -(string a, string b)
{
	string xx, yy, end;

	if (a[0] == '-' && b[0] != '-')
	{
		xx.assign(a, 1, a.length()-1);
		return "-" + (xx + b);
	}
	else if (a[0] != '-' && b[0] == '-')
	{
		yy.assign(b, 1, b.length()-1);
		return (a + yy);
	}
	else if (a[0] == '-' && b[0] == '-')
	{
		xx.assign(a, 1, a.length()-1);
		yy.assign(b, 1, b.length()-1);
		return (yy - xx);
	}

	if ((b>a) == true)
	{
		end += '-';
		end += (b - a);
		return end;
	}
	else if ((a>b) == true)
	{
		reverse(a.begin(), a.end());
		reverse(b.begin(), b.end());

		string temp;
		int j, sub;
		bool carry = false;
		char y;

		for (j = 0; j < max(&a, &b); j++)
		{
			if (carry == false) // 没有借位
			{
				if ((sub = (a[j] - b[j])) < 0) // 需要借位
				{
					carry = true;
					sub = (a[j] - 48) + (10 - (b[j] - 48));
				}
			}
			else // 有借位
			{
				if (a[j] == '0')
				{
					a[j] = '9';
					sub = a[j] - b[j];
				}
				else if ((sub=((a[j]-49)-(b[j]-48))) < 0) // 需要借位
					sub = (a[j] - 49) + (10 - (b[j] - 48));
				else
					carry = false;
			}

			itoa(sub, &y, 10);
			end += y;
		}

		string final;

		reverse(end.begin(), end.end());

		int position = end.find_first_not_of('0');
		final.assign(end, position, end.length() - position);

		return final;
	}
	else
		return end = "0";
}

string operator *(string a, string b)
{
	string xx, yy;

	if (a[0] == '-' && b[0] != '-')
	{
		xx.assign(a, 1, a.length()-1);
		return "-" + (xx * b);
	}
	else if (a[0] != '-' && b[0] == '-')
	{
		xx.assign(b, 1, b.length()-1);
		return "-" + (a * xx);
	}
	else if (a[0] == '-' && b[0] == '-')
	{
		xx.assign(a, 1, a.length()-1);
		yy.assign(b, 1, b.length()-1);
		return (xx * yy);
	}

	vector<string> temp;

	reverse(a.begin(), a.end()); // 先把a倒过来
	reverse(b.begin(), b.end()); // 再把b倒过来

	int i, j, multi, carry = 0;
	string end = "0";

	for (j = 0; j < b.length(); j++) // 取乘数第j位来乘
	{
		string y;
		y.append(j, '0');
		char x;
		carry = 0;

		for (i = 0; i < a.length(); i++)
		{
			multi = ((a[i]-48)*(b[j]-48) + carry) % 10;
			carry = ((a[i]-48)*(b[j]-48) + carry) / 10;
			itoa(multi, &x, 10);
			y += x;
		}
		if (carry != 0)
			y += (carry + 48);

		reverse(y.begin(), y.end());
		temp.push_back(y);
	}

	vector<string>::iterator pos;

	for (pos = temp.begin(); pos < temp.end(); ++pos)
		end = *pos + end;

	if (end.find_first_not_of('0') == string::npos)
		return "0";

	return end;
}

string division(string a, string b)
{
	int m,n;
	if((a.length()<=5)){
		m=atoi(a.c_str());
		n=atoi(b.c_str());
		char* p=new char [65535];
		int xx=(m/n);
		string pp;
		itoa(xx,p,10);
		pp=p;
		return pp;
	}
	string end;

	if (b > a)
		return "0";
	else
	{
		int len = b.length(), time;
		string temp;

		if (a[0] < b[0])//如果被除数的第一位数小于除数第一位数
			temp.assign(a, 0, len+1);//向后多找一位
		else//
		{
			temp.assign(a, 0, len);

			if(b > temp)//如果b仍大于temp
				temp.assign(a, 0, len+1);
		}
		string temp1 = temp;

		for (time = 1; time < 10; time++)
		{
			temp = temp - b;

			if((b > temp) == true)
				break;
		}

		char x = time + 48;
		string y, z;


		y = x;
		// 下面的for是把y后面的0补齐用来和除数b相乘之用
		if(a.length() > temp1.length())
			y.append(a.length()-temp1.length(),'0');

		
		string temp2;
		temp2 = temp;
		z = a;
		a = a - (y*b);
		
		
		return (y+division(a,b));
	}
}

string operator /(string a, string b)
{
	string xx, end;

	if (a[0] == '-' && b[0] != '-')//如果被除数a是负数,除数b是正数
	{
		xx.assign(a, 1, a.length()-1);

		if (b > xx)//除数大于被除数
			return "0";//商为0

		return "-" + division(xx, b);
	}
	else if (a[0] != '-' && b[0] == '-')//如果被除数a是正数,除数b是负数
	{
		xx.assign(b, 1, b.length()-1);

		if (xx > a)//除数大于被除数
			return "0";//商为0

		return "-" + division(a, xx);
	}
	else if (b == "0")
		return "错误：除数不得为0";

	if (b > a)
		return "0";

	return division(a, b);
}

string operator %(string a, string b)
{
	if (b == "0")
		return "错误：除数不得为0";

	return a-((a/b)*b);
}


bool operator >(string a, string b) // 判断两者谁比较大
{
	if (a.length() > b.length())
		return true;
	else if (a.length() < b.length())
		return false;
	else
	{
		int i;

		for (i = 0; i < a.length(); i++)
		{
			if (a[i] > b[i])
				return true;
			else if (a[i] < b[i])
				return false;
		}

		return false;
	}
}

int max(string* a, string* b) // 找出最大的长度，并将不足最大长度的补0
{
	if (a->length() >= b->length())
	{
		int i;

		for (i = b->length(); i < a->length(); i++)
			b->append("0");

		return a->length();
	}

	return max(b, a);
}

// end of program