CAST-128 分组密码算法的轮函数设计
字数 3824 2025-12-13 10:31:49

CAST-128 分组密码算法的轮函数设计

CAST-128 是一个由 Carlisle Adams 和 Stafford Tavares 在 1996 年设计的对称分组密码算法。它使用 64 位的分组长度，并支持 40 位到 128 位之间的可变密钥长度（通常以 8 位为增量）。其核心结构是基于增强的 Feistel 网络。今天，我们专注于其轮函数的设计，这是其实现混淆和扩散的关键。

题目描述：详细解释 CAST-128 分组密码算法中一轮操作（轮函数）的具体步骤，包括其输入、内部处理、以及输出。特别说明其核心组件：三个不同的轮函数类型、8个S盒的替代操作，以及模加/模减和异或的组合。

解题过程讲解：

1. 背景与整体结构
CAST-128 采用一个“平衡的 Feistel 网络”。对于一个 64 位的明文分组，它首先被分成两个 32 位的半块，通常标记为左半部分 \(L_i\) 和右半部分 \(R_i\)，其中 \(i\) 是轮数（从 0 开始）。
在每一轮（从第1轮到第16轮）中，操作如下：

  • 左半部分 \(L_i\) 保持不变，直接传递给下一轮的右半部分：\(R_{i+1} = L_i\)。
  • 右半部分 \(R_i\) 会与当前轮的轮密钥 \(K_i\) 一起，经过一个复杂的轮函数 F 的处理。这个处理结果与当前的左半部分 \(L_i\) 进行按位异或（XOR），结果成为下一轮的左半部分：\(L_{i+1} = R_i \oplus F(L_i, K_i)\)。

因此，理解 CAST-128 的核心，就是理解其轮函数 \(F\) 的内部运作。

2. 轮函数 F 的输入与概览
轮函数 \(F\) 接受两个 32 位的输入：

  1. 数据输入：当前轮的左半部分 \(L_i\)（32 位）。
  2. 轮密钥输入：当前轮的轮密钥 \(K_i\)（长度可变，最多 32 位。在轮函数内部，一个 32 位的中间值 I 会从 \(L_i\) 和 \(K_i\) 中衍生出来）。

轮函数 \(F\) 的输出是一个 32 位的值，它会与 \(R_i\) 进行异或。

3. 轮函数内部三阶段的详细分解
CAST-128 的轮函数 \(F\) 内部定义了三种不同的处理类型（Type 1, 2, 3）。整个加密过程的前 12 轮循环使用这三种类型（顺序是 1,2,3,1,2,3...），最后 4 轮（第13-16轮）使用类型 1, 2, 3, 1。每种类型的核心区别在于如何组合模加（模 2^32 加法，记作“+”）、模减（模 2^32 减法，记作“-”） 和异或（⊕） 操作。我们一步步来看。

  • 第一步：生成中间值 I
    首先，从 \(L_i\) 和 \(K_i\) 生成一个 32 位的中间值 \(I\)。

    • 轮密钥 \(K_i\) 被分成两部分：最高有效的 \(m\) 位（称为 \(K_{i, m}\)）和剩下的位（称为 \(K_{i, r}\)）。具体位数取决于轮密钥长度和当前轮数，这是密钥调度的一部分。我们暂时可以将其视为一个已知的 32 位值。
    • 将 \(L_i\) 与 \(K_i\) 进行组合。这里 CAST-128 使用了一个巧妙的“掩码”操作，但在最核心的、常见的描述中，这一步可以概括为：通过模加、模减或异或操作，将 \(L_i\) 和整个 32 位 \(K_i\) 结合，生成一个 32 位的 \(I\)。
      实际上，在标准描述中，\(I\) 的计算公式直接与轮类型挂钩：
    • 类型 1：\(I = ((K_i + D) \lll R_i)\) 的一种变形，但在简化理解中，可以认为 \(I = (K_i + D)\)，然后 \(I\) 被送入 S 盒。其中 \(D\) 是一个从 \(L_i\) 和 \(K_i\) 的另一部分导出的值，但为简化，我们先抓住主干：\(I\) 是 \(L_i\) 和 \(K_i\) 通过某种算术运算得到的 32 位数。

  • 第二步：S 盒替换
    这是轮函数实现“混淆”的核心。CAST-128 使用了 8 个不同的 8 位输入、32 位输出的 S 盒（记作 S1, S2, …, S8）。

    • 上一步得到的 32 位中间值 \(I\) 被平均分成 4 个字节（8 位一组）：\(I = [I_a, I_b, I_c, I_d]\)。
    • 每个字节独立地作为一个索引，输入到指定的 S 盒中进行查表替换。替换规则是固定的、公开的，但具有很强的非线性。
    • 具体映射是：
      • 字节 \(I_a\) 输入 S 盒 S1，输出一个 32 位的值 \(Sa\)。
      • 字节 \(I_b\) 输入 S 盒 S2，输出一个 32 位的值 \(Sb\)。
      • 字节 \(I_c\) 输入 S 盒 S3，输出一个 32 位的值 \(Sc\)。
      • 字节 \(I_d\) 输入 S 盒 S4，输出一个 32 位的值 \(Sd\)。
    • 然后，这四个 32 位的输出（\(Sa, Sb, Sc, Sd\)）会通过三种不同的算术/逻辑操作组合起来，生成最终的 32 位输出。组合方式再次取决于轮类型。

  • 第三步：组合操作（核心差异点）
    这是三种轮类型最根本的区别所在。我们用符号表示四个 S 盒输出：\(Sa, Sb, Sc, Sd\)。

    • 类型 1 轮函数：

