- 一. 前言
- 二. 什么是非对称加密算法
- 三. 双方交换信息工作流程
- 四.密钥生成数学原理
- 五.总结公钥和私钥生成步骤
- 六.解决大数运算
- 1.getCountAdd() 解决大数相加
- 2. getCountExp() 解决大数幂运算
- 3. getCountmod() 解决大数求余
- 七.举个例子
- 八.完整代码
- 1.随机生成随机数
- 2. 判断是否为质数
- 3. 最大公约数（辗转相除算法）
- 4.核心代码
一. 前言
最近想模仿一下qq，做一个通信软件，这是qq的登录界面，当我们选择记住密码后，每次运行qq，就会显示已保存的密码，无论是否联网，显然这个密码是保存在本地的，当点击登录，才会去和服务器上的数据库进行比对，那么这个密码显然不能是明文的，一定是经过加密的密文。至于qq用的什么加密方法，这个就无从所知了。
通过百度，发现一个叫非对称性加密算法非常有意思，可以保证数据的安全，所以用了一些时间来学习这个算法，这个算法涉及了大数幂运算，所以还会学习如何设计编写能够处理大数幂运算的函数。
看正题之前，说一些自己的感慨吧。
在一个项目中，实现功能的那一部分代码很少，更多的是对这一功能的维护，如果用户没有按照预期的方式输入数据，那么应该怎样应对，例如下面是张老师给同学出的一道题。 实现一个简单的输入，要求用户输入两个数，然后计算这两个数和，我相信所有人都会写出类似于下面的代码：
代码语言：javascript复制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 | 甲方要给乙方发消息时，甲方用乙方提供的公钥加密信息，之后乙方用自己的私钥解密。 |
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^70=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() 解决大数相加
代码语言：javascript复制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() 解决大数幂运算
代码语言：javascript复制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;
}执行效果
3. getCountmod() 解决大数求余
最高位开始，有余数就乘以10再加上低位的数继续求余，直到字符串遍历完毕。
代码语言：javascript复制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;
}运行效果：
七.举个例子
写了怎么多了，现在来举个例子，取q = 19， p = 17， n = 19*17 = 323， φ(n) = 288， e = 5， d = 173。
我本来是想使用字符类型来保存加密后的字符的，但是一个字符最多255位，图中经过加密的字符在选取的数极小的情况下就可能会超过255，当选取的素数极大时，必然是直接截断，应该这个问题，还耽误了很长时间，所以图中加密字符的显示是改用整形变量来保存的。
八.完整代码
1.随机生成随机数
代码语言：javascript复制long getRandomPrimeNum()
{
long num = 0;
while (true)
{
num = abs(rand()); //随机生成0 - RAND_MAX;
if (isPrimeNum(num))
return num;
}
return 0;
}2. 判断是否为质数
代码语言：javascript复制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. 最大公约数（辗转相除算法）
代码语言：javascript复制long long gcd(long long a, long long b)
{
if (b == 0)return a;
else return gcd(b, a%b);
return 0;
}如果返回值为1，则代表两个数互质
4.核心代码
代码语言：javascript复制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;
}
