可重构移位单元的设计与实现

1 引言
　　
随着通信和网络技术的飞速发展，安全应用的范围越来越广，而采用对称密码是提供保密性服务的主要手段。作为基础密码模块，对称密码可用于构造伪随机数产生器、流密码、认证码和Hash函数等，也可以作为消息或实体认证、数据完整性和数字签名方案等的核心部件。但是对于一种密码算法，系统不仅要求其在安全方面有很高的可靠性和保密性，还要求它能够使用软、硬件高效灵活的实现。
　　
在硬件设计方面，以前往往采用专用集成电路ASIC(Application Specific Integrated Circuit)来实现密码处理系统。它的缺点是灵活性不够，只能实现固定的一种算法或将几种算法的IP核集成到一起，当有新的算法产生时，只有重新设计密码芯片或IP核。因此可重构的密码处理系统的设计与实现已经成为了新的发展趋势[1]，而一个庞大的可重构密码系统是由多个可重构的密码运算单元共同组成的，而可重构的移位单元，就是其中一种密码处理单元。灵活、通用的移位单元的设计与实现，将会使一个芯片内集成更多的对称密码算法，同时资源消耗与处理性能不会受到影响。而目前的设计中并没有一个通用的可重构移位单元来支持对称密码算法中所有的移位操作。本文就针对这一问题，对移位操作的特性进行了研究与分析，并提出了一种支持4/8/28/32/128-bit移位位宽的任意移位长度的移位单元的设计方案，它不仅性能可以满足密码处理的需求，而且关键是达到了通用的目的，为可重构密码系统的设计与实现提供了基础。
　　
2 可重构移位单元的应用及硬件结构
　　
2.1 对称密码算法中的移位操作
　　
移位操作在对称密码算法中应用非常广泛[2]，但由于算法的不同，使得移位位宽和移位长度都不相同。经过总结现有的对称密码算法，它们的移位位宽包括以下几种：4-bit、8-bit、28-bit、32-bit和128-bit。因此一个可重构移位单元的设计首先就必须支持4/8/28/32/128-bit位宽的操作。为了满足不同算法的需求，移位操作的模式应该包括：逻辑左移、逻辑右移、循环左移和循环右移。而根据移位操作的特点，其又可分为定长的移位和变长的移位，区别是移位长度是常量还是变量，前者如IDEA和Twofish算法，后者如AES[3]和RC6等。并且目前常用的对称密码算法中，无论是哪种情况其移位长度都在1-bit到31-bit之间。下面给出了几种对称密码算法中使用移位操作的情况，如表1所示：
表格 1 对称密码算法中的移位操作


　　
可重构移位单元的设计主要是满足不同对称密码算法的需求，通过一致的接口和不同的控制信号，共同使用一个模块，完成不同移位位宽、移位长度的移位操作。因此，通过分析对称密码算法，此移位单元的设计目标就是，支持位宽为4/8/28/32/128-bit的移位长度在1-bit到31-bit之间的任意长度的移位操作。
　　
2.2 可重构移位单元的整体结构
　　
可重构移位单元又可称为通用移位单元，它的特点之一就是移位长度是可变的，这种变长的移位操作通常有两种实现方法：每次移1位多次操作的方法和采用桶形移位(Barrel Shift)的方法。前者通常是以线性反馈移位寄存器(LFSR)为基础进行设计，这种双向移位寄存器的移位操作受时钟控制，移N位就需要N个时钟，移位速度受最高时钟频率及移位数目的影响，采用这种方法进行移位运算很难满足高速数据处理的需求。因此，在本设计中采用了多级互联(Multilevel Connection)的桶形移位设计原理[4]。图1中给出了可重构移位单元的整体结构图，设计分为5级：第一级完成16-bit长度移位；第二级完成8-bit长度移位；第三级完成4-bit长度移位；第四级完成2-bit长度移位；最后一级完成1-bit长度移位。任意小于32-bit长度的移位均可以拆分为16-bit、8-bit、4-bit、2-bit和1-bit长度移位的组合。每一级的移位使能信号可以由移位长度的二进制代码得到，如移位长度为：（二进制），则为第一级的移位使能信号；为第二级的移位使能信号，……，最后一级由控制。S-128为128-bit位宽选择信号；S-32为32-bit位宽选择信号；S-8为8-bit位宽选择信号；S-4为4-bit位宽选择信号。



图 1 可重构移位单元结构图
　　
此设计中，数据总线的宽度采用2路并行的64-bit总线，因此目标移位单元可同时完成，2个64-bit的移位；4个32-bit的移位；16个8-bit的移位以及32个4-bit的移位。对于DES或3DES算法中的28-bit位宽的移位，可以补成32-bit后再进行移位操作，其移位长度仅为1-bit或2-bit的特点保证了移位结果的正确性。
　　
3 移位单元的指令系统设计
　　
当移位单元在处理器中实现时，需要有相应的指令系统支持各种操作的实现，根据对称密码算法中移位操作的类型，定义了此移位单元的功能，可将其分为下列四种指令：

LSL：逻辑左移(Logic Shift Left)；
LSR：逻辑右移(Logic Shift Right)；
CSL：循环左移(Circular Shift Left)；
CSR：循环右移(Circular Shift Right)。
　　
下面给出了移位操作的指令格式，在不考虑其他密码处理单元时，此移位指令需要10-bit编码，如图2所示：



图 2  移位操作的指令格式

其中Mode[9..8]为模式选择信号：

00——逻辑左移
01——逻辑右移
10——循环左移
11——循环右移
　　
位宽编码采用霍夫曼编码，长度编码为移位长度的二进制代码或长度寄存器的地址，因为当移位位宽为32-bit时，移位长度的来源有两种：立即数(如Serpent)或寻址寄存器(如RC6)，因此在位宽编码时，需要将这两种情况分别编码，以进行不同的操作，如表格2所示：

表格 2 移位指令中的位宽与长度编码


　　
密码处理系统的指令译码单元将相应移位指令译码后得到S-128、S-32、S-8、S-4、等信号，可重构移位单元在这些信号的控制下完成移位操作，即实现了不同算法的可重构移位配置。
　　
4 性能评估
　　
以上设计采用VHDL语言描述，在QuartusII 4.2环境下编译综合，选用Altera StratixII系列器件为目标器件进行整体综合、仿真和底层布局。对多组分数据进行测试仿真，均得到正确结果。
　　
下面将实现的可重构移位单元下载到Altera StratixII系列器件EP2S15F484C3后测得的主要性能指标在表3中给出。
表格 3 可重构移位单元的主要性能参数


　　
5 总结
　　
本文给出了一种适用于对称密码算法的可重构移位单元的设计方法及最终的实现性能。此移位单元设计了专用的移位指令，通过指令折的控制，分别执行4/8/28/32/128-bit的移位长度在1-bit到31-bit之间的任意长度的移位操作。经过在FPGA上的验证，其运行结果正确，且运算速度快，由于工艺的不同，当采用ASIC实现时，其性能还将在此基础上明显提高，从而能够满足实现多种对称密码算法的密码芯片的需求，并为可重构密码芯片的设计与实现奠定了基础。
　　
本文作者创新点：
　　
1) 分析了密码算法中的移位操作；
2) 设计实现了一个可重构的移位单元。