Threefish 块密码算法的密钥扩展过程
字数 4231 2025-12-10 03:54:30

Threefish 块密码算法的密钥扩展过程

我们来探讨 Threefish 块密码算法的密钥扩展过程。Threefish 是美国密码学家 Bruce Schneier 等人设计的对称密钥分组密码算法，与哈希函数 Skein 一同构成一个完整的密码学方案。它以其简洁性和与 Skein 哈希函数的协同设计而闻名。理解其密钥扩展过程，是掌握其加解密流程的基础。

一、 算法背景与基本参数

  1. 算法定位：Threefish 是一个无 Feistel 结构、无 S 盒的 ARX（Addition-Rotation-XOR）型分组密码。它直接操作 64 位字（word），结构非常规整，易于在 64 位处理器上高效实现。
  2. 核心参数：Threefish 根据块大小和密钥长度定义了三个变种：
    • Threefish-256：块大小 256 位，密钥 256 位。
    • Threefish-512：块大小 512 位，密钥 512 位。
    • Threefish-1024：块大小 1024 位，密钥 1024 位。
  3. 密钥扩展目的：Threefish 的加密过程需要用到 Nw + 1 个子密钥（其中 Nw 是块大小对应的字数，例如 512 位对应 Nw = 8 个字）。密钥扩展（也称为密钥调度）的任务就是将主密钥（和可选的“tweak”值）转换生成这一系列子密钥。

二、 密钥扩展的核心输入：主密钥与 Tweak

Threefish 的密钥扩展需要两个主要输入：

  1. 主密钥 K：长度为 Nw 个 64 位字。例如 Threefish-512，Nw = 8，主密钥就是 K[0], K[1], ..., K[7] 这 8 个 64 位字。
  2. Tweak 值 T：这是一个 128 位的辅助输入，用于增强算法的灵活性，可以关联消息序列号、随机数或特定应用上下文。T 被拆分成两个 64 位字 T[0] 和 T[1]。

三、 密钥扩展的预处理步骤：计算 K[Nw] 和 T[2]

Threefish 在生成子密钥前，会对主密钥 K 和 Tweak T 进行一个简单的预处理，目的是引入一个“常量”，增强对某些攻击的抵抗力（例如，防止密钥全零或固定值时算法的退化）。

  1. 扩展主密钥：

    • 我们定义一个新的密钥字 K[Nw]。
    • K[Nw] 的计算方式是：K[Nw] = C ⊕ K[0] ⊕ K[1] ⊕ ... ⊕ K[Nw-1]。
    • 其中 C 是一个固定的 64 位常数，C = 0x1BD11BDAA9FC1A22。这个常数称为“幻数”（Parity Constant），其作用是确保所有 Nw+1 个密钥字的异或和等于 C。
    • 为什么这样做？ 这使得密钥材料的总体具有一个非线性的“奇偶校验”性质，即使主密钥 K 的所有字都相等，经过此处理后，K[Nw] 也会变成一个不同的值，防止了整个密钥调度过程出现对称或弱化的情况。

  2. 扩展 Tweak：

    • 我们定义一个新的 Tweak 字 T[2]。
    • T[2] 的计算方式是：T[2] = T[0] ⊕ T[1]。

至此，我们有了扩展后的密钥数组 K[0], K[1], ..., K[Nw]（共 Nw+1 个字）和扩展后的 Tweak 数组 T[0], T[1], T[2]。

四、 子密钥的生成公式

Threefish 的加密过程需要进行 Nr = 72 轮（对于所有变种），每 4 轮为一组，称为一个“mixing round”。每一轮都需要一个子密钥（Nr+4 轮，因为开头有 1 个密钥加，每 4 轮中间有 3 个无密钥加的轮，最后还有 1 个密钥加）。

子密钥 ks[s][i] 的生成公式非常简洁，其中：

  • s 是子密钥的索引（s 从 0 到 Nr/4，因为每 4 轮用一组子密钥，所以共有 Nr/4 + 1 = 19 组子密钥）。
  • i 是子密钥中字的索引（i 从 0 到 Nw-1，因为一个子密钥的长度和块长度一样，也是 Nw 个字）。

