使用 EEA 計算 Rijndael S-box 的乘法逆

我目前正在學習，我被困在我認為很簡單的事情上。在許多學術資料中，他們建議使用擴展歐幾里得算法來計算乘法逆以計算 S-Box，但我找不到正確的解釋如何做到這一點。每種實用的方法都會計算 log+antilog 並使用它。但是我很固執，我想使用EEA！

我從這裡得到了我的算法：https ://www.youtube.com/watch?v=fq6SXByItUI

對於我的計算，我使用了值 0xCA 和 0x53。當我使用 Rijndael 有限域乘法將它們相乘時，我得到 1。所以我知道它們互為逆。但是當我將它們放入 EEA 時，我得到了不同的價值 :(

0x53 = 83
0xCA = 202
0x11B = 283 (Rijndael Plynomial)

283 = 3 * 83 + 43   |   34 = (1) * 283 + (-3) * 83
83 = 2 * 43 + 15   |   15 = (-2) * 283 + (7) * 83
34 = 2 * 15 + 4    |   4 = (5) * 283 + (-17) * 83
15 = 3 * 4 + 3     |   3 = (-17) * 283 + (58) * 83
 4 = 1 * 3 + 1     |   1 = (22) * 283 + (-75) * 83

根據Google計算器，最終結果是正確的。

當我在兩邊都使用模 283 時，我得到：

1 = (-75) * 83 = (283 - 75) * 83 = 208 * 83

所以我得到了 208 而不是 202！

我對這個過程的實驗實現在這裡。

public static int RijndaelInverse(int a)
{
   int old_s = 0; int s = 1; int new_s = 0;
   int old_t = 0; int t = 0; int new_t = 1;
   int old_r = 0x11B; int r = 0x11B; int new_r = a;

   while (new_r > 0)
   {
       int quotient = r / new_r;

       old_s = s;
       s = new_s;
       new_s = old_s - quotient * s;

       old_t = t;
       t = new_t;
       new_t = old_t - quotient * t;

       old_r = r;
       r = new_r;
       new_r = old_r - quotient * r;
   }

   if (r > 1) return 0;
   if (t < 0) t = t + 0x11B;

   return t;
}

我嘗試用​​ RijndaelMultiply 代替乘法，用 RijndaelSubtract 代替減法，但這破壞了整個算法並給了我瘋狂的值。我認為這是因為該算法需要負值才能工作，而且我知道沒有簡單的除法多項式的方法。

有誰知道如何正確使用 EEA 和 Rijndael 有限域？

---

$$ EDIT $$工作實施

public static uint RijndaelInverse(uint a)
{
   uint old_s = 0; uint s = 1; uint new_s = 0;
   uint old_t = 0; uint t = 0; uint new_t = 1;
   uint old_r = 0x11B; uint r = 0x11B; uint new_r = a;

   while (new_r > 0)
   {
       var r_msb = (int)Math.Log(r, 2.0);
       var new_r_msb = (int)Math.Log(new_r, 2.0);

       int quotient = r_msb - new_r_msb;

       if (quotient >= 0)
       {
           old_s = s;
           s = new_s;
           new_s = old_s ^ (s << quotient);

           old_t = t;
           t = new_t;
           new_t = old_t ^ (t << quotient);

           old_r = r;
           r = new_r;
           new_r = old_r ^ (r << quotient);
       }
       else
       {
           new_s = s ^ new_s;
           s = s ^ new_s;
           new_s = s ^ new_s;

           new_t = t ^ new_t;
           t = t ^ new_t;
           new_t = t ^ new_t;

           new_r = r ^ new_r;
           r = r ^ new_r;
           new_r = r ^ new_r;
       }
   }

   if (r > 1) return 0;

   if (t > 0xFF) t ^= 0x11B;

   return t;
}

要在有限域上執行 EEA，您不能使用整數環中的操作來執行操作（並且它們在域中也不是完全相同的操作，因為您使用的是位向量，而不是欄位元素）。尤其：

• 當您進行“加法”時，您需要像在偶數特徵欄位中一樣執行加法（也就是說，您實際上是進行異或）。
• “減法”實際上與“加法”相同，因此您也可以使用異或。是的; 加法和減法是一回事；我們已經不在堪薩斯了。
• “乘法運算”實際上是一個位移，所以我們會有類似的東西：

new_r = old_r ^ (r << quotient);

你想要的是 (r << quotient) 取消 old_r 的 msbit; 為了完成這項工作，您的“除法”操作需要有效地計算 r 需要向左移動多遠，以便異或將抵消 msbit（從而減小 r 的大小）。

• 底部的測試（如果t超出範圍）看起來不同。事實證明（通過上述更改）t永遠不會是負面的；它可能大於 255

可以使擴展歐幾里得算法起作用。另一方面，我很難看到它是這項工作的最佳算法的情況。它幾乎沒有簡單的表格查找那麼快，而且它甚至沒有輕微的側通道阻力。

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