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

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

一步优化了 DES 算法, Kwan 利用选择函数优化了 S 盒的计算, May 利用 Schaumüller-Bichl [18] 提供的 S 盒逻辑表
达式加速了算法. Matsuda 等人 [19] 、Papapagiannopoulos [20] 采用比特切片优化了 PRESENT 算法, 张笑从等人 [21] 、
王磊等人 [22] 、陈晨等人 [23] 采用比特切片优化了 SM4 算法, 并降低了计算 S 盒时需要的逻辑门个数. 对于 AES 算
法, 还有众多针对 CPU 平台 [24−28] 和 GPU 平台 [29,30] 的比特切片优化.
在 Biham 所提出的比特切片方法中, 每个寄存器代表一个比特位, 后续也产生了不一样的比特切片表示法.
例如, Könighofer [12] 考虑到 CPU 中仅有 16 个 64 比特寄存器, 已有的 AES 比特切片方法无法将数据全部保存在寄
存器中, 导致产生了大量影响性能的访存指令, 由此提出了访存开销更低的 AES 比特切片表示法. Käsper 等人 [13]
考虑 XMM 寄存器的数量, 采用与 Könighofer 类似的比特切片方法优化了 AES 算法的比特切片实现. 苗鑫等人 [31,32]
将 SM4 算法的明文数据视为立方体的结构, 提出新的针对 SM4 算法的比特切片表示法. 王闯等人 [33] 提出一种通
用的切片分组密码算法模型, 所优化的 SM4 算法在切片形式上与苗鑫等人的方法类似, 但其重点考虑的是减少数
据切片过程的开销. 陈晨等人 [14] 针对传统比特切片的访存问题, 设计了基于寄存器的优化方法, 并从指令层面分
析了优化前后的内存读取次数和耗时. Adomnicai 等人 [34] 提出针对 AES 算法的固定切片优化方法, 将行移位和列
混淆融合, 并利用 ARM 处理器的桶形移位器削减移位运算的开销. 此外, 一些密码算法在设计之初就考虑了比特
切片实现友好的性质, 例如 GIFT 算法 [35] 、ASCON 算法 [36] 、FESH 算法 [37] 、TANGRAM 算法 [38] 等. 对于 PRESENT
算法, 虽然原始结构不是比特切片实现友好的形式, 但 Reis 等人 [39] 提出了线性层分解方法, 将 PRESENT 算法转
变成了易于比特切片实现的形式, 从而可通过比特切片方法进行实现加速.
单指令多数据 (single instruction multiple data, SIMD) 指令集是加速密码算法实现的常用技术, 常见的 SIMD
指令集有 x86 架构的 SSE 指令集、AVX 指令集和 ARM 架构的 NEON 指令集. Hamburg [40] 利用 Permute 指令加
速 AES 算法实现, CBC 模式加密速率能够达到 10.8 c/B (cycles/byte), CTR 模式能够达到 5.4 c/B. Matsuda 等人 [19]
使用 AVX 指令集优化 PRESENT 算法和 Piccolo 算法, PRESENT-80/128 达到 5.79 c/B, Piccolo-80 达到 5.69 c/B.
Seo 等人 [41] 使用 NEON 指令集优化 LEA 算法, 4 线程并行能够达到 3.2 c/B. Park 等人 [42] 使用 NEON 指令集优化
SIMON/SPECK 算法, SIMON-128/128 能够达到 32.4 c/B, SPECK-128/128 能够达到 9.7 c/B, 多线程下分别达到
14.3 c/B 和 5.1 c/B. Adomnicai 等人 [43] 采用 S 盒分解方法优化 Skinny-128 算法, 在 ARM 平台达到 127 c/B, 在 x86
平台达到 44 c/B. 对于 Banik 等人 [35] 提出的 GIFT 算法, GIFT-64/128 在 AVX2 指令集的优化下能够达到 2.10 c/B.
对于 uBlock 算法 [1] , 在使用 x86 平台的 SSE 指令集优化下, uBlock-128/128 算法能够达到 11.8 c/B, uBlock-128/256
算法能够达到 17.4 c/B, uBlock-256/256 算法能够达到 13.6 c/B. 高莹等人 [44] 使用 AVX2 指令集优化 uBlock 算法,
比设计文档中的实现方法提升了 269%、182% 和 49%.
密码算法中所有的算术运算都是在处理器的寄存器上计算, 倘若算法需要使用的寄存器数量大于处理器提供
的物理寄存器数量, 则会产生访存开销. 研究者们进行了各种尝试减少访存开销. 在公钥密码算法中, Hutter 等
人 [45,46] 和 Seo 等人 [47] 提出新的高精度乘法计算方法, 减少读取指令的条数. 在分组密码算法中, Schwabe 等人 [27] 通
过设计寄存器调度算法优化 AES 算法, 减少 S 盒在比特切片下消耗的访存指令; Könighofer [12] 和 Käsper 等人 [13] 针
对算法结构提出了新的比特切片表示法, 减少寄存器使用数量; May 等人 [17] 在优化 DES 算法时发现, Schaumüller-
Bichl [18] 的 S 盒表达式逻辑门个数比 Kwan [16] 的更多, 但使用前者优化的 DES 算法实现速率反而比后者的更快, 他
们认为是访存导致了这一反常现象.
2 基础知识

2.1 uBlock 算法

uBlock 是一族分组密码算法, 整体结构是 PX 结构, 根据分组和密钥的比特长度可分为 uBlock-128/128、
uBlock-128/256 和 uBlock-256/256, 迭代轮数分别为 16、24 和 24. 图 1 展示了 uBlock 算法的加密轮函数, 加密输
入 n 比特明文 X, 每轮迭代中依次计算轮密钥加、S 盒、线性变换 B 和线性变换 PL/PR, 输出前再计算一次轮密
钥加. 解密是加密的逆过程, 在此不赘述.