密码学之对称加密体系（1）：AES、SM4的 S 盒有限域与复合域算法实现原理

Cryptography

发布日期: 2019-06-17

文章字数: 2.5k

阅读时长: 10 分

阅读次数:

🔥点击进入【硬件安全】社区，查看更多精彩内容🔥

📢 声明：
🥭 作者主页：【摆渡沧桑的CSDN主页】。
⚠️ 未经作者允许，禁止转载。
⚠️ 本文为非盈利性质，目的为个人学习记录及知识分享。因能力受限，存在知识点分析不正确的可能。若您参考本文造成了不良后果，本人不承担相关责任。
⚠️ 若本文所采用图片或相关引用侵犯了您的合法权益，请联系我进行删除。
😄 欢迎大家指出文章错误，欢迎同行与我交流 ~

@[toc]

一、引言

1.1 基于传统查表的S盒实现

本文要讲一下如何实现 AES 和 SM4 的 S 盒实现。
其实，除了我们平时使用查找表实现，如c 语言一个unsigned int Sbox[256] = {…}，verilog一个always case xxx:解决问题。而这种查表实现是S盒最基本的实现方法。
本文主要介绍一种较为复杂的S盒实现，可以将 S 盒的实现，并结合线性变换（AES 的 MixColumn，SM4 的 $L$变换）形成 $8\rightarrow 32$的大表 T-Table 进行加速，例如openssl的查表实现。
因此，我们本文将介绍通过逻辑运算的 S 盒实现方法。

1.2 基于逻辑运算的S盒实现
AES 和 SM4 的 S 盒都是由 $GF(2^8)$ 有限域上（有限域又称为伽罗瓦域）的运算进行生成的。可以直接基于其实现方法，对 S 盒进行计算实现。在 AES 和 SM4 的 S 盒生成公式中，均设计在 $GF(2^8)$ 的求逆运算，该运算比较耗时。有限域中求逆运算可以转化幂运算，例如 AES 的 S 盒可以表达为：
$S(x) = 63 + 05x^{254} + 09x^{253} + F9x^{251} + 25x^{247} + 01x^{223} + B5x^{191} + 8Fx^{127}.$
该运算定义在$GF(2^8)$上，直接实现同样较为复杂。

还有一种方法，是使用布尔函数对 S 盒进行表达，利用布尔函数进行实现。该方法其实可以看作$GF(2)$上的表达。D. Gligoroski(On Deviations of the AES S-box when Represented as Vector Valued Boolean Function)对 AES 的 S 盒进行了分析，得到其布尔函数表达式，例如，其中第0比特可表示为：

由此可以看出，布尔函数非常复杂，直接利用布尔函数表达式也不是一个好的思路。

D.Canright在A Very Compact Rijndael S-box一文中，提出一种实现思路：基于复合域进行实现。文章提出该方法实现在资源有限情况下的该类 S 盒的实现方式，后该方法被用于构造掩码实现（抵抗DPA攻击）和bitslice实现上。本文将对这个方法进行介绍。

二、原理

2.1 基本原理

AES 和 SM4 的 S 盒生成都是基于$GF(2^8)$进行构造的，利用逆运算和仿射变换(affine)。
仿射变换本身就能表示成逻辑运算，我们重点关注求逆运算。
AES 和 SM4 的表达都是基于多项式基，以 AES 的有限域为例，假设$A$为多项式 $x^8+x^4+x^3+x+1$ 的根，即:
$A^8+A^4+A^3+A+1=0$
那么任何一个元素$x$可以表示为 $x = x_7A^7+x_6A^6+x_5A^5+x_4A^4+x_3A^3+x_2A^2+x_1A+x_0$
这种做法是将$GF(2^8)$直接看作$GF(2)$的8次扩域。
我们也可以不这么看，将$GF(2^8)$看成$GF(2^4)$的2次扩域，$GF(2^{4})$可以进一步看作$GF(2^2)$的2次扩域，再进一步$GF(2^2)$可以看作$GF(2)$的2次扩域。
而$GF(2^8)$的求逆运算，可以通过数学表达式，转换为$GF(2^4)$的求逆和一些乘、加操作。
这些操作可以进一步向下转化。下面我们详细说明一下。

