AES作为新一代国际加密标准，因其具有的高效性和较高的安全性而得到了广泛的关注和研究^[1-2]。关于AES在硬件上实现的大量实验和优化，让其具有了相当高的效率，使得AES在硬件上得到了广泛的应用，但同时也使AES遭到了诸多的攻击。1999年，Kocher等^[3]提出了DPA的概念，对密码学界造成了极大地冲击，有别于传统的对加密方案分析进行的攻击，DPA攻击的对象是加密方案的硬件实现，通过测量获取进程中的差分信息而实现攻击。Daemen等^[4-5]通过添加掩码对DPA攻击进行防御，然而随着glitch攻击的引入，这些方案失去了效果。2006年，Nikova等^[6]提出了基于秘密共享、门限方案抵抗DPA攻击的思想。2011年，Moradi等^[7]在EUROCRYPT2011上提出了基于秘密共享、门限方案和多方计算思想，构造抗DPA攻击及故障攻击加密方案的理论方法。2013，Bilgin等^[8]又发表论文实现了针对较小S盒的硬件实现并对S盒分组做了深入的研究。2014年，Bilgin等^[9]又实现了一个AES的S盒的经典分组方案。

本文针对AES中单个S盒进行研究，利用元素在有限域GF(2⁸)与复合域GF(((2²)²)²)的转换实现了一个低消耗的S盒；随后基于秘密共享、门限方案和多方计算思想，构造出新的S盒，并采用的分解法进行分组，通过计算得到满足特性的分组。通过分析，本文方案具有较Nikova经典方案优良的功耗特性和更小的实现面积，且可以同等级地抵抗1阶DPA攻击及glitch攻击。

1 预备知识 1.1 DPA

差分功耗分析(differential power analysis, DPA)不同于针对密码方案进行攻击的传统密码攻击技术，它通过大量测量密码设备在加密过程中对数据进行处理时，产生的功耗、电磁辐射等信息，利用差分分析的方法，针对数据不同时信息的变化来确定数据是0或是1，反复进行猜测出算法所使用的密钥^[3]。DPA不需要知道密码设备的任何详细信息，只需已经公开的密码算法即可。

DPA攻击通常包括以下4个步骤：

1)选取密码设备在运行进程时产生的一个中间值D，构建一个用于进行差分运算的函数D(m, k)，其中, k是密钥的一个部分, m为运行过程中可测量非常量数据。

2)通过对密码设备输入大量不同数据，获取运行进程中产生的m_i及轨迹t_i。

3)猜测子密钥k_i，根据猜测的k_i与已知的m_i计算得到中间值D，按照选定模型将轨迹t_i分类，计算平均功耗轨迹t与分类的轨迹进行差分运算，公式如下：

$\begin{array}{l} {\Delta _D}\left( j \right) = \frac{{\sum\limits_{i = 1}^n {D\left( {{m_i},{k_i}} \right){t_i}\left( j \right)} }}{{\sum\limits_{i = 1}^n {D\left( {{m_i},{k_i}} \right)} }} - \\ \;\;\;\;\;\;\;\;\;\frac{{\sum\limits_{i = 1}^n {\left( {1 - D\left( {{m_i},{k_i}} \right)} \right){t_i}\left( j \right)} }}{{\sum\limits_{i = 1}^n {\left( {1 - D\left( {{m_i},{k_i}} \right)} \right)} }}。\end{array}$

若得到的结果出现尖峰则猜测正确，否则重复此步骤。

4)通过上述步骤猜测得到全部子密钥，计算恢复密码设备的密钥。

1.2 Shamir门限秘密共享方案

Shamir^[10]与Blakley于1979年分别提出了秘密共的概念，并给出了(k, n)门限秘密共享方案。(k, n)门限秘密共享方案是把一个秘密分成若干份并分给n个人，只有其中k个以上的人合作才能恢复秘密。Shamir门限秘密共享方案通过构建一个k-1次多项式，使用其中的常数项来保管秘密，将秘密分成n份分给参与者。k个以上的参与者可以使用拉格朗日插值公式恢复秘密，少于k个参与者则得不到关于秘密的任何信息。

