简介

Blowfish 是由 Bruce Schneier 在 1993 年发明的对称密钥分组加密算法，类似的 DES 和 AES 都是分组加密算法，Blowfish 是用来替代 DES 算法出现的，并且 Blowfish 是没有商用限制的，任何人都可以自由使用。

对比而言，虽然 AES 也是一种密码强度很高的对称密码算法，但是如果需要商用的话要向 NIST 支付授权费用。

blowfish 详解

blowfish 和 DES 一样，使用的是 feistel 密码来进行分组加密。blowfish 的分组块大小是 64bits,可变密钥长度可以从 32bits 到 448bits 不等。

blowfish 需要进行 16 轮的 feistel 加密操作，我们先从下图大致感受一下 blowfish 算法的加密流程：

大概的流程就是将 P(原始数据)分成左右两部分，先拿左边的部分和 K_r 做异或操作，得出的结果调用 F 函数，最后将 F 函数的输出结果和右半部分进行异或操作。

调换左右部分的位置，继续进行这样的操作，总共进行 16 轮就得到了最终的加密结果。

大家可以看到整个加密过程中最重要的两个变量就是 K_r 和 F 函数。

接下来我们会详细进行讲解。

密钥数组和 S-box

密钥数组

从图上我们可以看到，K_r 的范围是从 K₁ 到 K₁₈ 。总共有 18 个密钥组成的数组。 每个密钥的长度是 32 位。

我们来看一下密钥数组是怎么生成的。

首先我们使用随机数来对密钥数组进行初始化。怎么才能生成一个足够随机的 32 位数字呢？

一个很常用的方法就是使用常量π的小数部分，将其转换成为 16 净值，如下所示：

K₁ = 0x76a301d3

K₂ = 0xbc452aef

…

K₁₈ = 0xd7acc4a5

还记得 blowfish 的可变密钥的长度吗？是从 32bits 到 448bits，也就是从 1 到 14 个 32 位的数字。我们用 P_i来表示,那么就是从 P₁到 P₁₄总共 14 个可变密钥。

接下来我们需要使用 K 和 P 进行操作，从而生成最终的 K 数组。

我们使用 K₁和 P₁进行异或操作，K₂和 P₂进行异或操作，一直到 K₁₄和 P₁₄。

因为 P 只有 14 个值，而 K 有 18 个值，所以接下来我们需要重复使用 P 的值，也就是 K₁₅和 P₁进行异或，K₁₆和 P₂进行异或，直到 K₁₈和 P₄。

将异或之后的值作为新的 K 数组的值。

现在我们获得了一个新的 K 数组。

注意，这个 K 数组并不是最终的数组，我们接下来看。

S-box

在生成最终的 P 数组之前，我们还要介绍一个概念叫做 S-box。

在密码学中，s-box 的全称是 substitution-box，也就是一个替换盒子，可以将输入替换成不同的输出。

S-box 接收 n 个 bits 的输入，然后将其转换成 m 个 bits 的输出。

这里 n 和 m 可以是不等的。

我们看一下 DES 中 S-box 的例子：

上面的 S-box 将 6-bits 的输入转换成为 4-bits 的输出。

S-box 可以是固定的，也可以是动态的。比如，在 DES 中 S-box 就是静态的，而在 Blowfish 和 Twofish 中 S-box 就是动态生成的。

Blowfish 算法中的 F 函数需要用到 4 个 S-box，F 函数的输入是 32bits，首先将 32bits 分成 4 份，也就是 4 个 8bits。

S-box 的作用就是将 8bits 转换成为 32bits。

我们再详细看一下 F 函数的工作流程：

S-box 生成的值会进行相加，然后进行异或操作。最终得到最终的 32bits。

S-box 的初始值也可以跟 K 数组一样，使用常量π的小数部分来初始化。

生成最终的 K 数组

在上面两节，我们生成了初始化的 K 数组和 S-box。

blowfish 认为这样还不够安全，不够随机。

我们还需要进行一些操作来生成最终的 K 数组。

