计算GF(2^8)中系数多项式的模逆。(AES)

Question

AES在GF(2^8)中使用具有系数的下列多项式：

a(x) = {03}x^3 + {01}x^2 + {01}x + {02}

这个多项式mod x^4 + 1的逆是：

a'(x) = {0b}x^3 + {0d}x^2 + {09}x + {0e}

但是，如何计算GF(2^8)中系数的多项式的逆？我已经找到了一个部分的这里的工作示例，但是我不能计算出正确的结果，我也不知道我哪里出错了。

旁白:我用十六进制表示法来表示系数，这些系数本身就是GF(2)中系数的多项式。例如：

{03} = {00000011} = x + 1
{01} = {00000001} = 1
{01} = {00000001} = 1
{02} = {00000010} = x

{0b} = {00001011} = x^3 + x + 1
{0d} = {00001101} = x^3 + x^2 + 1
{09} = {00001001} = x^3 + 1
{0e} = {00001001} = x^3 + 1

GF(2^8)的这些元素被约化为模x^8 + x^4 + x^3 + x + 1 (不可约多项式)。

我尝试用扩展的欧几里德算法来寻找逆，但我没有得到同样的结果。

以下是我到目前为止的计算。

欧氏算法

a(x) = {03}x^3 + {01}x^2 + {01}x + {02}
p(x) = {01}x^4 + {01}

我使用多项式长除法来执行欧几里德算法：

Step 0:
                                   {f6}x   + {52}
                                 --------------------------------------------
{03}x^3 + {01}x^2 + {01}x + {02} | {01}x^4 + {00}x^3 + {00}x^2 + {00}x + {01}
                                   {01}x^4 + {f6}x^3 + {f6}x^2 + {f7}x
                                   ------------------------------------------
                                             {f6}x^3 + {f6}x^2 + {f7}x + {01}
                                             {f6}x^3 + {52}x^2 + {52}x + {a4}
                                             --------------------------------
                                                       {a4}x^2 + {a5}x + {a5}

首先，为了找出“{03}”和“{01}”的“多少次”，我计算出了{03} mod x^8 + x^4 + x^3 + x + 1的逆值，它的计算结果是{f6}。这似乎有效，因为当我将{f6}乘以{03}时，就得到了{01}，它“取消”了第一个项。

减去这两个多项式的步骤似乎很简单。它基本上是两个字节的异或。

接下来，我需要了解{03}进入{f6}的次数。我用长除法找到了{52}，这似乎是因为{52} * {03} = {f6}起作用了。但是，我不认为这种使用长除法总是有效的，因为这个方法恰好没有留下任何余数。

到目前为止，我的结果和这里的一样。

Step 1:
                         {8a}x   + {4f}
                       ----------------------------------
{a4}x^2 + {a5}x + {a5} | {03}x^3 + {01}x^2 + {01}x + {02}
                         {03}x^3 + {89}x^2 + {89}x        
                         --------------------------------
                                   {88}x^2 + {88}x + {02}         
                                   {88}x^2 + {c7}x + {c7}
                                   ----------------------
                                             {4f}x + {c5}            

同样，我需要知道{a4}“进入”{03}的次数。我这样做是通过找到{a4} (也就是{8f})的反义词，所以是{a4} * {8f} = {01}。现在我可以到{01}了，我相信我可以通过把这个逆乘以{03}得到{03}，所以{8f} * {03} = {8a}。因此，根据结合律，我相信{a4} * {8a} = {03}，所以{8a}必须是商中的第一系数。

同样的过程也适用于查找{a4} * {4f} = {88}：

{a4} * {8f} = {01} (find inverse)
{8f} * {88} = {4f} (multiply)
{a4} * {4f} = {88} (check)

这似乎还行。

在再次乘以并减去后，剩下的就是{4f}x + {e5}。然而，我认为这是我错的地方，因为根据这个例子，其余的应该是{4f}x + {a8} (或以十进制79x + 168表示)。我不知道这个{a8}是从哪里来的。

尽管如此，对于欧几里德算法的其余部分，我仍然使用了与上面相同的方法。

Step 2:

               {f3}x   + {ca}  
             ------------------------
{4f}x + {c5} | {a4}x^2 + {a5}x + {a5}
               {a4}x^2 + {bf}x         
               ----------------------
                         {1a}x + {a5}                  
                         {1a}x + {3f}          
                         ------------
                                 {9a}       

{4f} * {09} = {01}  (find inverse)
{09} * {a4} = {f3}  (multiply)

{4f} * {09} = {01}  (find inverse)
{09} * {1a} = {ca}  (multiply)

欧几里德算法的最后一步是：

Step 3:

       {a8}x + {9a}       
     --------------
{9a} | {4f}x + {c5}
       {4f}x                
       ------------
               {c5}                      
               {c5}              
               ----
               {00}       

{9a} * {9f} = {01}  (find inverse)
{9f} * {4f} = {a8}  (multiply)

{9a} * {9f} = {01}  (find inverse)
{9f} * {c5} = {9a}  (multiply)

余数为零，所以我停止欧几里德算法。

扩展欧氏算法

为了找到{03}x^3 + {01}x^2 + {01}x + {02}的逆，我使用上面的商来执行辅助计算(扩展欧几里得算法的“扩展”部分)。

pi = pi-2 - (pi-1 * qi-2)

p0 = {00}

p1 = {01}

p2 = {00} - ({01})*({f6}x + {52})
   = {00} - {f6}x - {52}
   = {f6}x + {52}

