两类非线性密码组件可重构研究与电路设计

引用本文

连宜新, 陈韬, 李伟, 等. 两类非线性密码组件可重构研究与电路设计[J]. 计算机工程, 2022, 48(2), 156-163, 172. DOI: 10.19678/j.issn.1000-3428.0060722.

LIAN Yixin, CHEN Tao, LI Wei, et al. Reconfigurable Research and Circuit Design of Two Types of Nonlinear Cryptographic Components[J]. Computer Engineering, 2022, 48(2), 156-163, 172. DOI: 10.19678/j.issn.1000-3428.0060722.

基金项目

国防创新基金（2019_JCJQ_JJ_123）

作者简介

连宜新(1996-), 男, 硕士研究生, 主研方向为信息安全、处理器体系结构、集成电路设计;
陈韬, 副教授;
李伟, 副教授;
南龙梅, 副教授

文章历史

收稿日期：2021-01-27
修回日期：2021-03-16

Contents Abstract Full text Figures/Tables PDF

两类非线性密码组件可重构研究与电路设计

连宜新 , 陈韬 , 李伟 , 南龙梅

战略支援部队信息工程大学密码工程学院, 郑州 450001

收稿日期：2021-01-27；修回日期：2021-03-16

基金项目：国防创新基金（2019_JCJQ_JJ_123）

作者简介：连宜新(1996-), 男, 硕士研究生, 主研方向为信息安全、处理器体系结构、集成电路设计; 陈韬, 副教授; 李伟, 副教授; 南龙梅, 副教授.

E-mail: 3180397475@qq.com

摘要：为解决对称密码中s盒和非线性布尔函数（NBF）在实现密码专用处理器时采用异构化设计导致的资源浪费问题，提出一种类AESs盒和NBF的可重构电路结构方法。分析s盒问题中的原有非线性布尔函数模块（NBFM），4-4、6-4的s盒电路能够提供更好的适配性，但不能很好地支持8-8的s盒电路。基于塔域分解理论，论证不同的类AESs盒电路差异在于输入前后的转换矩阵。采用混合基的方法将类AESs盒电路分解成GF（16）上的各个运算模块，并推导出模块比特级别表达式，在具体适配运算模块时采取门级实现、NBFM适配实现或对NBFM进行改进3种方案，实现类AESs盒和NBF的可重构电路。实验结果表明，该方法在不影响原有NBF功能的基础上，利用4个NBFM与22.7%的s盒电路面积即可实现一个完整的类AESs盒电路。

Reconfigurable Research and Circuit Design of Two Types of Nonlinear Cryptographic Components

LIAN Yixin , CHEN Tao , LI Wei , NAN Longmei

School of Cryptographic Engineering, Strategic Support Force Information Engineering University, Zhengzhou 450001, China

Abstract: During the implementation of a cryptographic processor, considerable resources are wasted because of the isomerization of the S box and the Non-linear Boolean Function(NBF) in its symmetric cipher.A reconfigurable circuit structure of an AES-like S box and NBF is proposed to address this problem.The original Non-linear Boolean Function Module (NBFM) in S-box problems is analyzed.The 4-4, 6-4 S-box circuits provide better adaptation but cannot support 8-8 S-box circuits.Based on the tower domain decomposition theory, this paper demonstrates that AES-like S box circuits differ only in terms of the conversion matrix before and after the decomposition.Using the mixed basis method, an AES-like S box circuit is decomposed into various operation modules on GF(16), and the bit level expression of these modules is derived.When adapting these modules specifically, the gate level implementation, NBFM adaptation implementation, or an appropriate improvement of the NBFM implementation are adopted.Finally, a reconfigurable circuit similar to the AES-like S box and NBF is realized.Experimental results show that a complete AES-like S box circuit can be realized by this method using four NBFMs and 22.7% of the S box circuit area without affecting the function of the original NBF.

开放科学（资源服务）标志码（OSID）：

0 概述

对称密码在网络和通信领域应用广泛，其按照加密方式的不同可进一步分为序列密码算法和分组密码算法^[1]。在基于比特级操作^[2]的序列密码算法中，非线性布尔函数成为其核心部件，在乱源更新和乱数生成过程中都参与运算，而s盒是分组密码唯一的非线性部件，为算法提供了非线性性和安全性，两者本质上都是非线性布尔函数，但在密码芯片实际处理中却存在不同的实现方式。在s盒实现方面，由于s盒构造方式的不同，国内外研究分为通用和专用s盒的实现加速，在通用领域^[3-5]均采用时序部件8-8的RAM搭建可重构运算单元，可不同程度地并行实现常规类型的s盒，区别在于文献[5]在电路的基础上增加了旁系电路，通过门控技术降低了s盒功耗。而文献[6]将s盒作为非线性布尔函数，利用与或阵列的形式搭建可重构s盒电路。在专用领域，s盒的实现主要针对基于塔域求逆和仿射变换设计s盒的算法，如AES、Camellia、SMS4等。文献[7-8]根据有限域上域的扩张理论，采用组合逻辑的方式优化单算法AESs盒。文献[9]提出的复合域求逆运算模型针对有限域求逆的s盒，其本质上仍然是域的扩张理论，文献[10]将AES、Camellia、SMS4等s盒电路采用GF（16）上的运算搭建进而重构，其核心的求逆电路相同，区别只是在于求逆电路输入前和输出后的转换矩阵。在针对序列密码的非线性布尔函数（NBF）实现方面，单算法设计如文献[11]采取直接实现的方法，而面向密码处理的NBF设计结构具有通用性，其可重构设计借鉴了FPGA思想。文献[12-14]在统计序列密码NBF运算特征，即参与运算变量个数与项次数基础上采用LUT搭建实现，其结构的区别在于LUT选取的粒度和规模不同。

