AES 混合柱階段

我正在學習 AES，但MixColumns 步驟有問題。

我讀過有限域，但我仍然不知道它是如何工作的。

1. 我該如何建構 $ GF(2^8) $ ?
2. 01010011 * 11001010 = 10001110-> 這是我在文本中看到的原始答案。我將兩個數字相乘，然後得到011111101111110. 現在我知道我應該將它與不可約數相除100011011。但我沒有得到真正的答案！
3. 我不知道如何為這樣的部門編寫程式碼。我們實際上是在使用 XOR（據我所知）嗎？

誰能用一個簡單的例子解釋完整的 MixColumns 步驟？

Rijndael 的有限域是什麼？

Rijndaels 有限域是 $ F=\mathrm{GF}(2^8) $ 具有最小多項式 $ f(x)=x^8 + x^4 + x^3 + x + 1 $ . 正式地，我們有 $ F=\mathbb F_2[x] / (f) $ 但不要擔心。那麼這是什麼意思？

嗯，元素 $ F $ 應該被認為是多項式 $ \mathbb{F}_2 $ ，加上最小多項式為零的事實。因為係數都是 $ \mathbb F_2 $ , 我們有 $ 1=-1 $ ， 所以：

$$ f(x)=0\iff x^8+x^4+x^3+x+1=0\iff x^8=x^4+x^3+x+1 $$ 將最後一個事實視為“重寫規則”，因為這就是我們要實現它的方式。要添加或相乘兩個數字，您只需像往常一樣將它們相加/相乘，然後減少任何大於 $ x^7 $ 使用重寫規則，以及任何大於 $ 1 $ 使用 $ 2=0 $ .

這與我的程式碼中的字節有什麼關係？

我們在程式時了解的第一個表示是無符號整數的表示。將字節視為元素 $ F $ ，我們讓 $ n^{th} $ 位是係數 $ x^n $ ，從右數。例如， $ 10010011\mapsto x^7+x^4+x+1 $ . 現在我們可以像在有限域中一樣對它們進行數學運算。

那麼，我如何實際添加/減去兩個數字？

只需採用他們的異或。加法與減法相同，因為 $ 1=-1 $ .

如何將兩個數字相乘？

乘以字節 $ a $ 和 $ b $ ，我們首先初始化一個變數來保存產品。檢查最低有效位 $ b $ ， 如果是 $ 1 $ 然後我們添加 $ a $ 到我們的產品（這是你小時候為乘法所做的）。然後，我們轉移 $ a $ 左（即我們將它乘以 $ x $ ） 和 $ b $ 對（除以 $ x $ ）。所以，最低有效位 $ b $ 實際上是係數 $ x $ 從原始值，但是因為我們已經乘以 $ a $ 經過 $ x $ ，我們仍然會得到正確的答案。然而，在我們循環之前，我們應用重寫規則來確保 $ a $ （現在是 $ ax $ ) 無權 $ x $ 比…更棒 $ x^7 $ .

下面是來自wikipedia的範常式式碼，附有我自己的評論。

uint8_t gmul(uint8_t a, uint8_t b) {
   uint8_t p = 0;    /* init product value */
   uint8_t counter;  /* init loop counter */
   uint8_t carry;    /* init carry variable for checking if ax has an x^8 term */
   for (counter = 0; counter < 8; counter++) { /* for each of the 8 bits in b */
       if (b & 1) /* if the least significant bit is set */
           p ^= a; /* add a to p */
       carry = a & 0x80;  /* Set carry to the x^7 term of a */
       a <<= 1;           /* Shift a left 1, turning a into a*x */
       if (carry)         /* if ax should have had an x^8 term (x^7*x=x^8) */
                 /* Using rewrite rule, turn x^8 into x^4+x^3+x+1
                                                         =00011011=0x001B  */
           a ^= 0x001B; /* Add this on to a, so a now stores ax */
       b >>= 1;  /* right shift b, so the least significant bit is coef of x */
   }   /* end loop, and since b=b/x, a=ax; loop will now add on a*x if required */
   return p;  /* finally, return the product */
}

剛剛寫下這些註釋後，可能更容易將進位變數視為ax_has_xxxxxxxx_term

乘法工作範例： $ m=01010011,n=00011010 $ . 計算 $ m*n $

初始化 $ a:=m=01010011 $ , $ b:=n=00011010 $ 和 $ p:=0 $ .

最後一點 $ b $ 未設置，所以我們不添加 $ a $ 到 $ p $ .

現在，我們設置 $ a:=m*x=10100110 $ 和 $ b:=(n>>1)=00001101 $ . $ a $ 適合 $ 8 $ 位（沒有進位）所以這個迭代完成了。

最後一點 $ b $ 已設置，所以設置 $ p:=p+a=10100110 $ .

放 $ a:=ax=mx^2=01001100 $ 攜帶 $ 1 $ ; $ b:=(n>>2)=110 $ .

我們不得不攜帶，因為 $ mx^2 $ 有一個任期 $ x^8 $ . 所以，我們把它變成 $ x^4+x^3+x+1 =00011011 $ 使用重寫規則並將其添加到 $ a $ :

$ a := a + 00011011 = 01001100 + 00011011 = 01010111 $

最後一點 $ b $ 沒有設置，所以我們不添加。

放 $ a:=ax=mx^3=(01010111<<1)=10101110 $ 沒有攜帶； $ b=11 $ . 沒有進位，所以這個迭代完成了。

最後一點 $ b $ 已設置，所以 $ p:=p+a=10101110+10100110=00001000 $

放 $ a:=a*x=(10101110<<1)=01011100 $ 攜帶1個； $ b:=b>>1=1 $ .

是進位，所以再次使用重寫規則我們有 $ a := a + 00011011 = 01011100 + 00011011 = 01000111 = m*x^4 $

最後一點 $ b $ 設置，所以 $ p:=p+a=00001000+01000111 = 01001111 $ 自從 $ b:=0 $ 這是最後一次迭代，我們完成了。

解決方案 $ p=01001111 $ .

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