一种基于Hierarchy LUT 的可重构S-box 实现方法

方 震，赵 伟，刘 勇

（中国电子科技集团公司第五十八研究所，江苏 无锡 214035）

0 引言

通信领域中，高吞吐量的加密和解密技术一直是研究的重点。分组密码算法在高速、海量数据加密解密应用中广泛使用。为使分组密码达到高的性能，通常采用硬件加速。专用集成电路（ASIC）虽然性能高，但是在算法切换、参数可变的应用中缺乏灵活性。可重构架构技术则可在一定程度上弥补短板，平衡高性能和灵活性，有利于分组密码算法硬件加速应用，进而通过优化分组密码算法实现。分组密码算法主要包括逻辑运算、算数运算[1]、置换处理[2]、字节替换（S-box）[2-3]。S-box作为分组密码算法的非线性处理单元，在分组密码算法中发挥着重要的作用。一般而言，不同的分组密码算法，S-box 的结构都有所不同，这也是分组密码算法的瓶颈所在。因而S-box 的性能和面积的优化成为了分组密码算法主要研究目标。

S-box 的构建方法通常有两种：一是基于逻辑结构的构建方法，二是基于查找表结构的方法。第一种方法主要基于真值表生成或基于生成规则的逻辑运算。例如 Product of Sums(POS)[4]、Positive Polarity Reed-Muller form(PPRM)[5]、Binary Decision Diagram(BDD)[6]采用两级逻辑实现，或者采用GF(28)、GF((24)2[7]或者GF(((22)2)2)[8]有限域运算逻辑实现。虽然逻辑构建实现占用资源较少，但缺乏灵活性，不能适配不同的S-box 结构。此外S-box 综合时会产生很大的累积资源占用。第二种方法基于查找表。通常将存储单元用于Look Up Table(LUT)，存储字节替换表。由于存储单元中的字节替换表可以很方便地更新，这种方法被广泛应用于分组密码的可重构实现[2-3,9-10]。相比与基于逻辑的方法，其缺点是需要占用更多的硬件资源，特别是在支持几种不同的S-box 操作时[3]。为了减少面积的资源消耗，文献[2]提出由多个子系统组成存储系统，谋求性能和资源的平衡，实用效果有限。

基于上述问题，本文提出了一种4R/1W 存储结构，并基于此存储单元构建分层查找表（Hierarchy LUT），以节省资源消耗，提高面积利用效率。

1 可重构S-box 存储单元改进

在基于查找表的实现中，S-box 的数据信息存储在一个基本的存储单元中。这些存储单元的数量会随着输入输出位宽、并行端口数量的增加而急剧增大。因此需要分析影响存储单元开销的因素。

例如，一个经典的分组密码算法Advanced Encryp‐tion Standard(AES)，每轮需要16 个相同的S-box，传统的S-box 查找表的实现如图1 所示，16 个RAM 存储块用来存储相同的查找表信息，每个RAM 块都有独立的读写端口。因为每个RAM 块存储的信息都一样，可以共用输入端口，将其换成图2 所示的结构，用触发器来存储查找表信息。这些触发器存储结构共用一个输入端口，而输出端口则通过多路选择器选择输出。

图1 重复RAM 块存储查找表

图2 寄存器储存查找表

基于此思路，本文提出一个定制的4R/1W(4 个读端口，1 个写端口)存储单元，用来减少整体存储的面积开销。如图3 所示，该电路基于6 管SRAM 结构，包括1 对写信号线（WBL 和WBLB）以及4 个单端的读信号线（RBL_1、RBL_2、RBL_3、RBL_4）。每个读信号线都由两个NMOS 组成，以M7 和M8 组成的读端口为例，M7的漏极连接M8 的源极，M8 的漏极接到读信号端口。其他三个读端口结构相同。这种存储结构可以同时接收4路彼此独立的读信号，获取4 个地址的数据，而无需额外例化3 个存储单元，因而有很高的存储密度。

图3 4R/1W 存储单元结构

用来存储S-box 的RAM 存储单元所占用的面积占据总面积的相当大的比重。以AES 算法为例，尽管IP vendors提供的RAM 存储器经过优化，占用很少的资源，但在AES算法中需要16 个RAM 单元存储S-box，这些累计存储单元面积开销则不容忽略，如图4 所示。通过主从触发器搭建的存储的结构虽然能够减少重复的存储面积的占用，但是其输出端口中的选择器占用的资源却很大。而采用本文提出的4R/1W 结构的存储器则占用很小的资源开销。

图4 各类存储在电路中面积开销

2 可重构S-box 查找表改进

S-box 有四个主要的特性，分别为输入位宽、输出位宽、S-box 的数量和每轮并行端口数量。不同的S-box 结构，四个特性有着较大的差异。为便于表述，在本文中定义了AW、DW、N、m四个参数：AW 为地址最大位宽，DW 为数据最大位宽，N为最大的S-box 数量，m为最大并行端口数量。表1 展示了几个常用的分组密码加密算法，其中RU 参数表征加解密处理的性能[2]。分组密码算法的S-box 结构不一样，其对应的一些参数也各不相同。

表1 不同算法中S-box 性能及特性表

当AW、DW、N和m四个参数变化时，分组密码算法的面积开销大有不同。如果只有一个读端口，则会大大增加面积的开销。为尽可能减小面积的开销，适当增大可读的端口数量、AW 和DW。但要注意，因为读写控制逻辑会占用一定的资源，过多的读写端口同样会引起面积开销增大。

基于上节提出的4R/1W 存储单元，本节提出一个分层查找表Hierarchy LUT，如图5 所示。Hierarchy LUT包括4 个32 端口存储器以及输入输出控制逻辑。其中32 端口的存储器由8 个4R/1W 存储单元组成，它们共用一个写数据线。

图5 分层查找表结构

Hierarchy LUT 可以根据S-box 的结构来配置重构输入输出位宽，进而重构电路。根据输入输出的位宽，可以提供6 种不同的查找表模式，如图6 所示。

图6 可重构S-box 查找表模式

Mode1：工作于4 个256×8 的多端口模式。

Mode2：工作于2 个256×16 的多端口模式。

Mode3：工作于1 个512×16 的多端口模式。

Mode4：工作于1 个256×32 的多端口模式。

Mode5：工作于1 个1024×8 的多端口模式。

Mode6：工作于2 个512×8 的多端口模式。

3 对比实现

本文在40 nm CMOS 工艺下，通过Synopsys IC com‐piler 工具进行综合，实现Hierarchy LUT 构造可重构Sbox，结果如表2 所示，面积利用率为1.724。与之对比的是基于Table Lookup Unit(TLU)[2]和Memory Sharing[3]的可重构S-box 结构。

表2 S-box 面积利用率对比表

基于TLU 结构的S-box 是可重构加解密处理器的一个主要部分。为了提供并行的数据端口，TLU 结构提供比较大的输入输出位宽，存储深度达1 024，其基本结构是由单端口的存储单元组成的。本文提出的基于Hier‐archy LUT 结构的S-box，减少了存储器的冗余，具有较高的存储密度，与TLU 结构相比，面积利用效率从1.136提高到1.724，性能提升51.76%。

基于Memory Sharing[3]触发器结构的可重构S-box，适用于AES、DES 及Serpent 的算法。该结构有16 个端口，其占用的面积很小，但是此结构不够灵活，且并行度不高，最大输入输出位宽为8 位，而且在数量多的端口情况下，因其端口数据选择器控制占用较多的资源，面积会迅速增大。与之相比，本文提出的基于Hierarchy LUT 结构的S-box，面积利用效率从1.613 提高到1.724，性能提升6.88%。

4 结论

本文提出了一种4R/1W 存储结构，构建一种分层的查找表结构（Hierarch LUT），在40 nm CMOS 工艺下，实现了可重构S-box 设计。与Table Lookup Unit (TLU)和Memory Sharing 触发器的可重构方案提出的结构相比，本文基于Hierarchy LUT 结构的可重构S-box 面积利用率得到有效改善，利用效率分别提高51.76% 和6.88%。