bg-pic

最近在公司项目中遇到了需要用RSA加密用户token的场景，在完成需求的同时，自己也向外进行发散，研究学习了数据加密方面的知识，收获很多，因此决定整理记录下来

数据加密的一点历史

在开始正文前，先聊一聊关于数据加密的发展史，拓展一下视野

在1976年以前，所采用的加密方式都是对称加密，即加密与解密信息都是用同一个秘钥。因为这种特性，所以发送方在传递信息前，需要先将秘钥发送给接受方之后才能真正开始发送数据，因此秘钥的传输与管理就显得异常重要。由于存在发送秘钥的行为，因此始终存在秘钥泄露的风险，所以这种算法的安全性是比较低的

但是俗话说的好：办法总比困难多，所以在1976的时候，两位美国计算机学家 Whitfield Diffie 和 Martin Hellman，提出了一种崭新构思，可以在不直接传递密钥的情况下，完成加解密过程，这被称为Diffie-Hellman密钥交换算法，这种算法的思路如下：

这便是如今鼎鼎大名的RSA算法的灵感来源，因为在1977年，三位数学家Rivest、Shamir、Adleman就设计出了它，而这种算法就是用他们三个人的名字的首字母命名的

bg-pic

这种算法之所以可靠，是因为它基于一个共识：寻求两个大素数比较简单，而将它们的乘积进行因式分解却极其困难。在正文中，我会详细讲解RSA的实现原理，现在先点到为止啦~

接下来开始正文吧~

加密算法的类型

总的来看，加密算法分为三大类：

下面针对每一种类型进行详细说明

对称加密

对称加密算法的常见种类有：

对称加密算法又称为共享密钥加密算法，在该使用场景下，通信双方持有的是同一个密钥，该密钥同时承担着加密与解密的职责。此算法的优缺点很明显，优点是加解密效率高，缺点是密钥一旦泄漏，那么就会存在信息被破解的风险，一般不会单独使用该算法，而是配合非对称加密一起使用

非对称加密

非对称加密算法的常见种类有：

非对称加密算法实现机密信息交换的基本过程是：甲方生成一对密钥并将公钥公开，需要向甲方发送信息的其他角色(乙方)使用该密钥(甲方的公钥)对机密信息进行加密后再发送给甲方，甲方再用自己私钥对加密后的信息进行解密。甲方想要回复乙方时正好相反，使用乙方的公钥对数据进行加密，同理，乙方使用自己的私钥来进行解密。非对称加密算法强度复杂、安全性高，但是正是由于这种特性而使得加密和解密的速度没有对称加密算法快，在某些极端情况下，甚至能比对称加密慢上1000倍

非对称加密不要求通信双方事先传递密钥或有任何约定就能完成保密通信，并且密钥管理方便，可实现防止假冒和抵赖，因此，更适合网络通信中的保密通信要求

散列算法

散列算法的常见种类有：

散列算法的特点如下：

散列算法通常用于数字签名，用户登录、修改密码的场景，这里多说一句，在用户登录和修改密码的场景中，不要只单纯地对密码进行md5，而是应该将密码与盐(一个随机字符串)进行结合后再进行md5运算(形如：result = md5(password + sault)),这样就保证了即使黑客通过消息摘要破解得到了原始信息，但是由于盐的存在，那么也就无法知晓用户真正的密码，从而提高了网站的安全性

深入研究RSA算法原理

接下来将详细讲解RSA算法是如何实现非对称加密的，其中会涉及到一些数论知识，但相信对于聪明的你来说都是小case啦～

bqb

一点数论知识背景

这一节先把一些必知必会的数论知识罗列出来，因为只有打好地基，咱们才能真正掌握其中的原理

质数又称素数，一个大于1的自然数，除了1和它自身外，不能被其他自然数整除的数叫做质数，否则称为合数（规定1既不是质数也不是合数），从质数的定义中可以很容易地推导出所有的质数都是奇数的结论

如果两个正整数，除了1以外，没有其他公约数，那么这两个数就是互质关系（coprime），比如4和7没有公约数，所以它们是互质关系。我们可以从中得到以下结论： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

1. 任意两个质数构成互质关系，比如3和7

2. 一个数是质数，另一个数只要不是前者的倍数，两者就构成互质关系，比如3和10

3. 如果两个数之中，较大的那个数是质数，则两者构成互质关系，比如5和4

4. 1和任意一个自然数是都是互质关系，比如1和10

5. p是大于1的整数，则p和p-1构成互质关系，比如4和3

6. p是大于1的奇数，则p和p-2构成互质关系，比如7和5

7. 质数与非质数也可以形成互质关系

欧拉函数的用途是求出小于等于正整数n的所有正整数中与n互质的数的数量，以 φ(n) 表示

举个栗子，当n=4时，小于等于4并且与4互质的正整数有：1、3，所以φ(4) = 2

φ(n)的求值过程很简单，但是我们可以从中推导出一些既定的结论，从而可以更好地帮助我们理解原理，列举如下

1
2
3
4
5
6
7

1. 如果n=1，则 φ(1) = 1 ,因为1与任何数（包括自身）都构成互质关系

2. 如果n是质数，则 φ(n)=n-1 ,因为质数与小于它的每一个数，都构成互质关系。比如5与1、2、3、4都构成互质关系

3. 如果n可以分解成两个互质的整数之积，既 n = p1 × p2，那么 φ(n) = φ(p1p2) = φ(p1)φ(p2)，即积的欧拉函数等于各个因子的欧拉函数之积

