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

龚子睿 等: FBS-uBlock: 灵活的 uBlock 算法比特切片优化方法 4837

成 2 个 n/(2r)×n/(2r) 的比特数据矩阵转置. 例如, 在数据打包算法中, 对于明文分组长度 n=128 比特的 uBlock-
128/128 和 uBlock-128/256 算法, 如果寄存器长度是 128 比特, 那么每个寄存器中存放 2 个分组的高 (或低) 64 比
特; 如果寄存器长度是 256 比特, 那么每个寄存器存放 4 个分组的高 (或低) 64 比特. 数据打包算法在 x86 平台可
使用 unpack 指令快速完成. 对于 uBlock-256/256 算法, 如果寄存器长度恰好是 n/2=128 比特, 直接将数据加载至
寄存器; 如果寄存器长度大于 128 比特, 利用 permute 指令可以快速完成数据打包.

−1
y 0 y 1 y 2 y 3 =s(x 0 x 1 x 2 x 3 ) y 0 y 1 y 2 y 3 =s (x 0 x 1 x 2 x 3 )
x 3
x 3
x 2
x 2
x 1
x 1
x 0
x 0
OR XOR NOT
OR XOR
AND XOR
OR XOR
AND XOR OR XOR y 3
OR XOR
y 2
y 3
NOT
y 1
y 2
OR XOR y 0
y 1
y 0
图 7 优化后的 uBlock 算法 s(x) 和 s (x) 的逻辑门
−1

S盒 逆S盒
X[0]=XOR2 (X[0], OR2 (X[1], X[2])); X[2]=XOR2 (X[2], OR2 (X[0], X[3]));
X[1]=NOT1 (X[1]); X[1]=XOR2 (X[1], AND2 (X[2], X[3]));
X[3]=XOR2 (X[3], OR2 (X[0], X[1])); X[3]=XOR2 (X[3], OR2 (X[0], X[1]));
X[1]=XOR2 (X[1], AND2 (X[2], X[3])); X[1]=NOT1 (X[1]);
X[2]=XOR2 (X[2], OR2 (X[0], X[3])); X[0]=XOR2 (X[0], OR2 (X[1], X[2]));
−1
图 8 uBlock 算法 s(x) 和 s (x) 的实现方式

轮密钥加是轮密钥和数据的异或运算. 因为比特切片对输入的数据进行了编排, 所以轮密钥也需要进行类似
的编排, 可以预先对每一轮的轮密钥做数据编排, 然后在加密和解密轮函数中直接用数据异或上编排好的轮密钥,
避免对密钥反复编排造成的开销.
非线性 S 盒使用第 3.2 节中给出的逻辑函数表达式计算, x86 架构的 SIMD 指令集不支持逻辑非运算指令, 实
现时通过和全 1 的数据异或来实现逻辑非运算.
线性变换 B 是以 32 比特的循环移位和异或, 根据 n/(2r) 的大小可以分为两种情况: 当 n/(2r)≥32 时, 此时 32
比特都分散在不同寄存器中, 直接使用逻辑异或指令计算; 当 n/(2r)<32 时, 利用第 3.1 节提到的性质, 使用重排指
令快速循环移位, 完成线性变换 B 的计算.
线性变换 PL 和 PR 可以使用移位、掩码和重排指令实现, 计算开销随着寄存器的减少呈现先增加后降低的
趋势. PL 和 PR 模块是规律性不强的字节重排, 本文为 uBlock 算法设计的比特切片表示法并不是非常切合 PL 和
PR 的计算, 无法仅使用简单的指令来抵消缩减寄存器数量带来的影响, 会引发寄存器和寄存器之间频繁的数据移
动. 但通过后续的分析可以看出, 当寄存器数量减少到一定程度时, PL 和 PR 不再有寄存器与寄存器之间的交互,
可以使用重排指令快速完成字节重排.
4.2 理论分析
根据 Intel 官方指令集的文档 (Intel intrinsics guide), 逻辑运算指令、重排指令、打包指令的开销基本一致, 可