但以上设计均只是从某种或者某类算法的角度出发，并未将对称密码非线性运算模块统一，实际上两者本质上并无区别，这样的异构化设计必然存在资源浪费的问题。此外由于s盒一般采用并行化处理，这使得s盒成为密码处理器中资源消耗最大的模块，如何降低对称密码非线性运算面积开销是急需解决的问题，因此可以采取一种统一的结构实现以降低硬件开销。

本文设计一种s盒非线性布尔函数模块（Sbox_Non-linear Boolean Function Module，SNBFM）架构，在MBFM架构的基础上融合部分类型的s盒，并结合有限域理论，对其中能够优化的类AESs盒进行适配，使其对类AES的s盒支持力度更高。

1 可重构分析 1.1 两类非线性密码组件操作特征分析

在对称密码中，s盒和非线性布尔函数都是作为异构的模块单独实现，其中NBF在序列密码的编码环节^[15]，即乱源更新，在乱数生成的过程中均参与运算，其通用表达式包含1，2，…，n次常数项，公式如下所示：

$ \begin{array}{l}f\left(x\right)={c}_{0}+{c}_{1}{x}_{1}+\cdots +{c}_{n}{x}_{n}+\\ {\begin{array}{cc}& \end{array}}_{}{}_{}{c}_{12}{x}_{1}{x}_{2}+\cdots +{{c}_{1}}_{, 2, \cdots , n}{x}_{1}\cdots {x}_{n}\end{array} $

通过统计NESSIE计划、CRYPTREC计划和ESTREAM计划，征集序列密码算法NBF操作特征，即对其状态序列长度、参与运算变量个数、项个数和次数进行分析，如表 1所示，发现虽然位宽为12$ ~ $256 bit，参与运算的变量个数可能很多，约为12$ ~ $128个，但与项次数多数不超过6次，因此相应的NBF结构均是能实现最高次数为6的变量结构^[12-14]。

下载CSV 表 1 NBF操作特征 Table 1 NBF operational characteristics

s盒设计方法主要包括随机选取测试和利用数学方法产生2种^[16]，并且需要满足一定的设计准则，而硬件设计人员在s盒实现上关注的是s盒的操作特征，即输入和输出变量数。本文对AES计划、NESSIE计划以及其他商用分组密码算法的s盒进行特征分析，发现s盒的种类大多集中在4-4、6-4、8-4、8-8、8-32上，同时s盒具有一定的并行性。

1.2 NBFM结构实现能力分析

在文献[13]所列出的4种NBFM结构中，其中的一种共享2输入NBFM结构如图 1所示，NBFM是一个10入4出的结构，这类含共享变量的结构充分考虑了NBFM操作特征，减少了端口数目，易于在处理器中集成，整体结构可以分为LUT存储和NBFM组合逻辑两部分。适配8-8 s盒的NBFM如图 2所示。NBFM实现能力如表 2所示，其中输出端用0、1、2、3代替。将s盒映射到NBFM是将s盒输出的每一路都看作输入的非线性布尔函数，然后根据输入变量的多少确定NBFM变量模式，可以看到，NBFM对于4输入、5输入、6输入的s盒能够分别支持4路、2路和1路输出，较好地支持了4-4、6-4类型的s盒。但由于NBFM缺少8变量模式，因此只能通过级联实现8变量NBFM，图 2所示为8-8 s盒输出任意一路在NBFM中的适配，而各类s盒在NBFM中适配资源消耗如表 3所示。

	Download: JPG larger image
图 1 NBFM结构 Fig. 1 NBFM structure

	Download: JPG larger image
图 2 适配8-8 s盒的NBFM Fig. 2 NBFM of adaptation 8-8 s box

下载CSV 表 2 NBFM实现能力 Table 2 NBFM Realization ability

下载CSV 表 3 不同类型s盒资源消耗 Table 3 Resource consumption of different types of s box

从表 3可以看出，NBFM在实现4-4和6-4的s盒上消耗资源较少，而在实现8输入变量的s盒上时需要多个NBFM级联才能实现1路输出。NBFM实现一个8-8的s盒与8-8的RAM如表 4所示。可以看出，NBFM在实现8-8 s盒上效率很低，性能指标也并不如RAM实现，但通过对8-8的s盒进行进一步细分发现，8-8的s盒中存在求逆和仿射变换构造的类AESs盒，这类s盒可通过组合逻辑的方法化简输出的NBF表达式，从而易于NBFM适配。

下载CSV 表 4 8-8的s盒适配资源评估 Table 4 8-8 s box adaptation resource evaluation

2 类AESs盒和非线性布尔函数可重构研究 2.1 类AESs盒可降解理论分析

在对文献[7-8]进行分析后发现，类AES的s盒存在2种分解形式：GF（4²）²和GF（（2²）²）²。2种分解形式区别在于基本模块规模的不同，而适合NBFM这种2输入LUT类型实现的是GF（（2²）²）²，因此本文将根据混合基方法^[17]推导s盒分解后的不同模块表达式。

