這個 AES SBOX 三元組屬性是什麼？

在使用 AES SBOX 時，我發現有 85 個無序三元組(a, b, c)具有以下特徵：

• a ^ b ^ c = 0
• SBOX[a] ^ SBOX[b] ^ SBOX[c] = SBOX[0]

此外，85*3 = 255三元組的值涵蓋了這個[1, 255]範圍，這很可愛，因為在等式的另一邊挑出了零。

這是一些python展示此屬性的程式碼：

SBOX = [
       99, 124, 119, 123, 242, 107, 111, 197,  48,   1, 103,  43, 254,
      215, 171, 118, 202, 130, 201, 125, 250,  89,  71, 240, 173, 212,
      162, 175, 156, 164, 114, 192, 183, 253, 147,  38,  54,  63, 247,
      204,  52, 165, 229, 241, 113, 216,  49,  21,   4, 199,  35, 195,
       24, 150,   5, 154,   7,  18, 128, 226, 235,  39, 178, 117,   9,
      131,  44,  26,  27, 110,  90, 160,  82,  59, 214, 179,  41, 227,
       47, 132,  83, 209,   0, 237,  32, 252, 177,  91, 106, 203, 190,
       57,  74,  76,  88, 207, 208, 239, 170, 251,  67,  77,  51, 133,
       69, 249,   2, 127,  80,  60, 159, 168,  81, 163,  64, 143, 146,
      157,  56, 245, 188, 182, 218,  33,  16, 255, 243, 210, 205,  12,
       19, 236,  95, 151,  68,  23, 196, 167, 126,  61, 100,  93,  25,
      115,  96, 129,  79, 220,  34,  42, 144, 136,  70, 238, 184,  20,
      222,  94,  11, 219, 224,  50,  58,  10,  73,   6,  36,  92, 194,
      211, 172,  98, 145, 149, 228, 121, 231, 200,  55, 109, 141, 213,
       78, 169, 108,  86, 244, 234, 101, 122, 174,   8, 186, 120,  37,
       46,  28, 166, 180, 198, 232, 221, 116,  31,  75, 189, 139, 138,
      112,  62, 181, 102,  72,   3, 246,  14,  97,  53,  87, 185, 134,
      193,  29, 158, 225, 248, 152,  17, 105, 217, 142, 148, 155,  30,
      135, 233, 206,  85,  40, 223, 140, 161, 137,  13, 191, 230,  66,
      104,  65, 153,  45,  15, 176,  84, 187,  22
      ]

triplets = [(0x01, 0xBC, 0xBD),
           (0x02, 0x61, 0x63),
           (0x03, 0xDC, 0xDF),
           (0x04, 0xC2, 0xC6),
           (0x05, 0x7A, 0x7F),
           (0x06, 0xA3, 0xA5),
           (0x07, 0x19, 0x1E),
           (0x08, 0x97, 0x9F),
           (0x09, 0x22, 0x2B),
           (0x0A, 0xF4, 0xFE),
           (0x0B, 0x43, 0x48),
           (0x0C, 0x51, 0x5D),
           (0x0D, 0xE0, 0xED),
           (0x0E, 0x32, 0x3C),
           (0x0F, 0x81, 0x8E),
           (0x10, 0x25, 0x35),
           (0x11, 0x89, 0x98),
           (0x12, 0x44, 0x56),
           (0x13, 0xEA, 0xF9),
           (0x14, 0xE7, 0xF3),
           (0x15, 0x4F, 0x5A),
           (0x16, 0x86, 0x90),
           (0x17, 0x2C, 0x3B),
           (0x18, 0xA2, 0xBA),
           (0x1A, 0xC1, 0xDB),
           (0x1B, 0x66, 0x7D),
           (0x1C, 0x64, 0x78),
           (0x1D, 0xC5, 0xD8),
           (0x1F, 0xA4, 0xBB),
           (0x20, 0x4A, 0x6A),
           (0x21, 0xD6, 0xF7),
           (0x23, 0x96, 0xB5),
           (0x24, 0x88, 0xAC),
           (0x26, 0xCF, 0xE9),
           (0x27, 0x54, 0x73),
           (0x28, 0xD5, 0xFD),
           (0x29, 0x41, 0x68),
           (0x2A, 0x9E, 0xB4),
           (0x2D, 0x87, 0xAA),
           (0x2E, 0x58, 0x76),
           (0x2F, 0xCB, 0xE4),
           (0x30, 0x5F, 0x6F),
           (0x31, 0xD2, 0xE3),
           (0x33, 0x80, 0xB3),
           (0x34, 0x99, 0xAD),
           (0x36, 0xCC, 0xFA),
           (0x37, 0x46, 0x71),
           (0x38, 0xC8, 0xF0),
           (0x39, 0x4D, 0x74),
           (0x3A, 0x91, 0xAB),
           (0x3D, 0x8F, 0xB2),
           (0x3E, 0x53, 0x6D),
           (0x3F, 0xD1, 0xEE),
           (0x40, 0x94, 0xD4),
           (0x42, 0xB7, 0xF5),
           (0x45, 0xAE, 0xEB),
           (0x47, 0x8A, 0xCD),
           (0x49, 0xB6, 0xFF),
           (0x4B, 0x9C, 0xD7),
           (0x4C, 0x85, 0xC9),
           (0x4E, 0xA8, 0xE6),
           (0x50, 0xB1, 0xE1),
           (0x52, 0x82, 0xD0),
           (0x55, 0x9B, 0xCE),
           (0x57, 0xAF, 0xF8),
           (0x59, 0x93, 0xCA),
           (0x5B, 0xA9, 0xF2),
           (0x5C, 0xB0, 0xEC),
           (0x5E, 0x8D, 0xD3),
           (0x60, 0xBE, 0xDE),
           (0x62, 0xBF, 0xDD),
           (0x65, 0xA1, 0xC4),
           (0x67, 0xA7, 0xC0),
           (0x69, 0x95, 0xFC),
           (0x6B, 0x9D, 0xF6),
           (0x6C, 0x83, 0xEF),
           (0x6E, 0x8C, 0xE2),
           (0x70, 0x8B, 0xFB),
           (0x72, 0x9A, 0xE8),
           (0x75, 0x84, 0xF1),
           (0x77, 0x92, 0xE5),
           (0x79, 0xA0, 0xD9),
           (0x7B, 0xB8, 0xC3),
           (0x7C, 0xA6, 0xDA),
           (0x7E, 0xB9, 0xC7),
           ]

