Salsa20流密码算法的密钥扩展与初始化过程详解

我们先明确目标：Salsa20是一种流密码算法，其核心是通过密钥和随机数（nonce）扩展生成一个伪随机的密钥流，然后用这个密钥流与明文进行异或加密。这个“密钥扩展与初始化”过程，是构建初始状态矩阵（内部状态）的关键，是整个算法运行的起点。下面我将把这个过程拆解成几个清晰的步骤。

1. 背景与基本概念

首先，需要理解几个关键输入：

• 密钥 (Key)：Salsa20支持128位（16字节）和256位（32字节）两种密钥长度。我们以256位密钥为例讲解，因为它更常见，且128位是其一个子集。
• 随机数 (Nonce)：一个8字节（64位）的唯一值。对于同一个密钥，每次加密必须使用不同的nonce，以确保生成的密钥流不同，这是流密码安全性的核心要求之一。
• 块计数 (Block Counter)：一个8字节（64位）的值。加密长消息时，消息被分成多个64字节的块，每个块拥有唯一的块计数值（通常从0开始递增），确保每个数据块使用不同的密钥流。

初始化过程的目的，就是将这三种输入，与一些预定义的常量，按照一个特定的固定顺序排列成一个4x4的状态矩阵。这个矩阵的每个元素是一个32位（4字节）的字。

2. 核心：状态矩阵的构成

Salsa20的内部状态是一个4x4的矩阵，共16个元素（16 * 32位 = 64字节）。我们把这个矩阵称为 State，其元素索引从0到15。

这个矩阵的构成遵循一个固定模式。模式由一些“魔数”或常量定义，这些常量是字符串 "expand 32-byte k" 或 "expand 16-byte k" 的ASCII码表示，分别用于256位和128位密钥。它们的作用是“打破对称性”，为算法提供初始的非线性扰动。

对于256位密钥，状态矩阵的初始布局如下：

位置 (索引)    值 (含义)
0    (0,0)   常量 "expa"   (0x61707865)
1    (0,1)   密钥 [0-3]    (Key[0..3])
2    (0,2)   密钥 [4-7]    (Key[4..7])
3    (0,3)   密钥 [8-11]   (Key[8..11])
4    (1,0)   密钥 [12-15]  (Key[12..15])
5    (1,1)   常量 "nd 3"   (0x3320646e)
6    (1,2)   随机数 [0-3]  (Nonce[0..3])
7    (1,3)   随机数 [4-7]  (Nonce[4..7])
8    (2,0)   块计数 [0-3]  (Counter[0..3])
9    (2,1)   块计数 [4-7]  (Counter[4..7])
10   (2,2)   常量 "2-by"   (0x79622d32)
11   (2,3)   密钥 [16-19]  (Key[16..19])
12   (3,0)   密钥 [20-23]  (Key[20..23])
13   (3,1)   密钥 [24-27]  (Key[24..27])
14   (3,2)   密钥 [28-31]  (Key[28..31])
15   (3,3)   常量 "te k"   (0x6b206574)

你可以把这个布局看作一个“模板”。它精确地规定了密钥、nonce、计数器和常量应该放在哪个位置。

关键记忆点：

1. 常量占据了位置0, 5, 10, 15。它们是固定的。
2. 密钥被拆分成8个4字节的字，分别放入位置(1,0), (1,1), (1,2), (1,3), (2,0), (2,1), (2,2), (2,3)。注意，在Salsa20的原始论文布局中，密钥是分散在矩阵四周的，但最终效果等价于将32字节密钥分成8个4字节块放入上述8个位置。
3. Nonce占据中间的两个位置（索引6和7）。
4. 块计数器占据索引8和9的位置。

在实际编程中，我们通常将上述模板表示为一个16个字的数组 x[0..15]。

3. 循序渐进：初始化过程实例

假设我们要加密第一个数据块（块计数器=0）。我们有以下具体数据：

• 密钥K: 32字节，例如全零（仅用于演示）：00 00 00 00 ... 00 (32个)
• Nonce N: 8字节，例如：00 00 00 00 00 00 00 01
• 块计数器C: 8字节，从0开始：00 00 00 00 00 00 00 00

步骤1：将输入解析为32位字（小端序）
计算机内存中数字通常按“小端序”存储，即最低有效字节在低地址。所以：

