文章目录
一. 前言二. 什么是非对称加密算法三. 双方交换信息工作流程四.密钥生成数学原理五.总结公钥和私钥生成步骤六.解决大数运算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;}
创作不易,快来一键三连!
欢迎加入我的官方粉丝群: