一种面向密码算法的轻量级可重构阵列

张宇帆

（上海交通大学电子信息与电气工程学院，上海200240）

0 引言

密码算法是关乎安全隐私问题的重要算法之一，各个国家都拥有各自独立的密码算法标准，例如：美国所使用的DES/AES[1]对称加密算法、SHA2/SHA3[2]系列散列算法、欧盟所使用IDEA算法、中国所使用的SM4[3]对称算法、SM3散列算法[4]，为各种各样的密码算法设计扩展指令集或专用加速电路是一项高成本的工作。

可重构处理器结合了通用处理器（GPP）的灵活性以及专用集成电路（ASIC）的性能结合到一起，可重构电路在制造之后，可重构的处理阵列的功能可以通过配置信息（即控制运算单元功能的二进制信息）动态地或部分地更改。配置完成后，可重构电路可以像ASIC电路一样，在数据流的驱动下，在阵列中执行多种计算。可重构电路的运算效率要远高于指令驱动的处理器[5]，同时具有远高于ASIC电路的灵活性。

对称密码算法、散列算法这类密码算法，普遍采用多轮迭代的加密方法、每轮迭代采用十分相似的运算步骤、具有类似的粗粒度算子，是一类具有高度确定性的算法。这些显著特性于可重构电路架构高度相符，因此出现了许多针对密码算法的可重构密码加速电路[6,7,8]。现有的可重构密码处理器与现场可编程逻辑门阵列（FPGA）的细粒度配置不同，可重构密码电路主要采用粗粒度的重构数据通路，减少了大量的配置信息，实现配置信息的高速切换。

本文提出了一种面向对称加密和散列算法的动态可重构密码加速器，采用4×4的PE（Processing Unit）阵列结构，阵列结构根据常用对称密码算法和哈希散列函数算法的基本操作和结构设计，由于密码算法之间高度的相似性，该体系架构也可适用于未来的密码算法。为了实现更高的面积效率，本文提出了两点改进方案，为密码算法设计了可重构的存储器阵列，4个存储器可以分别配置为集中式SBOX查找表或存储器，替代了目前主流的PE内嵌查找表算子和寄存器堆的架构设计[8]，大幅提升面积效率。其次设计了配置/常量混合寄存器堆，减少散列运算时的资源冗余提高面积效率。

1 密码算法的主要特征

在称密码算法和哈希散列算法是确保信息安全的重要手段之一，算法的安全性取决于密钥的安全性，对称和哈希算法通常通过轮运算的多次迭代来实现，轮次映射的性能直接影响算法的实现性能，分组和哈希散列运算密码的计算普遍具有以下特点：①轮内运算单向数据流通性，②每一轮运算具有高度相似性，③轮间运算具有依赖关系；同时对称密码算法和哈希算法也具有相同的运算粒度和算子。表1列出了常用的密码算法的基本操作类型和处理粒度。

表1 常用密码算法算子统计

根据对几种常用的密码算法进行统计，我们可以找出一些规律。首先，密码算法的运算操作均为无符号整型运算，没有浮点和定点类型。其次密码算法的基本操作主要为逻辑操作、移位、S盒置换、bit置换、模加/减、有限域乘法。最后密码算法的操作粒度通常普遍在32bit，AES和DES中的S盒置换为8bit细粒度操作。我们可以针对密码算法的这类特性设计能够加速算法的可重构电路，兼顾算法的公共特性，同时提供更高的运算性能。

2 粗粒度可重构密码处理器

2.1 整体架构

可重构密码阵列是一种用于密码数据流运算的架构，是密码算法映射的硬件基础，可重构电路主要包括运算阵列、存储单元、数据I/O和可重构通路四个部分。

图1 粗粒度可重构密码处理器总体架构

本文提出的可重构架构如图1，可重构密码处理器中包含一个4×4的运算单元（PE）阵列、4个独立的存储器（RM），以及带有常量寄存器堆的行间互联模块（RCR）。架构采用分布式配置存储策略，运算单元、可重构存储器、常量寄存器堆都拥有自己的配置存储空间；阵列运算由数据有效令牌进行时序控制与同步，数据的有效令牌由输入输出FIFO生成，有效令牌跟随数据一起流动进入输出FIFO或写入存储器后令牌消失。