1.3 门限秘密共享方案抗侧信道攻击和glitch攻击的应用 1.3.1 符号及用语

定义⊕为在域GF(2^m)的异或运算，∑为实数的加法运算；x表示一组变量(x₁, x₂, …, x_n)，x_i表示除去x_i的一组变量(x₁, x₂, …, x_i-1, x_i+1, …, x_n)，Pr (t(x)=T)表示t取值T的概率。

定义变量x被分成n份，如果下式成立：

$x = \mathop \oplus \limits_{x = 1}^n {x_i}。$

使用(n, n)秘密共享方案，为了唯一地确定x，需要全部n份秘密。对于一个优秀的(n, n)秘密共享方案，直至获得n-1份秘密仍无法获得关于x的任何信息。在这里引入(k, t, n)斜坡方案，方案中t个诚实的参与者可以恢复秘密，但超过k个恶意的参与者也可以从中获取秘密相关的信息。文中将使用(1, n, n)斜坡方案和秘密共享方案，且条件概率Pr (x|x)均匀，即：

$\forall \bar X:\Pr \left( {\bar x = \bar X} \right) = {\rm{c}}\Pr (x = \mathop \oplus \limits_{i = 1}^n {x_i})。$

其中, c是一个标准常量，以确保概率和为1。

1.3.2 基本原理

对于一个域GF(2^m)上的线性变换z=L(x)，最安全的实现方法是使独立地对n份分别处理。定义z_i=L(x_i)，0≤i < n, 可以得到：

$z = \mathop \oplus \limits_{i = 1}^n {z_i} = \mathop \oplus \limits_{i = 1}^n L({x_i}) = L(\mathop \oplus \limits_{i = 1}^n {x_i}) = L\left( x \right)。$

对于拥有更多输入的线性变换z=LL(x, y, …)，可以用同样的方法进行处理。

这样实现的线性变换具有一个典型的特征，就是任意的输出份z_i，只取决于一份输入变量(x_i, y_i, …)。这样的线性变换不会泄露信息，可以用于抵抗侧信道攻击^[6]。

为了使电路安全实现，希望非线性变换具有与线性变换相同的性质。直观地看，如果输出z_i的取值不取决于输入(x_i, y_i, …)，则z_i不会与(x_i, y_i, …)相关。通过额外的约束条件，也可以确保与z不相关。

定义z=N(x, y, …)为域GF(2^m)上的非线性变换，f₁, f₂, …, f_n为一组满足以下性质的函数：

性质1(不完整性) 每个函数至少与输入任意变量x, y, …的一份不相关

$\begin{array}{*{20}{c}} {{z_1} = {f_1}\left( {{{\bar x}_1},{{\bar y}_1}, \cdots } \right),}\\ {{z_2} = {f_2}({{\bar x}_2},{{\bar y}_2}, \cdots ),}\\ \ldots \\ {{z_n} = {f_n}({{\bar x}_n},{{\bar y}_n}, \cdots ){\rm{。}}} \end{array}$

性质2(正确性) n份输出的总和等于正确得到输出：

$z = \mathop \oplus \limits_{i = 1}^n {z_i} = \mathop \oplus \limits_{i = 1}^n {f_i}\left( \cdots \right) = N\left( x \right),$

定理1 对于满足性质1、2的具有s个变量的非线性变换，最小的分组数n满足：

$n \ge s + 1。$

由此可以得出，要实现一个非线性变换至少需要分成3组。对定理1的证明可以推广到一般的单项式，例如x²y²可以作为一个具有4个变量的乘法实现。因为并不一定所有的变量都不相关，可能存在其他更少分组的解决方法，可以得到以下推论：

推论1 域GF(2^m)上的具有u个变量的非线性变换N，最大的分组数为1+2^mu。

