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

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


一. 前言

非对称性加密算法——RSA算法原理及C++实现
最近想模仿一下qq,做一个通信软件,这是qq的登录界面,当我们选择记住密码后,每次运行qq,就会显示已保存的密码,无论是否联网,显然这个密码是保存在本地的,当点击登录,才会去和服务器上的数据库进行比对,那么这个密码显然不能是明文的,一定是经过加密的密文。至于qq用的什么加密方法,这个就无从所知了。

通过百度,发现一个叫非对称性加密算法非常有意思,可以保证数据的安全,所以用了一些时间来学习这个算法,这个算法涉及了大数幂运算,所以还会学习如何设计编写能够处理大数幂运算的函数。

看正题之前,说一些自己的感慨吧。

在一个项目中,实现功能的那一部分代码很少,更多的是对这一功能的维护,如果用户没有按照预期的方式输入数据,那么应该怎样应对,例如下面是张老师给同学出的一道题。
实现一个简单的输入,要求用户输入两个数,然后计算这两个数和,我相信所有人都会写出类似于下面的代码:

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

这三行代码已经完成了老师的要求,但是真的完成了吗?
这三行代码就好像是刚出生boby,没有自我健全,一旦照顾不周,就可以发生一些不可预料的后果。

如果我们输入汉字,如果我们输入一个数,如果,,,等等等等,我们的程序该如何应对,这就是代码的健全性。
所以为了我们的代码能够很好的运行,请做出错处理。

包括我们今天的主题,也是为了程序的健壮,话就说到这里,下面一起来看正文。


二. 什么是非对称加密算法

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

先说对称加密,二狗想要传递一些甜言蜜语给他的老相好,但是在这个不安全的信息进行加密或解密,例如给每个单词加上某个数,例如I LOVE YOU通过加密变成J MPWF ZPV(实际上,对称加密也没有怎么简单,这里只是简单举例),这样一些无关人员就无法偷窥他们互相交流的信息,同时,加密的信息再也不用像以前一样,躲躲藏藏,随意公开,因为只有双方才能解密。

但是经过时间的推移,二狗的老相好一时大意,将他们约定好的规则泄露了出去,于是他们恋爱的酸臭味又大白于天下。
对称加密,需要对加密和解密使用相同密钥的加密算法。由于其速度快,对称性加密通常在消息发送方需要加密大量数据时使用。在安全性上,对称加密,双方使用的是相同的密钥,也就是说有一方的密钥泄露,整个数据都会被破解。

在现实面前,数据都被破解了,速度快,能加密大量数据,这些优点又有什么用呢,如何能将信息安全的传递呢?这时,我们的主角非对称RSA加密登场了。
非对称性加密算法——RSA算法原理及C++实现
RSA加密,使用两个不同的密钥e和d,将公钥e公布于众,包括老相好在内的其他人,都可以得到这个公钥进行信息加密,但只有二狗自己有一个私钥用于解密。这样,信息的传输比之前的使用的对称加密更加安全了,但是随之而来,又出现了新问题,使用非对称加密,虽然解密比较轻松,但是加密需要的时间比解密多的多,以至于非对称加密只适用于少量数据加密,至于为什么慢,后面会填坑,虽然是实现了非对称加密,但是,这并不是真正的RSA。直到一个被称为迪菲赫尔曼密钥交换的出现,让RSA称为了真正的RSA。

扩展:

1976年以前,所有的加密方法都是同一种模式:加密和解密使用同样规则(简称"密钥"),这被称为"对称加密算法",使用相同的密钥,两次连续的对等加密运算后会回复原始文字,也有很大的安全隐患。对称加密中使用的主要算法有:DES(Data Encryption Standard)、3DES(Triple DES)、AES(Advanced Encryption Standard)、Blowfish等。

1976年,两位美国计算机学家Whitfield Diffie 和 Martin Hellman,提出了一种崭新构思,可以在不直接传递密钥的情况下,完成解密,这就是迪菲赫尔曼密钥交换

1977年,三位数学家Rivest、Shamir 和 Adleman 设计了一种算法,可以实现非对称加密。这种算法用他们三个人的名字命名,叫做RSA算法。从那时直到现在,RSA算法一直是最广为使用的"非对称加密算法"。毫不夸张地说,只要有计算机网络的地方,就有RSA算法。这种算法非常可靠,密钥越长,它就越难破解。根据已经披露的文献,目前被破解的最长RSA密钥是232个十进制位,也就是768个二进制位,因此可以认为,1024位的RSA密钥基本安全,2048位的密钥极其安全,当然量子计算机除外。
非对称加密中使用的主要算法有:RSA、Elgamal、背包算法、Rabin、D-H、ECC(椭圆曲线加密算法)等。

更好的方法是用对称加密加密大量数据,之后将对称加密的密钥进行非对称加密,结合双方优点和缺点,打造更完美的安全性。


三. 双方交换信息工作流程

步骤 描述
1 甲方和乙方发送信息之前,两方都要产生一对用于加密和解密的公钥和私钥。
2 甲方的公钥告诉乙方,私钥保密,乙方的公钥告诉甲方,私钥保密。
3 甲方要给乙方发消息时,甲方用乙方提供的公钥加密信息,之后乙方用自己的私钥解密。
4 对应的,乙方要给甲方发信息时,乙方用甲方提供的公钥加密信息,之后甲方用自己的私钥解密。

四.密钥生成数学原理

知道了双方交换信息的流程,现在来看密钥生成数学原理。

第一步是生成两个质数,什么是质数?

素数是这样的整数,它除了能表示为它自己和1的乘积以外,不能表示为任何其它两个整数的乘积。例如 2,3,5,7,11这一类数。

