RSA 这俩世纪最重要的算法之一No.91

本文大概1000字，读完共需5分钟

Diffie–Hellman加密算法的劣势

上一篇文章我们聊到 Diffie–Hellman key exchange 这个算法。（密钥交换有点不安全 No.89），虽然可以安全地交换密钥从而使用 AES，DES 等对称加密算法进行加密，但是却有一个天大的问题。就是他娘的，跟一个人通讯就要保存一个密钥，跟一百个人通讯就要保存一百个密钥，A 迟早会崩溃。

密钥崩溃中

RSA 算法的来历

所以科学家就思考，能不能减少密钥的个数呢？？这时候大佬就想到了，街头上的邮筒。

邮筒是一个公开的地方，所有人都可以往里面投递信件（传递信息），但是只有拥有邮筒的邮筒管理员才能打开这个邮筒进行信件的揽收（信息获取）。

虽然这个例子举得不是很恰当啊。但是是大概是这么一个意思，就是能不能将一个公开的加密的密钥分发给其他人，其他人用这个密钥进行加密，而只有拥有私钥的人才能进行解密呢？

来来来 RSA 算法了解一下。

RSA

RSA是1977年由罗纳德·李维斯特（Ron Rivest）、阿迪·萨莫尔（Adi Shamir）和伦纳德·阿德曼（Leonard Adleman）一起提出的。当时他们三人都在麻省理工学院工作。RSA就是他们三人姓氏开头字母拼在一起组成的。

但是呢，其实 RSA 算法并不是1977年被发明的，早在1973年，英国国家通信总局的数学家 Clifford Cocks 就发现了类似的算法，他的研究一被发现，立马被列为绝密，直到1998年才得以公诸于世。

RSA应用

说 RSA 加密算法是上世纪和本世纪最重要的算法之一绝不为过，RSA 是一种基于大数因式分解为保证的非对称加密算法，广泛应用在数字签名、数据加密等领域，是第一个同时能够数据签名以及数据加密的算法。所以其实公钥和私钥是一个相对的概念，大家不要纠结了，这个算法是双向的，用公钥加密的数据，只能用私钥解密。用私钥加密的数据，只能用公钥解密。这样一来一回呢，公钥加密就的数据传输的应用就变成了加密（加密在不安全信道中的数据传输），私钥加密的数据应用就变成了数据签名（检验某个数据是不是真的来自A）。

RSA的工作过程

好了，为了表达我是真的自己搞了一遍，证明过程了解一下。

算法分为五步。

1、选择 p、q两个比较大的质数

2、令n = p * q。取 φ(n) （欧拉函数自行度娘），

3、取 e ∈ 1 < e < φ(n) ，( n , e )为公钥对

4、令 ed mod φ(n) = 1，取得d，( n , d ) 为私钥对。

5、销毁 p、q。密文 = 明文 ^ e mod n ， 明文 = 密文 ^ d mod n

嗯，算法就是这么简单。但是其实可以很简单证明。

(明文 ^ e mod n)^d mod n = (明文 ^ d mod n)^e mod n

RSA如何保证安全？

如何破译？算法如何保证安全？

我们可以看到，经过上面的过程，出现了 p、q、n、φ(n)、e、d 这么多数字。那么如何破解d这个私钥呢？？

step1：e*d mod φ(n) = 1。

如果知道了φ(n)，而e又是公开的，那么d就被解密了。

step2：φ(n) = φ(p * q) = φ(p) * φ(q) = (p-1)(q-1)

好如果知道了 pq，那么φ(n)也是可以计算出来的。

step3：如何知道p、q呢？n = p * q。

将公开数据 n 进行因式分解就可以得到 p、q了。但是现在大数因式分解都是一个世界大难题。所以RSA只要密钥不泄露，那么信息就是安全的。

RSA为什么可以被加解密？

下面证明一下为什么上边的算法可以进行加解密。假设明文为 m（message），密文为 c (crypted)。

加密过程

c = m ^ e mod n

解密过程：

m

= c ^ d mod n（代入c）

= (m ^ e mod n)^ d mod n（进行模计算变换）

= m ^ (e * d) mod n

∵ e * d mod φ(n) = 1

∴e * d = k * φ(n) + 1 （k为整数）

∴

m

= m ^ (k * φ(n) + 1) mod n

= m ^ (k * φ(n)) * m mod n

若m与n互质，那么m ^ (k * φ(n)) mod n = 1 （欧拉公式）

那么上式子 可得直接等于 m。原题得证。RSA 原始论文也只讨论了m与n互质的情况，但是阮一峰老师还证明了另外一种情况，就是 m与n 如果不互质呢？？这种情况我上面也证明了，感兴趣的小伙可以了解一下。