Threefish 块密码算法的轮函数设计
字数 3056 2025-12-09 15:45:25

Threefish 块密码算法的轮函数设计

题目描述

Threefish 是一个为 SHA-3 竞赛候选算法 Skein 哈希函数而设计的对称密钥块密码算法，由 Bruce Schneier 等人设计。它是一种大块（如 256 位、512 位、1024 位）分组密码，采用了特殊的“无密钥调度”（实际上是与轮数相关的少量常量相加）和“可调分组密码”的设计理念。本题目要求详细解析其核心部分——轮函数的设计，包括其结构、混合操作、排列规则以及每轮中唯一的密钥相关操作。

解题过程详解

我们以 Threefish-256（即分组大小为 256 比特，密钥也为 256 比特，可调参数为 128 比特）为例，详细讲解其轮函数的设计。其轮函数是典型的“无 Feistel 结构、基于字（Word）的加-旋转-异或（ARX）设计”。

1. 核心结构：UBI（Unique Block Iteration）与 MIX 函数

Threefish 的核心变换由多轮（如 72 轮）组成。每一轮（Round）由以下两部分构成：

  1. 子密钥注入（Subkey Injection）：每隔若干轮（例如 4 轮），会与一个轮子密钥（Round Subkey）进行模 2^64 加法。这是轮函数中唯一直接与主密钥相关的部分。
  2. 内部混合（Mixing Rounds）：不注入子密钥的轮次，由多个并行的 MIX 变换 和一个 字排列（Permutation） 组成。这是算法的核心混淆和扩散步骤。

由于子密钥注入相对独立，我们首先重点讲解内部混合轮的核心操作。

2. 基本单元：MIX 函数

Threefish 将状态（256 比特）划分为 4 个 64 比特字（v0, v1, v2, v3）。MIX 函数一次操作两个字（一对）。它的定义如下：
MIX(d, j, x0, x1) = (y0, y1)， 其中：

  • d 是当前的轮次编号（从 0 开始）。
  • j 是该轮内 MIX 函数实例的索引（对于 256 位，j 可取 0 或 1，因为 4 个字可以组成 2 对）。
  • (x0, x1) 是输入的 2 个 64 比特字。
  • 运算为：
    1. y0 = (x0 + x1) mod 2^64 // 模 2^64 加法
    2. y1 = (x1 <<< R(d mod 8, j)) XOR y0 // 循环左移后与 y0 异或
      这里 R(d mod 8, j) 是一个预定义的常量旋转数表。这是 ARX 设计模式的典型体现：加法（A）提供非线性，旋转（R）提供位扩散，异或（X）组合结果。

为什么这样设计？

  • 加法：在模 2^64 下，加法是唯一非线性组件（相对于比特的异或和移位而言），能提供良好的非线性扩散。
  • 旋转：将低位的信息扩散到高位，打破了字的位与位之间的独立性。每轮的旋转常数不同，确保了在整个加密过程中，比特被充分混合。
  • 异或：将两个结果结合在一起，使得输出 y1 同时依赖于 x0 和 x1 的原始值以及它们的和。

3. 单轮内部混合步骤详解

对于 Threefish-256 的一轮内部混合（不包含子密钥注入的轮次），操作如下：

步骤 1：并行 MIX
将 4 个字的状态分成 2 对，同时对每对应用 MIX 函数。

  • 第 0 对：(v0, v1) = MIX(d, 0, v0, v1) // 计算新的 v0， v1
  • 第 1 对：(v2, v3) = MIX(d, 1, v2, v3) // 计算新的 v2， v3
    此时，状态从 (v0, v1, v2, v3) 更新为 (v0_new, v1_new, v2_new, v3_new)。

步骤 2：字排列（Permutation）
为了使不同字对之间的信息能相互扩散，在一轮的 4 个 MIX 操作之后，需要对 4 个字进行简单的位置交换。Threefish 使用一个固定的排列模式 P。
对于 256 位（4 字）版本，排列 P(i) 定义为：

  • P(0) = 0
  • P(1) = 3
  • P(2) = 2
  • P(3) = 1
    （对于 512 位是 8 个字的更复杂排列，1024 位是 16 个字）。
    这意味着经过排列后，新的状态字顺序变为：
    (v0_new, v3_new, v2_new, v1_new)。

排列的目的：确保经过几轮之后，最初在不同字对中的比特能够相遇，并进入同一个 MIX 函数进行处理，从而实现完全的扩散。

4. 子密钥注入

Threefish 没有复杂的密钥调度算法。主密钥 K[0..N-1] 和可调参数 T[0..1] 被用来生成一系列简单的轮子密钥。每 Nw 轮（对于 Threefish-256，Nw=4 轮）注入一个子密钥。