文献[17]采用混合基实现AESs盒的塔域分解，具体采用的基和不可约多项式如表 5所示，其中，$ \alpha $是$ e\left(x\right)=0 $的一个根，$ \beta $是$ f\left(x\right)=0 $的一个根，$ \gamma $是$ g\left(x\right)=0 $的一个根。为方便计算，记$ \lambda $=$ {\alpha }^{2}\beta $。塔域分解后的AESs盒电路如图 3所示，可以看到s盒的求逆部分由S₄、M₄、$ {\widehat{M}}_{4} $、$ \widehat{\lambda } $乘和求逆$ {\widehat{I}}_{4} $等5类模块组成，$ \boldsymbol{\delta } $、$ A{\boldsymbol{\delta }}^{-1}+\boldsymbol{C} $是复合仿射变换后的同构映射矩阵，规模为8行8列，负责对求逆的输入和输出进行转换。与文献[17]s盒采用GF（16）上的模块用GF（4）模块组合实现、GF（4）上模块再用GF（2）上的运算组合实现的两级模块化设计方法不同，由于各个模块具体适配到NBFM上时，适配的对象LUT_n表示一个n输入的NBF，最终的适配对象应该是一个个的NBF，因此只能推导出各个模块的NBF表达式，而文献[17]的两级模块搭建方法无法深入比特级表达式，因此无法适配各个模块。下文将依次推导出求逆所包含的5个模块的布尔表达式。

下载CSV 表 5 不可约多项式和基的选取 Table 5 Selection of irreducible polynomials and bases

	Download: JPG larger image
图 3 塔域分解后的AES s盒电路 Fig. 3 AES s box circuit after tower domain decomposition

s盒的求逆部分包含平方S₄、乘法M₄、乘法$ {\widehat{M}}_{4} $、常数乘法$ \widehat{\lambda } $乘、求逆$ {\widehat{I}}_{4} $等5类模块，涉及到的运算均在GF（16）上，其中S₄、M₄以多项式基输入和输出，$ {\widehat{M}}_{4} $、$ \widehat{\lambda } $乘和$ {\widehat{I}}_{4} $以多项式基输入、正规基输出。设GF（16）上元素A、B用多项式基表示：$ A={a}_{0}\oplus {a}_{1}\beta $，$ B={b}_{0}\oplus {b}_{1}\beta $，a₀b₀是低2位，a₁b₁是高2位，$ {a}_{0}{b}_{0}{a}_{1}{b}_{1}\in $ $ (\mathrm{0, 1}, \mathrm{2, 3}) $。

S₄、M₄、$ {\widehat{M}}_{4} $、$ \widehat{\lambda } $乘和求逆$ {\widehat{I}}_{4} $结果用A²、AB、AB_ptn、$ \lambda $A、$ {A}^{-1} $表示，则可得式（1）~式（5）。由于最后要推导出各个模块的布尔表达式，而$ {a}_{0}{b}_{0}{a}_{1}{b}_{1} $是GF（4）并非GF（2）上元素，因此需要继续分解。可以看到，式（1）~式（5）用到的基本运算包含GF（4）上的平方S₂、两类常数乘法$ \alpha $乘和$ {\alpha }^{2} $乘、乘法$ {M}_{2} $和求逆$ {I}_{2} $等4类。GF（4）上元素用正规基表示可以简化求逆和平方的计算，设$ C={c}_{0}\oplus {c}_{1}\alpha $，$ D={d}_{0}\oplus {d}_{1}\alpha $，其中，$ {c}_{0}{d}_{0} $是低位，$ {c}_{1}{d}_{1} $是高位，$ {c}_{0}{d}_{0}{c}_{1}{d}_{1}\in \left(\mathrm{0, 1}\right) $。

$ {A}^{2}=({a}_{0}\oplus {a}_{1}{\beta )}^{2}=({a}_{0}^{2}\oplus {a}_{1}^{2}\alpha )\oplus {a}_{1}^{2}\beta $

(1)

$ AB=\left({a}_{0}\oplus {a}_{1}\beta \right)\left({b}_{0}\oplus {b}_{1}\beta \right)= \\ \;\;\;\;\;\;\; \left({a}_{0}{b}_{0}\oplus {a}_{1}{b}_{1}\alpha \right)\oplus \left[\left({a}_{0}\oplus {a}_{1}\right)\left({b}_{0}\oplus {b}_{1}\right)\oplus {a}_{0}{b}_{0}\right]\beta $

(2)

$ AB\_\mathrm{p}\mathrm{t}\mathrm{n}=\left({a}_{0}\oplus {a}_{1}\beta \right)\left({b}_{0}\oplus {b}_{1}\beta \right)= \\ \;\;\;\;\;\; \left[\right({a}_{0}\oplus {a}_{1}\left)\right({b}_{0}\oplus {b}_{1}\left)\oplus {a}_{1}{b}_{1}\alpha \right]\beta \oplus \left({a}_{0}{b}_{0}\oplus {a}_{1}{b}_{1}\alpha \right){\beta }^{4} $

(3)

$ \lambda A=\lambda \left({a}_{0}\oplus {a}_{1}\beta \right)=\left({a}_{1}\alpha \oplus {a}_{0}{\alpha }^{2}\right)\beta \oplus {a}_{1}{\beta }^{4} $

(4)

$ {A}^{-1}=({a}_{1}\beta \oplus {a}_{0}{\beta }^{4}{)}^{-1}=[({a}_{0}\oplus {a}_{1}{)}^{2}\alpha \oplus {a}_{0}{a}_{1}{]}^{-1}\times \\ \;\;\;\;\;\;\; [{a}_{0}\oplus \left({a}_{0}\oplus {a}_{1}\right)\beta ] $

(5)