将前文提到的条件概率进行扩展，得到：

条件1

$\Pr \left( {\bar x = \bar X,\bar y = \bar Y, \cdots } \right) = c\Pr (x = \mathop \oplus \limits_i {X_i},y = \mathop \oplus \limits_i {Y_i}, \cdots )。$

这表明x、y的联合分布出现偏差将导致x、y的联合概率产生偏差。由此可以证明：

定理2 在电路实现中，一组函数满足性质1、2，且输入满足条件1，则所有的中间值与输入x、y、输出z不相关；同时任意单个函数f_i与x、y、z不相关。

性质1可以直观看出，条件1则可以全部列举出来进行验证，性质2由于

$\begin{array}{*{20}{l}} {{z_1} \oplus {z_2} \oplus {z_3} = }\\ {\left( {{x_1} \oplus {x_2} \oplus {x_3}} \right)\left( {{y_1} \oplus {y_2} \oplus {y_3}} \right) = xy = z。} \end{array}$

也得以证明。

性质3(均匀性) 对于所有满足条件1的输入x，y，…和输入份x_i，y_i，…，若条件概率${\rm{Pr}}(\bar z = \bar Z|z = \mathop \oplus \limits_i {Z_i})$是一个常量，则称z=N(x, y, …)是均匀的。

1.3.3 抵抗侧信道攻击及故障攻击的证明

定理3 如果输入份x_i, y_i, …的分布满足性质1、2及条件1，则电路实现的平均功耗与x、y、z不相关，甚至在一些输入中存在故障。

证明：由定理2可以得到任意单个函数f_i与x、y、z不相关，在电路实现中即可得到任意单个电路的平均功耗与x、y、z不相关；因为整个电路的平均功耗等于各个电路的平均功耗之和，所以整个电路的平均功耗之和也与x、y、z不相关；由定理2可知，并没有在研究特性是对是否存在故障做出假设，即证明对于存在故障的情况通用。

1.4 基于秘密共享对S盒分组的研究

要实现非线性变换，分组数量至少为3，又由于过多的分组将导致电路实现时消耗过大，这里选取分组数量d=3, 4进行研究。

定义1 如果存在一组可逆的仿射或线性置换A(x)和B(x)，使得2个S盒S₁(x)和S₂(x)满足S₁=${S_1} = B \circ {S_2} \circ \mathit{\boldsymbol{A}}$ ，则称2个S盒仿射或线性等价。

任何可逆仿射置换A(x)可以被表示成A·x+a，其中, a是一个n bit常量，A是一个在GF(2)上的n×n的可逆矩阵。可以轻易得出共有${2^n} \times \prod\limits_{i = 0}^{n - 1} {({2^n} - {2^i})} $个不同的可逆仿射置换。

用仿射等价来定义等价类^[8]:

当n=3时，通过计算共有4个等价类，其中3个等价类包含二次函数，1个包含仿射函数。

当n=4时，通过计算共有302个等价类，其中6个等价类包含二次函数，1个包含仿射函数，剩下的295个包含三次函数。

定理4 如果可以对一个类中的代表进行分组，则对于同一个类中的任何置换都可以进行分组。

对于等价类的分组，首先引入直接分组法：构造一个满足正确性的分组，这点十分容易做到；为了满足不完整性，使一次项仅x_i在f_i-1中包含，二次项x_ix_i+1仅在f_i-1中包含，三次项x_i仅在f_i-1中包含。

然而通过直接分组法得到的分组可能不满足均匀性，根据计算^[8]，在n=3、4时有大量的分组存在这一问题。为了解决这一问题，再次引入正确项法：

在直接分组法的基础上，在至少2个分组中加入不破坏不完整性的成对的项，使分组满足均匀性。同时由于项是成对加入的，并不会破坏正确性。

2 基于秘密共享的S盒的实现 2.1 S盒的实现

