面向密码算法的大位宽比特置换操作高速实现方案

Wide-width Bit Permutation Instructions for Accelerating Cryptographic Algorithms

针对面向字级优化的通用处理器,在应对密码算法中大位宽比特置换操作时效率较低的问题,该文提出2N-2N和kN-kN(k>2)的大位宽比特置换操作高速实现方案。并针对方案中涉及的比特提取和比特提取-移位两种操作,分别提出专用扩展指令BEX,BEX-ROT。在此基础上,对专用指令硬件架构的高效设计进行研究,提出一种基于Inverse Butterfly网络统一硬件架构-RERS(Reconfigurable Extract and Rotation Shifter)及相应可重构路由算法,以最大限度地共享硬件资源,减小电路面积。实验结果表明,所提方案能够将处理器架构执行大位宽比特置换操作的指令条数缩减约10倍,大幅提升其处理效率。同时,由专用指令所带来的硬件资源开销和延迟开销均较低,不会影响到原架构正常工作频率。

Wide-width bit permutation is a very commonly used operation in symmetric cryptographic algorithms. However, current word-oriented general microprocessors are inefficient to cope with the complex bit-level permutation operations. To solve this problem, two schemes for 2N-2N and kN-kN permutations are proposed respectively, including two extended instructions BEX and BEX-ROT. Furthermore, the efficient hardware implementation of the instructions are studied, and then a unified hardware circuit named RERS （Reconfigurable Extract and Rotation Shifter） is proposed with a corresponding reconfigurable routing algorithm. The RERS can share hardware resources to achieve the purpose of reducing area. The experimental results show that the proposed schemes can truly decrease the number of instructions for accomplishing an arbitrary wide-width bit permutation （instructions reduced by 10 times）, which greatly accelerate the performance of microprocessors. At the same time, the overhead of hardware resources and delay caused by the two extended instructions is very low, which will not affect the normal operating frequency of the original microprocessors.