基于Benes网络结构的比特置换在处理器中的实现

目前，通用微处理器大多是以字为单位进行操作的，它的指令结构isa（instruction-set architecture）不支持小于一个字的数据操作，而单比特的置换操作在分组密码算法中使用频率非常高，是提高算法安全性的重要手段；而且比特置换操作在处理器中快速高效的特点，也将影响密码处理得整体性能，但在现有的指令结构处理器中，任意的比特置换通常都采用逻辑操作或查找表的方式实现[1]，即使一个简单的置换操作（如循环位移），也需要多条指令才能完成。根据相关研究可知，一个n比特的置换操作，它的指令级复杂度是0（n），处理速度也就随着n的增加而不断降低，对于，目前实时的网络通信来说，这显然是不可容忍的，因此，针对这一问题在一些专用指令集微处理器asip（application-specific instruction-set processor）中，增加了特殊的置换指令，如多媒体处理器plx中增加了mix、mux和perm等指令 [2]，但这些指令并不能满足n-bit数据的任意置换操作，本文提出了一种在处理器中实现比特置换的方法，给出了相应的比特置换指令及其操作结构。

1 密码学中的比特置换及其一般实现方式

1.1 密码学中的比特置换

比较置换操作能使输入数据中第i比特置换到输出数据的第j比特上，而且置换过程中各位源数据之间不发生计算关系，输入的n比特数据需要log2n比特位置信息或配置信息。

置换是密码算法中隐藏明文信息中冗余度的重要手段，通过位置置换可以实现明文到密文的扩散。置换按明密文映射关系分为三类：直接置换、扩展置换和压缩置换，直接置换指明密文间是一一映射关系，且明文的每一位都有到密文的映射，扩展置换指明密文间为一对多的映射关系，它使得密文对明文的依赖性传播得更快，压缩置换指明密文间是一一映射关系，但并不是明文的每一位都有到密文的映射，置换输入和输出位宽根据算法和置换类型的不同而有所不同，例如des算法中有64bit的初始置换ip、末尾置换ip-1以及轮运算中的32-bit p置换[3]。

1.2 逻辑操作方式

逻辑操作方式是指采用and、or、shift等简单逻辑操作实现复杂的比特置换操作，在此方式下，每对1bit进行置换，处理器需要进行四步操作，1）产生目标比特的mask参数；2）提取相应比特值（and指令）；3）将该比特移至相应位置（shift指令）；4）存储到相应寄存器中（or指令）。由上述过程可知，一个n-bit的位置操作需要4n条指令才能完成，尽管一些处理器中针对这一问题有所改进，将1bit置换操作的指令压缩到2条--汲取指令（extract）和放置指令（deposit），但n-bit置换操作仍需要2n条指令，处理性能没有明显提高。

1.3 查找表方式

查找表方式是另一种实现比特置换的方法，它在速度上与逻辑操作相比有所提高，但需要大量的存储空间放置控制信息，完成一个n-bit的置换操作需要m个查找表，每个表的容量为2n/m×nbit，以64-bit输入数据为例，当m=1时，完成一次任意置换需要一个264×64bit的查找表，这在现有微处理器结构中是无法实现的；当m=8时，完成一次任意置换需要8个容量为28×64bit的查找表，每个表代表源操作数中连续8-bit的置换，表中除了8-bit置换的目标位置外，其他位置均为0，此时共需要23条指令来完成64-bit置换，8条extract指令获得表的索引值、8条load指令置换相应比特、7条or指令连接8个8-bit置换后的数据，这种方法相对于逻辑操作方式来说指令条数减少了很多，但它在实际执行中，load指令往往遇到未命中cache的情况，所以实现n-bit的置换操作需要的复杂度一般为o（n）。

2 比特置换操作的优化实现

2.1 butterfly结构

目前，butterfly结构[4]及其他一些相似的结构都广泛应用于信息处理领域中，如数字信号处理中的快速傅里叶变换（fft）等，图1（a而）中给出了8-bit输入的butterfly结构，图1（b）中给出了相应的inverse butterfly结构。

2.2 benes网络结构

benes网络结构由一个butterfly结构链接一个inverse butterfly 结构组成，它是一种可重排网络，能实现输入端到输出端的所有置换，完成n-bit置换操作需log2n级butterfly变换和log2n级inverse butterfly变换，对于一个64-bit置换，则需要2 log2n=12级变换，且每一级需要n/2-bit配置信息，在处理器中执行置换操作需要一条butterfly指令和一条inverse butterfly指令及log2n个n-bit配置信息。

图2给出了一个8-bit输出的bense网络结构，能完成（abcdefgh）到（cfghbdea）的置换，根据配置信息，它的置换过程如下：butterfly指令完成（abcdefgh）->（abgdefch）->（gdabehcf）->（dgabehfc）；inverse butterfly指令完成（dgabehfc）->（gcbaehcf）->（bdgacfeh）->（cfghbdea）。

2.3 比特置换指令

比特置换单元内部设置了一定的缓存区，用于存储配置信息，如图3所示的b1、b2、b3和i1、i2、i3。由于不同asip中指令格式存在差异，这些内部缓存区是可选择的，由于inverse butterfly指令类似于butterfly指令，下面以butterfly指令为例进行说明，对于超长指令字格式（vliw），支持多操作数方式，不需要内部寄存器存储配置信息，其指令可描述为：butterfly rd，rs，b1，b2，b3。其中rd为置换数据目的地址，rs为置换数据地址，b1、b2、b3为配置信息的外部存储地址，即一条butterfly指令包括rs、b1、b2、b3四个源操作数，对于精简指令格式（risc），最多支持两个源操作，相应指令可描述为：butterfly rd，rs，b3，即需要将配置信息b1、b2、i1、i2在进行置换操作前装入到置换单元内部缓存区中，而b3、i3则从外部存储器中获得，对于超标量结构处理器，假设其有两路并行处理通路，则butterfly 指令与inverse butterfly 指令可并行执行，对于所采用的不同指令格式，具体操作指令数也不同。

3 性能比较

如果一个处理器可以支持比特置换操作，则其比特置换操作的延时必须与逻辑运算单元（alu）的时钟频率相匹配，在alu中主要是乘法器[5]延时较大，通常占用3-5个时钟周期，因此只有使比特置换操作延时小于乘法运算延时，才能在不影响处理器整体性能的前提下，使处理器支持比特置换操作，而逻辑操作方式与查找表方式的比特置换实现方法所占用的时钟周期都远远大于3个时钟周期，如表1所示，当采用benes网络结构时，仅执行两次butterfly指令，在性能得到了很大提高，使n-bit的比特置换操作的复杂度从o（n）降至o（log（n））。

比特置换是现代对称密码算法中的一个基本操作，但由于它比其他操作延时大且需要大量的控制信息，使得目前的通用处理器并不支持比特置换操作，本文针对上述两个问题提出的解决方案，使其可以在处理器中快速实现，并以64-bit置换为例，在fpga上对这一结构进行了验证，结果仅占用700个逻辑单元，最高时钟频率达到了200mhz，采用asic实现时，其性能还将在此基础上显著提高，从而满足网络通信等方面的需求。