可适配多路并行移位操作指令及其硬件实现研究
2008-12-10
作者：张 琰, 戴紫彬
摘 要: 在分析Rijndael、Serpent、MARS等41种分组密码算法" title="密码算法">密码算法的基础上,对分组密码算法中移位的操作特征进行了研究,提出了可适配" title="适配">适配、支持多路并行执行的移位操作指令" title="操作指令">操作指令,通过适配参数,可完成固定或不定、循环或逻辑、左向或右向、不同位宽的移位操作,不同位宽的操作支持不同组数的并行执行,并给出了其级联" title="级联">级联及组合的指令模型,研究了移位操作的硬件实现算法,设计并实现了硬件单元,给出了其性能分析。
关键词: 分组密码; 可适配; 并行; 移位操作指令
分组密码具有速度快、易于标准化和便于软硬件实现等特点,已成为信息与网络安全中实现数据加密、数字签名、认证及密钥管理的核心体制之一。随着密码学和芯片设计技术的发展,专用密码处理器作为一个高速、灵活的实现方式已被广泛认可。专用分组密码处理器的指令集包含了较多运算指令,这些运算指令的灵活性与执行效率在一定程度上决定了系统处理数据的灵活性与速度。移位操作具有较好的扰乱与扩散作用,又易于软硬件实现,所以其使用频率非常高,因而移位操作指令的设计成为专用分组密码处理器指令集设计的关键之一。本设计基于32位RISC微处理器,提出了可适配的、支持多路并行执行的移位操作指令RPSI(Reconfigurable and Parallel Shift Instruction),能够实现字节移位、亚字移位、字移位以及双字的级联移位,并通过指令组合实现长字移位。文章给出了相应移位运算单元的硬件设计,最后给出了移位运算单元的性能分析。
1 分组密码算法中的移位操作
分组密码算法中用到了大量的移位操作,但其执行模式各不相同。
移位操作按照所移位数是否可变,分为固定移位和不定移位。基于常量的固定移位是分组密码处理中一种最主要的移位模式,它使数据比特到达指定的位置,且算法不易遭受定时攻击,包含移位位数及其补码的寄存器内容也可抵抗能量攻击[6],在Rijndael、DES、RC6等41种分组密码算法中有25种算法使用了固定移位[1]。依赖于分组运算中间数据或子密钥的不定移位模式,使不同子数据路径上的分组之间有了较好的扰乱与扩散效果,因此具有较强的抵抗线性密码分析的能力,目前已经得到广泛应用。所在分析的41种分组密码算法中有10种算法使用了不定移位。表1给出了移位操作在常用分组密码算法中的应用。
移位操作按照其移位方式,可分为循环移位方式和逻辑移位方式,其中,循环移位方式应用较多,如Serpent[2]、Twofish[3]、MARS[4]等算法均使用了循环移位。
移位操作按照移位方向,可分为左向移位和右向移位方式。
按照移位的操作位宽,可分为字节(8bit)移位、亚字(16bit)移位、字(32bit)移位、双字(64bit)移位及长字(128bit)移位。除DES算法移位操作的操作位宽为28bit外,其他算法的操作位宽均为2n bit(n=34567)。考虑到一些专用领域,像军事应用,有些专用密码算法所使用的移位操作位宽已达到256bit, 但因当前分组密码算法的处理位宽多为32bit,所以字移位操作的使用频率相对较高。
2 RPSI的设计及其可扩展、可级联特性研究
2.1 RPSI的设计
经对分组密码算法中移位操作特征的分析可知,完成一个指定的移位操作,需要确定其移位位数是否可变,采用何种移位方式、移位方向及移位操作位宽,所以移位操作指令的func域要包含的四个参数为:source、com、width、mode,加上标识移位位数是立即数的shift域,以及指令本身的操作数域rd、rs1及rs2,其指令格式如表2。
对func域上的source、come、width、mode适配不同的值后,此指令就可以完成不同的移位操作。由于当前常用密码算法的处理位宽多为32bit,且本设计是基于32位RISC微处理器,所以设定其操作数rd、rs1,rs2的位宽为32bit的寄存器数,imm为5bit的立即数,它根据参数source而定。
sourse的值可适配为1或0。适配为0时,代表所进行的操作为固定移位,imm为5bit的立即数;适配为1时,代表所进行的操作为不定移位,移位位数存放在rs2中,rs2为32bit的寄存器数(取后5位);mode为移位模式,00时为逻辑左移,01时为逻辑右移,10时为循环左移,11时为循环右移。width是8bit、16bit或32bit移位位宽的选择。width为00时,表示执行字节移位,一条指令可并行完成四组字节移位;width为01时,执行亚字移位,一条指令可并行完成两组;为10时,执行字移位。例如:指令IROLm Rd, Rs1, #3,它所完成的操作为:将寄存器Rs1中的32bit数按8bit分四组,分别进行固定的循环左移,移位位数为3;同理,进行相应的不定移位操作时,其指令为ROLm Rd, Rs1, Rs2,其移位位数由Rs2寄存器数的低5bit指定。图1(a)、图1(b)给出了当width为8时,执行四种字节移位操作指令的功能示意图,指令将输入的32bit数据分为4个字节,每个字节自身独立地进行指定模式的移位操作。图1(c)、图1(d)给出了当width为32bit时的字移位操作功能示意图。
2.2 RPSI的级联执行
随着分组密码算法主流分组宽度的增加,仅在32bit数据路径上的移位操作已不能满足要求,但由于RISC处理器32位位宽的局限性,不能改变其32bit的数据路径,因此在进一步研究移位操作的基础上,提出了移位操作指令的级联执行模式,即64bit级联移位。
假设要执行的操作为64bit循环左移,移位位数为m,其指令为CROL Rd, Rs1, Rs2, #imm,这时指令格式中func域的com值是1,表示级联。Rs1、Rs2是64bit源操作数,Rs1中存放的是64bit中高32bit,Rs2中存放的是64bit中低32bit,Rd为目的操作数,运算后存放的是64bit移位的高32bit结果。下一个时钟(第二步),交换64bit的高低32bit,运算后Rd存放64bit移位的低32bit结果。
这样就在32bit的数据路径上实现了64bit的移位操作。其功能示意图如图2所示。
同理可执行循环右移操作。但在执行级联的逻辑移位操作时有所不同,进行逻辑左移时,第一步与循环移位相同,在第二步时,Rs1中存放的是64bit中低32bit,Rs2中存放的操作数是全零;进行逻辑右移时,在第一步时,Rs1中存放的是64bit中高32bit,Rs2中存放的操作数全为零,第二步与循环移位相同。
2.3 RPSI的组合执行
某些密码算法的移位操作位宽是128bit,例如IDEA算法的子密钥生成中,就用到了长字移位操作。在级联移位指令的基础上,通过指令的组合实现128bit移位操作,或者更长位宽的移位操作,例如:要完成128bit的移位,需要执行四条级联移位指令。
以128bit逻辑左移5位为例,假设R4&R3&R2&R1表示128bit待移位的数据,则执行指令CSHL Rd, R1, Rs, #5(Rs中的数是全零),得到移位后最终结果的31~0位;执行指令CSHL Rd, R2, R1, #5,得到移位后最终结果的63～32位,执行指令CSHL Rd, R3, R2, #5,得到移位后最终结果的95~64位;执行指令CSHL Rd, R4, R3, #5,得到移位后最终结果的127～96位。
再以128bit循环左移5位为例,假设R4&R3&R2&R1表示128bit待移位的数据,则执行指令CROL Rd, R1,R4,#5,得到移位后最终结果的31～0位,执行指令CROL Rd,R2,R1,#5,得到移位后最终结果的63～32位;执行指令CROL Rd,R3,R2,#5,得到移位后最终结果的95～64位;执行指令CROL Rd,R4,R2,#5,得到移位后最终结果的127～96位。
同理,可以用这种多条指令组合的方式实现256bit的移位。128bit移位操作功能示意图如图3所示。
3 RPSI的硬件实现及其性能分析
3.1 移位操作硬件实现算法研究
传统的实现方法中,基于线性反馈移位寄存器LFSR是实现移位操作的一种主要方式,LFSR通常以移1位运算为基础,循环移k位通过k次调用移1位基本运算实现,占用k个时钟周期,移位速度受移位位数的影响。因此对于移位位数较大的操作,采用LFSR进行循环移位运算很难满足高速数据处理的需求。
循环移位操作还可以看作是一类特殊的置换,采用基于BENES网络的实现方法。但是,由于移位位数k的不确定性,导致配置信息生成电路较为复杂,不利于软硬件实现。下面在对循环移位及逻辑移位分别研究的基础上,给出了基于数据选择器" title="数据选择器">数据选择器的实现方法。
(1) 循环移位的实现
令移位位数k=kn-12n-1+kn-22n-2+…+…k12+k0,则循环移位可以表示为: y=RSH(a,k),y的第j位y(j)可以表示为: y(j)=a((j±k)modN)
其中,执行左移操作时操作符为“-”,执行右移操作时操作符为“+”,N为操作数a的位宽。由此可得:
即:任意位的循环移位操作分解为若干加减2i置换操作的级联。对于循环左移而言,循环移位操作可以分解为减2i置换操作。
循环左移操作算法描述:
Input:操作数a, k=kn-12n-1+ kn-22n-2+…+k12+k0 Output:y
(1) y←a
(2) For i=n-1 downto 0 do
(3) For j= 0 to N-1 do
If ki=1 then
If j≤k then b(j)=y((j-2i)modN)
else b(j)=0
else b(j)=y(j)
(4) y=b Return (y)
当N=2n时,循环左移操作可以采用n级数据选择器实现,每一级使用N个二选一数据选择器,共计需要nN个二选一数据选择器,系统的延迟相当于n级二选一数据选择器的延迟。循环右移操作可以看作循环移位位数为N-k的循环左移操作,由此可以构造如图4所示的循环移位结构。
(2) 逻辑移位的实现
对于逻辑左移,上述算法可以修改如下:
Input:操作数 a,移位位数 k=kn-12n-1+ kn-22n-2+…+k12+k0 Output:y
① y←a
② For i=n-1 downto 0 do
③ For j= 0 to N-1 do
If ki=1 then
If j≤k then b(j)=y((j-2i)modN)
else b(j)=0
else b(j)=y(j)
④ y=b Return (y)
可以采用类似的方法对逻辑右移操作算法进行修改,本文不再赘述。在硬件实现时,可以通过将上述循环移位电路的每一个数据选择器扩展为四选一实现支持循环移位和逻辑移位的电路。
3.2 移位操作硬件单元的实现及性能分析
根据基于数据选择器的实现原理,用verilog语言实现了32bit数据路径上的移位操作硬件单元,用modelsim SE 6.0仿真软件进行了功能仿真,对于RPSI所指定的功能,均能正确完成。使用Design Compiler综合工具进行了综合,在0.18μm工艺下综合结果如表3。
由前面分析可知,要完成32bit数据路径上RPSI不同模式的移位操作,只需在图4的每个选择输入上加一个四选一的数据选择器,其关键路径即为一级四选一数据选择器和六级二选一数据选择器的路径延迟。
移位操作是密码算法中常用的运算,特别是在密钥调度中用于子密钥的生成。本文在分析Rijndael、DES、RC6等41种分组密码算法的基础上,首先对分组密码算法中移位运算的操作特征进行了研究,结合移位操作特征,提出了可适配的、支持多路并行执行的RPSI;通过适配操作特征域上的source、com、width、mode四个参数,可完成固定或不定、循环或逻辑、左向或右向、不同位宽下的移位操作,能够支持字节移位、亚字移位、字移位以及双字的级联移位,并通过指令组合实现长字移位;设计并实现了其硬件单元,给出了硬件单元的性能分析。
参考文献
[1] ELBIRT A J. Reconfigurable computing for symmetric-key algorithms. PhD thesis, Electrical and Computer Engineering Department University of Massachusetts Lowell,2002,(4): 22.
[2] Ross Anderson Eli Biham Lars Knudsen Serpent: A Proposal for the Advanced Encryption Standard http://www.ii.uib.no/~larsr/
[3] Bruce Schneier John Kelsey Doug Whiting Twofish: A 128-Bit Block Cipher http://www.counterpane.com/twofish.html
[4] IBM Corporation Carolynn Burwick Don Coppersmith Edward D’Avignon, MARS-a candidate cipher for AES, Revised, 1999,(9):22.
[5] FISKIRAN A M, LEE R B. Fast parallel table lookups to accelerate symmetric-key cryptography, Proceedings of the International Conference on Information Technology Coding and Computing (ITCC), Embedded Cryptographic Systems Track, 2005,(4):4-6. Las Vegas, Nevada, USA
[6] 彭巍.一种分组密码算法测试平台设计.电子科技大学硕士学位论文,2004,12.