图解|什么是RSA算法

一时失言乱红尘 2022-12-03 05:26 253阅读 0赞

# 1. 数学之美和密码学 #

前阵子闲来无事看了会儿《数学之美》，其中第17章讲述了由电视剧《暗算》展开的密码学背后的一些数学原理。

![format_png][]

书中从凯撒密码到二战盟军和日军，讲到密码学中均匀分布&统计独立的基础理论，看得我津津有味，但是其中一些细节没有整明白，于是决定搞篇文章。

![format_png 1][]

# 2. 加密算法的一点历史 #

我们知道常见的加密算法有：**对称加密和非对称加密**，非对称加密是我们今天的主角。

非对称加密不是一蹴而就的，它是1976年之后才出现的，可以说非对称加密是对称加密的优化。

![format_png 2][]

## 2.1 对称加密的缺点 ##

所谓对称加密是指：**发送方使用一种规则对信息进行处理，接收方需要使用相同的规则对信息进行逆向处理**。

![format_png 3][]

对称加密要求通信双方使用**相同的规则和密钥进行加解密**，这样如何妥善保管密钥和规则就非常重要了。

如果密钥泄露那么再强大的对称加密算法也是徒劳的，所以**如何安全地交换对称加密的规则和密钥是短板**。

![format_png 4][]

如何安全地交换密钥呢？让人头疼。

## 2.2 密钥交换算法 ##

1976年两位美国计算机学家 Whitfield Diffie 和 Martin Hellman，**提出了一种崭新构思，可以在不传递密钥的情况下，完成解密**，听着很厉害的样子，这难道就是江湖上传说的隔空打牛？

![format_png 5][]

其实这是被称为 Diffie-Hellman **迪菲-赫尔曼密钥交换算法，**来看看维基百科上两位大神的简介：

![format_png 6][] ![format_png 7][]

这两位大神是密码学的先驱，为非对称加密算法指出了明路：**双方不一定要直接交换密钥**。

迪菲-赫尔曼密钥交换算法中**通信双方并没有真正交换密钥**，而是通过计算生成出一个相同的**共享密钥**，具体的过程还是比较复杂，在此不展开了。

非对称加密算法RSA借鉴了这种思想，**使用公钥和私钥来完成加解密，但是又避免了密钥传输，RSA算法的公钥是公开的，使用公钥加密的信息，必须使用对应的私钥才能解密**。

# 3. RSA算法 #

RSA算法可以说是地球上最重要的算法之一，是数据通信和网络安全的基石。

## 3.1 算法作者 ##

RSA是1977年由罗纳德·李维斯特（Ron Rivest）、阿迪·萨莫尔（Adi Shamir）和伦纳德·阿德曼（Leonard Adleman）一起提出的。

当时他们三人都在麻省理工学院工作，RSA就是他们三人姓氏开头字母拼在一起组成的。

![format_png 8][]

RSA算法密钥越长越难破解，根据相关文献，**目前被破解的最长RSA密钥是768个二进制位。一般认为，1024位的RSA密钥基本安全，2048位的密钥极其安全，RSA算法目前支持4096位长度**。

密钥长度和加解密的时间是成正比的，因此我们需要根据自己的场景来选择密钥长度，不必追求一味长密钥。

## 3.2 算法过程 ##

**RSA算法的本质就是数学**，公钥和私钥是数学上关联的，无须直接传递。

算法过程包括：**密钥生成、密钥加解密**。

![format_png 9][]

### 3.2.1 密钥生成 ###

RSA算法的密钥是成对的，公钥加密私钥解密，来看下这对密钥是如何被计算出来的。

*  **1.随机选择两个质数P和Q**

我们选择P=61，Q=53，计算PQ的乘积N=PQ=61\*53=3233，将N转换为二进制:110010100001，N的二进制长度是12，也就是密钥长度为12。

本文只是阐述算法原理，在实际中密钥长度在1024位以上才安全，12位基本上就是个演示。

*  **2.求N的欧拉函数值M**

欧拉函数的定义：任意给定正整数n，请问在小于等于n的正整数之中，有多少个与n构成互质关系？

欧拉函数有个通用的计算公式：![format_png 10][]

要证明欧拉函数需要分为很多种情况，特别地，**当n是质数时会出现一些特殊的情况**。

直接来个结论:

> a. 如果k是质数，则φ(k) = k-1;  
> b.如果 n = P \* Q，P 与 Q 均为质数，则 φ(n) = φ(P \* Q)= φ(P)φ(Q) = (P - 1)(Q - 1) 。

P=61、Q=53 则N=3233，那么N的欧拉函数记为M=(P-1)\*(N-1) = 60\*52=3120

*  **3.找一个与M互素的整数E**  
    M和E之间除了1以外没有公约数(互质)且E<M，我们随机选择E为17。
 *  **4.找一个整数D，满足如下关系：**  
    (E\*D) mod M = 1，换句话说E和D的乘积除以M的余数为1，这里有一个术语-模逆元，也就是指有一个整数d，可以使得ed被φ(n)除的余数为1。  
    等价于 如下计算过程：

> 当E=17，M=3120，K=1，2，3...时，  
> 17\*D - K\*M = 1，求解这个方程找到一组满足关系的D和K即可，可证其中一组为(D,K)=(2753,15)。

