乐趣区

关于密码学:密码学系列之blowfish对称密钥分组算法

jiezi

简介

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

密钥数组

从图上咱们能够看到，Kr 的范畴是从 K 1 到 K18。总共有 18 个密钥组成的数组。每个密钥的长度是 32 位。

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

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

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

K1 = 0x76a301d3

K2 = 0xbc452aef

…

K18 = 0xd7acc4a5

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

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

咱们应用 K 1 和 P 1 进行异或操作，K2 和 P 2 进行异或操作，始终到 K 14 和 P 14。

因为 P 只有 14 个值，而 K 有 18 个值，所以接下来咱们须要重复使用 P 的值，也就是 K 15 和 P 1 进行异或，K16 和 P 2 进行异或，直到 K 18 和 P 4。

将异或之后的值作为新的 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 1 和 K2。

而后将这个 64bits 作为输出，再次调用 blowfish 算法，作为新的 K 3 和 K4。

顺次类推，最终生成所有 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/

最艰深的解读，最粗浅的干货，最简洁的教程，泛滥你不晓得的小技巧等你来发现！

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

退出移动版