AES s-box – 我如何計算這個場方程的逆？

我想實現 AES 算法，而不是基於 LUT 的 S-box，但我在實現過程中被困在創建“方程的逆”的點上。

在創建 S-box 時，我使用以下步驟：

1. ( $ a_7a_6a_5a_4a_3a_2a_1a_0 $ ) 位轉換為場方程。
2. 計算場方程模( $ x^8 + x^4 + x^3 + x + 1 $ ).
3. 進行仿射變換。
4. 返回 8 位。

在這些步驟中，我沒有找到計算場方程逆的方法。

誰能幫我計算 Galios 場 mod 中的反方程（ $ x^8 + x^4 + x^3 + x + 1 $ )?

在有限域中，基本上有兩種主要的算法來計算逆：

• 擴展歐幾里得算法，也稱為“擴展 GCD” 。有一種稱為Binary 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} $ . 另請注意，invPow()返回 $ 0 $ 對於輸入 $ 0 $ : 零沒有任何逆，但 AES 規范正式表示，在計算該操作時，我們使用零作為它自己的“逆”。

現在這幾乎沒有效率。您可以首先預先計算一個逆表，但這將是一個查找表，您想避免這種情況。

優化是使用場塔：大小的有限場 $ 256 $ 可以定義為度的擴展 $ 2 $ 在有限的大小域上 $ 16 $ . 這在Rijmen 的簡潔說明中進行了描述，並允許在 $ \mathbb{F}{256} $ 通過做計算逆的相對簡單的任務 $ \mathbb{F}{16} $ . 如果你沿著這條路走，你會想閱讀Boyar 和 Peralta 的這篇文章，他們描述了目前最知名的 AES S-box 在邏輯門方面的實現。

進入邏輯門的軟體成本很高，因為這意味著每次 S-box 呼叫都要進行一百多個布爾運算。但是，如果與位切片一起使用，此類技術可提供相當大的加速，尤其是在具有大寄存器的機器上。Käsper -Schwabe 實現是眾所周知的，它使用 128 位 SSE2 寄存器。其他類似的實現，僅使用 32 位或 64 位寄存器，可以在BearSSL中找到（它還處理反向 S-box的情況，這是使用 AES/CBC 解密所需的；Käsper-Schwabe 程式碼僅支持前向 S 盒，因為它們只針對 AES/CTR）。

引用自：https://crypto.stackexchange.com/questions/56374