BlowFish 算法笔记

发表于 本文字数： 2.4k 阅读时长 ≈ 2 分钟
BlowFish 加密解密算法的简要笔记

BlowFish 简述

BlowFish 算法基于 Feistel 网络，加密函数迭代执行 16 轮，分组长度为 64 位，密钥长度可以从 32 位到 448 位。算法由两部分组成，密钥扩展部分和数据加密部分，密钥扩展部分将最长最长为 448 位的密钥转化成共 4168 字节长度的子密钥数组，其中，数据加密由一个 16 轮的 Feistel 网络完成，每轮由一个密钥相关置换和一个密钥与数据相关的替换组成。

blowfish 流程图

BlowFish 描述

密钥预处理

BlowFish 算法子密钥在加密前预计算产生。

主要涉及到 P-box 和 S-box。

密钥 Key

密钥 Key 是 32bits 到 448bits 的可变长度，即 1 到 14 个 DWORD 数字，即 Key 数组最大为 DWORD Key[14]。

接下来使用 Key[i] 表示第 i 个可变密钥。

P-box

P-box 也可以被称作密钥数组，由 18 个 32bits 的密钥组成，即数组 DWORD P_box[18]

我们首先要使用随机数对数组进行初始化，而常用的方法是使用常量 \(\pi\) 的小数部分，将其直接转化为 32bits 位 DWORD 数进行赋值，如

1
2
3
4
P_box[0] = 0x76a301d3;
P_box[1] = 0xbc452aef;
...
P_box[17] = 0xd7acc4a5;

之后让 P-box 与 Key 数组的每一个值进行异或，即 P_box[i] ^= Key[i]。

当超过 Key 数组的长度时，则重复使用 Key 的值进行异或，直到 P-box 中的元素全部异或完成。

如此我们便得到了新的 P-box。

S-box

在密码学中，S-box 的全称为 substitution-box，即替换盒子，可以将输入替换成不同的输出，换句话说，可以将 n bits 的输入转换为 m bits 的输出。

在 BlowFish 中，S-box 是动态生成的，负责将 8bits 的输入转换为 32bits 的输出。

故 S-box 的大小为 DWORD S_box[4][256]。

常用的方法是，使用常量 \(\pi\) 的小数部分，将其直接转化为 32bits 位 DWORD 数对 S-box 进行初始化，通常接在 P-box 后面进行初始化。

最终处理

通过以上，得到初始化的 P-box 与 S-box。

按照以下步骤对 P-box 进行处理：

  1. 取全为 0 的 64bits，使用 P-box 和 S-box 数组，对其进行 BlowFish 加密，生成第一个 64bits
  2. 将生成的 64bits 作为新的 P_box[0] 和 P_box[1]，再将这 64bits 作为输入，得到新的 P_box[2] 和 P_box[3]
  3. 同理反复步骤 2，最终生成所有 P-box 数组的元素。
  4. 同理反复步骤 2、3，最终生成所有 S-box 数组的元素 (使用 P-box[16] 和 P-box[17] 作为输入)。

加解密

BlowFish 由 16 轮的 Fistel 网络组成，输入是一个 64bits 的数据元素 X，将 X 分为两个 32bits 部分，为 XL 与 XH。

轮函数

轮函数使用代码描述即为

1
2
3
4
5
6
// 轮函数
DWORD Feistel(DWORD x)
{
	DWORD h = S[0][x >> 24] + S[1][x >> 16 & 0xff];
	return (h ^ S[2][x >> 8 & 0xff]) + S[3][x & 0xff];
}

加密算法

1
2
3
4
5
6
7
8
9
10
11
12
13
void encrypt(DWORD& XL, DWORD& XR)
{
	for (int i = 0; i < 16; i += 2)
	{
		XL ^= P[i];
		XR ^= Feistel(XL);
		XR ^= P[i + 1];
		XL ^= Feistel(XR);
	}
	XL ^= P[16];
	XR ^= P[17];
	swap(XL, XR);
}

解密算法

1
2
3
4
5
6
7
8
9
10
11
12
13
void decrypt(DWORD& XL, DWORD& XR)
{
	for (int i = 16; i > 0; i -= 2)
	{
		XL ^= P[i + 1];
		XR ^= Feistel(XL);
		XR ^= P[i];
		XL ^= Feistel(XR);
	}
	XL ^= P[1];
	XR ^= P[0];
	swap(XL, XR);
}

BlowFish & C++ 实现

请查看 https://github.com/HasegawaAzusa/BlowFish

代码堪堪能运行而已，仅作示例和理解。

BlowFish 优劣

优点

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

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

那么慢有没有好处呢？

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

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

缺点

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

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

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