通常AES的S盒的功能可以分成2个部分进行实现，分别是有限域GF(2⁸)上的逆变换和有限域GF(2)上的仿射变换，其中有限域GF(2⁸)上的逆变换是唯一的非线性部分。有限域GF(2)上的仿射变换由于是线性变换，这里只以模块表示。有限域GF(2⁸)上的逆变换，分为3步：

1)将元素输入由乘法器和计数器组成的模块使之变换到复合域GF(((2²)²)²)；

2)将元素输入反相器进行求逆；

3)将结果输入到2个乘法器组成的模块变换回有限域GF(2⁸)，实现求逆操作。

整个S盒的具体实现方法如图 1所示。在实现的电路中共用到1个GF(2²)反相器，1个GF(2²)平方计数器，3个GF(2²)乘法器和2个4 bit异或门。

2.2 共享S盒的实现 2.2.1 共享S盒实现的经典方案

在这里，首先对Nikova提出的经典方案做以介绍，该方案共分为3个阶段^[1]。

在第1阶段中，基于秘密共享将输入的8 bit信息分成4组8 bit的信息a、b、c、d，对4组信息进行线性变换，以实现GF(2)上的仿射变换。将每组信息分成2组4 bit的信息，得到8组4 bit的信息(a₁, b₁，c₁, d₁, a₂, b₂, c₂, d₂)，分为S₁、S₂两组写入寄存器中。将S₁、S₂输入8×3的GF(2⁴)乘法器，得到3组4 bit的信息；同时将S₁、S₂进行2组共6次异或操作，得到2组4 bit的信息，为了满足分组性质，与2对4 bit掩码信息进行异或操作。

在第2阶段中，将得到的5组4 bit信息输入5×5的反相器中，进行求逆变换，得到5组4 bit的输出信息。

在第3阶段中，引入3对4 bit掩码信息与5组4 bit的信息进行异或操作，得到满足分组性质的4组4 bit的信息S₃。将S₁、S₃输入8×3的GF(2⁴)乘法器，得到3组4 bit的信息m₁；将S₂、S₃输入8×3的GF(2⁴)乘法器，得到3组4 bit的信息m₂。将m₁、m₂合成得到3组8bit的信息，进行逆仿射变换，得到的3组8 bit的信息基于秘密共享相加即可正确输出。

2.2.2 共享S盒的具体实现

在选择分享份数n时，n的取值应大于2；可以看出当n=3时，满足秘密共享方案3个性质的分类方法十分有限，存在一定遭受穷举攻击的潜在风险^[2]。据此，在尽可能减小值，以减小实现所需消耗和面积的情况下，选择n=4。参考2.2.1节对S盒的实现，本文基于秘密共享的S盒实现方案分为3个阶段(图 2)。

在第1阶段中，GF(2)上的仿射变换的实现部分，将输入的8 bit信息基于秘密共享分成4组8 bit的信息a、b、c、d，对4组信息进行线性变换，以实现GF(2)上的仿射变换。将每组信息分成2组4 bit的信息，得到8组4 bit的信息(x₁, x₂, x₃, x₄, x₅, x₆, x₇, x₈)，分为S₁、S₂两组写入寄存器中。

在域变换的部分，将S₁、S₂输入8×4的GF(2²)乘法器，得到4组4 bit的信息(f₁, f₂, f₃, f₄)；同时将S₁、S₂进行4次异或操作，得到4组4 bit的信息(g₁, g₂, g₃, g₄)。将(f₁, f₂, f₃, f₄)与(g₁, g₂, g₃, g₄)进行异或操作得到4组4 bit的信息(h₁, h₂, h₃, h₄)乘法器电路中，采取直接分组法得到具体的方程式如下：