$K = GF(q^n)$为$GF(q)$的n次扩域，$\beta$ 为多项式的根，那么多项式基为 $\{ 1,\beta,\beta^2, \ldots, \beta^{n-1} \}$
任何一个元素$x$，可以表示为 $x = x_{n-1}\beta^{n-1}+\ldots+x_1\beta+x_0$
这也是AES 和 SM4 所采用的基表示方式。
此外，除了多项式基以外，域的表达方式还可以使用正规基进行表达，正规基为${\beta, \beta^q, \beta^{q^2}, \ldots, \beta^{q^{n-1}}}$，正规基使用了多项式的全部根。

2.2 $GF(2^8)$的逆

$GF(2^8)$，可以看作$GF(2^4)$的2次扩域，也就是在$GF(2^4)$上寻找一个不可约二次多项式： $r(y) = y^2 + \tau y +\upsilon$
其中，$\tau$ 和 $\upsilon$ 为 $GF(2^4)$ 的元素。
设 $Y$ 为 $r(y)$ 的根，则 $GF(2^8)$ 元素的多项式基为 ${Y, 1}$，正规基为${Y, Y^{16}}$。

#
Canright在文章中讨论了多项式基和正规基两种方式，我们这里只看正规基。对于$GF(2^8)$的元素 $g = \gamma_1 Y^{16} + \gamma_0 Y$
求逆：
$d = \delta_1 Y^{16} + \delta_0 Y$
$\gamma_i$ 和 $\delta_i$ 都是$GF(2^4)$的元素, $gd = 1$，待定系数求解，可得出
$\begin{cases} \delta_1 &= [\gamma_1 \gamma_0 \tau^2 + (\gamma_1^2 + \gamma_0^2)\upsilon]^{-1}\gamma_0 \\ \delta_0 &= [\gamma_1 \gamma_0 \tau^2 + (\gamma_1^2 + \gamma_0^2)\upsilon]^{-1}\gamma_1 \end{cases}\\$
在其文内有详细推导方法。
观察系数，其达到的效果就是，$GF(2^8)$的求逆运算，转化成为$GF(2^4)$的乘法、平方和求逆。

可以选择不可约多项式为 $r(y) = y^2 + y + \upsilon=(y+Y)(y+Y^{16})$
也就是 $\tau$ 取1来降低求解复杂度，这样，对$g = \gamma_1 Y^{16} + \gamma_0 Y$的求逆可简化为如下图：

2.3 $GF(2^4)$的逆

同样，$GF(2^4)$可以看作$GF(2^2)$的二次扩域，也就是在$GF(2^2)$寻找一个不可约二次多项式:
$s(z) = z^2 + Tz + N$
设$Z$ 为该多项式的根，取正规基${Z^4, Z}$。
和$GF(2^8)$计算方法相同，可计算$GF(2^4)$元素 $\upsilon = \Gamma_1 Z^4+\Gamma_0 Z$
求逆：
$\delta = \Delta_1 Z^4 + \Delta_0 Z$
其中$\upsilon\delta=1$,待定系数求解，可得出
$\begin{cases} \Delta_1 &= [\Gamma_1 \Gamma_0 T^2 + (\Gamma_1^2 + \Gamma_0^2)N]^{-1}\Gamma_0 \\ \Delta_0 &= [\Gamma_1 \Gamma_0 T^2 + (\Gamma_1^2 + \Gamma_0^2)N]^{-1}\Gamma_1 \end{cases}\\$
也可以取$T = 1$降低复杂度，那么在$GF(2^4)$求逆运算如下图所示：

2.4 $GF(2^4)$的乘法

在$GF(2^8)$求逆时，也涉及到了$GF(2^4)$的乘法。$GF(2^4)$的乘法$\upsilon\delta = (\Gamma_1 Z^4+\Gamma_0 Z)(\Delta_1 Z^4 + \Delta_0 Z)$可按照如下公式计算：
$\begin{cases} \Phi &= N(\Gamma_1+\Gamma_0)(\Delta_1+\Delta_0) \\ \upsilon\delta&= [\Phi+\Gamma_1\Delta_1]Z^4+[\Phi+\Gamma_0\Delta_0]Z \\ \Phi_1&=\Phi+\Gamma_1\Delta_1 \\ \Phi_0&=\Phi+\Gamma_0\Delta_0 \end{cases}\\$
如下图：

