RSA加密

RSA背景

在1976年以前，传统的加解密过程是:

1、A采用某种手段对数据进行加密。

2、数据传输到B的手中。

3、B逆向的实施A加密采用的步骤。

4、数据被还原。

这就是所谓的对称加密。

解密和加密的互为彼此的逆过程。加密的人必定知道解密的手段。解密的人也必定知道加密的手段。

这种加解密手段的最大特点就是对称（易于操作），但这也正是它的最大缺点。因为加密方，必须将加密规则告知解密方。

这就造成两个问题:

1、加解密规则定期就要更新，如何将加解密规则顺利的告诉对方。

2、如何安全的保存加解密规则。因为只要有一方将加解密规则泄露。那么这种加密手段就可以说被破解了。

基于此，在1976年由两位美国计算机科学家提出了一种全新的思路（"Diffie-Hellman密钥交换算法"），即采用公钥-私钥对的形式进行加解密。

1、解密方生成一对密钥：公钥-私钥对。两者不存在互相推导出彼此的可能。

2、公钥随普通网络到达加密方，私钥则始终保留在解密者手中。

3、加密方使用公钥将文件转为密文

4、将密文传输给解密方。

5、解密方使用私钥将密文转为明文，完成解密。

由于公钥和私钥在逻辑上无法互相推算出彼此。这样只要私钥不被泄露，那么密文就不会解密。基于此对称加密的第一个问题的风险被解决，第二个问题的风险被缩小了一半。

受这种思路的启发，在次年，也就是1977年，由三位数学家（Rivest、Shamir 和 Adleman ）联合发表了RSA算法，算法名称的来源是三位科学家的首字母的和。在随后的几十年，RSA加密算法，在密码领域中大放异彩，成为非对称加密的代表加密算法。并且随着密钥长度的不断增加，以当下的计算机运算水平，是不可能在有限的时间下，暴力破解出密钥，而攻破该算法的。

RSA加密算法的实现逻辑

在RSA算法中，需要存在五个重要的数字元素：

　　p、q：这是随机选取的两个不相等质数

　　n：n=p*q，也就是p和q的乘积

　　φ(n)：φ(n) = (p-1)(q-1) ，也就是p-1和q-1的乘积

　　e：随机选取一个和φ(n)互质的正整数。并且保证 e < φ(n)

d：根据ed ≡ 1 (mod φ(n))，计算出对于φ(n)的模反元素d

ed ≡ 1 (mod φ(n)) 的含义是，ed整除φ(n)之后，余数为1。

也就是ed=k*φ(n)+1

可以看作

ed=φ(n)x+1最终利用辗转相除法（看了一下网上的推导逻辑，觉得纯数学领域了，纯记住意义不大），可以计算出一组满足的解(d,x)。

这样(n,e)是公钥，(n,d)是私钥。

由于e，d的推导是依赖的φ(n)的，而φ(n)的值来自于p、q。p、q尽管是随机取得的，但是可以由n因式分解而成。因此n的因式分解速度就成为整个解密的瓶颈。n的因式分解换言之，类似于判断n是否是质数，目前除去不断的暴力尝试，并没有好的办法。目前已知的最大分解数目的量级是10^232,占768bit位，所以一旦n突破了768位，就可以说很难破解了。（但是据说量子计算机非常适合于计算因式分解，可惜现在还是雏形）

知道了，公钥和私钥的生成后。来看下公钥私钥是如何使用的：

1、将原始信息转化为数字：无论是ascii码值，还是Unicode码，或者是其他base64转码等等，生成数字序列之后。依次循环按照下文进行加密：

公钥(n,e)、原文m

m^e ≡ c (mod n)

换言之c等于m^e除以n的余数

也就是计算出密文c

2、将密文发送给解密者，解密者依次按照下文进行还原

c^d ≡ m (mod n)公式

换言之m等于c^d除以n的余数

反向求出m即为明文

证明过程这里就忽略了，有兴趣的可以看下阮一峰写的RSA加密博客。里边的算式推理比较严谨。

此外有一点需要说明的是，在公钥加密的过程中，需要m小于n，如果在加密的过程中，发现有元素比公钥的n还要大，则需要将原文进行切割成更小的元素，然后再进行加密。

其它

另外最近流行面非常广的病毒“永恒之蓝”，始于欧洲，通过网络传播了半个世界的勒索病毒，其核心的思路就是将RSA公钥传播到本机，接着用RSA公钥加密本地文件。使本地文件不可被正常使用，进而勒索机主。待勒索成功后，只要将私钥文件再发送到本机对文件进行解密即可。思路简单，但是非常有效，难以破解，每台机器的私钥文件也几乎不会相同。