可重构S盒运算单元的设计与实现
2008-03-19
作者：孟 涛， 戴紫彬
摘 要： 在分析多种对称密码算法" title="密码算法">密码算法的基础上，总结出常用的S盒运算模式，设计并实现了高效、灵活、安全的可重构" title="可重构">可重构S盒运算单元，并且给出了此单元通用的指令格式。
关键词： 密码算法 可重构 S盒 LUT
在信息安全技术飞速发展的今天,密码算法的使用范围越来越广泛。对称密码算法在密码算法应用中占有非常重要的位置,它可以用于构造伪随机数产生器、流密码、认证码和Hash函数等,也可以作为消息或实体认证、数据完整性和数字签名等方案的核心部分。在各种各样安全技术需求的促使下,可重构密码芯片已成为当今研究的一个方向。目前,可重构技术的研究已经非常广泛,在不同领域有着不同的研究层次。按照可重构处理单元的规模可划分细粒度可重构和粗粒度可重构。细粒度可重构是指以位为可重构的基本单元,例如: 现场可编程门阵列(FPGA);粗粒度可重构是指以能单独完成某些功能的单元为基本单元,例如:应用于特定领域的可重构系统MATRIX[1]。本文所设计的可重构S盒运算单元RSU(Reconfigurable Sbox Unit)即为粗粒度的可重构单元。可重构密码运算单元是可重构密码系统的重要组成部分,RSU就是其中一种密码运算单元。S盒运算单元灵活、高效的设计与实现,将会使一个芯片内集成更多的密码算法。针对这一问题,本文对S盒运算的特性进行了研究与分析,提出了一种能支持4-4、6-4、8-8、8-32四种运算模式的RSU。对于4-4模式,RSU一次可以配置16 个配置页CP(Configurable Pages);对于6-4模式,RSU一次可以配置4 CP;对于8-8模式,RSU一次可以配置2 CP;对于8-32模式,RSU一次可以配置2 CPs。如此高效、灵活的RSU设计方案,为可重构密码系统的设计与实现提供了基础。
1 S盒的应用及其实现方式的分析
1.1 对称密码算法中的S盒
在对称密码算法中,S盒运算单元的使用频率非常高。但在不同的算法中,S盒的使用方式各不相同。下面给出常用的20种对称密码算法中S盒运算模式的使用情况,如表1所示。
可重构S盒运算单元的设计主要是为了满足不同算法的要求,通过一致的接口和不同的控制信号" title="控制信号">控制信号,共同使用一个模块,完成不同模式的S盒运算。分析以上密码算法可知,常用的S盒运算有4-4、6-4、8-8、8-32四种运算模式,所以本文提出的RSU至少要支持这四种运算模式的操作。
1.2 S盒实现方式的分析
目前,常用的S盒的实现方法" title="实现方法">实现方法有两种:基于逻辑电路的实现方法和基于查找表(LUT)的实现方法。
(1)基于逻辑电路的实现方法
S盒字节变换的映射关系通常是由某个算法指定的,而这个特定的算法是用逻辑电路实现的,从而得到S盒的运算结果。例如:在MARS密码算法中,S盒映射关系由SHA-1摘要算法指定[3],而SHA-1摘要算法用逻辑电路实现,将S盒源操作数按要求输入SHA-1电路,那么SHA-1电路的运算结果便可作为S盒的结果输出。这种方法的好处在于使用的资源较少,但运算速度" title="运算速度">运算速度慢,会成为整个芯片的瓶颈。最主要的是,一个固定的电路只能完成一种运算,不具有可配置性,攻击手段较易成功,芯片本身的安全性较低。
(2)基于LUT的实现方法
设计者按照S盒字节变换的映射关系,将所有可能的结果(一般地,算法设计者会给出相应的数据向量表)放在一个存储器(RAM、ROM或是寄存器堆)内,当进行S盒运算时,将操作数作为查找地址,直接对存储单元进行查找,查找的结果作为S盒运算结果输出。基于LUT的实现方法如图1所示。
这种方法占用了较多的存储单元,但运算速度非常快,路径上的延迟只有寄存器或存储器的输出延迟。最主要的是它具有可配置性和较高的灵活性,能满足当前多种密码运算的需要,并且当芯片不进行配置时它本身不带有任何的算法信息,使得芯片本身更具有安全性。RSU的设计就是基于LUT方式,并加入了可重构的设计思想,使得RSU具有更高的灵活性和安全性。
2 RSU的设计
2.1 RSU电路的设计
为了使RSU能够配置不同S盒的LUT,本设计选择了可重写的RAM作为存储器,它可以动态地、重复地配置LUT;为使RAM的读地址和查找结果的映射关系为可重构的,以满足常用S盒输入位宽的大小,可重构的控制节点参加RAM读写地址的译码,控制RAM的读写模式,实现常用的4bit、6bit、8bit几种位宽。以上几种LUT模式的输入位宽最大为8bit,所以 RAM的深度至少为256。常用S盒输出位宽最宽为32bit,所以RAM的输出位宽至少为32bit。对于程序员来说,一种算法最好只需要进行一次配置,而MARS密码算法的S盒有两组256×32bit的LUT数据,所以RAM块最小应为512×32bit,但为了减小输出的路径延迟,选择以256×64bit的形式来实现,在物理上RSU是以8块256×8bit的RAM块来实现的,RSU整体电路结构如图2所示。
RSU_Datain为RSU的数据输入端口,RSU_CP为页面选择信号,RSU_mode为模式选择信号,RSU_ren为RAM块的读使能,RSU_clk为系统时钟,RSU_conf_wen为RSU的配置使能信号,RSU_conf_addr为RSU的配置地址输入。RSU的内部主要由四个RAM组构成,RAM组1的电路如图3所示。
RAM组1分为两个256×8bit的RAM块。信号RSU_G1_operater_H、RSU_G1_operater_L、RSU_G1_conf_address、RSU_G1_sel1、RSU_G1_sel2是由原驱动信号RSU_Datain、RSU_conf_addr在可重构控制节点RSU_mode、RSU_CP控制下生成的,作为控制信号和源操作数参加RAM组1的配置和运算操作。
当RSU_conf_wen有效时,RSU执行配置操作;当RSU_ren有效时,RSU进行运算操作。RSU_mode信号分别为00、01、10、11时,RSU分别完成8-8、8-32、4-4、6-4四种模式的配置和运算操作。RSU_CP为0000~1111时,分别对第0~15个配置页面进行读或写。在以上的可重构节点的控制下,RSU就可以完成相应的配置和运算操作,并且最优化地利用了资源:对于配置操作,在4-4模式下,本运算单元一次可以配置16CP;在6-4模式下,本单元一次可以配置8CP;在8-8模式下,本单元一次可以配置2CP;在8-32模式下,本单元一次可以配置2CP。对于运算法操作,配置完成后,在运算时由RS_CP指定相应的CP参加运算,在4-4模式下,一个执行时钟内可以完成8组运算;在6-4模式下,一个执行时钟内可以完成4组运算;在8-8模式下,一个执行时钟内可以完成4组运算;在8-32模式下,一个执行时钟内可以完成1组运算。
2.2 RSU指令的设计
将RSU应用到处理器中需要有相应的指令启动不同模式的配置和运算操作。下面根据RSU所支持的多CP配置和所支持的不同模式的运算操作,给出配置和运算的指令格式及编码格式。指令助记符的格式如下:
配置指令格式:CSB.nTm.CP RD RS
运算指令格式:ESB. nTm.CP RD RS
CSB表示执行配置操作,ESB表示执行运算操作,nTm表示模式选择,CP表示CP选择,RD为目的操作数,RS为源操作数,n的取值范围为4、6、8,m的取值范围为4、8、32,CP的取值范围为1~16。举例说明如下:
CSB.4T4.2 RD RS 表示在模式4-4,将源操作数RS作为配置数据配置到地址为RD的RAM单元中。
ESB. 4T4.2 RD RS 表示在模式4-4,将RS作为源操作数进行S盒运算,结果放在地址为RD的RAM单元中。
由以上可知,指令机器码中的控制信息至少要包括操作选择、模式选择和CP选择字段;对于操作数,在不同处理器中有不同的目的及源操作数寄存器的地址位数。图4给出控制字段所对应的机器码格式。
指令中相应字段编码如表2所示。
在4-4模式下,CP选择字段的取值范围为0000~1111;在6-4模式下,CP选择字段的取值范围为0000~0011;在8-8模式下,CP选择字段的取值范围为0000~0011;在8-32模式下,CP选择字段的取值范围为0000~0001。指令译码可以获得可重构节点的控制信号,RSU在这些控制信号的控制下执行配置或运算操作。
3 RSU的性能测试
以上设计采用verilog语言描述,在QuartusII 5.0环境下编译综合,选用Altera StratixII系列器件作为目标器件进行整体综合、仿真和底层布局。对多组数据进行测试仿真,均得到正确结果。
该模块的运算速度可以通过以下公式得出:
运算速度＝每个时钟运算数据的长度×系统频率
将实现的可重构S盒运算单元下载到Altera StratixII系列器件EP2S15F484C3后,测得的主要性能指标如表3所示。
本文提出的支持4-4、6-4、8-8、8-32四种运算模式的可重构的S盒运算单元,在执行配置操作时,对于4-4模式,可以一次配置16CP;对于6-4模式,可以一次配置8CP;对于8-8模式,可以一次配置2CP;对于8-32模式,可以一次配置2CP。在执行运算操作时,在一个运算时钟周期内可以完成8组4-4的运算,或者4组6-4的运算,或者4组8-8的运算,或者1组8-32的运算,并且当芯片不进行配置时它本身不带有任何特定算法的信息,满足了密码芯片设计所需的安全性。经过在FPGA上的验证,其运行结果正确,且运算速度较快,由于工艺的不同,当采用ASIC实现时,其性能还将在此基础上明显提高,从而能够满足实现多种密码算法的密码芯片的需求,为可重构密码芯片提供了新的支持。
参考文献
[1] Altera Corporation.Stratix II Device Handbook[M]. available at http://www.Altera.com.
[2] 嵩天，汤志忠，汪东升.可重构计算相关研究综述[G]. 2004年全国博士生学术论坛论文集,2004.
[3] 高娜娜，王沁，李占才.基于AES和DES算法的可重构S盒硬件实现[J].小型微型计算机系统，2006,(3):446－449.
[4] IBM Corporation Carolynn Burwick Don Coppersmith Edward D’Avignon Rosario Gennaro Shai Halevi Charanjit Jutla StephenM. Matyas Jr. Luke O’Connor Mohammad Peyravian David Safford Nevenko Zunic, MARS-a candidate cipher for AES, Revised, September, 22, 1999
[5] ELBIRT A J. Reconfigurable computing for symmetric-key algorithms[D]. PhD thesis, Electrical and Computer Engineering Department University of Massachusetts Lowell, April 22, 2002.
[6] SINGH H, LEE M H, LU G, et al.An integrated recon-figurable system for data-parallel and computation-intensive applications[J]. IEEE transactuions on computers,2000,49(5)465-481.