Salsa20流密码算法的轮函数设计

题目描述

Salsa20是一种流密码算法，以其简洁、快速和高度并行的设计而闻名。它的核心是“哈希”函数（实际上是一个伪随机函数），通过重复应用其轮函数，将一个256位密钥、一个64位随机数（nonce）和一个64位块计数器混合，生成密钥流。本题将详细拆解Salsa20轮函数（核心置换）的设计，解释其如何将16个32位字的内部状态进行多轮混淆和扩散，从而产生高质量的伪随机密钥流。

解题过程

我们将Salsa20轮函数的设计分解为以下几个步骤：

1. 理解算法背景与结构

Salsa20的加密过程可概括为：密钥流 = Salsa20(密钥, 随机数, 块计数器)，然后密文 = 明文 ⊕ 密钥流。这里的Salsa20函数，对每个64字节（512位）的密钥流块，执行以下操作：

1. 初始化：将256位密钥、64位随机数、64位块计数器和4个固定常量，组合成一个4x4的32位字矩阵（共16个字，512位），作为初始状态矩阵。
2. 核心置换：对该状态矩阵执行20轮（精简版为12或8轮）的混合操作。这20轮操作是轮函数的重复迭代。
3. 最终加和：将经过20轮混合后的状态矩阵与初始状态矩阵按字相加，得到最终的输出块（即密钥流块）。

轮函数 就是步骤2中每轮执行的具体操作。Salsa20的轮函数分为“列轮”和“行轮”，两者交替进行。

2. 分析内部状态表示

初始状态是一个4x4矩阵（记为x），每个元素是一个32位字（小端序）。其典型排列如下（k0-k7是密钥字，n0, n1是随机数字，c0-c3是固定常量，b0, b1是块计数器）：

x[0]  = c0       | x[1]  = k0 | x[2]  = k1 | x[3]  = k2
x[4]  = k3       | x[5]  = c1 | x[6]  = n0 | x[7]  = n1
x[8]  = b0       | x[9]  = b1 | x[10] = c2 | x[11] = k4
x[12] = k5       | x[13] = k6 | x[14] = k7 | x[15] = c3

轮函数将对这个矩阵x进行原地修改。

3. 剖析核心运算：quarterround

Salsa20所有混淆操作的基础是一个称为 quarterround (QR) 的函数。它接收4个32位字(a, b, c, d)，并原地修改它们。其定义如下（<<<表示32位循环左移，+是模2^32加法）：

1. b = b ⊕ ((a + d) <<< 7)
2. c = c ⊕ ((b + a) <<< 9)
3. d = d ⊕ ((c + b) <<< 13)
4. a = a ⊕ ((d + c) <<< 18)

作用：QR对4个字进行非线性混合，结合了模加、异或和循环移位，提供了良好的混淆和扩散。它是Salsa20中最小、最核心的变换单元。

4. 构建列轮与行轮

一轮完整的Salsa20轮函数由一个列轮和紧接着的一个行轮组成。每个“列轮”或“行轮”都会调用4次QR函数，分别处理矩阵的4列或4行。

• 列轮 (columnround)：对矩阵的4列分别应用QR。
  • 对第0列：QR(x[0], x[4], x[8], x[12])
  • 对第1列：QR(x[5], x[9], x[13], x[1]) （注意索引：这里处理的是(x[5], x[9], x[13], x[1])，这对应于矩阵的“第二行”开始的列循环视图，但更直观的理解是，它处理的是矩阵的4个“对角线”分组，确保每列4个字来自矩阵的不同行，从而实现列内的行间混合。在标准描述中，通常表述为对矩阵的4个“列” 进行处理，但这里的“列”是数学上的列向量，而索引的排列是为了实现最大扩散。最经典和易记的实现方式是：对j = 0,1,2,3，执行QR(x[j], x[j+4], x[j+8], x[j+12])。这就是处理矩阵的4个几何列。）
