企业官网建设流程全解析

如何逐行读懂Keccak-f[1600]：XKCP中24轮置换的θρπχι五步拆解

【免费下载链接】XKCPeXtended Keccak Code Package项目地址: https://gitcode.com/gh_mirrors/xk/XKCP

Keccak-f[1600] 是 XKCP（eXtended Keccak Code Package，eXtended Keccak 代码包）的核心置换原语，SHA3-256、SHAKE128 等哈希函数都由它驱动。本文带你逐行读懂 XKCP 里的 Keccak-f[1600] 参考实现：1600 位状态、5×5 道矩阵、以及每一轮中 θ（theta）、ρ（rho）、π（pi）、χ（chi）、ι（iota）五步置换的作用与代码位置，并附上 24 轮常量表的生成原理和多平台优化实现索引。

一、Keccak-f[1600] 在 XKCP 三层架构中的位置

XKCP 把整个密码库分成三层，理解这一点对读懂全部源码非常关键：

👆 XKCP 架构总览：Keccak-f[1600] 位于最底层的 SnP 层，海绵构造与所有哈希模式都建立在它之上。读懂这一个置换，就等于读懂了整个库的地基。

二、1600 位状态：一个 5×5 的 64 位道矩阵

Keccak-f[1600] 的状态是 1600 个比特。参考实现 KeccakP-1600-reference.c 把它切成25 条 64 位道（lane），排成 5×5 矩阵，坐标用公式 index(x, y) 映射到下标：

#define nrLanes 25 #define index(x, y) (((x)%5)+5*((y)%5))

也就是说A[index(x,y)]就是矩阵第 x 列、第 y 行的那个 64 位道。后面五步置换全是围绕这个坐标系统展开的。

三、单轮流程：θ ρ π χ ι 五步逐行拆解

一轮置换就是五个函数按固定顺序调用，见 KeccakP1600Round：

theta(state); // 列间扩散 rho(state); // 逐道循环移位 pi(state); // 重排位置 chi(state); // 行内非线性 iota(state, indexRound); // 注入轮常数

下面逐个拆开看。

1. θ（theta）：列异或 + 旋转，纵向扩散

static void theta(tKeccakLane *A) { for(x=0; x<5; x++) for(y=0; y<5; y++) C[x] ^= A[index(x, y)]; // 每列做纵向异或 for(x=0; x<5; x++) D[x] = ROL64(C[(x+1)%5], 1) ^ C[(x+4)%5]; // 邻居列参与 for(x=0; x<5; x++) for(y=0; y<5; y++) A[index(x, y)] ^= D[x]; // 整列广播 }

对应源码 theta。要点：

• C[x]收集第 x 列所有道的异或值；
• D[x]让左右邻居列（x+1和x-1，模 5）参与进来，再左旋 1 位；
• 最后把D[x]异或回整列——一个道只变自己的列，却混入了相邻两列的信息，这就是所谓的"纵向扩散"。

2. ρ（rho）：每条道旋转固定偏移量

A[index(x, y)] = ROL64(A[index(x, y)], KeccakRhoOffsets[index(x, y)]);

见 rho。25 条道各自旋转一个固定的比特数（0~61 各不相同），偏移表在 KeccakRhoOffsets。它的作用是把"列对齐"的比特打散，为后面的 π 错位做准备。

3. π（pi）：纯位置重排

A[index(0*x+1*y, 2*x+3*y)] = tempA[index(x, y)];

见 pi。每个道从 (x, y) 平移到 (y, 2x+3y)（坐标均模 5）——没有任何比特运算，只是搬位置。与 ρ 配合产生强烈的比特错位。

4. χ（chi）：每行内引入非线性

C[x] = A[index(x, y)] ^ ((~A[index(x+1, y)]) & A[index(x+2, y)]);

见 chi。整轮中唯一的非线性步骤：沿行方向让每个道与它的两个后继道做 异或/取反/与 组合。没有 χ，整个置换就退化成线性运算，安全性无从谈起。

5. ι（iota）：注入轮常数

A[index(0, 0)] ^= KeccakRoundConstants[indexRound];

见 iota。把当前轮的 64 位常数和到左上角道 A[0,0]，打破对称性，也是区分不同轮的唯一来源。

💡 记忆口诀：θ 竖着混、ρ 各转各、π 换位置、χ 行内咬、ι 加常数。

四、24 轮循环：轮数为什么是 24，常数表怎么来的

1. 24 轮的来源

置换宽度决定轮数：宽度为 1600×2ⁿ 时取 12×2ⁿ 轮，所以 Keccak-f[1600] 是24 轮。C++ 教学模型 initializeNominalNumberOfRounds 中一眼可见各宽度对应的轮数（25 位 12 轮 … 1600 位 24 轮）。执行入口是 KeccakP1600_Permute_Nrounds，它先把字节态转成 64 位道，再逐轮调用KeccakP1600Round。

2. 轮常数不用硬编码也能算出来

参考代码里既内置了 24 个常数 KeccakRoundConstants，也提供了从零生成的路径 KeccakP1600_InitializeRoundConstants：用一个 8 位线性反馈移位寄存器 LFSR86540（特征多项式 x⁸+x⁶+x⁵+x⁴+1）逐位取样，把 7 个比特放到 2⁰~2⁶ 位置再异或叠加，就得到每一轮的常数。ρ 偏移同理可用公式 ((t+1)(t+2)/2) mod 64 现算，见 KeccakP1600_InitializeRhoOffsets。

3. 想亲眼看到五步中间值？

定义KeccakReference宏后，每一轮的 θ/ρ/π/χ/ι 之后都会打印状态，输出可与测试向量 KeccakF-1600-IntermediateValues.txt 逐行比对——这是验证你的理解（或你的实现）是否正确的最直接手段。

五、从参考实现到多平台优化：同一轮函数的性能阶梯

参考实现清晰但慢，XKCP 为不同硬件提供了同一接口的优化版本，可以按顺序对照阅读：

🚀 优化实现的核心思想都来自 64.macros 里的同一个技巧：把prepare-theta（预先算好 C 数组）与五步合并成一条大宏，把 θ 的"先算后写"拆成两次流水线式计算，减少寄存器压力；汇编版则用x道命名（Aba、Abe…）让编译器/SIMD 寄存器分配更顺滑。

运行时由 x86-64-dispatch.c 这类分派代码根据 CPU 能力自动选择版本，上层代码无感知。

六、动手验证：用测试向量跑通你的理解

🧪 建议的阅读路线：

1. 通读 KeccakP-1600-reference.c 全文，只有 400 来行，五个函数都能一屏看全；
2. 对照 C++ 教学模型 Keccak-p.cpp 中的 pi 公式 与 轮常数生成，理解公式出处；
3. 用 KeccakF-1600-IntermediateValues.txt 核对每一轮、每一步的中间状态；
4. 最后看海绵层如何调用它：KeccakHash.c 中吸收-置换-挤出的循环，就是AddBytes → KeccakP1600_Permute_Nrounds → ExtractBytes三步的反复。

小结

Keccak-f[1600] 并不神秘：1600 位状态 = 25 条 64 位道排成 5×5 矩阵，每轮 θρπχι 五步、共 24 轮，全部逻辑在 参考实现 里 400 行内讲完。抓住"纵向扩散 → 旋转错位 → 位置重排 → 行内非线性 → 常数注入"这条主线，配合中间值测试向量逐轮对照，你就能逐行读懂 XKCP 中 SHA3 家族的整个心脏。

【免费下载链接】XKCPeXtended Keccak Code Package项目地址: https://gitcode.com/gh_mirrors/xk/XKCP