RSA加密：非对称密钥，公开密钥算法

RSA 加密，利用了单向函数正向求解很简单，反向求解很复杂的特性。

具体是利用了：

1. 对两个质数相乘容易，而将其合数分解很难的这个特点进行的加密算法。

   n=p1*p2，已知 p1、p2 求 n 简单，已知 n 求 p1、p2 困难。

2. (m^e) mod n=c，已知 m、e、n 求 c 简单，已知 e、n、c 求 m 很难。

   RSA 加密，实现了公开密钥，就是 A 可以给所有人发送锁，其他人把要加密的信息用这把锁加密后发送给 A，A 用自己的钥匙开锁就可以获得加密的信息了。反过来，A 要发送加密信息给 B，只要知道 B 的锁就可以了，而这个锁是公开的。

公开密钥 n、e 的生成：

随机选取两个质数 p1、p2，n=p1*p2，再随机选取一个整数 e，e 与φ(n) 互质。

加密过程：(m^e) mod n=c，其中 m 为原信息，c 为加密信息，n、e 为公开密钥。

解密过程：(c^d) mod n=m，其中 d 为解密密钥。

解密密钥 d 的求解：

(c^d) mod n=(((m^e) mod n)^d) mod n=((m^e)^d) mod n=(m^ed) mod n=m ①

根据费马定理 (m^φ(n)) mod n≡1，又 1^k≡1，所以 (m^k*φ(n)) mod n≡1，两边同乘以 m 得

m*((m^k*φ(n)) mod n)≡1*m，化简 (m^(k*φ(n)+1)) mod n≡m ②

由①、②得 ed=(k*φ(n)+1)，解得 d=(k*φ(n)+1)/e。
费马定理：若 p 是素数，a 与 p 互素，则 a^(p-1）≡1 （mod p）

过程如下：

A：有一个公钥 n、e。例如：3127、3。
B：有一个信息 m。例如：89。
C：偷听者

A：
第一步：随机找两个质数 p1、p2，一个奇数 e。例如：53、59、3。
第二步：计算 n=p1*p2 得到 n，计算欧拉函数φ(n)=(p1-1)*(p2-1) 得到φ(n)，计算钥匙 d=(k*φ(n)+1)/e 得到 d。例如：53*59=3127、(53-1)*(59-1)=3016、(k*φ(n)+1)/e=(2*3016+1)/3=2011。
第三步：发送 n、e 给大家知道

n、e 就是公钥也做锁，d 就是 n、e 的钥匙。

C：获得 n、e

B：
第一步：获得 n、e
第二步：加密信息 m，(m^e) mod n=c，获得加密信息 c。例如：(89^3) mod 3127=1394。
第三步：发送 c 给 A

C：
第一步：截获加密信息 c
第二步：破解信息 c，此时 C 只有 n、e、c，只有把 n 分解质因数才能破解，而此分解很困难特别是当 n 很大的时候。

A：
第一步：收到加密信息 c
第二步：解密信息 c，(c^d) mod n=m，获得信息 m。例如：(1394^2011) mod 3127=89。

完成