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

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

8. Z[r+k] ← ((Z[r] ∧ m j ) << k) ∨ (Z[r+k] ∧ m j )
9. Z[r] = t
10. end
11. end
2.3 SIMD 指令集
SIMD 指令集是一种提升算法性能的重要技术, 其并行处理能力能够让处理器在同一时间处理多份数据, 被
广泛应用于对称密码和非对称密码的软件实现中. 表 3 介绍了 x86 架构的 AVX2 指令集和 ARM 架构的 NEON
指令集, 其中 AVX2 指令集操作 256 比特长的寄存器, NEON 指令集操作 128 比特长的寄存器.

表 3 x86 和 ARM 指令集中的指令以及对应关系

指令简介 AVX2指令 NEON指令
数据加载 _mm256_loadu_si256 vld1q_u8
数据存储 _mm256_storeu_si256 vst1q_u8
逻辑与 _mm256_and_si256 vandq_u8
逻辑或 _mm256_or_si256 vorrq_u8
逻辑异或 _mm256_xor_si256 veorq_u8
64比特逻辑左移 _mm256_slli_epi64 vqshlq_n_u64
64比特逻辑右移 _mm256_srli_epi64 vrshrq_n_u64
数据重排/4比特查表 _mm256_shuffle_epi8 vqtbl1q_u8
64比特高位打包 _mm256_unpackhi_epi64 vzip2q_u64
64比特低位打包 _mm256_unpacklo_epi64 vzip1q_u64
128比特重排 _mm256_permute2x128_si256 －

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

3.1 算法轮函数结构分析
本文减少比特切片访存开销的核心思想是通过让每个寄存器表示多个 uBlock 算法的比特位来减少寄存器的
使用. 使用 Biham 的比特切片方法优化 uBlock 算法时, 每个寄存器表示 1 个比特位, 占用的寄存器数量和 uBlock
算法的分组比特数相同. 本文尝试让每个寄存器表示 uBlock 算法的 2 个、4 个、8 个和 16 个比特位, 从而使得占
用寄存器数量降低至之前的 1/2、1/4、1/8 和 1/16. 但一个寄存器表示多个比特位的方式会让数据中比特位与比
特位之间的联系变得更紧密, 因此会增加线性变换中不同比特位之间的运算开销. 本文针对 uBlock 算法的结构,
充分考虑线性变换的结构特点, 精心设计了多种比特切片表示法, 在削减寄存器数量的同时尽量减少额外的运算
开销. 下面从算法迭代过程的数据结构、轮密钥加、S 盒、线性变换 B 和线性变换 PL/PR 这些模块详细分析, 讨
论减少寄存器的可行性, 并说明本文是如何减少额外运算开销的.
uBlock 算法加密和解密的轮函数迭代分成了 X 0 和 X 1 左右两部分, 线性变换 B 是 X 0 和 X 1 相互的循环移位
与异或, 迭代最后一步的 PL 和 PR 置换分别对 X 0 和 X 1 进行. 因此, 本文将 X 0 和 X 1 这两部分占用的寄存器分别
考虑, 在减少寄存器占用时不再针对算法分组的整体, 而是针对 X 0 和 X 1 这两部分.
uBlock 算法的轮密钥加模块是异或运算, 是对应比特位的模 2 加法, 不存在不同比特位之间的运算. 因此, 任
何比特切片表示法都不会对该模块的计算造成影响, 只需要预先把轮密钥的表示形式转变成和明文一致的表示形
式即可.
uBlock 算法的非线性变换由多个相同的 4 比特的 S 盒并置而成, 这意味着一个分组内的多个 S 盒可以同时
计算. 另外, 比特切片中的 S 盒需要通过逻辑门函数计算, 包含大量的不同比特位之间的复杂运算, 所以需要让输
入 S 盒的这 4 个比特位分散在不同寄存器之中, 否则会极大增加 S 盒计算过程的额外开销.