4×4的PE阵列可以通过存储器以及行间互联结构的动态配置将各种密码算法映射为包含多级PE单元的流水线结构，图中的虚线箭头则代表额外的跨行互联结构，每一个箭头包含了四个跨行传递的PE输出结果。

2.2 运算单元（Processing Element）

可重构运算单元的设计主要来自于对密码算法的基本操作分析，本文提出的运算单元（PE）为32bit的粗粒度数据位宽，为灵活映射密码算法，设计了五种算子：①逻辑运算单元（LTU）；②模加单元（ADM）；③移位运算单元（SRU）；④置换单元（PU）；⑤伽罗华乘法单元（GM）。每个PE具有4输入2输出的数据通路，两个输出均提供了异或操作算子，根据配置信息进行调整。两个32bit输出路径可以根据配置信息实现1-4级寄存器输出。

图2 PE算子结构

图2（a）为逻辑树运算单元，由6个基本逻辑运算块LU组成一个树形逻辑运算单元，每个基本逻辑块可以实现取反、异或、与、或等基本逻辑功能，逻辑树运算单元可以将哈希算法中复杂的功能运算映射到一个PE中，例如SHA256中的Maj函数：

图2（b）模加运算单元由两级32bit加法器组成，根据配置信息进行两操作数加法或三操作数加法，支持模32/16/8和模231-1。图2（c）为移位运算单元，由六个移位器组成，针对散列算法的Gama函数进行了特定优化，可以大幅减少哈希算法所需要的PE个数，支持复杂的多输入循环移位操作映射：

图2（d）为bit级置换运算单元，通过配置Bense网络实现64bit间任意bit互换，主要为DES算法以及类似算法中的P盒置换而设计。图2（e）为伽罗华域多项式乘法运算单元，Mul模块中的伽罗华乘法器为8bit细粒度运算。

本文利用TSMC 28nm工艺库进行逻辑综合功耗面积评估，时钟约束为1GHz。

表2 PE算子综合结果

置换单元的大小大于其他单元的面积总和，置换运算单元和伽罗华乘法运算单元全部都用于对称密码算法，因此将置换运算单元和伽罗华乘法运算单元采用异构PE的方式排布，第一行和第四行采用带有置换运算单元、逻辑树运算单元、模加运算单元和移位运算单元的PE，第二行和第三行则采用带有伽罗华乘法运算单元、逻辑树运算单元、模加运算单元、移位运算单元的PE。异构PE的阵列方式可以为我们节省约27.9%的PE阵列面积。

PE单元采用寄存器输入输出，输入数据改变后数据会广播到每个PE的4个算子，未被选中的3个算子会产生不期望的翻转功耗；引入操作数隔离的优化方案在单个PE上实现了34.4%的功耗优化。

2.3 可重构行互联（Reconfigurable Connect Row）

可重构互联模块决定了可重构处理器效率和灵活性，本文提出的可重构行互联网络RCR针对密码算法的数据单向流通性进行设计，同时行互联模块还负责接收存储器、常量寄存器堆以及输入输出FIFO的数据来源。行互联RCR模块采用Crossbar结构，可以分为四个部分。

图3展示了一个PE的一个输入源的RCR互联结构，图中的一个箭头表示一个32bit的数据来源。PE_ROW_OUT模块，接收上一行4个PE的八个输出，对于第一行PE则接收四个输入FIFO和四个输出FIFO的数据来源。LATCH/MEM模块采用异构的功能设计，PE的4个输入所对应的该模块采集不同的输入源，PE的两个输入口通过该模块接收存储器的4个输出，另外两个输入则接收常量寄存器堆的4个输出。Y_IN模块负责接收跨行传输的数据，第一行的4个RCR接收的是第三行PE的跨行数据，第二行的4个RCR则是接收最后一行PE的跨行数据，第三行的4个RCR则是接收输入FIFO的数据源，第四行的4个RCR接收第二行的PE的跨行数据。最后的16个数据源通过一个16选1的选择器根据配置信息进行筛选，将结果传输给对应的PE输入端口。

图3 RCR互联结构

