关于RSA，你了解它吗？
说起RSA，可能很多人都或多或少了解过，看到了它，脑子里就打印出几个字“一种加密算法”，但真正让你讲出其原理呢？额...好像它变陌生了。哈哈，此时你就不得不静下心来问自己，真的了解它吗？
只要有战争，就会有密码，加密方式也就随之出现。提及RSA，就不得不说一下密码学。密码学的历史大致可以追溯到两千年前，相传古罗马名将凯撒大帝为了防止敌方截获情报，用密码传送情报。凯撒的做法很简单，就是对二十几个罗马字母建立一张对应表。这样，如果不知道密码本，即使截获一段信息也看不懂。
•在1976年以前，所有的加密方法都是同一种模式：加密、解密使用同一种算法。在交互数据的时候，彼此通信的双方就必须将规则告诉对方，否则没法解密。那么加密和解密的规则（简称密钥），它保护就显得尤其重要。传递密钥就成为了最大的隐患。这种加密方式被成为对称加密算法（symmetric encryption algorithm）
•1976年，两位美国计算机学家迪菲（W.Diffie）、赫尔曼（M.Hellman）提出了一种崭新构思，可以在不直接传递密钥的情况下，完成密钥交换。这被称为“迪菲赫尔曼密钥交换”算法。开创了密码学研究的新方向
•1977年三位麻省理工学院的数学家罗纳德·李维斯特（RonRivest）、阿迪·萨莫尔（AdiShamir）和伦纳德·阿德曼（LeonardAdleman）一起设计了一种算法，可以实现非对称加密。这个算法用他们三个人的名字命名，叫做RSA算法，RSA也就由此而来。
RSA的数学原理
说到了数学原理，大家可曾还记得以前学过的欧拉函数？不记得了？没关系，继续往下看。
首先在这里，我们一起回忆以下几个概念：
如果两个正整数，除了1以外，没有其他公因数，我们就称这两个数是互质关系（coprime）。
那么
任意给定正整数n，请问在小于等于n的正整数之中，有多少个与n构成互质关系呢？
其实呀，计算这个值的方式就叫做欧拉函数，使用：Φ(n)表示（此函数以其首名研究者欧拉命名）
如:
计算8的欧拉函数，和8互质的1、2、3、4、5、6、7、8 φ(8) = 4
计算7的欧拉函数，和7互质的1、2、3、4、5、6、7 φ(7) = 6
可是当这个正整数n过大的时候，怎么去计算呢？显然口算是很难的，这个时候我们也发现了一些特殊对应关系：
如计算56的欧拉函数
φ(56) = φ(8) * φ(7) = 4 * 6 = 24（ps：不信的同学可以自己列出来去数一数哦，但要认真别数错了）
可以看出，欧拉函数是由一些特点的
欧拉函数特点
1、当n是质数的时候，φ(n)=n-1。
2、如果n可以分解成两个互质的整数之积，如n=A*B则： φ(A*B)=φ(A)*φ(B)
根据以上两点得到：
如果N是两个质数P1和 P2的乘积则
φ(N)=φ(P1)*φ(P2)=(P1-1)*(P2-1)
欧拉定理
如果两个正整数m和n互质，那么m的φ(n)次方减去1，可以被n整除。
还有一个欧拉定理的特殊情况：
费马小定理（这个你自己可以随便举些例子验证）
如果两个正整数m和n互质，而且n为质数！那么φ(n)结果就是n-1。
现在我们来进行一些列公式转换
此时，我们先记录下此转换结果；
模反元素
如果两个正整数e和x互质，那么一定可以找到整数d，使得 ed-1 被x整除。那么d就是e对于x的模反元素
因为e*d 一定是x的倍数加1，所以在此转换一次：
此时，想起之前我们转换的结果
此时我们发现了两个公式有一定的关系，因此最终转换
此公式成立的前提是：1.d是e相对于(n)的模反元素（
(n)就相当于x ）;
2.m < n
我们也可以用python3（做运算很方便哦）来验证一下下：
m经过一些列运算后仍得m，那么是不是嗅出了一丝加密的味道呢？
mod n
m :
（加密）
C mod n = m （解密）
这样会出现一个问题：加密的结果C会非常大
那么如何有效的拆分这个公式呢
迪菲赫尔曼密钥交换
此图中客户端和服务器约定了一个数17得到它的源根3，
客户端取随机数13、服务器取随机数15；
客户端将通过运算将加密的结果12传递给服务器；而服务器通过运算将6传递给客户端；
我们可以知道通过传递的只有12和6两个数字，黑客就算截获后由于不知道私密数据13和15，所以他是没有办法得到10的
交换原理
说明：
公钥：n和e
私钥： n和d
明文: m
密文: c
关于RSA的安全：
除了公钥用到了n和e其余的4个数字是不公开的。
目前破解RSA得到d的方式如下：
1、要想求出私钥 d 。由于e*d=φ(n)*k+1。要知道e和φ(n);
2、e是知道的，但是要得到 φ(n)，必须知道p1和 p2。
3、由于 n=p1*p2。只有将n因数分解才能算出。
因此
n会非常大，长度一般为1024个二进制位。（目前人类已经分解的最大整数，232个十进制位，768个二进制位），这样就保证了RSA的可靠性。
最后由于RSA计算量比较大，进而效率低，适合加密小数据类型的文件。（ps：RSA通常用来加密密钥、数字签名等）。
以上就是本人对RSA的理解归纳，如果有误烦请指出哟。
