发展历史

在1976年以前，所有的加密方法都是同一种模式：加密、解密使用同一种算法。在交互数据的时候，彼此通信的双方就必须将规则告诉对方，否则没法解密。那么加密和解密的规则（简称密钥），它保护就显得尤其重要。传递密钥就成为了最大的隐患。这种加密方式被成为对称加密算法（symmetric encryption algorithm）

1976年，两位美国计算机学家 迪菲（W.Diffie）、赫尔曼（ M.Hellman ） 提出了一种崭新构思，可以在不直接传递密钥的情况下，完成密钥交换。这被称为“迪菲赫尔曼密钥交换”算法。开创了密码学研究的新方向

1977年三位麻省理工学院的数学家 罗纳德·李维斯特（Ron Rivest）、阿迪·萨莫尔（Adi Shamir）和伦纳德·阿德曼（Leonard Adleman）一起设计了一种算法，可以实现非对称加密。其加密方式比较特殊，需要两个密钥：公开密钥简称公钥（publickey）和私有密钥简称私钥（privatekey）。公钥加密，私钥解密；私钥加密，公钥解密。这个算法用他们三个人的名字命名，叫做RSA算法。

RSA的数学原理

RSA加密算法是通过欧拉定理、费马小定理、模反元素推导出来的

互质关系：如果两个正整数，除了1以外，没有其他公因数，我们就称这两个数是互质关系

任意给定正整数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

计算56的欧拉函数

φ(56) =  φ(8) *  φ(7) = 4 * 6 = 24

欧拉函数特点

一、当n是质数的时候，φ(n)=n-1。

二、如果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)  mod  n  ≡  1

费马小定理：欧拉定理的特殊情况：如果两个正整数m和n互质，而且n为质数！那么φ(n)结果就是n-1。m^(n-1)  mod  n  ≡  1

模反元素：如果两个正整数e和x互质，那么一定可以找到整数d，使得 ed-1 被x整除。

那么d就是e对于x的“模反元素”

公式转换：

公式转换

明文m经过一系列的运算之后又变成了m  如果可以发公式拆分 第一步运算得到一个中间值c  c经过第二步运算得到m 那么c就可以当成m的密文  第一步就是加密过程 第二步就是解密过程

迪菲赫尔曼秘钥交换

迪菲赫尔曼秘钥交换：场景为客户端和服务器需要生成一个对称加密的秘钥用于数据传输，如果直接发送秘钥给客户端，第三方很容易窃取到，迪菲赫尔曼通过拆分前面公式找到了解决方案，服务器和客户端约定使用3和17  1.服务端生成一个随机数15 使用公式得到6 发送给客户端 2.客户端生成一个随机数13 通过公式得到12 发送给服务器 3.客户端通过自己生成的随机数13 和 服务器返回的6 得到秘钥10  服务器通过自己生成的随机数15 和客户端发送的6 也可以得到秘钥10而黑客只能截取到 6  和 12 无法推导出秘钥10  就算黑客知道3 和 17 但是得不到 13 和 15 也是很难得到秘钥10的

原理：

迪菲赫尔曼秘钥交换原理

RSA算法：

m^e mod n = c 加密

c^d mod n = m 解密

公钥：n和e

私钥：n和d

明文：m

密文：c

说明：

1、n会非常大，长度一般为1024个二进制位。（目前人类已经分解的最大整数，232个十进制位，768个二进制位）

2、由于需要求出φ(n)，所以根据欧函数特点，最简单的方式n 由两个质数相乘得到: 质数：p1、p2

Φ(n) = (p1 -1) * (p2 - 1)

3、最终由φ(n)得到e 和 d 。

总共生成6个数字：p1、p2、n、φ(n)、e、d

关于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因数分解才能算出。