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

软件学报 ISSN 1000-9825, CODEN RUXUEW E-mail: jos@iscas.ac.cn
2025,36(10):4827−4845 [doi: 10.13328/j.cnki.jos.007316] [CSTR: 32375.14.jos.007316] http://www.jos.org.cn
©中国科学院软件研究所版权所有. Tel: +86-10-62562563

*
FBS-uBlock: 灵活的 uBlock 算法比特切片优化方法

龚子睿 1,2 , 郭 华 1,2 , 陈 晨 1 , 张宇轩 1 , 陈俊鑫 1 , 关振宇 1

1
(北京航空航天大学 网络空间安全学院, 北京 100191)
2
(复杂关键软件环境全国重点实验室 (北京航空航天大学), 北京 100191)
通信作者: 郭华, E-mail: hguo@buaa.edu.cn

摘 要: uBlock 算法在算法设计、侧信道防护、物联网应用、密码分析领域得到了广泛应用. 虽然 uBlock 算法适
合高速实现, 但目前该算法公开的实现速率远不如 AES、SM4 等算法. 比特切片是优化分组密码的常用方法, 但在
采用比特切片优化 uBlock 算法时, 面临着因寄存器资源不足而导致的巨大访存开销问题. 为 uBlock 算法设计了一
种灵活的比特切片优化方法 FBS-uBlock (flexible bit slicing uBlock), 降低算法在比特切片下占用的寄存器数量, 进
而降低访存开销, 提升速率. 经过测试, 该优化方法最多能够让 uBlock-128/128、uBlock-128/256 和 uBlock-256/256
算法的访存指令分别降低 71%、71% 和 72%, 加密速率最高能够分别达到 12 758 Mb/s、8 944 Mb/s 和 8 984 Mb/s,
比设计文档中的实现速率分别提升了 3.9、4.2 和 3.4 倍.
关键词: 分组密码; uBlock 算法; 软件优化; 比特切片; 单指令多数据
中图法分类号: TP309

中文引用格式: 龚子睿, 郭华, 陈晨, 张宇轩, 陈俊鑫, 关振宇. FBS-uBlock: 灵活的uBlock算法比特切片优化方法. 软件学报, 2025,
36(10): 4827–4845. http://www.jos.org.cn/1000-9825/7316.htm
英文引用格式: Gong ZR, Guo H, Chen C, Zhang YX, Chen JX, Guan ZY. FBS-uBlock: Flexible Bit Slicing Optimization Method of
uBlock Algorithm. Ruan Jian Xue Bao/Journal of Software, 2025, 36(10): 4827–4845 (in Chinese). http://www.jos.org.cn/1000-9825/
7316.htm

FBS-uBlock: Flexible Bit Slicing Optimization Method of uBlock Algorithm
1,2
1,2
1
1
1
GONG Zi-Rui , GUO Hua , CHEN Chen , ZHANG Yu-Xuan , CHEN Jun-Xin , GUAN Zhen-Yu 1
1
(School of Cyber Science and Technology, Beihang University, Beijing 100191, China)
2
(State Key Laboratory of Complex & Critical Software Environment (Beihang University), Beijing 100191, China)
Abstract: The uBlock algorithm has been widely used in algorithm design, side channel protection, Internet of Things applications, and
cryptanalysis. Although the uBlock algorithm is suitable for high-speed implementation, the publicly available implementation rate of this
algorithm is far lower than that of algorithms such as AES and SM4. Bit slicing is a common method to optimize block ciphers. However,
when using bit slicing to optimize the uBlock algorithm, it faces the problem of huge memory access overhead due to insufficient register
resources. In this study, a flexible bit slicing optimization method named FBS-uBlock is designed for the uBlock algorithm. It reduces the
number of registers occupied by the algorithm under bit slicing, thus reducing the memory access overhead and improving the speed. After
testing, the proposed optimization method can reduce the memory access instruction of uBlock-128/128, uBlock-128/256, and uBlock-256/256
algorithms by up to 71%, 71%, and 72%, respectively. The maximum encryption rates can reach 12 758 Mb/s, 8 944 Mb/s, and 8 984 Mb/s
respectively, which are 3.9, 4.2, and 3.4 times higher than the implementation rates in the design documentation.
Key words: block cipher; uBlock algorithm; software optimization; bit slicing; single instruction multiple data (SIMD)

* 基金项目: 北京市自然科学基金 (4242022); CCF-绿盟科技“鲲鹏”科研基金 (CCF-NSFOCUS 2023006); 大学生创新创业训练计划
(X202210006242)
收稿时间: 2024-02-06; 修改时间: 2024-10-08; 采用时间: 2024-10-29; jos 在线出版时间: 2025-07-09
CNKI 网络首发时间: 2025-07-10