AES S-盒-如何计算这个场方程的逆？

Question

我想要实现AES算法，而不是基于LUT的S盒，但在实现过程中，我坚持创建“方程的逆”。

在创建S盒的过程中，我使用了以下步骤：

1. ($a_7a_6a_5a_4a_3a_2a_1a_0$)位转换成场方程。
2. 计算场方程模($x^8+ x^4 + x^3 +x+ 1$)的逆。
3. 做仿射变换。
4. 把8位还回去。

在这些步骤中，我没有找到一种方法来计算场方程的逆。

有人能帮我计算Galios场模($x^8+ x^4 + x^3 +x+ 1$)方程的逆吗？

Answer 1

在有限域中，基本上有两种计算逆的主要算法：

• 扩展欧氏算法，也被称为“扩展GCD”。有一个叫做二元GCD的变体。在特征为2的有限域中，加法是按位异或的，二进制GCD更容易实现。
• 费马小定理，它很容易推广:如果字段顺序是$n$ (在您的例子中，$n = 2^8 = 256$)，那么$x$的逆是$x^{n-2}$，因为$x x^{n-2} = x^{n-1} = 1$。这是因为在阶$n$域中，可逆元素是阶$n-1$的乘法组，因此$n-1$的幂运算必须得到乘法中性元素$1$。

如果您已经有一个乘法函数(mul())，则可以在对该函数的相对较少的调用中进行幂运算。例如：

static inline unsigned
invPow(unsigned x)
{
        unsigned x2 = mul(x, x);
        unsigned x3 = mul(x, x2);
        unsigned x6 = mul(x3, x3);
        unsigned x12 = mul(x6, x6);
        unsigned x15 = mul(x12, x3);
        unsigned x30 = mul(x15, x15);
        unsigned x60 = mul(x30, x30);
        unsigned x120 = mul(x60, x60);
        unsigned x126 = mul(x120, x6);
        unsigned x127 = mul(x126, x);
        unsigned x254 = mul(x127, x127);
        return x254;
}

在这个C函数中，变量是从它们的内容中命名的：x60包含$x^{60}$。还请注意，对于$0$：零的输入，invPow()返回$0$，但AES规范正式规定，在计算该操作时，我们使用零作为自己的“逆”。

现在，这很难有效率。您可以先预先计算一个逆表，但这将是一个查找表，您想要避免。

优化的方法是使用一个字段塔:大小为256美元的有限域可以定义为在大小为16美元的有限域上2美元的扩展。这是在Rijmen的简略说明中描述的，并允许在$\mathbb{F}{256}$中通过在$\mathbb{F}{16}$中计算逆的相对简单的任务来计算逆。如果你沿着这条路走下去，你会想读博亚尔和佩拉尔塔的这篇文章，他们用逻辑门来描述目前最著名的俄歇S盒的实现。

深入到逻辑门在软件中是昂贵的，因为这意味着每次S盒调用都要执行100多个布尔操作。然而，如果与咬切一起使用，这种技术可以提供相当大的速度，特别是在具有大型寄存器的机器上.执行是众所周知的，使用128位SSE2寄存器.其他类似的实现，只使用32位或64位寄存器，可以在BearSSL中找到(它还处理倒S盒的情况，这是使用AES/CBC解密所需的；K sper-Schwabe代码只支持前向S盒，因为它们只针对AES/CTR)。