Blowfish加密算法的密钥扩展过程详解

Blowfish是一个由Bruce Schneier于1993年设计的对称分组密码算法。它以其简单、快速且可配置密钥长度的特点而闻名，尤其适合不具备硬件加速的软件环境。其密钥扩展过程（Key Expansion）是算法安全性的核心，负责将用户提供的可变长度密钥（32位到448位）转换成一个大型的、固定的子密钥数组，供后续的加密轮次使用。这个过程相对复杂且计算密集。

我将为您逐步拆解这个密钥扩展过程的每一个环节。

1. 预备知识：Blowfish的结构概述

在深入密钥扩展之前，需要理解Blowfish的基本框架：

• 分组大小：64位。
• 轮数：16轮。
• 核心组件：
  1. P-数组（P-Array）：一个包含18个32位子密钥的数组，记为 P[1], P[2], ..., P[18]。这些子密钥主要用于每轮加密开始和结束时的密钥加操作。
  2. S-盒（S-Boxes）：4个S盒，每个S盒是一个包含256个32位条目的查找表，记为 S[0][0..255], S[1][0..255], S[2][0..255], S[3][0..255]。它们用在轮函数的Feistel网络中进行非线性替换。
• 加密流程：基于Feistel结构，每轮使用一个来自P-数组的子密钥和所有四个S盒。

密钥扩展的任务，就是用用户密钥去初始化这个庞大的、总大小为 (18 + 4*256) * 32位 = 4168字节 的子密钥池（P-数组和S盒）。

2. 密钥扩展过程的详细步骤

密钥扩展过程分为两大阶段：初始化和子密钥生成。

步骤一：用固定常数初始化P-数组和S盒

在知道任何用户密钥之前，P-数组和S盒必须被赋予一个确定的初始状态。这个初始值来源于一个固定的数学常数——圆周率π的小数部分。

1. 取π的小数部分：算法使用十六进制格式的π小数部分（从第一个数字开始）。
2. 顺序填充：依次取出π的十六进制数字，拼接成32位的字（例如，0x243F6A88, 0x85A308D3, 0x13198A2E, 0x03707344, ...）。
3. 填充顺序：
   • 首先，用这些字按顺序填充P-数组的18个位置：P[1], P[2], ..., P[18]。
   • 然后，继续用后续的字，按顺序填充4个S盒的每一个条目（总共1024个条目）。即先填满 S[0][0] 到 S[0][255]，然后是 S[1][0..255]，以此类推。

至此，我们有了一个确定性的、公开的初始子密钥状态。这个状态是不安全的，因为它与用户密钥无关。下一步就是用用户密钥来“打乱”这个状态。

步骤二：用用户密钥扰乱（XOR）P-数组

这个步骤将用户的秘密信息首次引入到子密钥系统中。

1. 处理用户密钥：将用户提供的密钥（一个字节数组）视为一个32位字的循环序列。如果密钥长度不是4字节的整数倍，通常需要将其处理成字数组。例如，一个16字节（128位）的密钥 K，可以看作4个32位字：K[0], K[1], K[2], K[3]。
2. 异或操作：将P-数组的每一个元素，依次与这个用户密钥字序列进行循环异或。
   • 具体操作：
     P[1] = P[1] XOR K[0]
P[2] = P[2] XOR K[1]
P[3] = P[3] XOR K[2]
P[4] = P[4] XOR K[3]
P[5] = P[5] XOR K[0] （循环回到密钥的第一个字）
     P[6] = P[6] XOR K[1]
     ... 以此类推，直到 P[18] 被异或完毕。
   • 数学表达：对于 i = 1 to 18，P[i] = P[i] XOR K[(i-1) mod (密钥字数)]。

现在，P-数组已经被用户密钥初步“个性化”了，但S盒还是原始的π常数。我们需要一个更复杂的过程，让密钥信息扩散到整个庞大的子密钥空间（包括S盒）。

步骤三：用更新后的子密钥系统进行自我加密以生成最终子密钥

这是Blowfish密钥扩展中最精妙和耗时的部分。它利用Blowfish算法自身的加密函数（使用当前的、不完整的P和S状态）作为伪随机函数，来产生最终的子密钥。

这个过程用一个全零的64位分组（0x0000000000000000）作为输入数据。

1. 第一轮加密：
   • 使用当前的P-数组和S盒状态（即经过步骤二异或后的状态），对全零分组进行一次完整的Blowfish加密。
   • 这次加密的输出（一个64位密文）被拆分成两个32位部分：左半部分 L 和右半部分 R。
2. 更新P[1]和P[2]：
   • 将 P[1] 替换为这个加密输出的左半部分 L。
   • 将 P[2] 替换为这个加密输出的右半部分 R。
   • 关键点：现在P-数组的前两个元素，是由当前（部分由密钥影响的）系统对固定输入加密产生的。这比简单的异或具有更强的非线性混淆。
3. 迭代更新整个P-数组和S盒：
   • 接下来，用新更新过的P和S状态（注意，P[1], P[2]已经变了），再次对“上一次加密的密文”（即当前的 L 和 R 拼接）进行完整的Blowfish加密。
   • 将新的加密输出，用来替换 P[3] 和 P[4]。
   • 重复这个过程：总是用最新的、全部的子密钥状态，对上一次加密得到的密文再次加密，并将输出结果依次替换P数组的下两个元素。
   • 更新顺序：先更新完整个P数组（18个元素需要9次加密），然后继续这个过程来更新S盒。用同样的方式，每次加密的输出，依次替换 S[0][0] 和 S[0][1]，然后是 S[0][2] 和 S[0][3]，...，直到更新完所有4个S盒的全部1024个条目。
   • 总计：这个过程总共需要进行 (18 + 1024) / 2 = 521 次完整的Blowfish加密。

3. 过程总结与特点

让我们用流程图来概括整个密钥扩展过程：

开始
  ↓
用π的十六进制小数初始化 P[1..18] 和 S[0..3][0..255]
  ↓
将用户密钥循环与 P[1..18] 进行逐位异或
  ↓
设 data = 0x0000000000000000
  ↓
循环 i = 1 到 521 次：
    1. 用当前的 P 和 S 对 data 进行 Blowfish 加密
    2. 将加密结果作为新的 data
    3. 用 data 的左半部分替换 P[2i-1]
    4. 用 data 的右半部分替换 P[2i]（或S盒对应条目）
  ↓
结束，得到最终的、与用户密钥强相关的 P-数组和 S-盒

核心特点：

1. 计算密集型：521次加密是昂贵的。这是Blowfish的一个设计特点，旨在增加暴力破解密钥的成本（每个可能的密钥都需要进行这个昂贵的扩展才能测试）。
2. 密钥相关S盒：与AES等使用固定S盒的算法不同，Blowfish的S盒是每个密钥唯一的。这增加了算法的复杂性和抵抗某些密码分析的能力。
3. 单向性：从最终的P-数组和S盒，很难逆向推导出原始的用户密钥。
4. 慢速的密钥变更：由于扩展过程很慢，Blowfish不适合需要频繁更换密钥的场景。

总结

Blowfish的密钥扩展过程是一个巧妙的“自举”过程：它从一个公开的常数开始，通过简单的异或引入密钥，然后利用算法自身的加密核心，经过数百次迭代，将密钥信息彻底、非线性地扩散到庞大的子密钥表中。这种设计虽然在密钥设置上付出了性能代价，但为加密轮次提供了高度的密钥依赖性，是Blowfish算法安全基石的重要组成部分。