PBKDF2算法原理

算法介绍

PBKDF2(Password-Based Key Derivation Function) 应用一个伪随机函数以导出密钥。导出密钥的长度本质上是没有限制的（但是，导出密钥的最大有效搜索空间受限于基本伪随机函数的结构）。

它的基本原理是通过一个伪随机函数（例如 HMAC 函数），把明文和一个盐值作为输入参数，然后重复进行运算，并最终产生密钥。

如果重复的次数足够大，破解的成本就会变得很高。而盐值的添加也会增加“彩虹表”攻击的难度。

美国政府机构已经将这个方法标准化，并且用于一些政府和军方的系统。 这个方案最大的优点是标准化，实现容易同时采用了久经考验的SHA算法。

函数定义

DK = PBKDF2(PRF, Password, Salt, c, dkLen)
1

其中：

• DK是PBKDF2算法产生的密钥
• PRF是一个伪随机函数，例如HASH_HMAC函数，它会输出长度为hLen的结果
• Password 是用来生成密钥的原文密码
• Salt 是一系列用于生成密钥加密的盐值
• c是迭代运算的次数
• dkLen 是期望得到的密钥的长度

PBKDF2的算法流程

主密钥生成流程图

算法执行步骤

DK 的值由一个以上的 block 拼接而成。block 的数量是 dkLen/hLen 的值。
就是说如果 伪随机函数PRF 输出的结果比期望得到的密钥长度要短，则要通过拼接多个结果以满足密钥的长度，如下公式所示：
$$DK=T_1||T_2...||T_{dklen/hlen}$$
其中，每个 block 则通过则通过函数F得到：
$$T_i=F(Password,Salt,c,i)$$
函数 F 里，PRF会进行 c 次的运算，然后把得到的结果进行异或运算$⨁$，得到最终的值
$$F(Password,Salt,c,i)=U_1⨁U_2⨁...⨁U_c$$
注意：
第一次，PRF 会使用 Password 作为 key，Salt 拼接$||$上编码成大字节序的 32 位整型的i作为盐值进行运算，即：
$$U_1=PRF(Password,Salt||INT\_32\_BE(i))$$
而后续的 c-1 次则会使用上次得到的结果作为盐值,即：
$$\begin{gathered} U_2=PRF(Password,U_1) \\ \cdots \\ {U}_c=PRF(Password,U_{c-1}) \end{gathered}$$

结合SHA-256算法流程图

PBKDF2算法的产生背景

PBKDF2算法的产生是随着用户密码加密的不断发展而得来，因此，想要了解PBKDF2算法的产生背景，我们需要了解用户密码加密的发展历史。用户密码加密的方法演变如下：

1. 直接明文保存，比如用户设置的密码是“123456”，直接将“123456”保存在数据库中，这种是最简单的保存方式，也是最不安全的方式。但实际上不少互联网公司，都可能采取的是这种方式。
2. 使用对称加密算法来保存，比如3DES、AES等算法，使用这种方式加密是可以通过解密来还原出原始密码的，当然前提条件是需要获取到密钥。不过既然大量的用户信息已经泄露了，密钥很可能也会泄露，当然可以将一般数据和密钥分开存储、分开管理，但要完全保护好密钥也是一件非常复杂的事情，所以这种方式并不是很好的方式。
   该方法的图解如下：
3. 使用MD5、SHA1等单向HASH算法保护密码，使用这些算法后，无法通过计算还原出原始密码，而且实现比较简单，因此很多互联网公司都采用这种方式保存用户密码，曾经这种方式也是比较安全的方式，但随着彩虹表技术的兴起，可以建立彩虹表进行查表破解，目前这种方式已经很不安全了。
   该方法的图解如下：
   
4. 特殊的单向HASH算法，由于单向HASH算法在保护密码方面不再安全，于是有些公司在单向HASH算法基础上进行了加盐、多次HASH等扩展，这些方式可以在一定程度上增加破解难度，对于加了“固定盐”的HASH算法，需要保护“盐”不能泄露，这就会遇到“保护对称密钥”一样的问题，一旦“盐”泄露，根据“盐”重新建立彩虹表可以进行破解，对于多次HASH，也只是增加了破解的时间，并没有本质上的提升。
   该方法的图解如下：
   
5. PBKDF2算法，该算法原理大致相当于在HASH算法基础上增加随机盐，并进行多次HASH运算，随机盐使得彩虹表的建表难度大幅增加，而多次HASH也使得建表和破解的难度都大幅增加。使用PBKDF2算法时，HASH算法一般选用sha1或者sha256，随机盐的长度一般不能少于8字节，HASH次数至少也要1000次，这样安全性才足够高。一次密码验证过程进行1000次HASH运算，对服务器来说可能只需要1ms，但对于破解者来说计算成本增加了1000倍，而至少8字节随机盐，更是把建表难度提升了N个数量级，使得大批量的破解密码几乎不可行，该算法也是美国国家标准与技术研究院推荐使用的算法。
   

加密工具

工具试用：PBKDF2加密

参考资料

https://blog.csdn.net/xy010902100449/article/details/52078767
https://blog.csdn.net/wowotuo/article/details/77150796
https://baike.baidu.com/item/PBKDF2/237696?fr=aladdin