文章目录

一. 前言二. 什么是非对称加密算法三. 双方交换信息工作流程四.密钥生成数学原理五.总结公钥和私钥生成步骤六.解决大数运算1.getCountAdd() 解决大数相加2. getCountExp() 解决大数幂运算3. getCountmod() 解决大数求余 七.举个例子八.完整代码1.随机生成随机数2. 判断是否为质数3. 最大公约数（辗转相除算法）4.核心代码

一. 前言

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

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

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

在一个项目中，实现功能的那一部分代码很少，更多的是对这一功能的维护，如果用户没有按照预期的方式输入数据，那么应该怎样应对，例如下面是张老师给同学出的一道题。

实现一个简单的输入，要求用户输入两个数，然后计算这两个数和，我相信所有人都会写出类似于下面的代码：

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

这三行代码已经完成了老师的要求，但是真的完成了吗？

这三行代码就好像是刚出生boby，没有自我健全，一旦照顾不周，就可以发生一些不可预料的后果。

如果我们输入汉字，如果我们输入一个数，如果，，，等等等等，我们的程序该如何应对，这就是代码的健全性。

所以为了我们的代码能够很好的运行，请做出错处理。

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

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

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

但是经过时间的推移，二狗的老相好一时大意，将他们约定好的规则泄露了出去，于是他们恋爱的酸臭味又大白于天下。

对称加密，需要对加密和解密使用相同密钥的加密算法。由于其速度快，对称性加密通常在消息发送方需要加密大量数据时使用。在安全性上，对称加密，双方使用的是相同的密钥，也就是说有一方的密钥泄露，整个数据都会被破解。

在现实面前，数据都被破解了，速度快，能加密大量数据，这些优点又有什么用呢，如何能将信息安全的传递呢？这时，我们的主角非对称RSA加密登场了。

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，5，7，11这一类数。

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

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

任意一个正整数n，在小于等于n的正整数中有多少个数与n构成互质关系？计算这个值的方法叫做欧拉函数。

最后推算出来一个公式φ(n) = (p-1)(q-1)，p和q分别是第一步生成的两个质数。

参考1/question/304030251

参考2/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

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

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

假设 取质数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等于多少

这是一个非常大的数，以至于，我必须使用long long的类型来保存该数，并得到剩下的加密字符。

好景不长，当我进行解密时，我得到了负数，我马上意识到long long也不够了，让我们来看看这个数有多大。

加密后的字母D的ascii码是68，也就意味着这个数是68^13，结果是：

这个数有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当作字符串相加操作。

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

所谓的幂运算，其本质也就是乘法，再经分解运算还可以得到加法。

所以我们现在来写两个函数，一个用于计算乘法并分解，另一个是将分解的内容进行相加，就得到了我们想要的答案。

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

执行效果

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

string getCountExp(int a, int b){//计算a^bstring 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 * a1int 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;}

执行效果

3. getCountmod() 解决大数求余

最高位开始，有余数就乘以10再加上低位的数继续求余，直到字符串遍历完毕。

int getCountMod(string a, int b){int bit = -1; //判断是否需要进位//例如4255%5int 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;}

运行效果：

七.举个例子

写了怎么多了，现在来举个例子，取q = 19， p = 17， n = 19*17 = 323， φ(n) = 288， e = 5， d = 173。

我本来是想使用字符类型来保存加密后的字符的，但是一个字符最多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;}

创作不易，快来一键三连！

欢迎加入我的官方粉丝群：