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

如何逐行读懂Keccak-f[1600]XKCP中24轮置换的θρπχι五步拆解【免费下载链接】XKCPeXtended Keccak Code Package项目地址: https://gitcode.com/gh_mirrors/xk/XKCPKeccak-f[1600] 是 XKCPeXtended Keccak Code PackageeXtended Keccak 代码包的核心置换原语SHA3-256、SHAKE128 等哈希函数都由它驱动。本文带你逐行读懂 XKCP 里的 Keccak-f[1600] 参考实现1600 位状态、5×5 道矩阵、以及每一轮中 θtheta、ρrho、πpi、χchi、ιiota五步置换的作用与代码位置并附上 24 轮常量表的生成原理和多平台优化实现索引。一、Keccak-f[1600] 在 XKCP 三层架构中的位置XKCP 把整个密码库分成三层理解这一点对读懂全部源码非常关键层名称职责底层SnPSponge and Permutation纯置换原语Keccak-f[1600]、Xoodoo中层Construction海绵构造 Sponge / 双工构造 Duplex上层Mode哈希、MAC、PRNG、认证加密 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 位道。后面五步置换全是围绕这个坐标系统展开的。三、单轮流程θ ρ π χ ι 五步逐行拆解一轮置换就是五个函数按固定顺序调用见 KeccakP1600Roundtheta(state); // 列间扩散 rho(state); // 逐道循环移位 pi(state); // 重排位置 chi(state); // 行内非线性 iota(state, indexRound); // 注入轮常数下面逐个拆开看。1. θtheta列异或 旋转纵向扩散static void theta(tKeccakLane *A) { for(x0; x5; x) for(y0; y5; y) C[x] ^ A[index(x, y)]; // 每列做纵向异或 for(x0; x5; x) D[x] ROL64(C[(x1)%5], 1) ^ C[(x4)%5]; // 邻居列参与 for(x0; x5; x) for(y0; y5; y) A[index(x, y)] ^ D[x]; // 整列广播 }对应源码 theta。要点C[x]收集第 x 列所有道的异或值D[x]让左右邻居列x1和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*x1*y, 2*x3*y)] tempA[index(x, y)];见 pi。每个道从 (x, y) 平移到 (y, 2x3y)坐标均模 5——没有任何比特运算只是搬位置。与 ρ 配合产生强烈的比特错位。4. χchi每行内引入非线性C[x] A[index(x, y)] ^ ((~A[index(x1, y)]) A[index(x2, 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⁶ 位置再异或叠加就得到每一轮的常数。ρ 偏移同理可用公式 ((t1)(t2)/2) mod 64 现算见 KeccakP1600_InitializeRhoOffsets。3. 想亲眼看到五步中间值定义KeccakReference宏后每一轮的 θ/ρ/π/χ/ι 之后都会打印状态输出可与测试向量 KeccakF-1600-IntermediateValues.txt 逐行比对——这是验证你的理解或你的实现是否正确的最直接手段。五、从参考实现到多平台优化同一轮函数的性能阶梯参考实现清晰但慢XKCP 为不同硬件提供了同一接口的优化版本可以按顺序对照阅读实现路径特点优化 CKeccakP-1600-opt64.c变量重命名宏展开编译即可用宏核心KeccakP-1600-64.macrosthetaRhoPiChiIotaPrepareTheta单宏完成一整轮AVX2 汇编KeccakP-1600-AVX2.s256 位寄存器同时处理多道AVX512KeccakP-1600-AVX512.s512 位 ZMM 寄存器ARMv8-A SHA3 指令KeccakP-1600-v84a.c硬件原生 SHA3 指令32 位 ARM 汇编KeccakP-1600-inplace-32bi-armv7m-le-gcc.sCortex-M 微控制器 优化实现的核心思想都来自 64.macros 里的同一个技巧把prepare-theta预先算好 C 数组与五步合并成一条大宏把 θ 的先算后写拆成两次流水线式计算减少寄存器压力汇编版则用x道命名Aba、Abe…让编译器/SIMD 寄存器分配更顺滑。运行时由 x86-64-dispatch.c 这类分派代码根据 CPU 能力自动选择版本上层代码无感知。六、动手验证用测试向量跑通你的理解 建议的阅读路线通读 KeccakP-1600-reference.c 全文只有 400 来行五个函数都能一屏看全对照 C 教学模型 Keccak-p.cpp 中的 pi 公式 与 轮常数生成理解公式出处用 KeccakF-1600-IntermediateValues.txt 核对每一轮、每一步的中间状态最后看海绵层如何调用它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创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考