上述的欧拉函数是用于欧拉定理的推导，我们来看下欧拉定理的具体定义：若n, a为正整数，且n，a互质，则:a^φ(n) mod n = 1,翻译一下就是说若n, a为正整数，且n，a互质，那么a的φ(n)次方模上n恰好余1。

这里拓展一下欧拉定理与费马小定理的关系，我们从上文知道当n是质数时，φ(n)=n-1，那么我们就可以推导出如下变形公式：a^φ(n) mod n = 1 => a^(n-1) mod n = 1,这个变形公式也就是费马小定理所推导出来的，可以看出费马小定理是欧拉定理中n为质数时推导而来

欧拉定理是RSA算法的核心，所以一定要掌握它

如果两个正整数a和b互质，那么一定可以找到整数c，使得 ac-1 被b整除，或者说ac被b除的余数是1，既ac mod b = 1，那么c就叫做a的模反元素

举个栗子，比如3和11互质，那么3的模反元素就是4，因为 (3 × 4)-1 可以被11整除。显然，模反元素不止一个，4加减11的整数倍都是3的模反元素 {…,-18,-7,4,15,26,…}，即如果c是a的模反元素，则c+kb都是a的模反元素

相关的数论知识都已经罗列了出来，这些理论一定要吃透，我们才能真正去掌握RSA算法的原理，接下来将讲解RSA算法加解密的具体过程以及原理，相信你已经准备好了，那么就开始吧～

bqb

深入RSA算法加解密的过程与原理

本节主要分为两部分：

先来说说公钥与私钥的生成，先假设一个场景：周杰伦要与林俊杰进行加密通信，那么此时周杰伦需要生成公钥与私钥，私钥保存在本地，公钥需要发送给林俊杰，那么周杰伦是如何生成公钥与私钥的呢？

最终，周杰伦生成了他想要的私钥与公钥，于是便可以开始下面加密与解密的过程啦～

可以看到，RSA的密钥生成过程还是较为繁琐的，其中需要用到的变量有a,b,c,d,e,φ(c),其中公钥的生成用到了c和d，而其余四个都是不公开的，那么这里就会有一个疑问：是否能通过c和d推导出私钥，下面列出推导过程，了解下如果要得到私钥应该如何去做

从最终的结果可以看到，只要能拿到a和b，那么我们就可以推导出私钥，但是事情肯定没那么简单，玄机就藏在第二步与第三步之间，仔细观察可以发现第二步到第三步时，c被分解成了a*b，也就是c被因式分解了，我们知道寻求两个大素数比较简单，而将它们的乘积进行因式分解却极其困难，所以可以认为无法到达第三步，因此想要破解私钥也就无从谈起了

通过上述论证，我们就可以认为RSA是一种安全的加密算法，只要我们的密钥长度足够长，那么就可以认为被破解私钥是不可能的

通过上文我们应该对于RSA的密钥生成规则了然于胸了，那么接下来将讲解其具体的加解密过程，go，go，go！

bqb

首先我们要知道加密信息需要用公钥，解密信息需要私钥，明确这一点之后，接下来还是拿我的杰伦来举例，哈哈～

假设林俊杰需要给发送消息 m 给周杰伦(要注意的是m必须是整数，字符串可以取ascii值或unicode值，且 m 必须小于 c )，此时林俊杰需要用周杰伦的公钥(c,d)=>(15,3)对信息 m 进行加密，加密的算法公式为m^d mod c = f，这里其实就是求出f的值，假如 m 为7，其它的参数为上述栗子中的值，可以推导出7^3 mod 15 = f,可以很容易地算出f=13，于是林俊杰就将13发送给了周杰伦

当周杰伦接收到林俊杰发送的13时，就要用自己的私钥(15,3)进行解密，解密的公式为f^e mod c = m,带入相应的值推导出13^3 mod 15 = m，于是周杰伦可以很容易地算出m=7，最终也就获取到了林俊杰发给他的真实数据

到此，数据加密解密的过程就全部结束了，周杰伦与林俊杰终于可以愉快地开始通信啦～

聪明的你也许会问这个问题：公钥(c,d) 只能加密小于c的整数m，那么如果要加密大于c的消息,应该如何实现呢？所谓办法总比困难多，要想解决这个问题，目前有两种方案：

到这里，所有关于RSA算法原理的讲解就结束了，相信聪明的你已经能完全掌握了，如果还有不太明白的地方，多阅读几次，我相信RSA算法蕴含的精妙的思想韵味，聪明的你一定能体会到的～

bqb

结语

网络安全与我们每一个人都息息相关，正是因为有了那些伟大的科学家发明的这些让人拍案叫绝的加解密方案，所以我们才能有现在这么一个发达且相对安全的网络环境

之前自己也只是对RSA算法有个概念上的了解，但通过详细研究后，我被其中蕴含的思想所震撼，设计之精妙让我连连叫绝，一环扣一环如同在阅读一本破案小说一样，读到最后才发现事情的真相，而这个真相的推导离不开其过程中的每一个细节，哪怕其中一个细节出了小小的偏差，也会导致距离真相十万八千里

所以很多东西需要我们亲自去挖掘，这样才能真正体会到其中的真理与韵味，好啦，就写这么多吧，完结，撒花🎉～

参考

RSA算法原理（一）

RSA算法原理（二）