• 密钥K被分成8个4字节的字：K0, K1, K2, K3, K4, K5, K6, K7。对于全零密钥，每个Kx都是0。
• Nonce N被分成2个字：N0, N1。
  • N0 = 字节0-3: 00 00 00 00 -> 整数值 0
  • N1 = 字节4-7: 00 00 00 01 -> 整数值 0x01000000 (注意小端序，内存中是01 00 00 00，解释为整数是0x00000001？这里需要仔细：小端序下，字节序列 [01, 00, 00, 00] 表示的整数是 0x00000001。但在Salsa20的原始描述中，它被直接当作一个32位字使用，不进行端序转换，因为算法操作定义在字上。在实际实现中，我们直接从字节数组按4字节一组读出整数值即可）。
• 块计数器C被分成2个字：C0, C1。均为0。

步骤2：按照模板填充状态矩阵
我们使用上文所述的模板。常量是固定的ASCII字符串：

• 0x61707865 ("expa")
• 0x3320646e ("nd 3")
• 0x79622d32 ("2-by")
• 0x6b206574 ("te k")

将我们的数据代入模板，得到初始状态矩阵 x：

x[0]  = 0x61707865
x[1]  = K0 = 0x00000000
x[2]  = K1 = 0x00000000
x[3]  = K2 = 0x00000000
x[4]  = K3 = 0x00000000
x[5]  = 0x3320646e
x[6]  = N0 = 0x00000000
x[7]  = N1 = 0x00000001
x[8]  = C0 = 0x00000000
x[9]  = C1 = 0x00000000
x[10] = 0x79622d32
x[11] = K4 = 0x00000000
x[12] = K5 = 0x00000000
x[13] = K6 = 0x00000000
x[14] = K7 = 0x00000000
x[15] = 0x6b206574

步骤3：对状态矩阵进行“双轮”计算（核心扩散）
仅仅填充矩阵是不够的，这只是初始排列。Salsa20的安全核心在于接下来的“双轮”函数（通常是20轮，但这里指其核心的置换操作）。算法会对这个初始矩阵 x 进行20轮的混淆和扩散（每轮包含4个并行的“ quarter-round ”操作，作用在矩阵的对角线和列上）。20轮运算后，我们得到一个新的矩阵 x‘。

步骤4：生成密钥流块
计算完成后，将最终的矩阵 x‘ 与初始矩阵 x 逐字相加（模2^32）。这个相加的结果，就是一个64字节的密钥流块。

公式为：密钥流块 = x‘ + x (逐字模加)

步骤5：加密
用这个生成的64字节密钥流块，与明文的第一个64字节进行逐字节的异或（XOR）操作，就得到了密文。

对于下一个数据块：只需将块计数器C加1（例如，C0 或 C1 增加），然后重复步骤2到步骤5，用新的计数器值重新构造初始状态矩阵并计算，生成下一个64字节的密钥流块。密钥和nonce保持不变。

4. 对128位密钥的调整

如果使用128位（16字节）密钥，初始化模板稍有不同。常量字符串变为 "expand 16-byte k"，并且密钥的8个字会被重复使用一次来填满矩阵中所有8个密钥位置。具体来说，128位密钥被分成4个字 K0, K1, K2, K3，然后它们在矩阵中的排列是 K0, K1, K2, K3, K0, K1, K2, K3。Nonce和计数器的位置保持不变。

总结

Salsa20的密钥扩展与初始化过程可以精炼为以下几步：

1. 解析输入：将密钥、nonce、计数器分别解析为32位字的序列。
2. 填充模板：严格按照固定的布局模板，将这些字和四个预定义的常量字，填入一个4x4的矩阵（16个字的数组）中。这是构建算法初始内部状态的关键一步。
3. 混淆扩散：对这个初始状态矩阵进行20轮的Salsa20双轮函数运算，使其充分混淆。
4. 生成密钥流：将运算后的矩阵与初始矩阵逐字相加，得到最终的64字节密钥流块。
5. 迭代：要加密更长消息，只需递增块计数器，然后回到第2步，生成下一个密钥流块。

这个过程确保了相同的密钥+不同的(nonce, 计数器) 会产生完全不同的、看似随机的密钥流，从而满足流密码的安全需求。