這個計算 AES S-Box 的程式碼是如何工作的？

這段計算 AES S-Box 的程式碼是如何工作的？我不明白整個計算過程。程式碼附在下面：

function generate(irreducible_poly){
   try{
       p = parseInt(eval(irreducible_poly.replace(/x/g, '10')), 2);
   } catch(err){
       console.log('Irreducible Polynomial invalid');
       return;
   }

   let t = new Uint32Array(256);
   for (let i = 0, x = 1; i < 256; i ++) {
       t[i] = x;
       x ^= (x << 1) ^ ((x >>> 7) * p);
   }

   let Sbox = new Uint32Array(256);
   Sbox[0] = 0x63;
   for (let i = 0; i < 255; i ++) {
       let x = t[255 - i];
       x |= x << 8;
       x ^= (x >> 4) ^ (x >> 5) ^ (x >> 6) ^ (x >> 7);
       Sbox[t[i]] = (x ^ 0x63) & 0xFF;
   }

   return Sbox;
}


// Inverse of Sbox
function inverse(sbox){
   let InvSbox = new Uint32Array(256);
   for (let i =0; i < 256; i++){
       InvSbox[i] = sbox.indexOf(i);
   }

   return InvSbox;
}

大圖：此程式碼需要計算逆模二進制不可約多項式 $ P $ 每個非零二進制多項式的 $ R $ 程度低於 $ P $ . 為此，它選擇了一個生成多項式 $ G=1+x $ , 並製表 $ Q_i=G^i\bmod P $ ，達到所有期望的 $ R $ . 的乘法逆 $ R=Q_i $ 是 $ Q_{255-i} $ .

---

此程式碼評估 AES S-box，它的逆如下：

1. （從 開始的程式碼塊try）它評估p = 0x11b = 283表示二進制多項式 $ P=1+x+x^3+x^4+x^8 $ as an integer：計算此多項式為整數時獲得的值 $ x=2 $ . AES 中使用此通用約定將二進制多項式映射到整數。
2. （從 開始的程式碼塊let t）它計算t[i]表示二進制多項式的表 $ Q_i=(1+x)^i\bmod P $ 按照這個約定。那 $ Q_i $ 根據重複計算 $ Q_{i+1}=Q_i,(1+x)\bmod P $ 和 $ Q_0=1 $ ,根據上述約定翻譯¹為t[i+1] = t[i] ^ ((t[i] << 1) ^ ((t[i] >>> 7) * p))with 。t[0] = 1

例如： $ Q_0 $ 是（二進制）多項式 $ 1 $ ，由 表示t[0] = 1。 $ Q_1=1+x $ ，由 表示t[1] = 3。 $ Q_2=(1+x)^2=1+x^2 $ ，由 表示t[2] = 5。 $ Q_7=(1+x)^7=1+x+x^2+x^3+x^4+x^5+x^6+x^7 $ ，由 表示t[2] = 0xff = 255。 $ Q_8=(1+x)^8\bmod P=(1+x^8)\bmod P=x+x^3+x^4 $ ，由 表示t[8] = 0x1a = 26。 3. （從 開始的程式碼塊let Sbox） $ Q_i=(1+x)^i\bmod P $ 很有用，因為 $ (1+x)^{255}\bmod P=1 $ ， 所以 $ Q_{255-i} $ 是乘法的逆 $ Q_i $ . 和 $ Q_i $ 達到所有非零二進制多項式 $ <8 $ （那是 $ 1+x $ 是發電機）。因此整數t[255 - i]表示整數表示的多項式的乘法逆t[i]。當在循環i中從0到254產生 255 個非零度多項式中的每一個的乘法逆 $ <8 $ . 然後，循環僅應用² AES S-box 的其餘定義中指定的仿射變換。零多項式是特殊情況。

例如：當在循環中時i = 8，表示t[i]``t[8] = 0x1a = 26 $ Q_8=x+x^3+x^4 $ , 和t[255-i](去x, 不相關 $ x $ )t[247] = 0xfd = 253表示多項式 $ Q_{247}=1+x^2+x^3+x^4+x^5+x^6+x^7 $ . 那 $ Q_{247} $ 是乘法的逆 $ Q_8 $ . 根據 AES S-box 的定義，只需將仿射變換² 應用於x，然後將結果設置為Sbox[t[i]] = Sbox[26]。 4. ( function inverse) 逆表是通過搜尋表中的每個條目來計算的。這行得通，但效率低下。InvSbox[i] = sbox.indexOf(i);可以換成直截了當，效率更高InvSbox[sbox[i]] = i;。

---

¹ 理由：在t[i+1] = t[i] ^ ((t[i] << 1) ^ ((t[i] >>> 7) * p))

• t[i]是一個整數 $ [0,2^8) $ 並代表 $ Q_i $ 學位 $ <8 $
• t[i] << 1是一個偶數 $ [0,2^9) $ 並代表 $ Q_i,x $ .
• t[i] >>> 7要麼0要麼1。它是階項的係數 $ x^7 $ 在 $ Q_i $ .
• (t[i] >>> 7) * p相應地是0或0x11b = 283, 表示 $ 0 $ 或者 $ P $ .
• (t[i] << 1) ^ ((t[i] >>> 7) * p)相應地表示 $ (Q_i,x) $ 或者 $ (Q_i,x)+P $ ，並且（通過檢查這兩種情況）是一個整數 $ [0,2^8) $ , 因此表示度的二進制多項式 $ <8 $ ，因此是 $ (Q_i,x)\bmod P $ .
• t[i] ^ ((t[i] << 1) ^ ((t[i] >>> 7) * p))因此是一個整數 $ [0,2^8) $ 並代表 $ Q_i+(Q_i,x)\bmod P)=Q_i,(1+x)\bmod P=Q_{i+1} $ , 度數 $ <8 $ .

在 C 語言中，該表達式的標準可能恆定時間習語將是（基本上使用& -used 而不是乘法）

t[i+1] = t[i] ^ ((t[i] << 1) ^ (p & -(t[i] >> 7)))：。

注意：一些過分熱心的 C 編譯器會錯誤地對 . 吠叫-，讓它們沉默。

---

² 該語句x |= x << 8;複製變數中的位x（表示模逆 $ Q_i $ ) 以便隨後的右移在涉及低 8 位時變得等同於旋轉。該語句x ^= (x >> 4) ^ (x >> 5) ^ (x >> 6) ^ (x >> 7);實現循環矩陣乘法。那麼^ 0x63（代表多項式 $ 1+x+x^5+x^6 $ ) 是常數加法，並& 0xFF保持低 8 位（度數 $ <8 $ )，撤消重複。

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