S₂、$ \alpha $乘和$ {\alpha }^{2} $乘、M₂、I₂结果分别用$ {C}^{2} $、$ \alpha C $、$ {\alpha }^{2}C $、$ CD $、$ {C}^{-1} $表示，可得式（6）~式（10）。设GF（16）上元素AB的比特形式为$ A=\{{A}_{3}, {A}_{2}, {A}_{1}, {A}_{0}\} $，$ B=\{{B}_{3}, {B}_{2}, {B}_{1}, {B}_{0}\} $，将式（6）和式（7）代入式（1）得S₄，将式（7）和式（8）代入式（2）得$ \widehat{\lambda } $乘，将式（6）、式（7）、式（9）和式（10）代入式（3）得$ {\widehat{I}}_{4} $，将式（7）和式（9）代入式（4）和式（5）得$ {\widehat{M}}_{4} $和M₄，结果分别如式（11）~式（15）所示：

$ {C}^{2}=({c}_{0}\alpha \oplus {c}_{1}{\alpha }^{2}{)}^{2}={c}_{1}\alpha \oplus {c}_{0}{\alpha }^{2} $

(6)

$ \alpha C=\alpha \left({c}_{0}\alpha \oplus {c}_{1}{\alpha }^{2}\right)={c}_{1}\alpha \oplus \left({c}_{0}\oplus {c}_{1}\right){\alpha }^{2} $

(7)

$ {\alpha }^{2}C={\alpha }^{2}\left({\mathrm{c}}_{0}\alpha \oplus {c}_{1}{\alpha }^{2}\right)=\left({c}_{1}\oplus {c}_{0}\right)\alpha \oplus {c}_{0}{\alpha }^{2} $

(8)

$ \begin{array}{l}CD=\left({\mathrm{c}}_{0}\alpha \oplus {c}_{1}{\alpha }^{2}\right)\left({d}_{0}\alpha \oplus {\mathrm{d}}_{1}{\alpha }^{2}\right)=\\ \;\;\;\;\;\;\;\;\; \left({c}_{0}{d}_{1}\oplus {c}_{1}{d}_{0}\oplus {c}_{1}{d}_{1}\right)\alpha \oplus \\ \;\;\;\;\;\;\;\;\;\left({c}_{0}{d}_{1}\oplus {c}_{1}{d}_{0}\oplus {c}_{0}{d}_{0}\right){\alpha }^{2}\end{array} $

(9)

$ {C}^{-1}={C}^{2}=({c}_{0}\alpha \oplus {c}_{1}{\alpha }^{2}{)}^{2}={c}_{1}\alpha \oplus {c}_{0}{\alpha }^{2} $

(10)

$ {A}^{2}=\{{A}_{3}, {A}_{2}, {A}_{1}, {A}_{0}{\}}^{2}= \\ \;\;\;\;\;\;\;\;{A}_{2}{\alpha }^{2}\beta \oplus {A}_{3}\alpha \beta \oplus ({A}_{0}\oplus {A}_{2}\oplus {A}_{3}\left){\alpha }^{2}\oplus \right({A}_{1}\oplus {A}_{2})\alpha $

(11)

$ \lambda A=\lambda \{{A}_{3}, {A}_{2}, {A}_{1}, {A}_{0}\}={A}_{3}{\alpha }^{2}{\beta }^{4}\oplus {A}_{2}\alpha {\beta }^{4}\oplus \left({A}_{0}\oplus {A}_{2}\oplus {A}_{3}\right){\alpha }^{2}\beta \oplus \left({A}_{0}\oplus {A}_{1}\oplus {A}_{3}\right)\alpha \beta $

(12)

$ \begin{array}{l}{A}^{-1}=\{{A}_{3}, {A}_{2}, {A}_{1}, {A}_{0}{\}}^{-1}=({A}_{1}\oplus {A}_{3}\oplus {A}_{0}{a}_{3}\oplus {A}_{1}{A}_{2}\oplus {A}_{0}{A}_{1}{A}_{2}\oplus {A}_{0}{A}_{2}{A}_{3}){\alpha }^{2}{\beta }^{4}\oplus \\ \;\;\;\;\;\;\;\;\;\;\;\left({A}_{0}\oplus {A}_{1}\oplus {A}_{2}\oplus {A}_{3}\oplus {A}_{0}{A}_{3}\oplus {A}_{1}{A}_{2}\oplus {A}_{0}{A}_{1}{A}_{3}\oplus {A}_{1}{A}_{2}{A}_{3}\right)\alpha {\beta }^{4}\oplus \\ \;\;\;\;\;\;\;\;\;\;\; \left({A}_{1}\oplus {A}_{0}{A}_{2}\oplus {A}_{0}{A}_{3}\oplus {A}_{1}{A}_{3}\oplus {A}_{0}{A}_{1}{A}_{2}\right){\alpha }^{2}\beta \oplus \\ \;\;\;\;\;\;\;\;\;\;\; \left({A}_{0}\oplus {A}_{1}\oplus {A}_{0}{A}_{2}\oplus {A}_{0}{A}_{3}\oplus {A}_{0}{A}_{1}{A}_{3}\right)\alpha \beta \end{array} $

(13)

