MARS 分组密码算法的密钥扩展过程详解

一、算法背景
MARS 是 IBM 为参与 AES 竞赛提交的分组密码算法，采用 128 比特分组、128–448 比特可变密钥长度（AES 竞赛限定 128/192/256 比特）。其核心结构结合了 Feistel 网络、SP 网络 和 密钥加/密钥乘 操作，密钥扩展过程负责将用户密钥扩展为 40 个 32 比特字 的轮密钥（K[0]...K[39]），用于后续的加解密流程。

二、密钥扩展整体步骤
设用户密钥长度为 m 字节（16 ≤ m ≤ 56），密钥扩展分为四个阶段：

1. 密钥填充与初始数组生成
2. 线性扩散变换
3. 非线性 S 盒混合
4. 轮密钥派生与重排

三、逐步详解

步骤 1：密钥填充与初始数组生成

1. 将用户密钥按 字节 读入数组 Key[0…m-1]。
2. 计算需要扩展的 32 比特字数量：
   • 设 n = ⌈m/4⌉，即密钥按 4 字节对齐后的字个数。
   • 例如 128 比特（16 字节）密钥：n = 4。
3. 将密钥字节转为 大端序 32 比特字数组 T[0…n-1]。
   • 例如 Key[0..3] 依次作为 T[0] 的最高位到最低位字节。
4. 追加固定常量 0x9E3779B9（黄金比例倒数）作为 T[n]，并设置 T[n+1…14] 初始为 0。
   • 最终 T 数组长度为 15 个字（0–14）。

步骤 2：线性扩散变换

目标：通过循环移位和异或使密钥比特充分扩散。

1. 执行 4 轮循环（每轮对 T[0…14] 进行更新）：

   for i = 0 to 14:
       T[i] = T[i] XOR ((T[(i-7) mod 15] XOR T[(i-2) mod 15]) <<< 3) XOR (4*i + j)
   

   其中 j 为轮次索引（0–3），<<< 3 表示循环左移 3 位。
2. 此步骤确保每个 T[i] 依赖于多个其他字，增加线性扩散性。

步骤 3：非线性 S 盒混合

MARS 使用 两个 512 项的 S 盒：

• S0[512]：基于 3x+1 映射与固定置换生成。
• S1[512]：基于 5x+1 映射与固定置换生成。
  （S 盒生成算法独立于密钥，此处省略细节）

混合过程：

1. 对 T[0…14] 执行 10 轮循环（每轮更新全部 15 个字）：
   • 每轮中，依次处理 T[0]…T[14]，对当前字 T[i]：
     a. 取 T[i] 的 最低 9 比特 作为索引 idx = T[i] & 0x1FF。
     b. 若 i 为偶数，查 S0[idx]；若 i 为奇数，查 S1[idx]。
     c. 将查表结果与 T[(i+1) mod 15] 异或，并循环左移 1 位。
     d. 结果写回 T[i]。
2. 此步骤引入 非线性，打破线性扩散的规律性。

步骤 4：轮密钥派生与重排

1. 经过前几步，T[0…14] 已充分混合。从中选取 10 个字 作为 核心密钥：
   • 取 T[4], T[5], T[6], T[7], T[8], T[9], T[10], T[11], T[12], T[13]。
2. 通过这 10 个字 扩展生成 40 个轮密钥字 K[0…39]：
   • 使用线性递归与固定偏移：

     for i = 0 to 39:
         j = i mod 10
         K[i] = T[j] XOR (T[(j+3) mod 10] <<< 17) XOR constant[i]
     

     其中 constant[i] 为预计算的常量（与 i 相关的小素数模 2^32）。
3. 最终调整：
   • 对部分轮密钥（用于乘法运算的轮）进行 掩码处理，确保其最低 3 比特为 101b（二进制），避免乘法运算的弱密钥。

四、轮密钥在加密中的使用
MARS 加密分为：

• 前向混合（8 轮）：使用 K[0…7] 进行密钥加与 S 盒混淆。
• 核心加密（8 轮）：使用 K[8…31] 进行 Feistel 类运算，包含 密钥乘（模 2^32乘法）和 密钥加。
• 后向混合（8 轮）：使用 K[32…39] 进行逆向密钥加与 S 盒混淆。
  密钥扩展确保每个轮密钥与用户密钥高度非线性相关。

五、安全性要点

1. 抗相关攻击：线性扩散与非线性混合结合，防止密钥比特的线性追踪。
2. 抗弱密钥：通过 S 盒混合和掩码处理，避免乘法运算的退化情况。
3. 适应性：支持可变长度密钥，扩展过程均转化为固定长度的中间数组，确保一致性。

通过以上步骤，MARS 将用户密钥转换为 40 个轮密钥，为其复杂的加解密轮函数提供充分随机化的密钥材料。