非对称性加密算法——RSA算法原理及C++实现

cin>> a;
cin>> b;
cout<<a+b;

string getCountAdd(string a, string b)
{
	string c = "";
	int bit = -1; //判断是否进位 -1为否，其他为进位数
	int i = a.length()-1; //获得a字符串长度
	int j = b.length()-1; //获得b字符串长度
	//第一种情况 两者都处理完
	while (i != -1 && j != -1)
	{
		int t1 = a[i] - 48; 
		int t2 = b[j] - 48;
		//不存在进位
		if (bit == -1)
		{
			if (t1 + t2 >= 10)
			{
				int d = (t1 + t2) % 10;
				c.insert(0, 1, d + 48);
				bit = (t1 + t2) / 10;
			}
			else
			{
				c.insert(0, 1, t1 + t2 + 48);
			}
		}
		//存在进位
		else
		{
			if (t1 + t2 + bit >= 10)
			{
				int d = (t1 + t2 + bit) % 10;
				c.insert(0, 1, d + 48);
				bit = (t1 + t2 + bit) / 10;
			}
			else
			{
				c.insert(0, 1, t1 + t2 + bit + 48);
				bit = -1;
			}
		}
		i--;
		j--;
	}
	//第二种情况 前者处理完
	while (i == -1 && j != -1)
	{
		int t2 = b[j] - 48;
		if (bit == -1)
		{
			c.insert(0, 1, b[j]);
		}
		else
		{
			if (t2 + bit >= 10)
			{
				int d = (t2 + bit) % 10;
				c.insert(0, 1, d + 48);
				bit = (t2 + bit) / 10;
			}
			else
			{
				c.insert(0, 1, t2 + bit + 48);
				bit = - 1;
			}
		}
		j--;
	}
	//第三种情况 后者处理完
	while (i != -1 && j == -1)
	{
		int t1 = a[i] - 48;
		if (bit == -1)
		{
			c.insert(0, 1, a[i]);
		}
		else
		{
			if (t1 + bit >= 10)
			{
				int d = (t1 + bit) % 10;
				c.insert(0, 1, d + 48);
				bit = (t1 + bit) / 10;
			}
			else
			{
				c.insert(0, 1, t1 + bit + 48);
				bit = -1;
			}
		}
		i--;
	}
	//最后再判断是否存在进位
	if (bit != -1)
	{
		c.insert(0, 1, bit + 48);
	}
	bit = -1;
	return c;
}

string  getCountExp(int a, int b)
{
	//计算a^b
	string a1 = to_string(a);
	//string b1 = to_string(b);
	int i = a1.length()-1;//a的最后下角标
	//int j = b1.length()-1;//b的最后下角标
	//m位数*n位数长度不会超过m+n位
	string temp = a1; //temp一直变化
	string temp_2 = "0";
	int bitcount = 0; //判断当前位数
	int bit = -1;//判断是否存在进位
	string * arr = new string[a1.length()];//保存每次计算的数
	int arr_i = 0;
	for (int x = 1; x < b; x++)//几次方就循环几次
	{
		while (i != -1)//乘数的位数
		{
			//temp * a1
			int t1 = a1[i] - 48;
			int j = temp.length() - 1;//temp的最后下角标
			for (int z = 0; z < bitcount; z++)
			{
				arr[arr_i].insert(0, 1, '0');
			}
			while (j != -1)//temp的位数
			{
				int t2 = temp[j] - 48;
				if (bit == -1)//判断是否有进位
				{
					if (t1*t2 >= 10)
					{
						int d = (t1*t2) % 10;
						arr[arr_i].insert(0, 1, d + 48);
						int d_2 = (t1*t2) / 10;
						bit = d_2;
					}
					else
					{ 
						int d = t1*t2;
						arr[arr_i].insert(0, 1, d + 48);
					}
				}
				else
				{
					if ((t1*t2)+bit >= 10)
					{
						int d = ((t1*t2) + bit) % 10;
						arr[arr_i].insert(0, 1, d + 48);
						int d_2 = ((t1*t2) + bit) / 10;
						bit = d_2;
					}
					else
					{
						int d = (t1*t2) + bit;
						arr[arr_i].insert(0, 1, d + 48);
						bit = -1;
					}
				}
				j--;
			}
			if (bit != -1)
			{
				arr[arr_i].insert(0, 1, bit + 48);
				bit = -1;
			}
			temp_2 = getCountAdd(temp_2, arr[arr_i]);
			bitcount++;
			arr_i++;
			i--;
		}
		bitcount = 0;
		temp = temp_2;
		temp_2 = "0";
		for (int z = 0; z < arr_i; z++)
		{
			arr[z] = "";
		}
		arr_i = 0;
		i = a1.length() - 1;
	}
	return temp;
}