$ \begin{array}{l}AB\_\mathrm{p}\mathrm{t}\mathrm{n}=\left({A}_{0}{B}_{0}\oplus {A}_{0}{B}_{1}\oplus {A}_{1}{B}_{0}\oplus {A}_{2}{B}_{2}\oplus {A}_{3}{B}_{3}\right){\alpha }^{2}{\beta }^{4}\oplus \\ \;\;\;\;\;\;\;\;\;\;\; \left({A}_{0}{B}_{1}\oplus {A}_{1}{B}_{0}\oplus {A}_{1}{B}_{1}\oplus {A}_{2}{B}_{3}\oplus {A}_{3}{B}_{1}\right)\alpha {\beta }^{4}\oplus \\ \;\;\;\;\;\;\;\;\;\;\; \left({A}_{0}{B}_{0}\oplus {A}_{0}{B}_{1}\oplus {A}_{0}{B}_{2}\oplus {A}_{0}{B}_{3}\oplus {A}_{1}{B}_{0}\oplus {A}_{1}{B}_{2}\oplus {A}_{2}{B}_{0}\oplus {A}_{2}{B}_{1}\oplus {A}_{3}{B}_{0}\right){\alpha }^{2}\beta \oplus \\ \;\;\;\;\;\;\;\;\;\;\; \left({A}_{0}{B}_{1}\oplus {A}_{0}{B}_{3}\oplus {A}_{1}{B}_{0}\oplus {A}_{1}{B}_{1}\oplus {A}_{1}{B}_{2}\oplus {A}_{3}{B}_{3}\oplus {A}_{2}{B}_{1}\oplus {A}_{3}{B}_{0}\oplus {A}_{3}{B}_{1}\right)\alpha \beta \end{array} $

(14)

$ \begin{array}{l}AB=\left({A}_{0}{B}_{2}\oplus {A}_{0}{B}_{3}\oplus {A}_{1}{B}_{2}\oplus {A}_{2}{B}_{0}\oplus {A}_{2}{B}_{1}\oplus {A}_{2}{B}_{2}\oplus {A}_{2}{B}_{3}\oplus {A}_{3}{B}_{0}\oplus {A}_{3}{B}_{2}\right){\alpha }^{2}{\beta }^{4}\oplus \\ \;\;\;\;\;\;\;\;\;\;\; \left({A}_{0}{B}_{2}\oplus {A}_{1}{B}_{2}\oplus {A}_{1}{B}_{3}\oplus {A}_{2}{B}_{1}\oplus {A}_{2}{B}_{3}\oplus {A}_{3}{B}_{0}\oplus {A}_{3}{B}_{1}\oplus {A}_{3}{B}_{2}\oplus {A}_{3}{B}_{3}\right)\alpha {\beta }^{4}\oplus \\ \;\;\;\;\;\;\;\;\;\;\; \left({A}_{0}{B}_{0}\oplus {A}_{0}{B}_{1}\oplus {A}_{1}{B}_{0}\oplus {A}_{2}{B}_{2}\oplus {A}_{3}{B}_{3}\right){\alpha }^{2}\beta \oplus \\ \;\;\;\;\;\;\;\;\;\;\; \left({A}_{0}{B}_{1}\oplus {A}_{1}{B}_{0}\oplus {A}_{1}{B}_{1}\oplus {A}_{2}{B}_{2}\oplus {A}_{2}{B}_{3}\oplus {A}_{3}{B}_{2}\right)\alpha \beta \end{array} $

(15)

将AESs盒求逆表达式推导完成后，由于涉及到的是类AESs盒，因此还需要从原理上证明此类s盒适合重构。文献[10]对AES、Camellia、SMS4等类AESs盒做了可重构电路，其求逆统一在塔域GF（4²）²上实现，区别仅在复合了仿射变换后的前后同构映射矩阵上，但并未说明其理论基础。文献[18]根据包含相同个数元素的域是同构的原理，证明了GF（256）上s盒S和基于有限域扩张理论求出来的逆s盒T存在线性变换A₁、B₁，使得S=B₁（T（A（x）），并进一步证明有2 040个这样的转换对使得s盒原域和塔域的乘法逆s盒保持线性变换。A₁、B₁即为转换矩阵，在采用统一基类型和不可约多项式的前提下类AESs盒乘法逆T相同，这样即从原理上证明了此类s盒存在统一的结构，为可重构电路设计奠定了理论基础。

2.2 类AESs盒与NBFM可重构分析

将塔域分解后的s盒和NBFM结构重构，即将s盒适配到NBFM结构中，将s盒分解到GF（16）上的各个运算，考虑各模块输入输出情况，如乘法M₄是8入4出的结构，采用NBFM的6输入模式后，需要消耗16个NBFM，具体各模块资源消耗如表 6所示，其中，异或包括求逆的2个GF（16）上运算以及2个转换矩阵，1个异或门面积$ \approx \frac{1}{2} $个2_LUT。

下载CSV 表 6 各模块资源消耗 Table 6 Resource consumption of each module

Sbox_area=3M₄+S₄+I₄+λ+异或，相当于用51个NBFM加一部分异或门实现一个可分解的8-8 s盒，这样效率不如直接实现，由于M₄布尔表达式是8入4出的结构，如果直接采取NBFM的6变量模式搭建一个完备的NBF将导致资源浪费，冗余度过高，应该针对M₄继续分解。

将GF（16）上的乘法继续分解到GF（4）上，用到3个M₂乘法、1个α乘以及部分异或门资源，电路如图 4所示。涉及到的各模块资源损耗如表 7所示，其中，M₂电路只考虑LUT资源的情况下消耗4个2输入LUT，相当于1/4个NBFM。

	Download: JPG larger image
图 4 M₄电路 Fig. 4 M₄ circuit

下载CSV 表 7 M₄资源消耗 Table 7 M₄ resource consumption