综上所述，我们找到了**通过随机选择的互质的P和Q计算得到N、M、E、D，我们把这些数字分为两组：(E,N)和(D,N)分别为公钥组和私钥组，E是公钥、D是私钥**。

在本例中公钥组为(E,N)=(17,3233)，私钥组(D,N)=(2753,3233)，接下来我们将使用这对密钥进行加解密。

![format_png 11][]

### 3.2.1 加密过程 ###

由于RSA算法本质是数字的运算，因此我们在对字符串进行加密时需要先将字符串数值化，可以借助ascii码、unicode编码、utf-8编码等**将字符串转换为数字**。

需要特别注意转换后的**数字X需要小于密钥组中的N**，如果字符串转换后的数字大于N则需要进行拆分，这可能也是在数据量大时我们使用对称加密算法来加密内容，用非对称加密算法来加密密钥的原因吧。

加密过程满足：

> **X^E mod N = Y**  
> 其中X为明文，E为公钥，N为大整数，Y为密文，mod取余运算。

### 3.2.3 解密过程 ###

我们获得密文Y后，开始解密，过程满足：

> **Y^D mod N = X**  
> 其中Y为密文，D为私钥，N为大整数，X为明文，mod取余运算。

上述的加密和解密过程涉及到了费尔马小定理。

### 3.2.4 欧拉定理和费尔马小定理 ###

这块**有点晦涩**，但是确实RSA算法的核心部分，简单看下吧：

![format_png 12][] ![format_png 13][]

费尔马小定理给出了**素数检测性质**，欧拉对其进行了证明，也就是**费马-欧拉定理**。

## 3.3 RSA算法可靠性分析 ##

经过上面的密钥生成、加解密过程，我们难免要问：**RSA算法可靠吗**？通过公钥组(E,N)能否推导出私钥D呢？

来梳理一下：

*  由于ed≡1 (mod φ(N))，只有知道e和φ(N)，才能算出d，e是公钥匙，所以需要知道φ(N)就可以。
 *  根据欧拉函数 φ(N)=(P-1)(Q-1)，只有知道P和Q，才能算出φ(N)。
 *  N=pq，只有将N进行因数分解，才能算出P和Q。

所以，如果大数N可以被因数分解，私钥D就可以算出，从而破解密文。

## 3.5 大整数因数分解 ##

大整数的因数分解是极其困难的，属于**NPC问题**，除了暴力破解没有很好的解决方案，目前人类分解的最大长度的二进制数为768位，1024位的长度目前尚未破解，因此1024长度的二进制密钥是安全的。

所以**RSA算法的安全性取决于大整数分解的难度**，目前RSA算法可以支持4096位密钥长度，分解难度超乎想象，即使借助于量子计算机难度和时间都是非常非常大的。

![format_png 14][]

# 4. 总结 #

本文从对称加密算法传递密钥安全性为起点，说到迪菲-赫尔曼算法进行密钥交换协商，该算法为RSA算法的公钥和私钥提供了灵感。

麻省理工的三位数学家在欧拉定理&费尔马定理等等一些数学定理的基础上创造了伟大的RSA非对称加密算法。

RSA算法的安全性取决于大数质因数分解的难度，目前而言1024位二进制长度的密钥人类都没有破解，为了安全性考虑可使用2048位长度的RSA密钥进行加密。

确实是烧脑的硬核内容啊，不由得感叹**素数真是个神奇的东西**，段位有限只能抛砖引玉，到此为止啦！

[format_png]: /images/20221123/cdbabcd58a424d0fac2021f833fb38c0.png
[format_png 1]: /images/20221123/49ffe558ab09429fb4ef0f2d4f072e5b.png
[format_png 2]: /images/20221123/c7ccba856c3b4cef878170c414d65e23.png
[format_png 3]: /images/20221123/a573ec5f4604466abfb3f0b21330909a.png
[format_png 4]: /images/20221123/f0e91e67e729442b87e32424e8429f5b.png
[format_png 5]: /images/20221123/762257ffd83f449c87cbc9574e988379.png
[format_png 6]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy93QWtBSUZzMTFxYXhTbkpBZ3FpY2ppYXZTMU5BNll0ZndWWHpkSGZpY3ZjM1Y4Z0NGRWVpY3Rlems3akNQSFN4ODB5V1RFdjNuQWs5cExHOXpvSDlpYko2TE9RLzY0MA?x-oss-process=image/format,png
[format_png 7]: /images/20221123/441ed8279aff4ec6b3c95f59a52b45d8.png
[format_png 8]: /images/20221123/b941ac83ca014074a56a12e1a68012ff.png
[format_png 9]: /images/20221123/abcd1a20a3ad48069d02460bf512f767.png
[format_png 10]: /images/20221123/d87aa4441b31479e974b950e98a94c03.png
[format_png 11]: /images/20221123/227904ee877a407582ac0c6217997d37.png
[format_png 12]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy93QWtBSUZzMTFxYXhTbkpBZ3FpY2ppYXZTMU5BNll0ZndWdERkWVBJN2xDVHRUN1FkdFhuMEc5RTlsNWRhOVJwRzRXS3hudnhNYTJ1aDJobWlhcGxjV1Nidy82NDA?x-oss-process=image/format,png
[format_png 13]: /images/20221123/00d019a2237f4122a4f1c5599a6cfee3.png
[format_png 14]: /images/20221123/dfc1eef87bec48d0b3e47e6bfd80cdea.png