2.5 $GF(2^2)$的逆

进一步，$GF(2^2)$可以看作$GF(2)$的二次扩域，在$GF(2)$上的不可约多项式只有 $t(\omega) = \omega^2+\omega+1$
取正规基${W^2, W}$
则 $\Gamma = g_1W^2+g_0W$
逆为 $\Delta = d_1W^2+d_0W$
其中, $\Gamma\Delta =1$,待定系数求解，可得出
$\begin{cases} d_1 &= g_0 \\ d_0 &= g_1 \end{cases}\\$

2.6 $GF(2^2)$的乘法

$GF(2^2)$的乘法:
$\Gamma\Delta = (g_1W^2+g_0W)(d_1W^2+d_0W)$
计算如下：
$\begin{cases} f &= (g_1+g_0)(d_1+d_0) \\ \upsilon\delta&= [f+g_1d_1]W^2+[f+g_0d_0]W\\ f_1 &=f+g_1d_1\\ f_0 &=f+g_0d_0\\ \end{cases}\\$
如下图：

2.7 其他结论

将$GF(2^8)$进行转化，我们还有一些操作未介绍，包括 $\upsilon\gamma^2$、$N\Gamma^2$ 和 $N\Gamma$。这些值可通过选择不同的 $\upsilon$ 和 $N$ 进行简化。文章详细讨论了选取的方法。
直接给结论：

对于$GF(2^2)$，不可约多项式为 $t(\omega) = \omega^2+\omega+1$
正规基${W^2, W}$

对于$GF(2^4)/GF(2^2)$，不可约多项式为 $s(z) = z^2 + z + N \\ N = W^2$ ，
正规基${Z^4, Z}$，$N(g_1W^2+g_2W)^2 = W^2(g_1W^2+g_2W) = g_1W^2+(g_1+g_0)W$

对于$GF(2^8)/GF(2^4)$，不可约多项式为 $r(y) = y^2 + y +\upsilon \\ \upsilon = N^2Z$
如此: $\upsilon(AZ^4+BZ)^2 = (A+B)^2Z^4+N^2B^2$ 复合域下，实际上是以 $[(b_7w^2 + b_6w)z^4 + (b_5w^2 + b_4w)z]y^{16} + [(b_3w^2 + b_2w)z^4 + (b_1w^2 + b_0w)z]y =\\ b_7w^2z^4y^{16} + b_6wz^4y^{16} + b_5w^2zy^{16} + b_4wzy^{16} + b_3w^2z^4y + b_2wz^4y + b_1w^2zy + b_0wzy$ 表示$GF(2^8)$的一个元素。
而 S 盒的输入是以多项式基表示进行输入的。要利用复合域进行运算，需要将输入表示进行转换。
以线性空间的角度看，这复合域表示相当于是给$GF(2^8)$找了一组新基。两组基有如下关系： $g_7A^7+g_6A^6+g_5A^5+g_4A^4+g_3A^3+g_2A^2+g_1A+g_0 \\= b_7w^2z^4y^{16} + b_6wz^4y^{16} + b_5w^2zy^{16} + b_4wzy^{16} + b_3w^2z^4y + b_2wz^4y + b_1w^2zy + b_0wzy$ 找到$w^2z^4y^{16}$等在多项式基下的表示，形成矩阵X： $\left( \begin{array}{c} g_7\\ g_6 \\ g_5\\ g_4 \\ g_3 \\ g_2\\ g_1 \\ g_0 \end{array} \right) = X \left( \begin{array}{c} b_7\\ b_6 \\ b_5\\ b_4 \\ b_3 \\ b_2\\ b_1 \\ b_0 \end{array} \right)$ 计算$X^{-1}$，乘以多项式基下的表示即可得到复合域基下的表示。
S盒计算完成后，再进行反变换即可。