Twofish分组密码算法的密钥扩展过程

我将为你详细讲解Twofish算法中密钥扩展过程的完整设计。Twofish是1998年AES竞赛的决赛算法之一，由Bruce Schneier等人设计，采用Feistel网络结构，其密钥扩展过程特别复杂且安全。

一、算法背景与核心思想

Twofish支持128、192和256位三种密钥长度，对应128位分组大小。其密钥扩展的目标是：

1. 从主密钥派生40个32位轮密钥（K₀到K₃₉）
2. 生成四个32位S盒密钥（用于动态S盒生成）
3. 整个过程设计为抵御相关密钥攻击和侧信道攻击

二、前置处理：将主密钥分为子密钥字

首先，将主密钥MK按字节划分为：

• 128位密钥：分成4个32位字（M₀, M₁, M₂, M₃）
• 192位密钥：分成6个32位字（M₀到M₅）
• 256位密钥：分成8个32位字（M₀到M₇）

设密钥字节数为N（N=4,6,8），那么密钥字数量k = N/2（即k=2,3,4）。

三、生成S盒密钥（S向量）

这是Twofish最具特色的部分：使用主密钥来生成动态S盒。

步骤1：计算Me和Mo向量

定义两个长度为k的向量：

Me[i] = M₂ᵢ        (i=0,...,k-1)  // 取偶数下标字
Mo[i] = M₂ᵢ₊₁      (i=0,...,k-1)  // 取奇数下标字

例如256位密钥（k=4）：

• Me = (M₀, M₂, M₄, M₆)
• Mo = (M₁, M₃, M₅, M₇)

步骤2：生成S向量（S盒密钥）

S向量长度为4个32位字，通过以下过程计算：

for i = 0 to 3:
    S[i] = 0
    for j = 0 to k-1:
        // 使用RS矩阵乘法
        temp = Me[j] ⊕ Mo[j]
        S[i] = S[i] ⊕ (RS[i][4j]·temp[0] ⊕ RS[i][4j+1]·temp[1] 
                      ⊕ RS[i][4j+2]·temp[2] ⊕ RS[i][4j+3]·temp[3])

其中RS是预定义的4×8矩阵，元素在GF(2⁸)上运算，使用0x14D的不可约多项式。

这个设计确保S盒密钥均匀依赖于主密钥的所有位。

四、轮密钥生成（40个子密钥）

轮密钥通过h函数生成，h函数是Twofish的核心组件。

h函数设计

h(X, L)  // X是32位输入，L是长度为k的32位字向量

计算过程：

1. 将X按字节拆分：X = (x₀, x₁, x₂, x₃)
2. 如果k=4（256位密钥）：

   q₀ = q₁(x₀) ⊕ L₃[0]
   q₁ = q₀(x₁) ⊕ L₂[0]
   q₂ = q₀(x₂) ⊕ L₁[0]
   q₃ = q₁(x₃) ⊕ L₀[0]
   

   其中q₀、q₁是预定义的8位→8位置换表。
3. 对结果应用MDS矩阵乘法（在GF(2⁸)上）

生成具体轮密钥

定义固定序列ρ = (2^24 + 2^16 + 2^8 + 2^0)

对于i=0到19：

Aᵢ = h(2iρ, Me)    // 使用Me向量
Bᵢ = h((2i+1)ρ, Mo) // 使用Mo向量
Bᵢ = ROL(Bᵢ, 8)     // 循环左移8位

然后组合成轮密钥：

K₂ᵢ = (Aᵢ + Bᵢ) mod 2³²
K₂ᵢ₊₁ = ROL((Aᵢ + 2Bᵢ) mod 2³², 9)

这样生成40个轮密钥（K₀到K₃₉）。

五、密钥扩展的代数性质与安全性

1. 白密钥设计

Twofish在首轮和末轮使用了额外的密钥加操作：

输入白化：R₀,₀ = P₀ ⊕ K₀
          R₀,₁ = P₁ ⊕ K₁
输出白化：C₀ = R₁₈,₀ ⊕ K₄
          C₁ = R₁₈,₁ ⊕ K₅

其中轮密钥K₄到K₃₉仅用于白化，不用于轮函数内部。

2. 抗攻击特性

• 相关密钥攻击防护：h函数中混合使用Me和Mo，且ρ序列确保即使相关密钥也会产生不同输出
• 侧信道防护：S盒密钥生成过程复杂，难以通过简单功耗分析恢复密钥
• 雪崩效应：改变主密钥1位，平均会改变50%的轮密钥位

3. 效率优化

虽然密钥扩展计算较慢，但Twofish设计为：

• 加密/解密时预计算S盒（使用S向量）
• 轮密钥可预先计算存储
• 适用于多次使用同一密钥的场景

六、实例演示（128位密钥简化版）

设128位密钥：0x0123456789ABCDEFFEDCBA9876543210

1. 分割：

   M₀ = 0x01234567
   M₁ = 0x89ABCDEF
   M₂ = 0xFEDCBA98
   M₃ = 0x76543210
   k = 2
   Me = (M₀, M₂) = (0x01234567, 0xFEDCBA98)
   Mo = (M₁, M₃) = (0x89ABCDEF, 0x76543210)
   

2. 计算S向量：

   • 通过RS矩阵乘法混合Me和Mo的异或结果
   • 得到S₀, S₁, S₂, S₃四个S盒密钥

3. 生成轮密钥：

   • 计算h(2iρ, Me)得到Aᵢ
   • 计算h((2i+1)ρ, Mo)得到Bᵢ
   • 组合生成40个轮密钥

七、与AES密钥扩展对比

Twofish的密钥扩展体现了“密钥相关S盒”的创新理念，虽然最终未成为AES标准，但其设计思想影响了后续许多密码算法。