int getCountMod(string a, int b)
{
	int bit = -1; //判断是否需要进位
	//例如4255%5
	int i = 0;
	while (i < a.length())
	{
		int t1 = a[i] - 48;
		if (bit == -1)
		{
			if (t1%b > 0)
			{
				bit = t1%b;
			}
		}
		else
		{
			if (((bit * 10) + t1) % b>0)
			{
				bit = ((bit * 10) + t1) % b;
			}
		}
		i++;
	}
	if (bit != -1)
	{
		return bit;
	}
	else
	{
		return 0;
	}
	return 0;
}

long getRandomPrimeNum()
{
	long num = 0;
	while (true)
	{
		num = abs(rand());  //随机生成0  - RAND_MAX;
		if (isPrimeNum(num))
			return num;
	}
	return 0;
}

bool isPrimeNum(long long num)
{
	if (num < 2)return false;
	for (int i = 2; i < num / 2; i++)
	{
		if (num % i == 0)return false;
	}
	return true;
}

long long gcd(long long a, long long b)
{
	if (b == 0)return a;
	else return gcd(b, a%b);
	return 0;
}

int main()
{
	fstream file;
	ifstream in("C:\\Users\\fdog\\Desktop\\mingwen.txt", ios::in);
	istreambuf_iterator<char> beg(in), end;
	string strdata(beg, end);
	in.close();
	cout <<"读取的数据为："<< strdata << endl;
	string str = strdata;
	srand((unsigned)time_t(NULL));
	long long q = getRandomPrimeNum();
	long long p = getRandomPrimeNum();
	cout << "取随机素数p = " << p << " q = " << q;
	long long e = 0;
	long long n = q*p;
	cout << "   n：" << n ;
	long long fi = (q - 1)*(p - 1);
	cout << "  欧拉函数：" << fi ;
	long long * count = new long long[str.length()];
	srand((unsigned)time_t(NULL));
	while (1)
	{
		if (1 < e&&e < fi&& Prime::isPrimeNum(e) && gec(e,fi) ==1)
		{
			break;
		}
		e++;
	}
	cout << "   e：" << e;
	long long d =0;
	while (1)
	{
		if ((e*d) % fi == 1)
		{
			break;
		}
		d++;
	}
	cout << "   d: " << d << endl;
	string strc="";
	for (int i = 0; i < str.length(); i++)
	{
		long long  m = str[i]; //明文
		string str = getCountExp(m, e);
		long long c = getCountMod(str, n);
		cout << "当前需加密字符：" << m << " 加密之后  加密字符：" << c << endl;
		count[i] = c;
		strc.append(1, char(c));
	}
	string strm="";
	for (int i = 0; i < strc.length(); i++)
	{
		long long c = count[i]; //密文
		string str = getCountExp(c, d);
		long long m = getCountMod(str, n);
		strm.append(1, char(m));
		cout <<"解密之后的字符：" << m << endl;
	}
	cout << "明文：" << strm << endl;
	return 0;
}