Page 439 - 《软件学报》2025年第10期

4836 软件学报 2025 年第 36 卷第 10 期

表 4 符号定义

符号 符号解释
X uBlock算法的数据
n 数据X的比特长度, 代表X是n比特数据
X i 第i组输入的数据
X[j] 数据X的第j比特
r 寄存器缩减率, 代表将寄存器占用个数减少到原先的1/r
0 1 k–1
数据第i比特的集合, 长度n/(2r), b[i] = X [i] X [i] … X [i],
b[i]
k=n/(2r)

图 6 中矩阵共 n/2 列, 但并不代表只适合 n/2 比特长度的寄存器. 该切片表示法可以通过水平拼接矩阵的方式
拓展到任意比特长度的寄存器中, 处理的数据量也等比例翻倍. 处理器的 SIMD 指令集支持并行的向量运算, 拼接
后能够更好地发挥处理器的并行能力.
3.3 非线性 S 盒表达式
uBlock 算法设计文档中的 S 盒逻辑函数需要 8 个硬件逻辑门, 但在比特切片软件实现中, 处理器没有提供或
非、与非等复合逻辑门的逻辑运算指令, 需要把或非门拆分成或门和非门这两步运算, 所以在软件比特切片中,
图 2 的逻辑函数需要耗费 14 条逻辑运算指令, 比特切片逻辑门复杂度为 14.
为了降低 S 盒的计算开销, 本文采用 Lighter 工具 [15] 搜索比特切片逻辑门复杂度更低的 S 盒逻辑表达式.
Lighter 工具可以指定搜索时使用的逻辑门, 还能够设置各逻辑门的开销权重. 在 x86 架构的 AVX2 指令集中, 支
持的逻辑运算是 and、or、xor、andn、not, 开销相同; 在 ARM 架构的 NEON 指令集中, 支持的逻辑运算是 and、
or、xor、orn、not, 开销相同. 因此, 本文分别针对 x86 架构和 ARM 架构这两个处理器平台架构进行 S 盒逻辑函
数的搜索与化简, 限制最终的逻辑函数仅能使用特定处理器平台支持的逻辑运算, 以减少比特切片门复杂度为目
标搜索适合比特切片实现的 uBlock 算法 S 盒逻辑函数.
表 5 是 Lighter 工具搜索的结果, 图 7 是对应的逻辑函数. 根据搜索结果, 经过 Lighter 工具优化后的 S 盒比特
切片门复杂度为 9, S 盒的逆也为 9. 并且搜索得到的逻辑函数不包含 andn 或 orn 逻辑运算, 这意味着同样的表达
式可以同时用于 x86 和 ARM 架构两个平台.

表 5 比特切片逻辑门复杂度 (个)

模块 设计文档 x86-AVX2 ARM-NEON
s(x) 14 9 9
−1
s (x) － 9 9

图 8 是 uBlock 算法 S 盒与逆 S 盒的实现方式, 式中对 4 比特的 X 执行多次逻辑运算来更新每个比特位的值,
执行完毕后的 X 是算法 S 盒或逆 S 盒的输出, 计算过程只需要使用 1 个额外的临时变量.
4 具体实现

本节主要介绍如何利用处理器的 SIMD 指令集实现本文提出的 FBS-uBlock, 依次介绍数据编排、轮密钥加、
非线性 S 盒、线性变换 B、线性变换 PL 与 PR 这 5 部分的实现方法, 并理论分析需要的运算指令条数.
4.1 实现过程
数据编排指将原始输入数据转变成适合比特切片运算的数据的过程, 数据编排的逆过程称为数据逆编排. 本
文的数据编排和数据逆编排算法在使用 AVX2 指令集实现时的指令开销都是 2n/r+8n/r×log 2 [n/(2r)] 条, 包括数据
打包和数据切片两个子算法. 在数据打包算法中, 输入的 n 比特数据原本位于一个寄存器中, 需要拆分成高 n/2 比
特和低 n/2 比特, 并分别统一放在两个不同的寄存器中. 在数据切片算法中, 采用第 2.2 节提到的数据转置算法, 完