子密钥生成（以第 s 个子密钥为例）：
SubKey_s[i] = K[(s + i) mod (N+1)]， 对于 i = 0 到 N-2。
SubKey_s[N-1] = K[(s + N-1) mod (N+1)] + T[s mod 3]。
SubKey_s[N] = K[(s + N) mod (N+1)] + s。
其中，K[N] 是一个定义好的常量（C240...），T[2] = T[0] XOR T[1]，s 是从 0 开始的子密钥索引。这里用到了模 (N+1) 的简单循环和常量加法，设计非常简洁。

注入过程：
在指定的注入轮（例如第 0, 4, 8, ... 轮），状态字的操作是：
v_i = (v_i + SubKey_s[i]) mod 2^64， 对于 i = 0 到 N-1。
这是一个简单的字级模加。这之后，轮数计数器 d 增加 1，继续进行下一轮的内部混合。

5. 完整轮函数流程示例（以三轮为例）

假设我们处于第 d 轮（非子密钥注入轮）。

  1. 输入状态：四个 64 比特字 V = (v0, v1, v2, v3)。
  2. 执行 MIX：
    • (v0, v1) = MIX(d, 0, v0, v1)
    • (v2, v3) = MIX(d, 1, v2, v3)
  3. 执行排列：V = (v0, v3, v2, v1) // 应用排列 P
  4. 轮数递增：d = d + 1
  5. 判断是否注入子密钥：如果 d 是 4 的倍数（假设每 4 轮注入一次），则先进行子密钥注入再进行步骤 1-3。注入时，V_i = (V_i + SubKey_{d/4}[i]) mod 2^64。

总结

Threefish 的轮函数设计体现了简洁、可分析、高并行的理念：

  • 核心混合：由简单的、可并行计算的 MIX 函数（ARX）和固定的字排列交替进行，提供了良好的混淆和扩散。
  • 密钥使用：密钥材料通过简单的模加法周期性地、稀疏地注入到状态中，极大地简化了密钥调度，避免了因复杂密钥调度引入的弱点，也使得算法在密钥已知和未知情况下都能有良好的性能。
  • 安全性：其安全性依赖于大量的轮数（72 轮）和 ARX 操作的数学性质。这种设计使得它能够有效抵抗差分密码分析和线性密码分析，同时也非常适合在现代 CPU 上实现高性能的软件加密。

理解 Threefish 轮函数，关键在于掌握其“MIX（混淆扩散） + Permutation（位置交换） + 周期性密钥加法”这一清晰、模块化的设计模式。