\[ F = ((Sa \oplus Sb) - Sc) \oplus Sd \]

    计算顺序是：先计算 $ Sa $ 和 $ Sb $ 的异或（$ Sa \oplus Sb $），然后对这个结果与 $ Sc $ 进行**模 2^32 减法**（减法结果再对 2^32 取模），最后将这个减法结果与 $ Sd $ 进行**异或**。

- **类型 2 轮函数**：

\[ F = ((Sa - Sb) + Sc) \oplus Sd \]

    计算顺序是：先对 $ Sa $ 和 $ Sb $ 进行**模 2^32 减法**，然后将结果与 $ Sc $ 进行**模 2^32 加法**，最后将这个加法结果与 $ Sd $ 进行**异或**。

- **类型 3 轮函数**：

\[ F = ((Sa + Sb) \oplus Sc) - Sd \]

    计算顺序是：先对 $ Sa $ 和 $ Sb $ 进行**模 2^32 加法**，然后将结果与 $ Sc $ 进行**异或**，最后将这个异或结果与 $ Sd $ 进行**模 2^32 减法**。

**注意**：这里的加、减、异或都是 32 位字之间的操作。模运算确保了结果仍在 32 位范围内。

4. 轮函数输出
经过第三步组合计算得到的 32 位结果，就是本轮轮函数 \(F(L_i, K_i)\) 的最终输出。这个输出将与右半部分 \(R_i\) 进行异或，产生下一轮的左半部分 \(L_{i+1}\)。

5. 设计意图与小结

  • 多种轮类型：通过交替使用基于模加、模减和异或的不同组合顺序，CAST-128 增加了算法的非线性和复杂性，使得密码分析（如差分分析或线性分析）更为困难，因为攻击者需要同时处理多种不同的代数结构。
  • 大 S 盒：使用 8x32 位的 S 盒（即 8 位输入，32 位输出）提供了强大的非线性变换，是实现混淆的主要组件。输出是 32 位的，这比很多密码（如 DES 的 4 位或 6 位 S 盒）提供了更大的“雪崩效应”。
  • 混合群运算：模加和异或分别属于不同的代数群（模 2^32 加法群和模 2 加法群，即异或），将它们混合使用可以破坏代数结构中可能存在的简单关系，增强安全性。

总结一下 CAST-128 一轮操作的流程：

  1. 拆分输入：当前左半块 \(L_i\) 和轮密钥 \(K_i\) 作为轮函数 \(F\) 的输入。
  2. 生成中间值：根据轮类型，通过模加/模减/异或组合 \(L_i\) 和 \(K_i\)，生成一个 32 位中间值 \(I\)。
  3. S盒替换：将 \(I\) 分成 4 个字节，分别输入 4 个不同的 8x32 S 盒（S1, S2, S3, S4），得到四个 32 位的输出 \(Sa, Sb, Sc, Sd\)。
  4. 组合运算：根据当前轮的类型（1, 2 或 3），用特定的顺序对 \(Sa, Sb, Sc, Sd\) 进行模加、模减和异或操作，得到一个 32 位结果。
  5. 输出与 Feistel 交换：上一步的结果就是 \(F(L_i, K_i)\)。然后计算 \(L_{i+1} = R_i \oplus F(L_i, K_i)\)，\(R_{i+1} = L_i\)。完成一轮。

这个精巧的轮函数设计，结合其可变的密钥长度和 16 轮的迭代，使得 CAST-128 在其提出时成为了一个安全、高效的对称密码算法，并被广泛采纳（例如在早期 PGP 和某些 TLS 版本中）。