首先我们取一个全为 0 的 64bits，然后 K 数组和 S-box，应用 blowfish 算法，生成一个 64bits。

将这个 64bits 分成两部分，分别作为新的 K₁ 和 K₂。

然后将这个 64bits 作为输入，再次调用 blowfish 算法，作为新的 K₃ 和 K₄。

依次类推，最终生成所有 K 数组中的元素。

4 个 S-box 的数组也按照上面的流程来进行生成。从而得到最终的 S-box。

blowfish

有了最终的 K 数组和 S-box，我们就可以真正的对要加密的文件进行加密操作了。

用个伪代码来表示整个流程：

uint32_t P[18];uint32_t S[4][256];
uint32_t f (uint32_t x) {   uint32_t h = S[0][x >> 24] + S[1][x >> 16 & 0xff];   return ( h ^ S[2][x >> 8 & 0xff] ) + S[3][x & 0xff];}
void encrypt (uint32_t & L, uint32_t & R) {   for (int i=0 ; i<16 ; i += 2) {      L ^= P[i];      R ^= f(L);      R ^= P[i+1];      L ^= f(R);   }   L ^= P[16];   R ^= P[17];   swap (L, R);}
void decrypt (uint32_t & L, uint32_t & R) {   for (int i=16 ; i > 0 ; i -= 2) {      L ^= P[i+1];      R ^= f(L);      R ^= P[i];      L ^= f(R);   }   L ^= P[1];   R ^= P[0];   swap (L, R);}
  // ...  // initializing the P-array and S-boxes with values derived from pi; omitted in the example  // ...{   for (int i=0 ; i<18 ; ++i)      P[i] ^= key[i % keylen];   uint32_t L = 0, R = 0;   for (int i=0 ; i<18 ; i+=2) {      encrypt (L, R);      P[i] = L; P[i+1] = R;   }   for (int i=0 ; i<4 ; ++i)      for (int j=0 ; j<256; j+=2) {         encrypt (L, R);         S[i][j] = L; S[i][j+1] = R;      }}

blowfish 的应用

从上面的流程可以看出，blowfish 在生成最终的 K 数组和 S-box 需要耗费一定的时间，但是一旦生成完毕，或者说密钥不变的情况下，blowfish 还是很快速的一种分组加密方法。

每个新的密钥都需要进行大概 4 KB 文本的预处理，和其他分组密码算法相比，这个会很慢。

那么慢有没有好处呢？

当然有，因为对于一个正常应用来说，是不会经常更换密钥的。所以预处理只会生成一次。在后面使用的时候就会很快了。

而对于恶意攻击者来说，每次尝试新的密钥都需要进行漫长的预处理，所以对攻击者来说要破解 blowfish 算法是非常不划算的。所以 blowfish 是可以抵御字典攻击的。

因为 blowfish 没有任何专利限制，任何人都可以免费使用。这种好处促进了它在密码软件中的普及。

比如使用 blowfish 的 bcrypt 算法，我们会在后面的文章中进行讲解。

blowfish 的缺点

Blowfish 使用 64 位块大小（与 AES 的 128 位块大小相比）使它容易受到生日攻击，特别是在 HTTPS 这样的环境中。 2016 年，SWEET32 攻击演示了如何利用生日攻击对 64 位块大小的密码执行纯文本恢复（即解密密文）。

因为 blowfish 的块只有 64bits，比较小，所以 GnuPG 项目建议不要使用 Blowfish 来加密大于 4 GB 的文件。

除此之外，Blowfish 如果只进行一轮加密的话，容易受到反射性弱键的已知明文攻击。 但是我们的实现中使用的是 16 轮加密，所以不容易受到这种攻击。但是 Blowfish 的发明人布鲁斯·施耐尔（Bruce Schneier）还是建议大家迁移到 Blowfish 的继承者 Twofish 去。

本文已收录于 http://www.flydean.com/blowfish/

最通俗的解读，最深刻的干货，最简洁的教程，众多你不知道的小技巧等你来发现！

欢迎关注我的公众号:「程序那些事」,懂技术，更懂你！