最后相当于用1个NBFM实现GF（16）上的乘法。最终的s盒占用变为6个NBFM加一部分的异或门，相比将s盒输出展开写成NBF表达式的方法节约了近9倍的NBFM资源。

2.3 结合类AESs盒的NBFM结构优化分析

由2.1节对塔域分解后的不同模块表达式的推导可知，式（11）~式（15）复杂程度不一，映射到NBFM上还是采用门级电路实现未定，根据推导出的表达式复杂程度，结合表达式输入输出特征，将各个模块分为3类实现形式：1）基于异或实现平方S₄，$ \widehat{\lambda } $乘和前后的同构映射；2）基于NBFM实现求逆$ {\widehat{I}}_{4} $；3）基于改进后的SNBFM实现和M₄乘法。图 5所示为类AESs盒适配的电路，可以看到只需用到4个NBFM便可以实现一个完整的类AESs盒。

	Download: JPG larger image
图 5 s盒适配后的整体结构 Fig. 5 Overall structure of s-box after adaptation

基本模块平方S₄、$ \widehat{\lambda } $乘根据式（11）、式（12）结果只有少数的1次项，如果采用能实现从1次项到4次项且变量任意组合的NBFM的4变量模式，将造成极大的资源浪费，考虑到s盒实现的并行性，用较少的NBFM实现是需要考虑的性能指标，基于此，平方S₄和求逆$ \widehat{I} $₄采用异或实现，这样只需要用到6个2输入异或门便可实现S₄模块，需要7个2输入异或门便可实现$ \widehat{\lambda } $乘模块。此外，同构映射矩阵也采用异或门实现，异或门的数量=矩阵中1的数量减1，由于前后的同构映射矩阵不属于求逆部分，类AESs盒的差别即在于此，因此设置成可配置类型，共需要128 bit配置信息和126个异或门，配置信息为1时输入位取反，为0时输入位不变。下面给出AESs盒输入转换$ y={\boldsymbol{A}}_{\mathrm{A}\mathrm{E}\mathrm{S}}^{\mathrm{\delta }}x $和输出转换$ y={\boldsymbol{A}}_{\mathrm{A}\mathrm{E}\mathrm{S}}^{\mathrm{A}{\mathrm{\delta }}^{-1}+\mathrm{c}}x $的转换矩阵，其中x、y均按小端排列。

$ \begin{array}{l}{\boldsymbol{A}}_{\mathrm{A}\mathrm{E}\mathrm{S}}^{\mathrm{\delta }}=\left[\begin{array}{cccccccc}0& 1& 1& 0& 1& 0& 0& 0\\ 0& 1& 0& 1& 0& 1& 0& 0\\ 1& 1& 1& 1& 0& 0& 0& 0\\ 0& 0& 0& 1& 0& 0& 1& 0\\ 0& 0& 0& 0& 1& 1& 1& 0\\ 0& 0& 1& 1& 0& 0& 0& 0\\ 0& 1& 0& 0& 0& 1& 0& 1\\ 0& 0& 0& 0& 1& 0& 1& 1\end{array}\right]\\ {\boldsymbol{A}}_{\mathrm{A}\mathrm{E}\mathrm{S}}^{\mathrm{A}{\mathrm{\delta }}^{-1}+\mathrm{c}}=\left[\begin{array}{cccccccc}0& 1& 0& 1& 0& 1& 1& 0\\ 1& 0& 1& 0& 0& 1& 0& 1\\ 1& 1& 0& 0& 1& 0& 0& 0\\ 0& 0& 0& 0& 0& 0& 1& 1\\ 1& 0& 0& 0& 1& 1& 0& 1\\ 1& 0& 1& 0& 1& 1& 0& 0\\ 0& 1& 1& 0& 0& 1& 1& 0\\ 1& 0& 1& 0& 0& 0& 0& 1\end{array}\right]\end{array} $

由式（13）可得，求逆$ {\widehat{I}}_{4} $相比较平方S₄和$ \widehat{\lambda } $乘表达式较为复杂不适合门级实现，将$ {\widehat{I}}_{4} $看作4入4出的布尔函数后可以采用1个NBFM实现，NBFM模式为4变量模式。由于$ {\widehat{I}}_{4} $的4个输出的表达式输入变量均相同，NBFM的4变量模式含有2个共享变量a、b，因此可以用来实现$ {\widehat{I}}_{4} $。具体的端口映射如表 8所示。$ {\widehat{M}}_{4} $和$ {M}_{4} $是GF（16）上的乘法，$ {\widehat{M}}_{4} $输入是多项式基（1，$ \beta $），输出是正规基（$ \beta , {\beta }^{4} $），$ {M}_{4} $输入输出均是多项式基，两者从表达式输入输出特征上看均是8入4出的结构。如上文分析，$ \mathrm{两}\mathrm{类}\mathrm{乘}\mathrm{法} $电路并不适合NBFM直接适配，将表达式推导出以后也并未起到化简变量个数、次数的作用。基于此，本文采取先适配实现GF（4）上M₂、α乘电路，再用两者的组合实现GF（16）上乘法的方法。

下载CSV 表 8 $ {\widehat{\boldsymbol{I}}}_{4} $电路端口映射 Table 8 $ {\widehat{\boldsymbol{I}}}_{4} $ circuit port mapping