Threefish 块密码算法的轮函数设计 题目描述 Threefish 是一个为 SHA-3 竞赛候选算法 Skein 哈希函数而设计的对称密钥块密码算法，由 Bruce Schneier 等人设计。它是一种大块（如 256 位、512 位、1024 位）分组密码，采用了特殊的“无密钥调度”（实际上是与轮数相关的少量常量相加）和“可调分组密码”的设计理念。本题目要求详细解析其核心部分——轮函数的设计，包括其结构、混合操作、排列规则以及每轮中唯一的密钥相关操作。 解题过程详解 我们以 Threefish-256（即分组大小为 256 比特，密钥也为 256 比特，可调参数为 128 比特）为例，详细讲解其轮函数的设计。其轮函数是典型的“无 Feistel 结构、基于字（Word）的加-旋转-异或（ARX）设计”。 1. 核心结构：UBI（Unique Block Iteration）与 MIX 函数 Threefish 的核心变换由多轮（如 72 轮）组成。每一轮（Round）由以下两部分构成： 子密钥注入（Subkey Injection） ：每隔若干轮（例如 4 轮），会与一个轮子密钥（Round Subkey）进行模 2^64 加法。这是轮函数中 唯一 直接与主密钥相关的部分。 内部混合（Mixing Rounds） ：不注入子密钥的轮次，由多个并行的 MIX 变换 和一个 字排列（Permutation） 组成。这是算法的核心混淆和扩散步骤。 由于子密钥注入相对独立，我们首先重点讲解内部混合轮的核心操作。 2. 基本单元：MIX 函数 Threefish 将状态（256 比特）划分为 4 个 64 比特字（v0, v1, v2, v3）。MIX 函数一次操作两个字（一对）。它的定义如下： MIX(d, j, x0, x1) = (y0, y1) ， 其中： d 是当前的轮次编号（从 0 开始）。 j 是该轮内 MIX 函数实例的索引（对于 256 位，j 可取 0 或 1，因为 4 个字可以组成 2 对）。 (x0, x1) 是输入的 2 个 64 比特字。 运算为： y0 = (x0 + x1) mod 2^64 // 模 2^64 加法 y1 = (x1 <<< R(d mod 8, j)) XOR y0 // 循环左移后与 y0 异或 这里 R(d mod 8, j) 是一个预定义的常量旋转数表。 这是 ARX 设计模式的典型体现 ：加法（A）提供非线性，旋转（R）提供位扩散，异或（X）组合结果。 为什么这样设计？ 加法 ：在模 2^64 下，加法是唯一非线性组件（相对于比特的异或和移位而言），能提供良好的非线性扩散。 旋转 ：将低位的信息扩散到高位，打破了字的位与位之间的独立性。每轮的旋转常数不同，确保了在整个加密过程中，比特被充分混合。 异或 ：将两个结果结合在一起，使得输出 y1 同时依赖于 x0 和 x1 的原始值以及它们的和。 3. 单轮内部混合步骤详解 对于 Threefish-256 的一轮内部混合（不包含子密钥注入的轮次），操作如下： 步骤 1：并行 MIX 将 4 个字的状态分成 2 对， 同时 对每对应用 MIX 函数。 第 0 对： (v0, v1) = MIX(d, 0, v0, v1) // 计算新的 v0， v1 第 1 对： (v2, v3) = MIX(d, 1, v2, v3) // 计算新的 v2， v3 此时，状态从 (v0, v1, v2, v3) 更新为 (v0_ new, v1_ new, v2_ new, v3_ new)。 步骤 2：字排列（Permutation） 为了使不同字对之间的信息能相互扩散，在一轮的 4 个 MIX 操作之后，需要对 4 个字进行简单的 位置交换 。Threefish 使用一个固定的排列模式 P。 对于 256 位（4 字）版本，排列 P(i) 定义为： P(0) = 0 P(1) = 3 P(2) = 2 P(3) = 1 （对于 512 位是 8 个字的更复杂排列，1024 位是 16 个字）。 这意味着经过排列后，新的状态字顺序变为： (v0_new, v3_new, v2_new, v1_new) 。 排列的目的：确保经过几轮之后，最初在不同字对中的比特能够相遇，并进入同一个 MIX 函数进行处理，从而实现 完全的扩散 。 4. 子密钥注入 Threefish 没有复杂的密钥调度算法。主密钥 K[ 0..N-1] 和可调参数 T[ 0..1 ] 被用来生成一系列简单的轮子密钥。每 Nw 轮（对于 Threefish-256，Nw=4 轮）注入一个子密钥。 子密钥生成 （以第 s 个子密钥为例）： SubKey_s[i] = K[(s + i) mod (N+1)] ， 对于 i = 0 到 N-2。 SubKey_s[N-1] = K[(s + N-1) mod (N+1)] + T[s mod 3] 。 SubKey_s[N] = K[(s + N) mod (N+1)] + s 。 其中， K[N] 是一个定义好的常量（ C240... ）， T[2] = T[0] XOR T[1] ， s 是从 0 开始的子密钥索引。这里用到了模 (N+1) 的简单循环和常量加法，设计非常简洁。 注入过程 ： 在指定的注入轮（例如第 0, 4, 8, ... 轮），状态字的操作是： v_i = (v_i + SubKey_s[i]) mod 2^64 ， 对于 i = 0 到 N-1。 这是一个简单的 字级模加 。这之后，轮数计数器 d 增加 1，继续进行下一轮的内部混合。 5. 完整轮函数流程示例（以三轮为例） 假设我们处于第 d 轮（非子密钥注入轮）。 输入状态 ：四个 64 比特字 V = (v0, v1, v2, v3)。 执行 MIX ： (v0, v1) = MIX(d, 0, v0, v1) (v2, v3) = MIX(d, 1, v2, v3) 执行排列 ：V = (v0, v3, v2, v1) // 应用排列 P 轮数递增 ：d = d + 1 判断是否注入子密钥 ：如果 d 是 4 的倍数（假设每 4 轮注入一次），则先进行子密钥注入再进行步骤 1-3。注入时，V_ i = (V_ i + SubKey_ {d/4}[ i ]) mod 2^64。 总结 Threefish 的轮函数设计体现了 简洁、可分析、高并行 的理念： 核心混合 ：由简单的、可并行计算的 MIX 函数（ARX）和固定的字排列交替进行，提供了良好的混淆和扩散。 密钥使用 ：密钥材料通过简单的模加法周期性地、稀疏地注入到状态中，极大地简化了密钥调度，避免了因复杂密钥调度引入的弱点，也使得算法在密钥已知和未知情况下都能有良好的性能。 安全性 ：其安全性依赖于大量的轮数（72 轮）和 ARX 操作的数学性质。这种设计使得它能够有效抵抗差分密码分析和线性密码分析，同时也非常适合在现代 CPU 上实现高性能的软件加密。 理解 Threefish 轮函数，关键在于掌握其“ MIX（混淆扩散） + Permutation（位置交换） + 周期性密钥加法 ”这一清晰、模块化的设计模式。