如何破解沒有非線性分量的類 AES 分組密碼？
我正在學習關於分組密碼的課程，最近我遇到了這樣一個練習：如果原始 AES 的高度非線性 Sbox 被線性替換替換（見下面的範例），如何嘗試破解密文？
練習的完整文本如下所示：有一個 5120 位文件（40 個 AES 塊），它是通過我在上面描述的 ECB 模式下使用未知密鑰的“修改”AES-256 加密的。攻擊者擁有密文和前4個密文塊對應的前4個明文塊。攻擊者沒有能力生成選擇的明文/密文對。
攻擊者是否有可能恢復明文的未知部分？
這是修改後的 Sbox：
sbox = [142, 163, 232, 197, 255, 210, 153, 180, 2, 47, 100, 73, 115, 94, 21, 56, 156, 177, 250, 215, 237, 192, 139, 166, 16, 61, 118, 91, 97, 76, 7, 42, 87, 122, 49, 28, 38, 11, 64, 109, 219, 246, 189, 144, 170, 135, 204, 225, 69, 104, 35, 14, 52, 25, 82, 127, 201, 228, 175, 130, 184, 149, 222, 243, 15, 34, 105, 68, 126, 83, 24, 53, 131, 174, 229, 200, 242, 223, 148, 185, 29, 48, 123, 86, 108, 65, 10, 39, 145, 188, 247, 218, 224, 205, 134, 171, 214, 251, 176, 157, 167, 138, 193, 236, 90, 119, 60, 17, 43, 6, 77, 96, 196, 233, 162, 143, 181, 152, 211, 254, 72, 101, 46, 3, 57, 20, 95, 114, 240, 221, 150, 187, 129, 172, 231, 202, 124, 81, 26, 55, 13, 32, 107, 70, 226, 207, 132, 169, 147, 190, 245, 216, 110, 67, 8, 37, 31, 50, 121, 84, 41, 4, 79, 98, 88, 117, 62, 19, 165, 136, 195, 238, 212, 249, 178, 159, 59, 22, 93, 112, 74, 103, 44, 1, 183, 154, 209, 252, 198, 235, 160, 141, 113, 92, 23, 58, 0, 45, 102, 75, 253, 208, 155, 182, 140, 161, 234, 199, 99, 78, 5, 40, 18, 63, 116, 89, 239, 194, 137, 164, 158, 179, 248, 213, 168, 133, 206, 227, 217, 244, 191, 146, 36, 9, 66, 111, 85, 120, 51, 30, 186, 151, 220, 241, 203, 230, 173, 128, 54, 27, 80, 125, 71, 106, 33, 12]
由於 sbox 是仿射的，因此您可以查看 $ s(v)=mv+b $ 在哪裡 $ m $ 是一個 8×8 矩陣，並且 $ b $ 和 $ v $ 是一個 8 維向量 $ F_2 $ . 我會告訴你如何找到 $ m $ 和 $ b $ 在 Pari-GP 中。如果不清楚如何使用它與 AES 的描述相結合來創建更大的線性方程並求解，請詢問。
寫 $ \mathbf{0} =(0, 0, 0, 0, 0, 0, 0, 0) $ . 注意 $ s(\mathbf{0}) = b $ , 所以剩下要做的就是找到 $ m $ . 定義
$$ l(v) = s(v) + s(\mathbf{0}) = mv + b + m\mathbf{0}+b=mv + b + b = mv $$ 注意這是一個線性函式：
s(n) = sbox[n+1] \\ pari-gp is 1-indexed l(n) = bitxor(s(n), s(0)) a = 10 b = 37 print( bitxor(l(a),l(b)) == l(bitxor(a,b)) )將輸出 1（在 Pari-GP 中為真）。要找出矩陣是什麼，
m = matrix(8, 8, {j}, {i}, { ei = 1 << (i-1); ej = 1 << (j-1); bitand(s(ei), ej) == ej }) print(m)哪個輸出
[1, 0, 0, 0, 0, 1, 0, 1; 0, 0, 0, 1, 1, 0, 0, 1; 1, 1, 0, 1, 1, 0, 1, 0; 0, 0, 1, 0, 0, 1, 1, 0; 0, 1, 1, 0, 0, 1, 1, 1; 1, 1, 1, 0, 1, 0, 0, 1; 0, 0, 1, 1, 0, 1, 1, 0; 0, 0, 1, 0, 0, 1, 0, 1]請注意，由於索引的工作方式，閱讀起來有點奇怪。sbox 中的第 128 個條目，對應於向量 $ (0, 0, 0, 0, 0, 0, 0, 1)^T $ 是 179，最後一列是 $ (1, 1, 0, 0, 1, 1, 0, 1)^T $ 和
binary(179) = [1, 0, 1, 1, 0, 0, 1, 1]。