简介
明天要给大家介绍的一种加密算法叫做 bcrypt, bcrypt 是由 Niels Provos 和 David Mazières 设计的明码哈希函数，他是基于 Blowfish 明码而来的，并于 1999 年在 USENIX 上提出。
除了加盐来抵挡 rainbow table 攻打之外，bcrypt 的一个十分重要的特色就是自适应性，能够保障加密的速度在一个特定的范畴内，即便计算机的运算能力十分高，能够通过减少迭代次数的形式，使得加密速度变慢，从而能够抵挡暴力搜寻攻打。
bcrypt 函数是 OpenBSD 和其余零碎包含一些 Linux 发行版（如 SUSE Linux）的默认明码哈希算法。
bcrypt 的工作原理
咱们先回顾一下 Blowfish 的加密原理。blowfish 首先须要生成用于加密应用的 K 数组和 S -box, blowfish 在生成最终的 K 数组和 S -box 须要消耗肯定的工夫，每个新的密钥都须要进行大略 4 KB 文本的预处理，和其余分组明码算法相比，这个会很慢。然而一旦生成结束，或者说密钥不变的状况下，blowfish 还是很疾速的一种分组加密办法。
那么慢有没有益处呢？
当然有，因为对于一个失常利用来说，是不会常常更换密钥的。所以预处理只会生成一次。在前面应用的时候就会很快了。
而对于歹意攻击者来说，每次尝试新的密钥都须要进行漫长的预处理，所以对攻击者来说要破解 blowfish 算法是十分不划算的。所以 blowfish 是能够抵挡字典攻打的。
Provos 和 Mazières 利用了这一点，并将其进一步倒退。他们为 Blowfish 开发了一种新的密钥设置算法，将由此产生的明码称为 “Eksblowfish”（”expensive key schedule Blowfish”）。这是对 Blowfish 的改良算法，在 bcrypt 的初始密钥设置中，salt 和 password 都被用来设置子密钥。而后通过一轮轮的规范 Blowfish 算法，通过交替应用 salt 和 password 作为 key，每一轮都依赖上一轮子密钥的状态。尽管从实践上来说，bcrypt 算法的强度并不比 blowfish 更好，然而因为在 bcrpyt 中重置 key 的轮数是能够配置的，所以能够通过减少轮数来更好的抵挡暴力攻打。
bcrypt 算法实现
简略点说 bcrypt 算法就是对字符串OrpheanBeholderScryDoubt 进行 64 次 blowfish 加密失去的后果。有敌人会问了，bcrypt 不是用来对明码进行加密的吗？怎么加密的是一个字符串？
别急，bcrpyt 是将明码作为对该字符串加密的因子，同样也失去了加密的成果。咱们看下 bcrypt 的根本算法实现：
Function bcrypt
Input:
cost: Number (4..31) log2(Iterations). e.g. 12 ==> 212 = 4,096 iterations
salt: array of Bytes (16 bytes) random salt
password: array of Bytes (1..72 bytes) UTF-8 encoded password
Output:
hash: array of Bytes (24 bytes)
//Initialize Blowfish state with expensive key setup algorithm
//P: array of 18 subkeys (UInt32[18])
//S: Four substitution boxes (S-boxes), S0...S3. Each S-box is 1,024 bytes (UInt32[256])
P, S <- EksBlowfishSetup(cost, salt, password)
//Repeatedly encrypt the text "OrpheanBeholderScryDoubt" 64 times
ctext <- "OrpheanBeholderScryDoubt" //24 bytes ==> three 64-bit blocks
repeat (64)
ctext <- EncryptECB(P, S, ctext) //encrypt using standard Blowfish in ECB mode
//24-byte ctext is resulting password hash
return Concatenate(cost, salt, ctext)上述函数 bcrypt 有 3 个输出和 1 个输入。
在输出局部，cost 示意的是轮循的次数，这个咱们能够本人指定，轮循次数多加密就慢。
salt 是加密用盐，用来混同明码应用。
password 就是咱们要加密的明码了。
最初的输入是加密后的后果 hash。
有了 3 个输出，咱们会调用 EksBlowfishSetup 函数去初始化 18 个 subkeys 和 4 个 1K 大小的 S -boxes，从而达到最终的 P 和 S。
而后应用 P 和 S 对 ”OrpheanBeholderScryDoubt” 进行 64 次 blowfish 运算，最终失去后果。
接下来看下 EksBlowfishSetup 办法的算法实现：
Function EksBlowfishSetup
Input:
password: array of Bytes (1..72 bytes) UTF-8 encoded password
salt: array of Bytes (16 bytes) random salt
cost: Number (4..31) log2(Iterations). e.g. 12 ==> 212 = 4,096 iterations
Output:
P: array of UInt32 array of 18 per-round subkeys
S1..S4: array of UInt32 array of four SBoxes; each SBox is 256 UInt32 (i.e. 1024 KB)
//Initialize P (Subkeys), and S (Substitution boxes) with the hex digits of pi
P, S <- InitialState()
//Permutate P and S based on the password and salt
P, S <- ExpandKey(P, S, salt, password)
//This is the "Expensive" part of the "Expensive Key Setup".
//Otherwise the key setup is identical to Blowfish.
repeat (2cost)
P, S <- ExpandKey(P, S, 0, password)
P, S <- ExpandKey(P, S, 0, salt)
return P, S代码很简略，EksBlowfishSetup 接管下面咱们的 3 个参数，返回最终的蕴含 18 个子 key 的 P 和 4 个 1k 大小的 Sbox。
首先初始化，失去最后的 P 和 S。
而后调用 ExpandKey，传入 salt 和 password，生成第一轮的 P 和 S。
而后循环 2 的 cost 方次，轮流应用 password 和 salt 作为参数去生成 P 和 S，最初返回。
最初看一下 ExpandKey 的实现：
Function ExpandKey
Input:
password: array of Bytes (1..72 bytes) UTF-8 encoded password
salt: Byte[16] random salt
P: array of UInt32 Array of 18 subkeys
S1..S4: UInt32[1024] Four 1 KB SBoxes
Output:
P: array of UInt32 Array of 18 per-round subkeys
S1..S4: UInt32[1024] Four 1 KB SBoxes
//Mix password into the P subkeys array
for n <- 1 to 18 do
Pn <- Pn xor password[32(n-1)..32n-1] //treat the password as cyclic
//Treat the 128-bit salt as two 64-bit halves (the Blowfish block size).
saltHalf[0] <- salt[0..63] //Lower 64-bits of salt
saltHalf[1] <- salt[64..127] //Upper 64-bits of salt
//Initialize an 8-byte (64-bit) buffer with all zeros.
block <- 0
//Mix internal state into P-boxes
for n <- 1 to 9 do
//xor 64-bit block with a 64-bit salt half
block <- block xor saltHalf[(n-1) mod 2] //each iteration alternating between saltHalf[0], and saltHalf[1]
//encrypt block using current key schedule
block <- Encrypt(P, S, block)
P2n <- block[0..31] //lower 32-bits of block
P2n+1 <- block[32..63] //upper 32-bits block
//Mix encrypted state into the internal S-boxes of state
for i <- 1 to 4 do
for n <- 0 to 127 do
block <- Encrypt(state, block xor salt[64(n-1)..64n-1]) //as above
Si[2n] <- block[0..31] //lower 32-bits
Si[2n+1] <- block[32..63] //upper 32-bits
return stateExpandKey 次要用来生成 P 和 S，算法的生成比较复杂，大家感兴趣的能够具体钻研一下。
bcrypt hash 的构造
咱们能够应用 bcrypt 来加密明码，最终以 bcrypt hash 的模式保留到零碎中，一个 bcrypt hash 的格局如下：
$2b$[cost]$[22 character salt][31 character hash]比方：
$2a$10$N9qo8uLOickgx2ZMRZoMyeIjZAgcfl7p92ldGxad68LJZdL17lhWy
\__/\/ \____________________/\_____________________________/
Alg Cost Salt Hash下面例子中，$2a$ 示意的 hash 算法的惟一标记。这里示意的是 bcrypt 算法。
10 示意的是代价因子，这里是 2 的 10 次方，也就是 1024 轮。
N9qo8uLOickgx2ZMRZoMye 是 16 个字节（128bits）的 salt 通过 base64 编码失去的 22 长度的字符。
最初的 IjZAgcfl7p92ldGxad68LJZdL17lhWy 是 24 个字节（192bits）的 hash，通过 bash64 的编码失去的 31 长度的字符。
hash 的历史
这种 hash 格局是遵循的是 OpenBSD 密码文件中存储明码时应用的 Modular Crypt Format 格局。最开始的时候格局定义是上面的：
$1$: MD5-based crypt (‘md5crypt’)$2$: Blowfish-based crypt (‘bcrypt’)$sha1$: SHA-1-based crypt (‘sha1crypt’)$5$: SHA-256-based crypt (‘sha256crypt’)$6$: SHA-512-based crypt (‘sha512crypt’)
然而最后的标准没有定义如何解决非 ASCII 字符，也没有定义如何解决 null 终止符。订正后的标准规定，在 hash 字符串时：
- String 必须是 UTF- 8 编码
- 必须蕴含 null 终止符
因为蕴含了这些改变，所以 bcrypt 的版本号被批改成了 $2a$。
然而在 2011 年 6 月，因为 PHP 对 bcypt 的实现 crypt_blowfish 中的一个 bug，他们倡议系统管理员更新他们现有的明码数据库，用 $2x$ 代替$2a$，以表明这些哈希值是坏的（须要应用旧的算法）。他们还倡议让 crypt_blowfish 对新算法生成的哈希值应用头$2y$。当然这个改变只限于 PHP 的crypt_blowfish。
而后在 2014 年 2 月，在 OpenBSD 的 bcrypt 实现中也发现了一个 bug，他们将字符串的长度存储在无符号 char 中（即 8 位 Byte）。如果明码的长度超过 255 个字符，就会溢出来。
因为 bcrypt 是为 OpenBSD 创立的。所以当他们的库中呈现了一个 bug 时, 他们决定将版本号降级到$2b$。
本文已收录于 http://www.flydean.com/37-bcrypt/
最艰深的解读，最粗浅的干货，最简洁的教程，泛滥你不晓得的小技巧等你来发现！
欢送关注我的公众号:「程序那些事」, 懂技术，更懂你！