Page 434 - 《软件学报》2025年第10期
P. 434
龚子睿 等: FBS-uBlock: 灵活的 uBlock 算法比特切片优化方法 4831
表 2 uBlock 算法 PL/PR 置换表和逆置换表
x 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
PL 128 1 3 4 6 0 2 7 5 － － － － － － － －
PR 128 2 7 5 0 1 6 4 3 － － － － － － － －
PL −1 4 0 5 1 2 7 3 6 － － － － － － － －
128
PR −1 3 4 0 7 6 2 5 1 － － － － － － － －
128
PL 256 2 7 8 13 3 6 9 12 1 4 15 10 14 11 5 0
PR 256 6 11 1 12 9 4 2 15 7 0 13 10 14 3 8 5
PL −1 15 8 0 4 9 14 5 1 2 6 11 13 7 3 12 10
256
PR −1 9 2 6 13 5 15 0 8 14 4 11 1 3 10 12 7
256
2.2 比特切片方法
在 Biham [11] 的比特切片方法中, 数据分组的每个比特位会被分散存储在不同寄存器中, 每个寄存器代表一个
比特. 对于分组密码算法, 比特切片很适合处理算法中比特粒度的运算, 尤其是线性部分中以比特为单位的置换和
异或运算.
图 3 是比特切片的示意图, 如果处理器提供 n 比特长的寄存器, 那么采用比特切片优化后的分组密码算法需
要一次性读入 n 组数据, 然后将每组数据的第 i 号比特存放到第 i 号寄存器中. 以分组长度是 128 比特的密码算法
为例, 这种切片方法总共需要 128 个寄存器.
数据分组0 寄存器0
数据分组1 寄存器1
⋮ ⋮
数据分组n−1 寄存器127
图 3 比特切片示例图
数据分组的比特位开始连续存储在内存中, 比特切片需要将它们分散存储在不同寄存器中. 本文将这种对数
据处理的过程称为数据编排. 将 n 个数据分组按行排列成 n 行, 分组的 k 个比特位视作 k 列, 数据编排可以看成
n×k 的矩阵转置, 转置后变成 k 行 (k 个寄存器) 和 n 列 (每个寄存器 n 比特长). 算法 1 是比特切片的数据编排算
法, 以 n 阶方阵为例, 算法复杂度是 n/2×log 2 (n).
算法 1. 比特切片数据编排算法.
输入: n×n 的数据矩阵 Z;
输出: 转置后的 n×n 的数据矩阵 Z.
1. for j = 0 to log 2 (n) – 1 do
2. k ← 2 j
k
k
3. m j ← 2 个比特 0 拼接上 2 个比特 1
4. m ← ¬m j
′
j
5. for i=0 to n/2 – 1 do
6. r ← 2×(i – (i mod k)) + (i mod k)
7. t ← (Z[r] ∧ m ) ∨ ((Z[r+k] ∧ m ) >> k)
′
′
j j
