前言：之前在做密码学题的时候了解了一下RSA，但总感觉那时总结的过少，而且也理解的不到位，这次就再来详细的了解一下，并通过做题来巩固一下。
一、对称加密与非对称加密
对称加密：
加密和解密用的是同一密钥，也是最简单、最快速的加密方式，通常使用的密匙相对较小，容易被破解，如果密钥过大，安全性确实可以得到保证，但同样加密和解密的效率将会很低。
因为双方都需要密钥进行加密解密，如果有一方的密钥泄露出去，整个安全性将不复存在，所以这也是对称加密的缺点。
非对称加密：
相较于对称加密，非对称加密使用两个密匙，即公开密钥和私钥密钥。
非对称加密很有趣，公钥是任何人都可以请求得到的，但私钥只有一个人持有，而且用公钥加密的密文只能通过私钥来解开，解密者无需像对称加密一样接收加密者的密钥，而是自己保存一个密钥，这样就不在网上传送密匙，不会被拦截，会更加安全，但是相对于对称加密，非对称加密加密和解密的效率会低一些
下面就来学习属于非对称加密中的RSA算法
RSA概述：
1977年，三位数学家Rivest、Shamir 和 Adleman 设计出RSA算法，可以实现非对称加密。而在此之前，使用的都是对称加密。
RSA算法涉及的数学知识
了解RSA之前，需要了解一些数学知识
一、互质关系
两个正整数，除1以外，没有其他公因子，那么这两个数就是互质关系。
例如：30与7就是互质关系，但是30不是质数，这就是说明不是质数也能构成互质关系
由互质关系能得出以下结论：
- 任意两个质数构成互质关系，比如7和61。
- 一个数是质数，另一个数只要不是前者的倍数，两者就构成互质关系，比如3和10。
- 如果两个数之中，较大的那个数是质数，则两者构成互质关系，比如97和57。
- 1和任意一个自然数是都是互质关系，比如1和99。
- p是大于1的整数，则p和p-1构成互质关系，比如57和56。
- p是大于1的奇数，则p和p-2构成互质关系，比如17和15。
二、欧拉函数
在数论，对正整数n，欧拉函数是小于n的正整数中与n互质的数的数目，以φ(n)表示
其实欧拉函数就是用来计算这样一个问题
任意给定正整数n，在小于等于n的正整数之中，有多少个与n构成互质关系？
举个列子：
在1—10中，与10互质的有1、3、7、9，即φ(n)=4
通过欧拉函数又衍生出几种情况：
第一种情况： 如果n=1，则
φ(1) = 1。因为1与任何数（包括自身）都构成互质关系。
第二种情况： 如果n是质数，则φ(n)=n-1。因为质数与小于它的每一个数，都构成互质关系。比如7与1、2、3、4、5、6都构成互质关系。
其中对RSA最重要的一种情况就是：
如果n可以分解成两个互质的整数之积
n = p1 × p2
则
φ(n) = φ(p1p2) = φ(p1)φ(p2)
通过这个公式可以看出积的欧拉函数等于各个因子的欧拉函数之积
举个列子：
n=21
n=3*7
φ(n) = φ(p1p2) = φ(3)φ(7)=2*6=12
三、欧拉定理
欧拉定理表明，若
n,a为正整数，且n,a互质，则以下公式成立：
换句话就是a的φ(n)次方被n除的余数为1或者是a的φ(n)次方减去1，可以被n整除。
举个列子：
例如：2和5互质，φ(5)=4，则2的4次方(16)减1,15恰好被n(5)整除
欧拉定理还有一个特殊情况：
如果
正整数a与质数p互质，因为质数p的φ§等于p-1，则欧拉定理可以写成：
四、模反元素
如果两个正整数a和n互质，那么一定可以找到整数b，使得 ab-1 被n整除，或者说ab被n除的余数是1。这时，b就叫做a的“模反元素”。
举个列子：
a=3,n=4
(3*b-1)%4=0
故b=7或b=3
显然模反元素不止一个，即如果b是a的模反元素，则 b+kn 都是a的模反元素（k为正整数）
可以看出，a的 φ(n)-1 次方，就是a对模数n的模反元素
五、模运算
让m去被n整除，只取所得的余数作为结果，就叫做模运算。
举个例子：
10 mod 4=2、8 mod 3=2
六、同余
给定一个正整数m，如果两个整数a和b满足a-b能被m整除，即(a-b) mod m=0，
那么就称整数a与b对模m同余，记作a≡b (mod m)，同时可成立a mod m=b
而且同余与模运算是不同的
a≡b (mod m)仅可推出b=a mod m
七、欧几里德算法
欧几里德算法是用来求两个正整数最大公约数的算法
计算公式gcd(a,b) = gcd(b,a mod b)
计算方法：
用较大数除以较小数，再用出现的余数（第一余数）去除除数，再用出现的余数（第二余数）去除第一余数，如此反复，直到最后余数是0为止
计算流程图为：
需要的数学知识已经了解完了，接下来就来学习RSA
RSA算法
（一）、生成密钥过程：
一、随机选择两个不相等的质数p和q
二、计算p和q的乘积n
三、计算n的欧拉函数φ(n)
四、随机选择一个整数e，条件是1< e < φ(n)，且e与φ(n) 互质
五、计算e对于φ(n)的模反元素d
六、将n和e封装成公钥，n和d封装成私钥
下面就通过一个列子来执行一遍
一、选取两个不相等的质数p=11 q=13
二、n=p*q=143
三、φ(n)=(p-1)(q-1)=10*12=120
四、从1<e<60, 随机选取一个e,这里选取7
五、根据欧拉定理 e*d ≡ 1 (mod φ(n))，该公式又可转化为e*d - 1 = kφ(n)
所以7*d+120*k=1,这个方程可以由扩展欧几里得算法（辗转相除法）来得出结果：
六、120 = 7 * 17 + 117 = 17 * 1//余数放前面1 = 120 * 1 + 7 * (-17)1 = 120 * 1 + 7 *(-17)故d = -17 k = 1在RSA中d必须是正整数，所以将它翻转d=120 + （-17）=103故公钥为（n,e）=(143,7)私钥为（n,d）=(143,103)
（二）、加密解密过程
求出公钥和私钥，就可以对信息进行加密和解密
一、通过公钥进行加密（n,e）
设明文为M，密文为C，则加密公式为：
假设明文为13，则
M^e ≡ c (mod n)
13^7 = 117 (mod 143)
二、通过私钥进行解密（n,d）
密文为C，明文为M，则解密公式为：
C^d ≡ M (mod n)
117^103 = 13 (mod 143)
换句通俗的话说C的d次方除以n的余数为M
(三)、RSA安全性
在已知n和e的情况下即（公钥），能否推导出d？
（1）ed≡1 (mod φ(n))。只有知道e和φ(n)，才能算出d。（2）φ(n)=(p-1)(q-1)。只有知道p和q，才能算出φ(n)。（3）n=pq。只有将n因数分解，才能算出p和q。
但现实生活中，不可能跟我们举例子一样那么小，而且大整数的因数分解，是一件非常困难的事情，例如：
1230186684530117755130494958384962720772853569595334792197322452151726400507263657518745202199786469389956474942774063845925192557326303453731548268507917026122142913461670429214311602221240479274737794080665351419597459856902143413
没法对这个整数进行因数分解，过于大了，而且目前破解的只有暴力破解，所以RSA才号称是地球上最安全的算法。
总结：这次总结更加详细的了解了RSA的原理以及涉及的数学原理，接下来就通过做题来进行巩固。
参考博客：
RSA算法基础详解
RSA算法原理（二）
RSA超详细讲解