第二步,求公共模值,也就是第一步生成的两个数的乘积叫做模值。

第三步,求欧拉函数φ(n)。

任意一个正整数n,在小于等于n的正整数中有多少个数与n构成互质关系?计算这个值的方法叫做欧拉函数。
最后推算出来一个公式φ(n) = (p-1)(q-1),p和q分别是第一步生成的两个质数。

参考1https://www.zhihu.com/question/304030251
参考2https://blog.csdn.net/weixin_30399871/article/details/98251483

第四步,求e

e是一个与欧拉函数φ(n)互质的数,且e的取值必须在 1<e<φ(n)之间。

第五步,求模反元素d

什么是模反元素,如果两个整数e和x互质,那么一定可以找到整数d,使得e*d-1被x整除,这里的x就是我们的欧拉函数。
d的取值也不唯一。

第六步,加密

m^e % n = c

第七步,解密

c^d % n = m


五.总结公钥和私钥生成步骤

步骤 说明 描述 备注
1 随机找出两个质数(素数) p ,q 一个大于1的正整数,如果除了1和它本身以外,不能被其他正整数整除,就叫素数
2 计算公共模数 n = p*q
3 欧拉函数 φ(n) = (p-1)(q-1)
4 计算公钥e 1<e<φ(n) 取一个随机整数e,且与φ(n)互为互质数
5 计算私钥d e*d%φ(n)=1 d是模反元素,取值不唯一,满足公式即可
6 公钥加密 m^e % n = c m:明文 c:密文
7 私钥解密 c^d % n = m c:密文 m:明文

现在来给大家举一个例子:

假设 取质数q = 11,p=10

计算公共模数 n = 110

欧拉函数φ(n) = 90

随机找一个与φ(n)互质的整数e = 7

求模反元素 d = 13(这个13也不唯一,符合条件即可)

假设有一个为" 43!1"50(3)+ ”的字符串需要加密

’4‘的ascii码为48+4=52,想要为字符’4’加密,就需要执行m^e % n = c,得到52^7%110=c。

这里有一个需要注意的点,需要加密的m必须小于n,这样公式才能成立。

先来看下52^7等于多少

非对称性加密算法——RSA算法原理及C++实现
这是一个非常大的数,以至于,我必须使用long long的类型来保存该数,并得到剩下的加密字符。
非对称性加密算法——RSA算法原理及C++实现
好景不长,当我进行解密时,我得到了负数,我马上意识到long long也不够了,让我们来看看这个数有多大。

加密后的字母D的ascii码是68,也就意味着这个数是68^13,结果是:
非对称性加密算法——RSA算法原理及C++实现
这个数有24位,而longlong最大只能保存9后面再加18个0,超过了这个数就应该考虑精度问题了。

现在,你应该意识到一个问题,当程序计算步骤6和7的时候,尽管选用了很小的两个素数,尽管是longlong类型,但这依旧无法保证数据不溢出(准确的说是基本上数据都会溢出),在java里面应该有对应的大数处理,但是对于所以C++,抱歉,需要我们自己实现,如何解决大数幂运算?,不论是int类型还是longlong类型,它总会有一个最大值,如果一个类型有最大值,那么就很难不溢出,有没有什么数据类型是不溢出的呢?答案是字符串。


六.解决大数运算

理论上来说,只要你的内存足够,字符串就不会被溢出,将一串数字用字符串的思想表达有两种方式:

一是使用int类型的数组,int类型数值有限,但是int类型数组长度无限,例如使用int a[]={1,2,3,4,5,6};来表示是十二万三千四百五十六。

二是使用string类型来表示,例如 string a=“123456”; 同样可以来表示十二万三千四百五十六。

现在虽然你知道了这种规则,但是计算机不知道啊,你让计算机计算a+a,得出来的结果是”123456123456“,计算机会把a+a当作字符串相加操作。

所以我们要教计算机来识别字符串数值并处理,在这之前,先要缕一缕思路。

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

所谓的幂运算,其本质也就是乘法,再经分解运算还可以得到加法。
所以我们现在来写两个函数,一个用于计算乘法并分解,另一个是将分解的内容进行相加,就得到了我们想要的答案。


1.getCountAdd() 解决大数相加

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; } 

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


2. getCountExp() 解决大数幂运算

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; } 

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


3. getCountmod() 解决大数求余

非对称性加密算法——RSA算法原理及C++实现
最高位开始,有余数就乘以10再加上低位的数继续求余,直到字符串遍历完毕。

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; } 

运行效果:
非对称性加密算法——RSA算法原理及C++实现


七.举个例子

写了怎么多了,现在来举个例子,取q = 19, p = 17, n = 19*17 = 323, φ(n) = 288, e = 5, d = 173。
非对称性加密算法——RSA算法原理及C++实现
我本来是想使用字符类型来保存加密后的字符的,但是一个字符最多255位,图中经过加密的字符在选取的数极小的情况下就可能会超过255,当选取的素数极大时,必然是直接截断,应该这个问题,还耽误了很长时间,所以图中加密字符的显示是改用整形变量来保存的。


八.完整代码

1.随机生成随机数

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

2. 判断是否为质数

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; } 

3. 最大公约数(辗转相除算法)

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

如果返回值为1,则代表两个数互质

4.核心代码

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; } 

创作不易,快来一键三连!

欢迎加入我的官方粉丝群:
非对称性加密算法——RSA算法原理及C++实现

版权声明:玥玥 发表于 2021-04-05 11:37:31。
转载请注明:非对称性加密算法——RSA算法原理及C++实现 | 女黑客导航