#include"stdafx.h"

#include <math.h>

#include<string.h>

/*/求解密密钥d的函数(根据Euclid算法)96403770511368768000*/

unsigned long  rsa(unsigned long p, unsigned long q, unsigned long e)  /*/求解密密钥d的函数(根据Euclid算法)*/

{

	unsigned long g, k, r, n1, n2, t;

	unsigned long b1 = 0, b2 = 1;

	g = (p - 1)*(q - 1);

	n1 = g;

	n2 = e;

	while (1)

	{

		k = n1 / n2;

		r = n1 - k*n2;

		if (r != 0)

		{

			n1 = n2;

			n2 = r;

			t = b2;

			b2 = b1 - k*b2;

			b1 = t;

		}

		else

		{

			break;

		}

	}

	return (g + b2) % g;

}

/*/判断一个数是否为素数*/

bool is_prime(int p) {

	int end = sqrt(p);

	for (int i = 2; i <= end; i++)

		if (p%i == 0)

			return false;

	return true;

}

/*/利用利用倍增法实现x^p mod m */

long long expmod(int x, int p, int m) {

	//x^p mod m

	const int N = 110;

	int a[N];

	long long s;

	//scanf("%d%d%d", &x, &p, &m);

	//将p转成二进制传入a数组

	int k = 0;

	while (p>0) {

		++k;

		a[k] = p % 2;

		p = p / 2;

	}

	//for (int i = k; i>0; --i) printf("%d", a[i]);

	//printf("\n");

	//初始化连续变量t和答案s

	long long t = x;

	if (a[1] == 0) s = 1;

	else s = x;

	//倍增

	for (int i = 2; i <= k; ++i) {

		t = t*t%m;

		if (a[i] == 1) s = s*t%m;

	}

	//printf("%I64d", s);

	return s;

}

int main() {

	int p, q, e;//素数p,q和随机数e

	printf("welcom come to the ESA program\n");

	printf("please input two prime unsigned number p,q  and a rand unsigned number e\n");

	printf(" p=");	scanf("%d", &p);

	printf(" q=");	scanf("%d", &q);

	printf(" e=");	scanf("%d", &e);

	bool bp=false, bq=false;

	while (bp == false || bq == false) {

		if (p*q < 127||p<0||q<0) {

			if(p>0&&q>0)printf("please input two more big prime unsigned number p,q\n");

			else if (p<0 || q<0)printf("please input two  prime unsigned number p,q(p>1,q>1)\n");

			printf(" p=");	scanf("%d", &p);

			printf(" q=");	scanf("%d", &q);

			bp = bq = false;

		}

		else {

			bp = is_prime(p);

			if (p <= 1)

				bp = false;

			bq = is_prime(q);

			if (q <= 1)

				bq = false;

			if (bp == false)

			{

				if (p == 1)

					printf("input a more big prime  number p=");

				else

					printf("input a prime unsigned number p=");

				scanf("%ud", &p); printf("\n");

			}

			if (bq == false) {

				if (q == 1)

					printf("input a more big prime  number q=");

				else

					printf("input a prime unsigned number q=");

				scanf("%ud", &q); printf("\n");

			}

		}

	}

	//计算公钥与私钥

	int n = p*q;

	int fn = (p - 1)*(q - 1);

	int d = rsa(p, q, e);

	printf("公钥：（e,n）为（%d,%d)\n",e,n);

	printf("私钥：（d,n）为（%d,%d)\n",d,n);

	printf("---------加密/解密---------\n");

	char ch = 'a';

	while (ch != 'd' && ch != 'D' && ch != 'e' && ch != 'E') {

		printf("加密输入e或E,解密输入d或D,请选择：\n");

		getchar();

		scanf("%c",&ch);

	}

	char* str = new char[1024];

	int i, len;

	//encryption加密

	if (ch == 'e' || ch == 'E') {

		printf("---------加密--------\n");

		printf("please input what you want to encryption(String):\n");

		scanf("%s", str);

		i = 0, len = strlen(str);

		int mingwen;

		while (i < 1024 && i < len) {

			mingwen = (int)str[i];

			int pr = expmod(mingwen, e, n);

			if (i != 0)

				printf(",");

			printf("%d", pr);

			i++;

		}

		printf("\n");

	}

	//decryption解密

	else if (ch == 'd' || ch == 'D') {

		printf("---------解密--------\n");

		printf("please input what you want to decryption(String)\n");

		printf("you should input just as XXX,XXX,XXX,XXX,XXX\n");

		scanf("%s", str);

		i = 0, len = strlen(str);

		long long im = 0;

		while (i < 1024 && i < len) {

			if (str[i] != ',')

				im = im * 10 + (int)str[i] - 48;

			else {

				im = expmod(im, d, n);

				printf("%c", (char)im);

				im = 0;

			}

			if (i == 1023 || i == len - 1) {

				im = expmod(im, d, n);

				printf("%c", (char)im);

				im = 0;

			}

			i++;

		}

		printf("\n");

	}

	getchar();

	getchar();

	return 0;

}