生成公式如下：

ks[s][i] = K[(s+i) % (Nw+1)]

然后，对于满足 i = Nw-3 或 i = Nw-4 的情况，还需要加上一个特殊的 Tweak 混合项：

ks[s][Nw-3] += T[s % 3]
ks[s][Nw-2] += T[(s+1) % 3]

最后，对于 s 是最后一组（即第 18 组）的子密钥，还需要加一个轮次常数：

ks[18][Nw-1] += s （这里 s 就是 18）

让我们通过一个 Threefish-256 (Nw = 4) 的例子来逐步理解。

  1. 预处理：

    • 主密钥 K = [K0, K1, K2, K3]。
    • 计算 K[4] = C ⊕ K0 ⊕ K1 ⊕ K2 ⊕ K3。
    • Tweak T = [T0, T1]。
    • 计算 T[2] = T0 ⊕ T1。
    • 现在，我们拥有 K[0..4] 和 T[0..2]。

  2. 生成第 0 组子密钥 (s=0)：

    • 基本公式：ks[0][i] = K[(0+i) % 5]。
      • ks[0][0] = K[0]
      • ks[0][1] = K[1]
      • ks[0][2] = K[2]
      • ks[0][3] = K[3] （注意，i = 3 对应 Nw-1，不是 Nw-3 或 Nw-2，所以不加 Tweak。对于 Nw=4，Nw-3=1，Nw-2=2，但这里公式特指最后两个字？实际上标准定义是固定的索引位置。让我们重新核对通用公式）

通用公式修正与精炼：

更准确的标准定义是，对于 i 从 0 到 Nw-1：

ks[s][i] = K[(s+i) % (Nw+1)]

然后，在三个特定位置加上 Tweak 值：

  • ks[s][(Nw-3) % Nw] += T[s % 3]
  • ks[s][(Nw-2) % Nw] += T[(s+1) % 3]
  • ks[s][(Nw-1) % Nw] += T[(s+2) % 3]

最后，对于 s 是最后一组（s = Nr/4）的子密钥，再额外加上轮次常数 s 到其中一个字（通常是 ks[s][Nw-1]）。

让我们用 Threefish-512 (Nw=8) 重新举例，因为它更常见，且索引更清晰。

例：Threefish-512 (Nw=8) 的第 s=0 组子密钥：

  1. 预处理得到 K[0..8] 和 T[0..2]。
  2. 应用基本公式：
    • ks[0][0] = K[(0+0)%9] = K[0]
    • ks[0][1] = K[(0+1)%9] = K[1]
    • ks[0][2] = K[(0+2)%9] = K[2]
    • ks[0][3] = K[(0+3)%9] = K[3]
    • ks[0][4] = K[(0+4)%9] = K[4]
    • ks[0][5] = K[(0+5)%9] = K[5] (此位置对应 i=5, 即 Nw-3=5)
    • ks[0][6] = K[(0+6)%9] = K[6] (此位置对应 i=6, 即 Nw-2=6)
    • ks[0][7] = K[(0+7)%9] = K[7] (此位置对应 i=7, 即 Nw-1=7)
  3. 加上 Tweak 混合：
    • ks[0][5] += T[0 % 3] = T[0] // i = Nw-3
    • ks[0][6] += T[(0+1) % 3] = T[1] // i = Nw-2
    • ks[0][7] += T[(0+2) % 3] = T[2] // i = Nw-1
  4. 因为 s=0 不是最后一组（最后一组是 s=18），所以不加轮次常数。

再举一组，例如第 s=1 组子密钥：

  1. 基本公式：
    • ks[1][0] = K[(1+0)%9] = K[1]
    • ks[1][1] = K[(1+1)%9] = K[2]
    • ...
    • ks[1][7] = K[(1+7)%9] = K[8] (注意，这里用到了预处理生成的 K[8])
  2. 加上 Tweak 混合：
    • ks[1][5] += T[1 % 3] = T[1]
    • ks[1][6] += T[(1+1) % 3] = T[2]
    • ks[1][7] += T[(1+2) % 3] = T[0] (注意，Tweak 的索引是循环的)