$\begin{array}{l} ({f_1},{f_2},{f_3},{f_4}) = ({x_1},{x_2},{x_3},{x_4}) \times ({x_5},{x_6},{x_7},{x_8}),\\ {f_1} = {x_2}{x_5} \oplus {x_3}{x_5} \oplus {x_4}{x_5} \oplus {x_2}{x_6} \oplus {x_3}{x_6} \oplus {x_4}{x_6} \oplus \\ \;\;\;\;\;\;\;{x_2}{x_7} \oplus {x_3}{x_7} \oplus {x_4}{x_7} \oplus {x_2}{x_8} \oplus {x_3}{x_8} \oplus {x_4}{x_8},\\ {f_2} = {x_1}{x_5} \oplus {x_3}{x_5} \oplus {x_4}{x_5} \oplus {x_1}{x_6} \oplus {x_3}{x_6} \oplus {x_4}{x_6} \oplus \\ \;\;\;\;\;\;\;{x_1}{x_7} \oplus {x_3}{x_7} \oplus {x_4}{x_7} \oplus {x_1}{x_8} \oplus {x_3}{x_8} \oplus {x_4}{x_8},\\ {f_3} = {x_1}{x_5} \oplus {x_2}{x_5} \oplus {x_4}{x_5} \oplus {x_1}{x_6} \oplus {x_2}{x_6} \oplus {x_4}{x_6} \oplus \\ \;\;\;\;\;\;\;{x_1}{x_7} \oplus {x_2}{x_7} \oplus {x_4}{x_7} \oplus {x_1}{x_8} \oplus {x_2}{x_8} \oplus {x_4}{x_8},\\ {f_4} = {x_1}{x_5} \oplus {x_2}{x_5} \oplus {x_3}{x_5} \oplus {x_1}{x_6} \oplus {x_2}{x_6} \oplus {x_3}{x_6} \oplus \\ \;\;\;\;\;\;\;{x_1}{x_7} \oplus {x_2}{x_7} \oplus {x_3}{x_7} \oplus {x_1}{x_8} \oplus {x_2}{x_8} \oplus {x_3}{x_8}。\end{array}$

与Nikova的方案相比，在这里减少了异或操作的数量，并且由于下一阶段的求逆操作引入分解的分组方法，并不需要通过添加掩码信息来满足分组性质，这两方面能够降低消耗和减小面积。

在第2阶段中，将得到的4组4 bit信息(h₁, h₂, h₃, h₄)输入4×4的GF(2²)反相器中，进行求逆变换，得到4组4 bit的输出信息(m₁, m₂, m₃, m₄)。

在反相器电路中，无法直接分类得到满足性质的分类，使用正确值法会因为添加掩码信息而产生大量的消耗，同样扩大分组数也会指数级增大所需等价门数。因此在这里引入分解法^[8]：将一个困难的置换分解为已经可以分解的置换，如Inv (x)=F(G(H(x)))。通过这种方法，得到反相器的具体方程式如下：

$\begin{array}{l} ({m_1},{m_2},{m_3},{m_4}) = {\rm{Inv}}({h_1},{h_2},{h_3},{h_4}),\\ {m_1} = {h_2} + {h_3} \oplus {h_1}{h_3} \oplus {h_2}{h_3} \oplus {h_2}{h_3}{h_4},\\ {m_2} = {h_4} \oplus {h_1}{h_3} \oplus {h_2}{h_3} \oplus {h_2}{h_4} \oplus {h_1}{h_3}{h_4},\\ {m_3} = {h_1} \oplus {h_2} \oplus {h_1}{h_3} \oplus {h_1}{h_4} \oplus {h_1}{h_2}{h_4},\\ {m_4} = {h_2} \oplus {h_1}{h_3} \oplus {h_1}{h_4} \oplus {h_2}{h_4} \oplus {h_1}{h_2}{h_3}。\end{array}$

与Nikova的方案相比，我们的方案通过使用分解法这一新方法，避免了掩码信息的添加，进一步降低消耗和减小面积。

