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

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

以仅统计这些运算指令的总条数来评估计算开销, 不需要单独统计每种指令. 下面以采用 AVX2 指令集实现的版
本为例, 统计了 uBlock 算法加密过程中每个模块需要的运算指令条数和占比, 包括数据编排、轮密钥加、S 盒、
线性变换 B、PL/PR 这 5 个模块.
表 6–表 8 统计了 uBlock 算法每个模块在不同切片表示法下平均每分组需要的运算指令条数, 用于分析寄存
器数量减少对加密计算复杂度的影响, 每分组需要的运算指令条数通过“单次调用需要的运算指令条数/单次加密
处理的分组数”来计算. 通过理论分析可以看出, 随着需要的寄存器数量减少 (r 增加), 轮密钥加和 S 盒的开销不
变, 数据编排部分开销降低, 线性变换 B 的开销先不变后增加, PL/PR 模块开销先增高后降低. 从总共的运算指令
条数上看, 趋势是先增高, 然后降低, 然后再升高.

表 6 uBlock-128/128 每个模块在不同比特切片表示下平均每分组需要的运算指令条数

表示法 数据编排 轮密钥加 S盒 线性变换B PL/PR模块 总计
r=1 13 0.5 1.125 1.5 0 76.5
r=2 11 0.5 1.125 1.5 1.5 96.5
r=4 9 0.5 1.125 2 1.5 100.5
r=8 7 0.5 1.125 2.375 0.5 86.5
r=16 5 0.5 1.125 3.5 0.5 100.5
注: uBlock-128/128单次加密需要分别调用上述模块2、17、16、16、16次

表 7 uBlock-128/256 每个模块在不同比特切片表示下平均每分组需要的运算指令条数

表示法 数据编排 轮密钥加 S盒 线性变换B PL/PR模块 总计
r=1 13 0.5 1.125 1.5 0 101.5
r=2 11 0.5 1.125 1.5 1.5 133.5
r=4 9 0.5 1.125 2 1.5 141.5
r=8 7 0.5 1.125 2.375 0.5 122.5
r=16 5 0.5 1.125 3.5 0.5 145.5
注: uBlock-128/256单次加密需要分别调用上述模块2、25、24、24、24次

表 8 uBlock-256/256 每个模块在不同比特切片表示下平均每分组需要的运算指令条数

表示法 数据编排 轮密钥加 S盒 线性变换B PL/PR模块 总计
r=1 30 1 2.25 3 0 211.0
r=2 26 1 2.25 3 3 275.0
r=4 22 1 2.25 3 9.5 423.0
r=8 18 1 2.25 4 3 283.0
r=16 14 1 2.25 4.75 1 245.0
r=32 10 1 2.25 7 1 291.0
注: uBlock-256/256单次加密需要分别调用上述模块2、25、24、24、24次

表 9 给出了 PL/PR 模块需要的指令条数相对于整个加密过程的占比, 用于分析制约性能的主要模块, 模块需
要的指令条数占比通过“该模块需要的指令条数/单次加解密需要的指令条数”来计算. 通过表 9 的数据可知,
PL/PR 模块的开销随着寄存器数量的减少会急剧增大, 当 r=4 时, uBlock-256/256 算法 50% 的运算指令都用于计
算该模块, 说明此时 PL/PR 模块制约着整个算法的性能. 但寄存器数量减少到一个临界值后, 运算指令占比便会
急剧降低, uBlock-128/128 和 uBlock-128/256 的临界值是 r=8, 即 128/8=16 个寄存器; uBlock-256/256 的临界值是
r=16, 也是 256/16=16 个寄存器.
本文提出的切片优化方法关键在于减少寄存器数量, 间接减少了访存指令的条数, 但会增加一些运算指令
的条数. 第 5 节实验中将会说明, 本文的 FBS-uBlock 方法有效地减少了 uBlock 算法比特切片优化时的访存指令
条数.