計算有限域的逆問題高飛_(28)GF(28)GF(2^8)AES 的
我知道這個問題在這裡被問死了，但請聽我說完。
我正在學習如何使用 AES 進行加密，在其中一種方法中，我們必須在有限域中計算乘法逆 $ \operatorname{GF}(2^8) $ 使 $ S-box $ .
我學習了有限域及其運算，但是在計算 $ x^7+x+1 $ （十六進制為 83） $ \bmod x^8+x^4+x^3+x+1 $ （AES 標準）。
這是我使用擴展歐幾里得算法的計算：
$$ \begin{align} (x^8+x^4+x^3+x+1) &= (x^7+x+1)(x) + (x^4+x^3+x^2+1)\ (x^7+x+1) &= (x^4+x^3+x^2+1)(x^3+x^2+1) + (x)\ (x^4+x^3+x^2+1) &= (x)(x^3+x^2+x) + 1\ \end{align} $$
現在計算 $ s $ 和 $ t $ 為了$$ (x^8+x^4+x^3+x+1) \cdot s + (x^7+x+1)\cdot t = 1 $$
- 讓 $ a = x^8+x^4+x^3+x+1 $ ,
- $ b = x^7+x+1 $ ,
- $ c = x^4+x^3+x^2+1 $ ,
- $ d = x $
$$ c + d(x^3+x^2+x) = 1 $$
$$ c + (x^3+x^2+x)(b + c(x^3+x^2+1)) = 1 $$
$$ c + (x^3+x^2+x)b + (x^6+x^4+x^3+x^2)c = 1 $$
$$ (x^3+x^2+x)b + (x^6+x^4+x^3+x^2+1)c = 1 $$
$$ (x^3+x^2+x)b + (x^6+x^4+x^3+x^2+1)(a + b(x)) = 1 $$
$$ (x^3+x^2+x)b + (x^6+x^4+x^3+x^2+1)a + (x^7+x^5+x^4+x^3+x)b $$
$$ (x^6+x^4+x^3+x^2+1)a + (x^7+x^5+x^4+x^2)b $$
現在，（c逆） $$ c^{-1} = t* \mod a $$
$$ c^{-1} = t $$
$$ =x^7+x^5+x^4+x^2 $$
這是十六進制 = B4 這不是這個表顯示 http://tratliff.webspace.wheatoncollege.edu/2016_Fall/math202/inclass/sep21_inclass.pdf
倒數應該是 80（十六進制）。當我嘗試不同的值時，我發現擴展歐幾里得算法中兩步或更少的值是正確的，這意味著當它需要超過 2 步時，我得到不同的值當然我可能只是在這裡弄錯了，但這就是我知道。
Ps：-我現在正在嘗試解決這個謎團 3 天，因此感謝您的幫助，謝謝
讓 $ g(x) = (x^8+x^4+x^3+x+1) $ 和 $ p(x) = (x^7+x+1) $
GCD 是正確的 $ 1 $ 作為最後一個非零餘數。
$$ \begin{align} (x^8+x^4+x^3+x+1) &= (x^7+x+1)(x) + \color{blue}{(x^4+x^3+x^2+1)}\ (x^7+x+1) &= (x^3+x^2+1)\color{blue}{(x^4+x^3+x^2+1)} + \color{red}{(x)}\ (x^4+x^3+x^2+1) &= (x^3+x^2+x)\color{red}{(x)} + 1\ \end{align} $$
現在收集回來找到Bézout的身份 $$ a(x)g(x) + b(x)p(x) = d(x) $$在哪裡 $ d(x) $ 是個 $ \gcd(p(x),g(x)) $
我們想保持 $ g(x) $ 和 $ p(x) $
從最後一個方程開始（最後一個具有非零餘數的方程）
$$ (x^4+x^3+x^2+1) = (x^3+x^2+x) \color{red}{(x)} + 1 $$ 更改為（在 $ GF(2) $ 我們有 $ -1=1 $ )
$$ 1 = (x^4+x^3+x^2+1) + (x^3+x^2+x) \color{red}{(x)} $$
現在替代 $ \color{red}{(x)} $ 從上一個
$$ (x^7+x+1) = (x^3+x^2+1)\color{blue}{(x^4+x^3+x^2+1)} + \color{red}{(x)} $$
那是
$$ \color{red}{(x)} = p(x) + (x^3+x^2+1)\color{blue}{(x^4+x^3+x^2+1)} $$
現在替代
$$ \begin{align} 1 &= \color{blue}{(x^4+x^3+x^2+1)}) + (x^3+x^2+x)\big[(p(x) + (x^3+x^2+1)\color{blue}{(x^4+x^3+x^2+1)}\big]\ 1 &= \color{blue}{(x^4+x^3+x^2+1)}) + (x^3+x^2+x)p(x) + (x^6 + x^2 + x)\color{blue}{(x^4+x^3+x^2+1)})\ 1 &= (x^3+x^2+x)p(x) + (x^6 + x^2 + x +1)\color{blue}{(x^4+x^3+x^2+1)})\ \end{align} $$
現在替代 $ \color{blue}{(x^4+x^3+x^2+1)} $ 從第一個方程
$$ g(x) = p(x)(x) + \color{blue}{(x^4+x^3+x^2+1)} $$
$$ \color{blue}{(x^4+x^3+x^2+1)} = p(x)(x) + g(x) $$
$$ \begin{align} 1 &= (x^3+x^2+x)p(x) + (x^6 + x^2 + x +1) \big[p(x)(x) + g(x)\big]\ 1 &= (x^3+x^2+x)p(x) + (x^7 + x^3 + x^2 + x) p(x) + (x^6 + x^2 + x+1) g(x))\ 1 &= (x^7 ) p(x) + (x^6 + x^2 + x) g(x))\ \end{align} $$
現在那個模 $ g(x) $ 雙方的
$$ 1 = (x^7 ) p(x) $$這意味著 $ p(x)^{-1} = x^7 $
**注意：**對於欄位計算，我使用瞭如下的 Sagemath 程式碼，這可用於 AES 計算。
#Base field R.<y> = PolynomialRing(GF(2), 'y') #Defining polynomial G = y^8+y^4+y^3+y+1 #The field extension S.<x> = QuotientRing(R, R.ideal(G)) S.is_field() #this is zero X = x^8+x^4+x^3+x+1 print(X) #GCD print(X.gcd(x^7+x+1)) #to find and inverse use the 1/ 1/(x^7+x+1) #field calculations (x^3+x^2+1)* (x^4+x^3+x^2+1) + (x)