2.4 可重构存储器（Reconfigurable Memory）

本文的可重构密码加速器拥有4组32bit位宽256深度的可重构存储器，存储器由16个8bit伪双口DRAM组成，支持同时读写，读写流水化。本文的可重构存储器都有用单独的读通道和写通道配置信息控制器，写通道的地址由配置信息生成，通过配置单元进行计算；读通道的存储器访问地址可以通过配置信息生成，也可以来源于PE阵列的PE输出。为了减少互联资源开销，PE阵列到存储器的互联网络进行了优化设计。

图4下方为可重构存储器与PE阵列的写数据通道，R1~R3代表每一列PE的8个输出数据，根据配置信息每列选取一个数据送入下级互联，第二级D4由4个地址译码器和四个写通道组成通过配置信息内含的地址信息和将每一列与存储器交互的PE输出数据写入对应的存储器之中，每一个通道均可以写入到任意一个存储器的任意一个地址，第一列PE具有最高优先级。

图4 可重构存储器

图4上方为可重构存储器和PE阵列的读数据通道，箭头0代表PE的第0列和第1列的16个输出，箭头1代表PE的第2列和第3列的16个输出。根据配置信息由4个16选1的选择器选出4个数据送入到第二级互联模块。第二级包含4个地址译码器和一个可旁路的128bit Bense互换网络，可以根据配置信息将任意一个MEM配置为查找表模式，查找表模式的读通道会将PE数据通过Bense互换网络送入MEM中，可以实现16个8bit的并行查表，方便映射对称算法中的非线性代换操作。

读操作产生的数据会通过一个可旁路的Bense网络转换后广播到每行RCR的副本寄存器中，为RCR提供存储器数据来源。

2.5 可重构配置、常量锁存器堆

PE单元内含的Bense 64bit置换单元，需要352bit配置信息进行控制，而本文设计的其他功能单元，只需要32bit就可以实现重构配置；算法映射时，一部分算法并不需要Bense置换网络这一个硬件资源，因此本文将Bense置换网络的配置存储空间进行了重新设计。为减少动态切换的大位宽数据开销，将Bense配置信息和密码算法运算需要的常量通过静态配置的方式存储到常量存储器堆中。

静态配置在整个阵列运算的时候一般处于保持状态，所以将配置信息用锁存器存储，可以实现45%的面积优化。锁存器堆会存储四组Bense网络信息，PE被映射为置换操作时，会根据配置信息的2bit索引选取对应的配置信息。常量锁存器堆还有四个位宽均为32bit的只读端口，每一个端口读出对应16个锁存器中的一个数据。锁存器堆的四个读数据端口广播到RCR模块中，作为PE单元的次要输入源之一。

3 架构实现及性能分析

使用Verilog语言实现本文提出的粗粒度可重构密码处理器架构，使用Cadence Genus工具基于TSMC28nm工艺库进行逻辑综合；配置信息通过手动编程实现对应的算法功能。

表3 芯片参数以及性能

本文所提出的架构对于AES-ECB模式的非反馈加密算法能够实现12Gbps的加密速率，SM4由于需要更多的迭代轮所以性能低于AES；对于带有反馈的哈希散列函数仍能维持较高的性能水平。

该架构使用轻量级的设计策略，采用4×4的PE阵列规模，在执行AES-ECB算法时，拥有略强于Anole的面积效率；由于对一些哈希算法的复杂操作进行了优化设计，SHA256算法的面积效率远高于同类型的可重构阵列。

表4 性能对比

图5 归一化面积效率比较

图5为归一化后的面积效率柱状图，柱形代表AES算法的面积效率，对应为左边的坐标轴，本文提出的架构对比128个PE阵列的Anole架构实现了10%的效率提升；折线代表SHA256算法对应的面积效率，可以看到本文的架构对比160个PE阵列的Cryptor架构面积效率提升了180%，实现2.8倍的面积效率。

4 结语

本文提出了一种面向对称和哈希散列算法的轻量级粗粒度可重构阵列，通过软硬件协同设计对硬件结构进行针对性优化，相比以往的大规模可重构密码阵列具有更高的面积效率，同时还保证了较高的算法性能，适用于一些的嵌入式领域。