前言

Blowfish是一个对称密钥加密分组密码算法，由Bruce Schneier于1993年设计，意在替代老旧的DES及避免其他算法的问题与限制。Blowfish刚刚研发出的时候，大部分其他加密算法是专利所有的或属于商业(政府)机密，所以发展起来非常受限制。Schneier则声明Blowfish的使用没有任何限制，任何国家任何人任何时候都可以随意使用Blowfish算法。

Blowfish加密简介

Blowfish是一种可变密钥长度的64 位分组密码。该算法由两部分组成：密钥扩展部分和数据加密部分。密钥扩展将最多448bits的密钥转换为多个子密钥数组，总计 4168 字节。

密钥（Key）

Blowfish 是一种可变密钥长度的64 位分组密码，其密钥长度可去范围是1-448bits。

子密钥（Subkey）

Blowfish使用了大量的子密钥。在进行任何数据加密或解密之前，必须预先计算这些密钥。

P数组

P数组由18个32bits的子密钥组成；

S盒

需要4个S盒，每个S盒由256个32bits的数据组成；

子密钥的生成和使用将在下面详细介绍。

加密

Blowfish调用16轮Feistel函数进行加密操作，操作流程如下图。

输入内容是一个64bits的数据块，将其均分为高低两部分与，均为32bits，每一轮将与异或，结果设为，将其调用函数后得出的结果与异或，结果设为。与调换位置后即为下一轮的与。
第16轮结束后与不需调换位置。将与异或后的结果拼接上与异或的结果得到最终的加密后的64bits数据块。

Feistel函数内部流程如下图：

首先将32bits分成4个8bits，S-box的作用就是将8bits转换成为32bits。
将S1盒得到的32bits与S2盒得到的32bits相加后，与S3盒得到的32bits异或后，与S4盒得到的32bits相加，得到最终32bits结果。

即：

解密操作时需要将颠倒，其他与加密操作完全相同。

密钥扩展

首先用一个固定的字符串初始化P数组，然后按顺序初始化四个S盒。该字符串是随机选取的，例如可由的十六进制数字(减去最初的3)组成。
Blowfish的密钥长度为1-448bits，可以分成1-14个32bits的数据块，记作。
接下来需要使用和进行异或操作，生成最终的数组，由于的数量少于，因此需要循环使用，得到最终的数组。假设只有13个，则
使用上述生成的P数组和S盒加密全为0的64bits数据，输出64bits加密后的数据，代替。
使用更新后的P数组和S盒加密步骤4输出的数据，替代。
依次加密9轮生成新的P数组。
新的S盒数据也按照上述流程生成。

故生成最终的P数组和S盒共需要加密次。

由此可见Blowfish初始化需要大量的计算，但是一旦初始化完毕，或者说密钥不变的情况下，相对于 DES算法Blowfish是一种快速的分组加密方法，因此Blowfish一般用于密钥不经常变化的应用程序中，比如通信链路或自动文件加密器。

伪代码实现

根据Blowfish加密流程，编写伪代码如下：

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优缺点

优：

每个新的密钥都需要进行约4 KB文本的预处理，和其他分组密码算法相比，初始化相对较慢。但对于一个正常应用来说，不会经常更换密钥，所以预处理一般只会生成一次。
而对于恶意攻击者来说，每次尝试新的密钥都需要进行漫长的预处理，所以对攻击者来说要破解blowfish算法是非常不划算的。所以认为blowfish是可以抵御字典攻击的。

缺：

Blowfish使用64bits分组（与AES的128bits分组相比）容易受到生日攻击。 2016年，SWEET32攻击演示了如何利用生日攻击对64bits分组大小的密码执行纯文本恢复。
因为Blowfish的分组只有64bits，比较小，所以GnuPG项目建议不要使用Blowfish来加密大于4 GB的文件。
Blowfish如果只进行一轮加密的话，容易受到反射性弱键的已知明文攻击。实现时使用的是16轮加密，不容易受到这种攻击。但是Blowfish的发明人Bruce Schneier仍然建议迁移到Blowfish的继承者Twofish。

Leeyuxun の note

Blowfish加密算法

前言