在第3阶段中，将(m₁, m₂, m₃, m₄)与(f₁, f₂, f₃, f₄)输入8×4的GF(2²)乘法器得到4 bit信息(p₁, p₂, p₃, p₄)，将(m₁, m₂, m₃, m₄)与(g₁, g₂, g₃, g₄)输入8×4的GF(2²)乘法器得到4 bit信息(q₁, q₂, q₃, q₄)；将(p₁, p₂, p₃, p₄)与(q₁, q₂, q₃, q₄)进行异或，再进行逆仿射变换，得到的输出即为正确的输出。

3 共享方案的优化 3.1 针对设计电路图的优化

通过测量S盒中不同阶段的功耗值，DPA攻击仍可以获得一些信息^[11-12]。因此，在不同阶段分别引入随机掩码，进一步使中间值随机化，以此来杜绝这些信息的泄露。

在第1阶段中，将4组4 bit的信息(g₁, g₂, g₃, g₄)与成对的随机掩码进行异或运算，使输出结果随机化，且保证结果的正确。

在第2阶段中，将通过反相器输出的4组4 bit的信息(m₁, m₂, m₃, m₄)与3对随机掩码进行异或，其中3组与单组掩码异或，剩下一组通过4×1异或门与对应的3组掩码进行异或，具体实现如图 3所示。

3.2 针对分组方法的优化

可以直观看出，用于乘法器的分组方法较为复杂，消耗了大量的资源^[13-17]。通过逐步推演，得到了一组更优的分法，可以有效地减少所需等价门数。具体的方程式如下所示：

$\begin{array}{l} ({f_1},{f_2},{f_3},{f_4}) = ({x_1},{x_2},{x_3},{x_4}) \times ({x_5},{x_6},{x_7},{x_8}),\\ {f_1} = {x_1}{x_5} \oplus {x_3}{x_5} \oplus {x_4}{x_5} \oplus {x_2}{x_6} \oplus {x_3}{x_6} \oplus {x_1}{x_7} \oplus \\ \;\;\;\;\;\;\;{x_2}{x_7} \oplus {x_3}{x_7} \oplus {x_4}{x_7} \oplus {x_1}{x_8} \oplus {x_3}{x_8},\\ {f_2} = {x_2}{x_5} \oplus {x_3}{x_5} \oplus {x_1}{x_6} \oplus {x_2}{x_6} \oplus {x_4}{x_6} \oplus {x_1}{x_7} \oplus \\ \;\;\;\;\;\;\;{x_2}{x_8} \oplus {x_4}{x_8},\\ {f_3} = {x_1}{x_5} \oplus {x_2}{x_5} \oplus {x_3}{x_5} \oplus {x_4}{x_5} \oplus {x_1}{x_6} \oplus {x_3}{x_6} \oplus \\ \;\;\;\;\;\;\;{x_1}{x_7} \oplus {x_2}{x_7} \oplus {x_3}{x_7} \oplus {x_1}{x_8} \oplus {x_4}{x_8},\\ {f_4} = {x_1}{x_5} \oplus {x_3}{x_5} \oplus {x_2}{x_6} \oplus {x_4}{x_6} \oplus {x_1}{x_7} \oplus {x_4}{x_7} \oplus \\ \;\;\;\;\;\;{x_2}{x_8} \oplus {x_3}{x_8} \oplus {x_4}{x_8}。\end{array}$

4 结论

在对基于秘密共享对抵抗侧信道攻击的应用及S盒的分组进行研究的前提下，构建了一个低消耗的AES的S盒，并对S盒基于秘密共享进行分组，构造了一个新的S盒。与Nikova的经典方案进行比较，本文方案具有等价的整体结构，对1阶DPA攻击及glitch攻击具有同等级的抵抗能力；同时基于分解法的采用及对具体实现的方程式的优化和改进，本文方案具有较之更为良好的功耗特性和更小的实现面积。但即使进行优化，与传统不抗1阶DPA攻击及glitch攻击的S盒相比，新的S盒在功耗方面仍有所增加，因此在使用时应有一定的取舍。下一步，将继续研究更加优化的方案，并构造可以抵抗高阶DPA攻击的S盒。