#include<iostream>
#include<math.h>
using namespace std;

class Rsa
{
private:
	int p, q;	//two different primes
	int n;		//p*q
	int e;		//choose one
	int d;		//calculated
public:
	Rsa(int a, int b) {		//constructor
		p = a;
		q = b;
		n = a*b;
		e = confirmE(a, b);
		d = confirmD(e, a,b);
	}
//========constructor in use==========
	void swap(int a, int b) {	//swap two nums
		int c;
		c = a;
		a = b;
		b = c;
	}
	int gcd(int a, int b) {		//get gcd
		if(a == 0) {
			return b;
		}
		if(b == 0) {
			return a;
		}
		if(b < a) {
			swap(a ,b);
		}
		int c;
		for(c = a % b; c > 0; c = a % b) {
			a = b;
			b = c;
		}
		return b;
	}
	int confirmE(int p, int q) {			//confirm the "E"
		int phi;
		phi = (p-1)*(q-1);
		int e;
		for(e = 2; gcd(phi, e) != 1; e++) {
		}
		return e;
	}
	int confirmD(int e, int p, int q) {			//confirm the "D"
		int phi = (p-1)*(q-1);
		int u1, u2, u3;
		int v1, v2, v3;
		int t1, t2, t3;
		int uu, vv;
		int temp;
		int inverse;
		u1 = 1;
		u2 = 0;
		u3 = phi;
		v1 = 0;
		v2 = 1;
		v3 = e;
		
		while(v3 != 0) {
			temp = u3 / v3;
			
			t1 = u1 - temp*v1;
			t2 = u2 - temp*v2;
			t3 = u3 - temp*v3;
			
			u1 = v1;
			u2 = v2;
			u3 = v3;
			
			v1 = t1;
			v2 = t2;
			v3 = t3;
		}
		uu = u1;
		vv = u2;
		
		if(vv < 0) {
			inverse = vv + phi;
		}
		else {
			inverse = vv;
		}
		return inverse;
	}

	long mod(long base,long exponent,long num) {	//計算形如base^exponent mod num
		long bin[32], i = 0, result(1);
		while (exponent != 0) {		//轉換成二進制
			long temp;
			temp = exponent%2;
			bin[i++] = temp;
			exponent = exponent/2;
		}
		i = i-1;					//i自減1，回到二進制的最高位
		while(i >= 0) {				//快速指數算法
			long c(0);
			c = 2*c;
			result = (result*result)%num;
			if(bin[i] == 1) {
				c = c+1;
				result = (result*base)%n;
			}
		i--;
		}
		return result;
	}

//====================================
	void setP(int a) {
		p = a;
	}
	void setQ(int a) {
		q = a;
	}
	int getP() {
		return p;
	}
	int getQ() {
		return q;
	}
	int getN() {			//n = p*q
		return n;
	}
	int getE() {
		return e;
	}
	int getD() {
		return d;
	}
	long getPhi() {
		return (p-1)*(q-1);
	}

//========get KU======================
	void getKu() {		//Key Public
		cout<<"公鑰為：{"<<e<<","<<n<<"}"<<endl;
	}
	void getKr() {		//Key Private
		cout<<"私鑰為：{"<<d<<","<<n<<"}"<<endl;
	}
};


//======================================
long isPrime(long num) {		//Is prime number?
	long temp, i;
	temp = sqrt((double)num);
	for(i = 2; i <= temp; i++) {
		if(num%i == 0) {
			break;
		}
	}
	if(i>temp) {
		return 1;
	}
	else {
		return 0;
	}
}

long Auto(long t) {
	long prime;
	for(prime = t; isPrime(prime) == 0; prime = t) {
		t++;
	}
	return prime;
}

int input(char word) {				//接受數字并判斷是否素數
	int inputnum;
	char yesno;
	cout<<"請輸入"<<word<<"：";
	cin>>inputnum;			//get inputnum
//=======input over, check it===========
	while(isPrime(inputnum) == 0) {
		cout<<"您輸入的不是素數。"<<endl;
		while((yesno != 'n') & (yesno != 'y')) {
			cout<<"是否讓系統自動為你生成一個素數。(y/n):";
			cin>>yesno;
		}
		if(yesno != 'y') {
			cout<<"請輸入"<<word<<"：";
			cin>>inputnum;
		}
		else {
			inputnum = Auto(inputnum);
			cout<<word<<"："<<inputnum<<endl;
		}
		yesno = 0;
	}
	return inputnum;
}

void outputAllArguments(Rsa rsa) {				//輸出參數值
	cout<<"==========首先輸出各參數值=========="<<endl;
	cout<<"p="<<rsa.getP()<<endl;
	cout<<"q="<<rsa.getQ()<<endl;
	cout<<"n=p*q="<<rsa.getN()<<endl;
	cout<<"Φ(n)=(p-1)*(q-1)="<<rsa.getPhi()<<endl;
	cout<<"e="<<rsa.getE()<<endl;
	cout<<"d="<<rsa.getD()<<endl;
	rsa.getKu();
	rsa.getKr();
	cout<<"==========參數值輸出結束============"<<endl;
}

void main()
{
//	char yesno;
	long p;
	long q;
	char quit;
//=======output congratulations=========
	cout<<"===========8000104008彭鵬============="<<endl;
	cout<<"RSA加密軟件"<<endl<<endl;
	cout<<"通過輸入兩個素數p和q，產生一個公鑰(e,n)和一個私鑰(d,n)。"<<endl;
	cout<<"其中公鑰用于加密，私鑰用于解密。"<<endl;
	while(quit != 'n') {
		//=======input p & q======================
		cout<<"===================================="<<endl;
		p = input('p');				//input p
		q = input('q');				//input q
		//=======p & q are all over===========

		//=======caculate=======================
		Rsa rsa1(p, q);
		cout<<"p和q都已經輸入完畢，下面進行加密和解密進程。"<<endl;
		//=======output all arguments===========
		outputAllArguments(rsa1);
		//=======input num======================
		cout<<"輸入明文數字："<<endl;
		long mnum;			//明文數字
		cin>>mnum;
		cout<<"輸入明文為："<<mnum<<endl;
		//======================================
		cout<<"輸出密文為：";
		long c_num;			//密文數字
		//	c_num = c(mnum, rsa1);		//encryption
		c_num = rsa1.mod(mnum, rsa1.getE(), rsa1.getN());		//encryption
		cout<<c_num<<endl;
		//======================================
		cout<<"輸出明文為：";
		long m_num;			//解密出的明文數字，理論應與mnum一樣
		//	m_num = m(c_num, rsa1);		//decryption
		m_num = rsa1.mod(c_num, rsa1.getD(), rsa1.getN());		//decryption
		cout<<m_num<<endl;
		//===========coutinue ?=================
		cout<<"是否繼續使用?(按任意鍵繼續，按'n'結束)";
		cin>>quit;
	}
}