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

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

uBlock 是一族分组密码算法, 自提出以来就受到了广泛关注, 在算法设计 [2,3] 、侧信道防护 [4] 、物联网应用 [5]
[1]
和密码分析领域 [6−10] 都有相关研究工作. uBlock 算法在设计之初就考虑了处理器的计算资源, 采用的 4 比特 S 盒在
软件平台可利用 SSE、NEON 指令集高效实现, 但 uBlock 算法目前的实现速率仍不如 AES、SM4 等分组密码算法.
比特切片是分组密码算法常用的优化方法. 自 Biham [11] 提出比特切片思想后, 学者们对比特切片进行了广泛
研究, 包括将比特切片应用在各种算法的优化中、提出比特切片的变体、让设计的算法天然具备比特切片的形式
等. 当将 Biham 的比特切片方法用于分组密码算法实现时, 扩散运算使得采用比特切片优化的算法不满足程序设
计的局部性原则, 从而产生大量的访存开销. 例如, 当使用类似 Biham 的比特切片方法优化 uBlock 算法时, uBlock-
128/128 和 uBlock-128/256 至少需要占用 128 个寄存器, uBlock-256/256 至少需要占用 256 个寄存器, 但通用处理
器仅有 16 个或 32 个寄存器. 由于密码算法中所有的算术运算都是在处理器的寄存器上计算, 倘若算法需要使用
的寄存器数量大于处理器提供的物理寄存器数量, 则会产生额外的访存开销. 因为访存指令比一般的算术指令更
耗时, 所以应该尽量减少比特切片的访存指令. 虽然目前学术界也有针对其他密码算法的访存优化方法和比特切
片优化方法, 但用于优化 uBlock 算法的比特切片实现时但仍存在以下问题.
(1) 在优化 uBlock 算法比特切片实现带来的访存开销时, 发现 AES 或 SM4 算法的切片表示方法并不适合
uBlock 算法轮函数中的运算, 因此无法直接使用 Könighofer [12] 、Käsper 等人 [13] 和陈晨等人 [14] 的切片表示方法, 需
要针对 uBlock 算法重新设计新的切片表示方法.
(2) 目前公开的 uBlock 算法 S 盒逻辑函数使用了硬件平台特有的同或、与非、或非门, 这些逻辑运算在软件
平台上需要多条处理器指令组合才能完成, 因此现有的逻辑函数不适合比特切片软件实现, 降低 S 盒在比特切片
时的计算开销需要以降低比特切片门复杂度 (bitslice gate complexity, BGC) 为目标优化 S 盒.
针对上述问题 (1), 本文通过分析 uBlock 算法轮函数结构来总结设计新的比特切片表示法的指导思想, 依据
指导思想推出多种不同寄存器占用数量的 uBlock 算法比特切片表示法, 减少算法计算过程需要的访存指令, 灵活
适用于各种拥有不同寄存器数量的处理器平台. 针对上述问题 (2), 本文利用现有的 Lighter [15] 工具优化 uBlock 算
法 S 盒, 限制最终的逻辑函数仅能使用软件处理器支持的逻辑运算, 以减少比特切片门复杂度为目标搜索更适合
比特切片实现的 S 盒逻辑函数. 本文主要工作如下.
(1) 提出了一种灵活的 uBlock 算法比特切片优化方法 FBS-uBlock (flexible bit slicing uBlock), 降低算法在比
特切片下占用的寄存器数量, 进而降低实现时的访存开销. 基于该方法, 对于 uBlock-128/128 和 uBlock-128/256,
本文提出了占用 128、64、32、16 和 8 个寄存器的比特切片表示法; 对于 uBlock-256/256, 本文提出了占用 256、
128、64、32、16 和 8 个寄存器的比特切片表示法.
(2) 给出了适合比特切片软件实现的 uBlock 算法 S 盒逻辑函数, 降低了算法 S 盒和逆 S 盒的比特切片门复杂
度. 本文采用 Lighter 工具完成 S 盒的逻辑函数化简, 得到 BGC 为 9 的 S 盒逻辑函数以及 BGC 为 9 的逆 S 盒逻
辑函数, 优于设计文档中 BGC 为 14 的 S 盒逻辑函数.
(3) 基于上述优化方法在 x86 平台实现了 uBlock 算法, 并进行了理论分析和实验分析. 本文基于所提出的优
化方法分别实现了 uBlock-128/128、uBlock-128/256 和 uBlock-256/256 算法, 与设计文档相比, 加解密速率分别提
升了 3.9、4.2 和 3.4 倍; 与 Biham 的比特切片表示法相比, 访存指令条数最多能够分别降低 71%、71% 和 72%,
访存指令占比从 60%、61% 和 62% 最多能够降低到 25%、25% 和 24%.
本文第 1 节介绍相关工作. 第 2 节介绍背景知识, 包括 uBlock 算法、比特切片方法和单指令多数据指令集.
第 3 节介绍本文提出的优化方法 FBS-uBlock, 包括算法轮函数结构分析、比特切片表示法、优化非线性 S 盒这
3 个部分. 第 4 节介绍实现的细节和理论分析. 第 5 节给出性能测试和分析. 第 6 节总结全文.
1 相关工作

比特切片是分组密码算法常用的优化方法. 自 Biham [11] 提出比特切片思想后, 学者们对比特切片进行了广泛
研究, 包括将比特切片应用在各种算法的优化中、提出比特切片的变体、设计比特切片友好的算法. 1997 年,
Biham 在优化 DES 算法时使用了比特切片思想, 将 DES 加解密速率提升了 64%. 之后 Kwan [16] 、May 等人 [17] 进