比较式（4）和式（5），发现$ {\widehat{M}}_{4} $和$ {M}_{4} $均用到3个M₂和1个α乘电路，区别只是在于输出的组合形式不同，其中M₂电路占据4个2输入LUT，α乘电路只用到1个异或门，基于此，提出NBFM改进的结构——SNBFM，使之在原有NBF功能基础上实现两类乘法电路，电路结构如图 6所示。类AESs盒的GF（16）上的乘法和NBF共享LUT存储，其中乘法电路用到12个2输入LUT，但乘法逻辑和NBF逻辑设计相对独立，乘法逻辑相当于在NBFM基础上再增加部分异或门即例化3个M₂电路和1个α乘电路实现。由于涉及到两类乘法，需要经过M₄_mode选择后输出乘法结果C[3：0]，M₄_mode为1时选择$ {\widehat{M}}_{4} $的输出结果，为0时选择M₄的输出结果。由于乘法电路的输入是按照类AESs盒电路的组织形式得到，其输入来源于中间值，与NBF输入直接对外不同，因此SNBFM扩展了输入端口，即针对两类乘法电路，扩展9 bit输入端，其中8 bit由2个乘法操作数占据，另外1 bit是QEL信号用于对12个共享LUT的输入来源进行选择，由于篇幅限制图中没有显示。

	Download: JPG larger image
图 6 SNBFM结构 Fig. 6 SNBFM structure

3 性能评估

采用以上的模块搭建类AESs盒电路，可以看到除了$ {\widehat{M}}_{4} $、$ {M}_{4} $、$ {\widehat{I}}_{4} $电路利用了NBFM资源外，其余模块并未采用NBFM资源，而是通过一些简单的异或门直接实现。本文针对$ {\widehat{M}}_{4} $、$ {M}_{4} $电路用改进后的SNBFM实现，针对$ {\widehat{I}}_{4} $电路用NBFM实现，因此类AESs盒电路只消耗4个NBFM资源加一部分的异或门资源。

在保证NBFM原有NBF功能前提下，采用verilog实现各个改进的NBFM模块，最后按照类AESs盒电路的组织形式对改进后的NBFM进行级联实现s盒功能。功能验证通过后在CMOS 65 nm工艺库下对该电路进行综合，与塔域直接实现的s盒电路和NBFM电路进行对比分析后的结果如表 9所示。

下载CSV 表 9 电路性能指标 Table 9 Circuit performance index

RAM是一个时序部件，虽然延迟最小但规模过大，而文献[13]的NBFM结构在适配s盒时将s盒作为NBF适配，这种方法虽然适合通用8-8的s盒，但由于NBM最多只能支持6变量模式，因此NBFM个数消耗过多以致占用资源最多。这种NBF适配的方法适合6变量、4变量输入的s盒，但并不适合8-8的通用s盒。文献[17]所选用的塔域分解是一种用组合逻辑的方法实现AESs盒，其目的是为了降低面积开销，但是这种组合逻辑的方法在单个算法s盒性能表现上并不是最优的。文献[19]将各模块的表达式推导出以后，采用CSE算法将其中的各模块表达式含有的公共项消除进一步减少了s盒面积和延迟。本文验证了类AESs盒电路差异仅在转换矩阵上，实现了类AESs盒和NBF的可重构，由于可重构的结构是要实现两类非线性运算，但NBFM的结构并不适合对类AESs盒直接实现，需要对NBFM进行改进，这使得NBFM的电路资源并非完全参与s盒的运算，采用CSE算法也会造成一定的冗余度。也因此，本文采用类似的塔域分解的方法，相比文献[19]增加了1倍多面积。

但实际上面积不是唯一的指标，由于牵扯到复杂的NBF适配，NBFM的个数是多个级联在一起，因此在保证充分复用前提下用最少的NBFM个数来实现s盒。本文采用的方法相当于在4个改进后的NBM电路加一部分异或阵列，可以看到在4个NBFM基础上增加1 632-362×4=184 μm²实现了一个类AES的8-8的s盒，相当于只用22.7%的s盒电路面积实现了一个类AES的s盒，而电路延迟基本不变。

在电路实现功能上，如表 10所示，由于塔域分解定理只针对部分s盒，因此并不能实现通用的8-8 s盒的实现。

下载CSV 表 10 电路实现功能的对比 Table 10 Comparison of circuit realization functions

4 结束语

本文实现了类AESs盒和NBFM的可重构电路，并基于塔域分解理论，提出一种新的SNBFM结构。采用混合基方法将AES类s盒电路分解为GF（16）上的各种运算模块，并推导出这些模块的位级表达式。实验结果表明，改进后的整体结构只用到4个NBFM加上原s盒的22.7%面积实现一个完整的类AESs盒，而延迟基本不变，并保证了已有NBF功能。但类AESs盒相比通用s盒种类较少，使得该结构的用途受到限制，下一步将研究运用更少的资源实现通用s盒和NBF的可重构，并通过扩展指令的方式加速密码运算^[20]。

参考文献

