关于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的模反元素

这里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的理解归纳，如果有误烦请指出哟。