五、 密钥扩展的特点与安全性

  1. 简洁性：整个密钥扩展过程几乎没有复杂的运算，只有模加、异或和固定索引的循环。这使得它在软硬件实现上都非常高效。
  2. 非线性来源：算法的非线性主要来自轮函数内部的模加和循环移位，而不是密钥扩展本身。密钥扩展引入的非线性主要来自预处理阶段的奇偶常数 C 和 Tweak 的异或扩展 T[2]=T[0]⊕T[1]。
  3. 抗弱密钥：预处理步骤 K[Nw] = C ⊕ ΣK[i] 确保了即使主密钥是弱值（如全零），扩展后的密钥数组也不会是平凡的，从而防止了因密钥导致的算法行为退化。
  4. 与 Tweak 的绑定：Tweak 值被紧密地织入到每一组子密钥中，确保了即使使用相同的主密钥，不同的 Tweak 也会产生完全不同的加密路径，这在实际应用中（如磁盘加密中每个扇区使用不同的 Tweak）非常有用。

总结

Threefish 的密钥扩展过程可以概括为三个步骤：

  1. 预处理：计算奇偶密钥字 K[Nw] 和扩展 Tweak 字 T[2]。
  2. 循环取用：通过公式 ks[s][i] = K[(s+i) % (Nw+1)] 循环地从扩展密钥数组中选取字来构建子密钥的“骨架”。
  3. 注入 Tweak 与常数：在子密钥的最后三个字（索引 Nw-3, Nw-2, Nw-1）上分别加上循环变化的 Tweak 值 T[s % 3], T[(s+1) % 3], T[(s+2) % 3]，并在最后一组子密钥上添加一个简单的轮次常数。

这个过程确保了子密钥既与主密钥强相关，又受到 Tweak 的有效调制，同时通过预处理避免了弱密钥，最终为 Threefish 强大而高效的 ARX 轮函数提供了所需的所有轮密钥材料。