for t in triplets:
 print("%02X ^ %02X ^ %02X" % t, "= %02X" % (t[0] ^ t[1] ^ t[2]), " |  SB[%02X] ^ SB[%02X] ^ SB[%02X]" % t, "= %02X" % (SBOX[t[0]] ^ SBOX[t[1]] ^ SBOX[t[2]]))

我正在尋找任何關於這是來自哪裡的解釋。我熟悉 AES，但無法將這些觀察與我所知道的任何事情聯繫起來。

如果您了解有限域，這相當漂亮，如果您不了解，這將相當令人費解。所有的算術都發生在 $ GF(256) $ , 所以如果你不習慣 $ 1+1=0 $ ， 我道歉。

轉換為純 $ GF(256) $ 算術

回想一下 AES $ S $ -box 可以寫成 $ x\mapsto\ell(x^{254}) $ 在哪裡 $ x^{254} $ 款待 $ x $ 作為一個元素 $ GF(256) $ 和 $ \ell $ 是可逆仿射圖。 $ x^{254} $ 有時被稱為偽逆 $ x\neq 0 $ 我們有 $ x^{254}=1/x $ . 通過操作數的奇偶性、線性和可逆性，我們看到 $$ \ell(x)+\ell(y)+\ell(z)=\ell(0)\iff x+y+z=0. $$ 它遵循 $ (a,b,c) $ 當且僅當兩個方程都形成一個三元組 $$ a+b+c=0 $$ 和 $$ \frac1a+\frac1b+\frac1c=0 $$ 堅持 $ a $ , $ b $ 和 $ c $ 不同且非零。

求解聯立方程

我們的第一個方程將成立 $ a+b=c $ 所以我們有一個解決方案當且僅當 $$ \frac1a+\frac1b+\frac1{a+b}=0 $$ 對於不同的，非零 $ a $ 和 $ b $ . 我們將這個方程乘以非零量 $ ab(a+b) $ 並看到我們有一個解決方案當且僅 $$ a^2+ab+b^2=0 $$ 對於不同的非零 $ a $ 和 $ b $ . 除以 $ b^2 $ 我們看到我們有一個解決方案當且僅當 $$ \left(\frac ab\right)^2+\frac ab+1=0 $$ 這是真的當且僅當 $ a/b $ 是方程的根 $ x^2+x+1 $ . 這個方程有兩個根 $ GF(256) $ 因為它是定義多項式 $ GF(4) $ 這是一個子欄位 $ GF(256) $ . 在 AES 表示法中，它的根是 0xBC 和 0xBD（我將它們寫為 $ \alpha $ 和 $ \alpha+1 $ ).

三元組的配方

我們現在可以建構所有的三元組。讓 $ a $ 是的任何非零元素 $ GF(256) $ （考慮到我們列表中所有值的出現）。讓 $ b=\alpha a $ 然後讓 $ c=(\alpha+1) a $ . 我們現在有 $$ a+b+c=0 $$ 和 $$ S(a)+S(b)+S(c)=0. $$ 給我們三倍。這給出了 255 個解決方案，但我們已經超過了 3 倍，因為該過程將找到每個三倍三倍。QED。

我對隨機 8 位排列 sbox 進行了一些測試；我發現（在對 10,000 個不同的隨機 sbox 進行計數後）平均有 42.5 個三元組符合標準（0 < a < b < c < 256，a^b^c=0，sbox

$$ a $$^sbox$$ b $$^sbox$$ c $$=sbox$$ 0 $$). 是的，AES sbox 中還有更多；不過數量不是很大…

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