• 行轮 (rowround)：对矩阵的4行分别应用QR。
  • 对第0行：QR(x[0], x[1], x[2], x[3])
  • 对第1行：QR(x[5], x[6], x[7], x[4]) （类似地，标准描述是处理4个“行”，索引排列也是为了交叉混合。最经典的实现方式是：对i = 0,1,2,3，执行QR(x[4*i], x[4*i+1], x[4*i+2], x[4*i+3])。这就是处理矩阵的4个几何行。）

关键点：在“列轮”中，QR操作的4个输入来自同一列的不同行（在内存中是每隔4个索引取一个字）。在“行轮”中，QR操作的4个输入来自同一行的不同列（在内存中是连续4个索引的字）。这种行列交替的处理方式，确保了在经过几轮之后，状态矩阵中每一位的变化都能快速扩散到所有其他位，满足雪崩效应。

5. 组合成完整轮函数与多轮迭代

一轮完整的Salsa20轮函数（称为一个doubleround）定义为：

doubleround(state):
    columnround(state)  // 先进行列混合
    rowround(state)    // 再进行行混合

完整的Salsa20核心置换（以20轮标准版为例）就是执行10次doubleround：

for i in range(10):
    doubleround(state)

每次doubleround调用8次quarterround（4次列轮QR + 4次行轮QR），所以20轮总共调用20 * 4 = 80次quarterround（因为每轮doubleround包含2个“半轮”，每个“半轮”4个QR，总计8个QR，20轮是160个QR？这里需要澄清：标准Salsa20的20轮，是指20个“round”，每个“round”执行4个QR操作。在原始论文中，一轮（one round）的定义是：先执行4个并行的QR（列轮），再执行4个并行的QR（行轮）。这8个QR操作合起来称为一个“double round”。然后标准Salsa20/20是执行10个“double round”，即总共80个QR操作。而Salsa20/12和Salsa20/8分别执行6个和4个“double round”，即48个和32个QR操作。在表述上，有时“一轮”指一个QR，有时指一个“double round”。本讲解中，将doubleround（列轮+行轮）视为算法的一“大轮”，标准算法是10大轮（20小轮，每小轮4个QR）。）

为了避免混淆，我们采用最常见的实现描述：Salsa20核心置换是迭代执行R轮，每轮对状态矩阵进行“列轮”和“行轮”各一次。标准版本R=10（即10个“doubleround”）。 在每一“列轮”或“行轮”中，并行地对4列或4行各自独立地进行一次quarterround操作。

6. 最终步骤与输出

经过R轮（标准为10轮doubleround）的混合后，得到最终的状态矩阵x'。最终的密钥流块输出是：

最终输出[i] = x[i] + x'[i]  (i = 0, 1, ..., 15)

即将混淆后的状态与初始状态按字模加。这一步是为了使整个函数成为可逆的（从输出和初始状态可以恢复混淆后的状态），但逆向计算轮函数本身是困难的，这为算法提供了安全性。这个最终加和也增加了攻击的复杂度。

总结

Salsa20轮函数的设计精髓在于其简洁、对称和高度并行的结构：

1. 基础构件：quarterround函数，通过模加、异或、循环移位实现快速非线性混合。
2. 结构设计：交替进行“列轮”和“行轮”，每个轮次对矩阵的4列或4行并行应用quarterround，确保比特变化在行和列两个维度上快速扩散。
3. 迭代与安全：通过重复应用这种行列混合（标准为10个doubleround，即20个小轮），达到足够的混淆和扩散，抵抗密码分析。
4. 可逆性与白盒性：最后的“加回初始状态”操作使得整个变换是容易求逆的（如果知道密钥和输入），但在不知道初始状态时，从输出逆向轮函数计算是困难的。整个设计没有S盒，所有操作都是简单的算术和逻辑运算，非常适合软件高效实现和硬件并行化。

通过以上步骤，我们循序渐进地解析了Salsa20流密码算法中轮函数的设计原理、构成组件和执行流程，揭示了其如何通过简单的操作迭代构建出安全的伪随机数生成器。