Threefish 块密码算法的密钥扩展过程 我们来探讨 Threefish 块密码算法的密钥扩展过程。Threefish 是美国密码学家 Bruce Schneier 等人设计的对称密钥分组密码算法，与哈希函数 Skein 一同构成一个完整的密码学方案。它以其简洁性和与 Skein 哈希函数的协同设计而闻名。理解其密钥扩展过程，是掌握其加解密流程的基础。 一、 算法背景与基本参数 算法定位 ：Threefish 是一个无 Feistel 结构、无 S 盒的 ARX（Addition-Rotation-XOR）型分组密码。它直接操作 64 位字（word），结构非常规整，易于在 64 位处理器上高效实现。 核心参数 ：Threefish 根据块大小和密钥长度定义了三个变种： Threefish-256：块大小 256 位，密钥 256 位。 Threefish-512：块大小 512 位，密钥 512 位。 Threefish-1024：块大小 1024 位，密钥 1024 位。 密钥扩展目的 ：Threefish 的加密过程需要用到 Nw + 1 个子密钥（其中 Nw 是块大小对应的字数，例如 512 位对应 Nw = 8 个字）。密钥扩展（也称为密钥调度）的任务就是将主密钥（和可选的“tweak”值）转换生成这一系列子密钥。 二、 密钥扩展的核心输入：主密钥与 Tweak Threefish 的密钥扩展需要两个主要输入： 主密钥 K ：长度为 Nw 个 64 位字。例如 Threefish-512， Nw = 8 ，主密钥就是 K[0], K[1], ..., K[7] 这 8 个 64 位字。 Tweak 值 T ：这是一个 128 位的辅助输入，用于增强算法的灵活性，可以关联消息序列号、随机数或特定应用上下文。 T 被拆分成两个 64 位字 T[0] 和 T[1] 。 三、 密钥扩展的预处理步骤：计算 K[Nw] 和 T[2] Threefish 在生成子密钥前，会对主密钥 K 和 Tweak T 进行一个简单的预处理，目的是引入一个“常量”，增强对某些攻击的抵抗力（例如，防止密钥全零或固定值时算法的退化）。 扩展主密钥 ： 我们定义一个新的密钥字 K[Nw] 。 K[Nw] 的计算方式是： K[Nw] = C ⊕ K[0] ⊕ K[1] ⊕ ... ⊕ K[Nw-1] 。 其中 C 是一个固定的 64 位常数， C = 0x1BD11BDAA9FC1A22 。这个常数称为“幻数”（Parity Constant），其作用是确保所有 Nw+1 个密钥字的异或和等于 C 。 为什么这样做？ 这使得密钥材料的总体具有一个非线性的“奇偶校验”性质，即使主密钥 K 的所有字都相等，经过此处理后， K[Nw] 也会变成一个不同的值，防止了整个密钥调度过程出现对称或弱化的情况。 扩展 Tweak ： 我们定义一个新的 Tweak 字 T[2] 。 T[2] 的计算方式是： T[2] = T[0] ⊕ T[1] 。 至此，我们有了扩展后的密钥数组 K[0], K[1], ..., K[Nw] （共 Nw+1 个字）和扩展后的 Tweak 数组 T[0], T[1], T[2] 。 四、 子密钥的生成公式 Threefish 的加密过程需要进行 Nr = 72 轮（对于所有变种），每 4 轮为一组，称为一个“mixing round”。每一轮都需要一个子密钥（ Nr+4 轮，因为开头有 1 个密钥加，每 4 轮中间有 3 个无密钥加的轮，最后还有 1 个密钥加）。 子密钥 ks[s][i] 的生成公式非常简洁，其中： s 是子密钥的索引（ s 从 0 到 Nr/4 ，因为每 4 轮用一组子密钥，所以共有 Nr/4 + 1 = 19 组子密钥）。 i 是子密钥中字的索引（ i 从 0 到 Nw-1 ，因为一个子密钥的长度和块长度一样，也是 Nw 个字）。 生成公式如下： ks[s][i] = K[(s+i) % (Nw+1)] 然后，对于满足 i = Nw-3 或 i = Nw-4 的情况，还需要加上一个特殊的 Tweak 混合项： ks[s][Nw-3] += T[s % 3] ks[s][Nw-2] += T[(s+1) % 3] 最后，对于 s 是最后一组（即第 18 组）的子密钥，还需要加一个轮次常数： ks[18][Nw-1] += s （这里 s 就是 18） 让我们通过一个 Threefish-256 ( Nw = 4 ) 的例子来逐步理解。 预处理 ： 主密钥 K = [K0, K1, K2, K3] 。 计算 K[4] = C ⊕ K0 ⊕ K1 ⊕ K2 ⊕ K3 。 Tweak T = [T0, T1] 。 计算 T[2] = T0 ⊕ T1 。 现在，我们拥有 K[0..4] 和 T[0..2] 。 生成第 0 组子密钥 ( s=0 ) ： 基本公式： ks[0][i] = K[(0+i) % 5] 。 ks[0][0] = K[0] ks[0][1] = K[1] ks[0][2] = K[2] ks[0][3] = K[3] （注意， i = 3 对应 Nw-1 ，不是 Nw-3 或 Nw-2 ，所以不加 Tweak。对于 Nw=4 ， Nw-3=1 ， Nw-2=2 ，但这里公式特指最后两个字？实际上标准定义是固定的索引位置。让我们重新核对通用公式） 通用公式修正与精炼 ： 更准确的标准定义是，对于 i 从 0 到 Nw-1 ： 然后， 在三个特定位置加上 Tweak 值 ： ks[s][(Nw-3) % Nw] += T[s % 3] ks[s][(Nw-2) % Nw] += T[(s+1) % 3] ks[s][(Nw-1) % Nw] += T[(s+2) % 3] 最后，对于 s 是最后一组（ s = Nr/4 ）的子密钥，再额外加上轮次常数 s 到其中一个字（通常是 ks[s][Nw-1] ）。 让我们用 Threefish-512 ( Nw=8 ) 重新举例，因为它更常见，且索引更清晰。 例：Threefish-512 ( Nw=8 ) 的第 s=0 组子密钥： 预处理得到 K[0..8] 和 T[0..2] 。 应用基本公式： ks[0][0] = K[(0+0)%9] = K[0] ks[0][1] = K[(0+1)%9] = K[1] ks[0][2] = K[(0+2)%9] = K[2] ks[0][3] = K[(0+3)%9] = K[3] ks[0][4] = K[(0+4)%9] = K[4] ks[0][5] = K[(0+5)%9] = K[5] (此位置对应 i=5 , 即 Nw-3=5 ) ks[0][6] = K[(0+6)%9] = K[6] (此位置对应 i=6 , 即 Nw-2=6 ) ks[0][7] = K[(0+7)%9] = K[7] (此位置对应 i=7 , 即 Nw-1=7 ) 加上 Tweak 混合： ks[0][5] += T[0 % 3] = T[0] // i = Nw-3 ks[0][6] += T[(0+1) % 3] = T[1] // i = Nw-2 ks[0][7] += T[(0+2) % 3] = T[2] // i = Nw-1 因为 s=0 不是最后一组（最后一组是 s=18 ），所以不加轮次常数。 再举一组，例如第 s=1 组子密钥 ： 基本公式： ks[1][0] = K[(1+0)%9] = K[1] ks[1][1] = K[(1+1)%9] = K[2] ... ks[1][7] = K[(1+7)%9] = K[8] (注意，这里用到了预处理生成的 K[8] ) 加上 Tweak 混合： ks[1][5] += T[1 % 3] = T[1] ks[1][6] += T[(1+1) % 3] = T[2] ks[1][7] += T[(1+2) % 3] = T[0] (注意，Tweak 的索引是循环的) 五、 密钥扩展的特点与安全性 简洁性 ：整个密钥扩展过程几乎没有复杂的运算，只有模加、异或和固定索引的循环。这使得它在软硬件实现上都非常高效。 非线性来源 ：算法的非线性主要来自轮函数内部的模加和循环移位，而不是密钥扩展本身。密钥扩展引入的非线性主要来自预处理阶段的奇偶常数 C 和 Tweak 的异或扩展 T[2]=T[0]⊕T[1] 。 抗弱密钥 ：预处理步骤 K[Nw] = C ⊕ ΣK[i] 确保了即使主密钥是弱值（如全零），扩展后的密钥数组也不会是平凡的，从而防止了因密钥导致的算法行为退化。 与 Tweak 的绑定 ：Tweak 值被紧密地织入到每一组子密钥中，确保了即使使用相同的主密钥，不同的 Tweak 也会产生完全不同的加密路径，这在实际应用中（如磁盘加密中每个扇区使用不同的 Tweak）非常有用。 总结 Threefish 的密钥扩展过程可以概括为三个步骤： 预处理 ：计算奇偶密钥字 K[Nw] 和扩展 Tweak 字 T[2] 。 循环取用 ：通过公式 ks[s][i] = K[(s+i) % (Nw+1)] 循环地从扩展密钥数组中选取字来构建子密钥的“骨架”。 注入 Tweak 与常数 ：在子密钥的最后三个字（索引 Nw-3 , Nw-2 , Nw-1 ）上分别加上循环变化的 Tweak 值 T[s % 3] , T[(s+1) % 3] , T[(s+2) % 3] ，并在最后一组子密钥上添加一个简单的轮次常数。 这个过程确保了子密钥既与主密钥强相关，又受到 Tweak 的有效调制，同时通过预处理避免了弱密钥，最终为 Threefish 强大而高效的 ARX 轮函数提供了所需的所有轮密钥材料。