第二章 基础算法
1、加密算法
1.1【问】请介绍一下你知道的加密算法
参考回答：
一般分类如下
对称加密
非对称加密
哈希摘要
电子签名
密码存储
其中
对称加密常见的有：DES、AES 等，国家标准有 SM4
非对称加密常见的有：RSA，ECDSA 等，国家标准有 SM2
哈希摘要有：MD5、SHA-2、SHA-3 等，国家标准有 SM3
电子签名有：通常会结合 RSA、ECDSA 和哈希摘要完成签名，或者是 HMAC
密码存储：直接使用哈希摘要作为密码存储、加盐存储、BCrypt
1.2【追问】解释对称加密、非对称加密、哈希摘要
对称加密
加密和解密的密钥使用同一个
因为密钥只有一个，所以密钥需要妥善保管
加解密速度快
非对称加密
密钥分成公钥、私钥，其中公钥用来加密、私钥用来解密
只需将私钥妥善保管，公钥可以对外公开
如果是双向通信保证传输数据安全，需要双方各产生一对密钥
A 把 A公钥 给 B，B 把 B公钥 给 A，他们各自持有自己的私钥和对方的公钥
A 要发消息给 B，用 B公钥 加密数据后传输，B 收到后用 B私钥 解密数据
类似的 B 要发消息给 A，用 A公钥 加密数据后传输，A 收到后用 A私钥 解密数据
相对对称加密、加解密速度慢
哈希摘要，摘要就是将原始数据的特征提取出来，它能够代表原始数据，可以用作数据的完整性校验
举个例子，张三对应着完整数据
描述张三时，会用它的特征来描述：他名叫张三、男性、30多岁、秃顶、从事 java 开发、年薪百万，这些特征就对应着哈希摘要，以后拿到这段描述，就知道是在说张三这个人
为什么说摘要能区分不同数据呢，看这段描述：还是名叫张三、男性、30多岁、秃顶、从事 java 开发、月薪八千，有一个特征不符吧，这时可以断定，此张三非彼张三
1.3【追问】解释签名算法
电子签名，主要用于防止数据被篡改。
先思考一下单纯用摘要算法能否防篡改？例如
发送者想把一段消息发给接收者
中途 message 被坏人改成了 massage（摘要没改）
但由于发送者同时发送了消息的摘要，一旦接收者验证摘要，就可以发现消息被改过了
坏人开始冒坏水
但摘要算法都其实都是公开的（例如 SHA-256），坏人也能用相同的摘要算法
一旦这回把摘要也一起改了发给接收者，接收者就发现不了
怎么解决？
发送者这回把消息连同一个密钥一起做摘要运算，密钥在发送者本地不随网络传输
坏人不知道密钥是什么，自然无法伪造摘要
密钥也可以是两把：公钥和私钥。私钥留给发送方签名，公钥给接收方验证签名，参考下图
注意：验签和加密是用对方公钥，签名和解密是用自己私钥。不要弄混
1.4【追问】你们项目中密码如何存储？
首先，明文肯定是不行的
第二，单纯使用 MD5、SHA-2 将密码摘要后存储也不行，简单密码很容易被彩虹表攻击，例如
攻击者可以把常用密码和它们的 MD5 摘要结果放在被称作【彩虹表】的表里，反查就能查到原始密码
加密结果
原始密码
e10adc3949ba59abbe56e057f20f883e
123456
e80b5017098950fc58aad83c8c14978e
abcdef
...
...
因此
要么提示用户输入足够强度的密码，增加破解难度
要么我们帮用户增加密码的复杂度，增加破解难度
可以在用户简单密码基础上加上一段盐值，让密码变得复杂
可以进行多次迭代哈希摘要运算，而不是一次摘要运算
还有一种办法就是用 BCrypt，它不仅采用了多次迭代和加盐，还可以控制成本因子来增加哈希运算量，让攻击者知难而退
1.5【追问】比较一下 DES、AES、SM4
它们都是对称加密算法
DES（数据加密标准）使用56位密钥，已经不推荐使用
AES（高级加密标准）支持 128、192、256位密钥长度，在全球范围内广泛使用
SM4（国家商用密码算法）支持 128位密钥，在中国范围内使用
1.6【追问】比较一下 RSA、ECDSA 和 SM2
它们都是非对称加密算法
RSA 的密钥长度通常为 1024~4096，而 SM2 的密钥长度是 256
SM2 密钥长度不需要那么长，是因为它底层依赖的是椭圆曲线、离散对数，反过来 RSA 底层依赖的是大数分解，前者在相同安全级别下有更快的运算效率
SM2 是中国国家密码算法，在国内受政策支持和推广
ECDSA 与 SM2 实现原理类似
2、排序
2.1 【问】请介绍一下你知道的排序算法有哪些
初级答法
常见的排序算法有：冒泡排序、选择排序、插入排序、快速排序、归并排序、堆排序等
P.S.
适合对以上排序算法一知半解，不太自信的同学，所谓言多必失，回答基本的就行
但要对接下来【各种排序的时间复杂度】的追问做到心中有数，这个必须背一背（参考后面的表格）
进阶答法
排序算法大致可分为两类：
A. 基于比较的排序算法
B. 非比较排序算法
比较排序算法有：快排、归并、堆排序、插入排序等
非比较排序算法有：计数排序、桶排序、基数排序等
比较排序算法中
快排、归并、堆排序能够达到 $$O(n \cdot \log{n})$$的（平均）时间复杂度
而插入排序的（平均）时间复杂度是 $$O(n^2$$
但并不是说复杂度高的算法就差，这要看数据规模和数据有序度，例如
数据量小，或是有序度高的数据就适合用插入排序
同样是数据量大的数据排序，如果数据的有序度高，归并优于快排
快排虽然是比较排序中最快的算法，但若是分区选取不好，反而会让排序效率降低
工业级的排序都是混合多种排序算法，例如 java 排序的实现就是混合了插入、归并与快排，不同的数据规模、不同场景下切换不同的排序算法
至于计数、桶、基数可以达到进一步让时间复杂度降至$$O(n$$，当然这与被排序数字的位数、范围等都有关系，您想知道的话，咱们可以细聊。
P.S.
适合对这些排序算法非常熟悉的同学，这时应注重回答的条理性
首先，对算法进行简单分类，让答案更为清晰
其次，不要等面试官来继续追问，而是主动回答各个算法的时间复杂度和适用场景，体现你对它们的熟悉
第三，一定要对各个算法的细节有充分准备，否则问到答不出来就尴尬了，这时不如降级为【初级答法】