CAST-128 分组密码算法的轮函数设计 CAST-128 是一个由 Carlisle Adams 和 Stafford Tavares 在 1996 年设计的对称分组密码算法。它使用 64 位的分组长度，并支持 40 位到 128 位之间的可变密钥长度（通常以 8 位为增量）。其核心结构是基于增强的 Feistel 网络。今天，我们专注于其轮函数的设计，这是其实现混淆和扩散的关键。 题目描述 ：详细解释 CAST-128 分组密码算法中一轮操作（轮函数）的具体步骤，包括其输入、内部处理、以及输出。特别说明其核心组件：三个不同的轮函数类型、8个S盒的替代操作，以及模加/模减和异或的组合。 解题过程讲解 ： 1. 背景与整体结构 CAST-128 采用一个“平衡的 Feistel 网络”。对于一个 64 位的明文分组，它首先被分成两个 32 位的半块，通常标记为左半部分 \( L_ i \) 和右半部分 \( R_ i \)，其中 \( i \) 是轮数（从 0 开始）。 在每一轮（从第1轮到第16轮）中，操作如下： 左半部分 \( L_ i \) 保持不变，直接传递给下一轮的右半部分：\( R_ {i+1} = L_ i \)。 右半部分 \( R_ i \) 会与当前轮的轮密钥 \( K_ i \) 一起，经过一个复杂的 轮函数 F 的处理。这个处理结果与当前的左半部分 \( L_ i \) 进行按位异或（XOR），结果成为下一轮的左半部分：\( L_ {i+1} = R_ i \oplus F(L_ i, K_ i) \)。 因此，理解 CAST-128 的核心，就是理解其轮函数 \( F \) 的内部运作。 2. 轮函数 F 的输入与概览 轮函数 \( F \) 接受两个 32 位的输入： 数据输入 ：当前轮的左半部分 \( L_ i \)（32 位）。 轮密钥输入 ：当前轮的轮密钥 \( K_ i \)（长度可变，最多 32 位。在轮函数内部，一个 32 位的中间值 I 会从 \( L_ i \) 和 \( K_ i \) 中衍生出来）。 轮函数 \( F \) 的输出是一个 32 位的值，它会与 \( R_ i \) 进行异或。 3. 轮函数内部三阶段的详细分解 CAST-128 的轮函数 \( F \) 内部定义了 三种不同的处理类型 （Type 1, 2, 3）。整个加密过程的前 12 轮循环使用这三种类型（顺序是 1,2,3,1,2,3...），最后 4 轮（第13-16轮）使用类型 1, 2, 3, 1。每种类型的核心区别在于如何组合 模加（模 2^32 加法，记作“+”） 、 模减（模 2^32 减法，记作“-”） 和 异或（⊕） 操作。我们一步步来看。 第一步：生成中间值 I 首先，从 \( L_ i \) 和 \( K_ i \) 生成一个 32 位的中间值 \( I \)。 轮密钥 \( K_ i \) 被分成两部分：最高有效的 \( m \) 位（称为 \( K_ {i, m} \)）和剩下的位（称为 \( K_ {i, r} \)）。具体位数取决于轮密钥长度和当前轮数，这是密钥调度的一部分。我们暂时可以将其视为一个已知的 32 位值。 将 \( L_ i \) 与 \( K_ i \) 进行组合。这里 CAST-128 使用了一个巧妙的“掩码”操作，但在最核心的、常见的描述中，这一步可以概括为：通过模加、模减或异或操作，将 \( L_ i \) 和整个 32 位 \( K_ i \) 结合，生成一个 32 位的 \( I \)。 实际上，在标准描述中，\( I \) 的计算公式直接与轮类型挂钩： 类型 1 ：\( I = ((K_ i + D) \lll R_ i) \) 的一种变形，但在简化理解中，可以认为 \( I = (K_ i + D) \)，然后 \( I \) 被送入 S 盒。其中 \( D \) 是一个从 \( L_ i \) 和 \( K_ i \) 的另一部分导出的值，但为简化，我们先抓住主干：\( I \) 是 \( L_ i \) 和 \( K_ i \) 通过某种算术运算得到的 32 位数。 第二步：S 盒替换 这是轮函数实现“混淆”的核心。CAST-128 使用了 8 个不同的 8 位输入、32 位输出的 S 盒（记作 S1, S2, …, S8）。 上一步得到的 32 位中间值 \( I \) 被平均分成 4 个字节（8 位一组）：\( I = [ I_ a, I_ b, I_ c, I_ d ] \)。 每个字节独立地作为一个索引，输入到指定的 S 盒中进行查表替换。替换规则是固定的、公开的，但具有很强的非线性。 具体映射是： 字节 \( I_ a \) 输入 S 盒 S1，输出一个 32 位的值 \( Sa \)。 字节 \( I_ b \) 输入 S 盒 S2，输出一个 32 位的值 \( Sb \)。 字节 \( I_ c \) 输入 S 盒 S3，输出一个 32 位的值 \( Sc \)。 字节 \( I_ d \) 输入 S 盒 S4，输出一个 32 位的值 \( Sd \)。 然后，这四个 32 位的输出（\( Sa, Sb, Sc, Sd \)）会通过三种不同的算术/逻辑操作组合起来，生成最终的 32 位输出。组合方式再次取决于轮类型。 第三步：组合操作（核心差异点） 这是三种轮类型最根本的区别所在。我们用符号表示四个 S 盒输出：\( Sa, Sb, Sc, Sd \)。 类型 1 轮函数 ： \[ F = ((Sa \oplus Sb) - Sc) \oplus Sd \] 计算顺序是：先计算 \( Sa \) 和 \( Sb \) 的异或（\( Sa \oplus Sb \)），然后对这个结果与 \( Sc \) 进行 模 2^32 减法 （减法结果再对 2^32 取模），最后将这个减法结果与 \( Sd \) 进行 异或 。 类型 2 轮函数 ： \[ F = ((Sa - Sb) + Sc) \oplus Sd \] 计算顺序是：先对 \( Sa \) 和 \( Sb \) 进行 模 2^32 减法 ，然后将结果与 \( Sc \) 进行 模 2^32 加法 ，最后将这个加法结果与 \( Sd \) 进行 异或 。 类型 3 轮函数 ： \[ F = ((Sa + Sb) \oplus Sc) - Sd \] 计算顺序是：先对 \( Sa \) 和 \( Sb \) 进行 模 2^32 加法 ，然后将结果与 \( Sc \) 进行 异或 ，最后将这个异或结果与 \( Sd \) 进行 模 2^32 减法 。 注意 ：这里的加、减、异或都是 32 位字之间的操作。模运算确保了结果仍在 32 位范围内。 4. 轮函数输出 经过第三步组合计算得到的 32 位结果，就是本轮轮函数 \( F(L_ i, K_ i) \) 的最终输出。这个输出将与右半部分 \( R_ i \) 进行异或，产生下一轮的左半部分 \( L_ {i+1} \)。 5. 设计意图与小结 多种轮类型 ：通过交替使用基于模加、模减和异或的不同组合顺序，CAST-128 增加了算法的非线性和复杂性，使得密码分析（如差分分析或线性分析）更为困难，因为攻击者需要同时处理多种不同的代数结构。 大 S 盒 ：使用 8x32 位的 S 盒（即 8 位输入，32 位输出）提供了强大的非线性变换，是实现混淆的主要组件。输出是 32 位的，这比很多密码（如 DES 的 4 位或 6 位 S 盒）提供了更大的“雪崩效应”。 混合群运算 ：模加和异或分别属于不同的代数群（模 2^32 加法群和模 2 加法群，即异或），将它们混合使用可以破坏代数结构中可能存在的简单关系，增强安全性。 总结一下 CAST-128 一轮操作的流程 ： 拆分输入 ：当前左半块 \( L_ i \) 和轮密钥 \( K_ i \) 作为轮函数 \( F \) 的输入。 生成中间值 ：根据轮类型，通过模加/模减/异或组合 \( L_ i \) 和 \( K_ i \)，生成一个 32 位中间值 \( I \)。 S盒替换 ：将 \( I \) 分成 4 个字节，分别输入 4 个不同的 8x32 S 盒（S1, S2, S3, S4），得到四个 32 位的输出 \( Sa, Sb, Sc, Sd \)。 组合运算 ：根据当前轮的类型（1, 2 或 3），用特定的顺序对 \( Sa, Sb, Sc, Sd \) 进行模加、模减和异或操作，得到一个 32 位结果。 输出与 Feistel 交换 ：上一步的结果就是 \( F(L_ i, K_ i) \)。然后计算 \( L_ {i+1} = R_ i \oplus F(L_ i, K_ i) \)，\( R_ {i+1} = L_ i \)。完成一轮。 这个精巧的轮函数设计，结合其可变的密钥长度和 16 轮的迭代，使得 CAST-128 在其提出时成为了一个安全、高效的对称密码算法，并被广泛采纳（例如在早期 PGP 和某些 TLS 版本中）。