p3 = {01} - ({f6}x + {52})*({8a}x + {4f})
   = {01} - ({8f}x^2 + {cc}x + {8c}x + {44})
   = {8f}x^2 + {40}x + {45}

p4 = ({f6}x + {52}) - ({8f}x^2 + {40}x + {45})*({f3}x + {ca})
   = ({f6}x + {52}) - ({09}x^3 + {ea}x^2 + {92}x^2 + {50}x + {80}x + {9f})
   = {09}x^3 + {78}x^2 + {26}x + {cd}

因此，根据我的计算，{03}x^3 + {01}x^2 + {01}x + {02} mod {01}x^4 + {01}的逆是{09}x^3 + {78}x^2 + {26}x + {cd}。

然而，这是不正确的，因为由AES指定的逆应该是{0b}x^3 + {0d}x^2 + {09}x + {0e}。

我意识到这是一个非常有效的例子，但我想知道是否有人能就我可能出错的地方给我提供建议。我使用扩展算法并对GF(2^8)中的系数执行算法(例如加法、乘法)。

我还没有找到一个完整的例子，说明如何计算GF(2^8)中系数在任何地方(只有一个部分一)的多项式的逆，我很想知道它是如何实现的。

Answer 1

更新

你的计算分别是正确的。然而，你在最后得到的多个p4几乎是你要寻找的模逆。

扩展的Eulclid算法的步骤如下：

\begin{array}{rcccc} p & = & 1 \times p & + & 0 \times a\\ a & = & 0 \times p & + & 1 \times a \\ r_0 & = & 1\times p & + &q_0 \times a \\ r_1 & = & q_1 \times p & + &(q_0q_1 + 1) \times a \\ r_2 & = & (q_1q_2 + 1)\times p & + & (q_2(q_0q_1 + 1) + q_0)\times a \end{array}

a前面的系数是多项式p_0，p_1，p_2，p_3和p_4。正如你将看到的，最后一行说

p_4\times a \equiv r_2 \bmod p,

因此，a的逆值实际上是p_4 \times r_2^{-1}，这里的值r_2是{9a}。

在GF(2^8)中，你只是一个模块逆，离完成计算只有一步之遥。

我将提出另一种方法来求多项式的逆。

设p(x) = ax^3 + bx^2 + cx + d是有限域GF(2^8)多项式环中的一次3多项式。我们想找到这样的q(x) = \alpha x^3 + \beta x^2 + \gamma x + \delta，p(x)q(x) \equiv 1 \bmod x^4 + 1。

我们计算乘积p(x)q(x)：

\begin{array}{rcl} p(x)q(x) & = & a\alpha x^6 + (a\beta + \alpha b) x^5 + (a\gamma + b\beta + c\alpha) x^4 + \\ & & (a\delta + b\gamma + c\beta + d\alpha) x^3 + (b\delta + c\gamma + d\beta) x^2 +\\ & & (c\delta + d\gamma) x + d\delta. \end{array}

但是我们想要的是产品mod x^4 + 1，我们有x^4 \equiv -1 \bmod x^4 + 1，更好的是，因为我们在一个特性2的领域，我们有x^4 \equiv 1 \bmod x^4 + 1，所以x^5 \equiv x \bmod x^4 + 1和x^6 \equiv x^2 \bmod x^4 + 1。

所以我们有

\begin{array}{rcl} p(x)q(x) & \equiv & (a\delta + b\gamma + c\beta + d\alpha) x^3 +\\ & & (b\delta + c\gamma + d\beta + a\alpha) x^2 + \\ & & (c\delta + d\gamma + a\beta + b\alpha) x + \\ & & (d\delta + a\gamma + b\beta + c\alpha) \end{array}\mod x^4 + 1

因为我们想要p(x)q(x) \equiv 1 \bmod x^4 + 1，所以我们必须解一个线性方程组：

\left\{\begin{array}{rcl} a\delta + b\gamma + c\beta + d\alpha & = & 0 \\ b\delta + c\gamma + d\beta + a\alpha & = & 0 \\ c\delta + d\gamma + a\beta + b\alpha & = & 0 \\ d\delta + a\gamma + b\beta + c\alpha & = & 1, \end{array}\right.

可以重写为

\begin{bmatrix} a & b & c & d \\ b & c & d & a \\ c & d & a & b \\ d & a & b & c \end{bmatrix}\cdot \begin{bmatrix}\delta\\ \gamma \\ \beta \\ \alpha\end{bmatrix} = \begin{bmatrix}0\\0\\0\\1\end{bmatrix}

若要求多项式的系数\alpha、\beta、\gamma和\delta，只需求矩阵的逆：

\begin{bmatrix}\delta\\ \gamma \\ \beta \\ \alpha\end{bmatrix} = \begin{bmatrix} a & b & c & d \\ b & c & d & a \\ c & d & a & b \\ d & a & b & c \end{bmatrix}^{-1}\cdot\begin{bmatrix}0\\0\\0\\1\end{bmatrix}

事实上，系数将是这个矩阵的最后一列。

您可以使用一种方法来计算逆，例如高斯消去，其中所有的计算都在字段GF(2^8)中。

在这种特殊情况下，保持符号的矩阵是：

\begin{bmatrix} 03 & 01 & 01 & 02 \\ 01 & 01 & 02 & 03 \\ 01 & 02 & 03 & 01 \\ 02 & 03 & 01 & 01 \end{bmatrix}

不管你用哪种方法，我都希望你能通过所有的计算。