[1]	刘嘉勇. 应用密码学[M]. 北京: 清华大学出版社, 2008. LIU J Y. Applied cryptography[M]. Beijing: Tsinghua University Press, 2008. (in Chinese)
[2]	JIAO L, LIN Y. Stream cipher designs: a review[J]. Science China Information Sciences, 2020, 63(3): 80-104.
[3]	孟涛, 戴紫彬. 可重构S盒运算单元的设计与实现[J]. 电子技术应用, 2007, 33(5): 139-139. MENG T, DAI Z B. Design and implementation of reconfigurable S-box computing unit[J]. Application of Electronic Technique, 2007, 33(5): 139-141. (in Chinese)
[4]	常忠祥, 陈卓. 可重构S盒替换单元研究与设计[J]. 微电子学与计算机, 2018, 35(12): 125-128, 132. CHANG Z X, CHEN Z. Research and design of reconfigurable S-box replacement unit[J]. Microelectronics and Computer, 2018, 35(12): 125-128, 132. (in Chinese)
[5]	李兆奇. 面向分组密码算法的粗粒度可重构架构高能效设计与优化[D]. 南京: 东南大学, 2017. LI Z Q. Energy efficient design and optimization of coarse grained reconfigurable architecture for block cipher algorithm[D]. Nanjing: Southeast University, 2017. (in Chinese)
[6]	郭怡惠, 李森森, 戴紫彬, 等. RISC微处理器S盒替换指令扩展[J]. 微电子学与计算机, 2014, 31(5): 53-57. GUO Y H, LI S S, DAI Z B, et al. S-box replacement instruction extension of RISC microprocessor[J]. Microelectronics and Computer, 2014, 31(5): 53-57. (in Chinese)
[7]	张肖强. 基于复合域运算的AES密码电路优化设计方法研究[D]. 南京: 南京航空航天大学, 2016. ZHANG X Q. Research on optimization design method of AES cipher circuit based on compound field operation[D]. Nanjing: Nanjing University of Aeronautics and Astronautics, 2016. (in Chinese)
[8]	MAXIMOV A, EKDAHL P. New circuit minimization techniques for smaller and faster AES S-Boxes[J]. IACR Transactions on Cryptographic Hardware and Embedded Systems, 2019, 32(4): 91-125.
[9]	张学颖. 对称密码有限域运算模块可重构设计技术研究[D]. 郑州: 解放军信息工程大学, 2010. ZHANG X Y. Research on reconfigurable design technology of symmetric cipher finite field operation module[D]. Zhengzhou: PLA University of Information Engineering, 2010. (in Chinese)
[10]	SATPATHY S, SURESH V, MATHEW S, et al. 220MV-900MV 794/584/754/GBPS/W reconfigurable GF(24)² AES/SMS4/camellia symmetric-key cipher accelerator in 14NM tri-gate CMOS[C]//Proceedings of 2018 IEEE Symposium on VLSI Circuits. Washington D.C., USA: IEEE Press, 2018: 158-167.
[11]	黄荫钊. 基于FPGA的低延迟Grain-128a算法设计与实现[D]. 西安: 西安电子科技大学, 2019. HUANG Y Z. Design and implementation of low latency grain-128a algorithm based on FPGA[D]. Xi'an: Xi'an University of Electronic Science and Technology, 2019. (in Chinese)
[12]	纪祥君, 陈迅, 戴紫彬, 等. 一种改进的非线性布尔函数硬件设计与实现[J]. 计算机应用与软件, 2014, 31(7): 283-285, 302. JI X J, CHEN X, DAI Z B, et al. Hardware design and implementation of an improved nonlinear Boolean function[J]. Computer Applications and Software, 2014, 31(7): 283-285, 302. (in Chinese)
[13]	常忠祥, 戴紫彬, 李伟. 面向密码算法的非线性布尔函数实现技术研究[J]. 电子技术应用, 2014, 40(7): 61-64. CHANG Z X, DAI Z B, LI W. Research on implementation technology of nonlinear Boolean function for cryptographic algorithm[J]. Application of Electronic Technology, 2014, 40(7): 61-64. (in Chinese)
[14]	戴紫彬, 王周闯, 李伟, 等. 可重构非线性布尔函数利用率模型研究与硬件设计[J]. 电子与信息学报, 2017, 39(5): 1226-1232. DAI Z B, WANG Z C, LI W, et al. Reconfigurable nonlinear Boolean function utilization model research and hardware design[J]. Acta electronica Sinica, 2017, 39(5): 1226-1232. (in Chinese)
[15]	张振民. 序列密码非线性组件的设计研究[D]. 西安: 西安电子科技大学, 2014. ZHANG Z M. Research on the design of nonlinear component of sequence cipher[D]. Xi'an: Xi'an University of Electronic Science and Technology, 2014. (in Chinese)
[16]	李声涛. 分组密码中S盒的设计与分析[D]. 长沙: 国防科学技术大学, 2004. LI S T. Design and analysis of S-box in block cipher[D]. Changsha: University of Defense Science and Technology, 2004. (in Chinese)
[17]	NOGAMI Y, NEKADO K, TOYOTA T, et al. Mixed bases for efficient inversion in F(2²)² and conversion matrices of sub bytes of AES[C]//Proceedings of International Workshop on Cryptographic Hardware and Embedded Systems. Berlin, Germany: Springer, 2010: 156-168.
[18]	刘健. 两类密码组件的实现优化方法研究[D]. 郑州: 战略支援部队信息工程大学, 2019. LIU J. Research on optimization m_ethod of two kinds of cryptographic components[D]. Zhengzhou: PLA Strategic Support Force Information Engineering University, 2019. (in Chinese)
[19]	戴强, 戴紫彬, 李伟. 基于增强型延时感知CSE算法的AES S盒电路优化设计[J]. 电子学报, 2019, 47(1): 129-136. DAI Q, DAI Z B, LI W. Optimization design of AES S-box circuit based on enhanced delay sensing CSE algorithm[J]. Acta Electronica Sinica, 2019, 47(1): 129-136. (in Chinese)
[20]	刘元锋. RISC架构微处理器扩展对称密码处理指令的研究[D]. 郑州: 解放军信息工程大学, 2006. LIU Y F. Research on RISC architecture microprocessor extending symmetric cipher processing instruction[D]. Zhengzhou: PLA Information Engineering University, 2007. (in Chinese)