在更大的 GF 中推廣 AES s-box 循環移位
根據維基百科：
https://en.wikipedia.org/wiki/Rijndael_S-box
AES 正在做有趣的事情（在哪裡 $ <<< $ 是循環移位）：
$ s = b \oplus (b \lll 1) \oplus (b \lll 2) \oplus (b \lll 3) \oplus (b \lll 4) $
這等於（ $ \times $ 是乘法 $ GF(2^8) $ ):
$ s = b \times 31 \mod 257 $
這為我的眼睛提供了很多混合。假設我有 128 位 $ x $ 和 $ y $ 我想計算類似的東西：
$ x = y \oplus (y \lll 1) \oplus (y \lll 2) \oplus (y \lll 3) \oplus … \oplus (y \lll 64) $
我可以使用乘法更快地完成嗎 $ GF(2^{128}) \mod 2^{128}+1 $ ? 我不知道這背後的理論，所以我有兩種類型的乘數：
$ 2^{125}-1 $
和
$ 2^{65}-1 $
我認為第二個可能以相同的方式在 $ GF(2^{128}) $ ，這是規則。那麼我可以使用類似的數字嗎？那個號碼是多少？
編輯：看起來文章中有錯誤，並且循環移位可能在其他方向：
$ s = b \oplus (b \ggg 1) \oplus (b \ggg 2) \oplus (b \ggg 3) \oplus (b \ggg 4) $
無論如何，我們可以概括它嗎？在本文件中，沒有關於該步驟的 GF 乘法的相等性：
https://csrc.nist.gov/csrc/media/publications/fips/197/final/documents/fips-197.pdf
好的，左移與右移問題與變數是否由“big-endian”或“little-endian”約定表示，即最低有效位是在左邊還是在右邊有關。
操作：
$$ s = b \oplus (b \lll 1) \oplus (b \lll 2) \oplus (b \lll 3) \oplus (b \lll 4) $$
相當於乘法（其中移位是 $ \times x $ 以下）
$$ s(x)=b(x)(1+x+x^2+x^3+x^4)=b(x)\frac{x^5-1}{x-1} $$ 但由於左移也加倍，讓 $ x=2, $ 要得到 $ s(x)=(2^5-1)b(x). $ 在任何情況下，循環移位都等價於操作 $ \pmod x^n-1 $ 在哪裡 $ n $ 是以位為單位的字長。
你的第二個操作確實相當於乘以 $ 2^{65}-1. $
由於您似乎在數學上足夠有能力，我建議：
完整閱讀 Daemen 和 Rijmen 的文件“AES Proposal”以熟悉這些類型的操作和表示。同一作者還出版*了《Rijndael 的設計》一書。*你正在學習特徵 2 的伽羅瓦域之間的相互作用， $ GF(2^n) $ 和整數環 $ \mathbb{Z}{2^n-1} $ 也可以“分解”成 $ \mathbb{Z}{2^{n/2}-1} \times \mathbb{Z}_{2^{n/2}+1}, $ 什麼時候 $ n $ 甚至。另一個值得關注的地方是 Jim Massey 關於 SAFER-64 設計的文件。更一般地說，數論變換 (NTT) 概括了快速傅里葉變換。
如果你有我上面提到的類型的遞歸分解，你就有了快速的實現。最簡單的這種變換是快速沃爾什-哈達瑪變換中使用的西爾維斯特哈達瑪矩陣，其中 $ n $ 相同矩陣的克羅內克積 $ H_2 $ 用來： $$ H_n =H_2 \otimes H_2 \otimes \cdots \otimes H_2 $$ 和 $$ H_2=\left[\begin{array}{cc} +1 & +1 \ +1 & -1 \end{array} \right]. $$ 因為這是二進制向量空間的傅里葉變換 $ GF(2)^n={0,1}^n $ 等價地，上面的 Hadamard 矩陣的行是加法群的群特徵 $ (\mathbb{GF(2)^n},\oplus) $ 這一切都說得通。
總之，祝閱讀愉快。