理解AES_S-box盒生成

一开始，我以为S-box这玩意就是随便找的一个map去做substitution，但仔细研究发现原来这里面数学原理深奥去了。光S-box的生成就很有意思，核心就是求多项式的逆元和访射变化，之后有大量时间再做更深层次的分析，本次对AES中的S-box的生成做一个笔记，学习AES是为了了解它的数学设计思想，为之后理解Number theoretic transform热身。

求乘法逆元

首先，对于S-box是行从00~ff，列也是从00～ff的一个matrix，也就是有限域GF(2^8)的所有element（0～255）

00 01 02 03 04 05 06 07 08 09 0A 0B 0C 0D 0E 0F 
10 11 12 13 14 15 16 17 18 19 1A 1B 1C 1D 1E 1F
20 21 22 23 24 25 26 27 28 29 2A 2B 2C 2D 2E 2F 
30 31 32 33 34 35 36 37 38 39 3A 3B 3C 3D 3E 3F
40 41 42 43 44 45 46 47 48 49 4A 4B 4C 4D 4E 4F 
50 51 52 53 54 55 56 57 58 59 5A 5B 5C 5D 5E 5F
60 61 62 63 64 65 66 67 68 69 6A 6B 6C 6D 6E 6F 
70 71 72 73 74 75 76 77 78 79 7A 7B 7C 7D 7E 7F
80 81 82 83 84 85 86 87 88 89 8A 8B 8C 8D 8E 8F 
90 91 92 93 94 95 96 97 98 99 9A 9B 9C 9D 9E 9F
A0 A1 A2 A3 A4 A5 A6 A7 A8 A9 AA AB AC AD AE AF 
B0 B1 B2 B3 B4 B5 B6 B7 B8 B9 BA BB BC BD BE BF
C0 C1 C2 C3 C4 C5 C6 C7 C8 C9 CA CB CC CD CE CF 
D0 D1 D2 D3 D4 D5 D6 D7 D8 D9 DA DB DC DD DE DF
E0 E1 E2 E3 E4 E5 E6 E7 E8 E9 EA EB EC ED EE EF 
F0 F1 F2 F3 F4 F5 F6 F7 F8 F9 FA FB FC FD FE FF

把每个字节看成一个多项式用来表达它的二进制形式，ai代表第i比特位的值（0或者1）

将矩阵里的所有elements都求它的乘法逆元

00的逆元就是00本身

最重要的是如何计算多项式的乘法逆元，a(x)就是此时的字节，m(x)是一个固定的不可约多项式（因式只有1和它本身）

这里提一句，这个S-box的设计真的给AES带来了很强的扩展性，光m(x)其实就可以扩展使用其他的数来代替，比如下面这些，RJNDAEL选择了0x11b，也就是上述的m(x)多项式，关于这块想更了解的可以看这篇论文Generation of AES S-Boxes with various modulus and additive constant polynomials and testing their randomization

1	11B, 11D, 12B, 12D, 139, 13F, 14D, 15F, 163, 165, 169, 171, 177, 17B, 187, 18B, 18D, 19F, 1A3, 1A9, 1B1, 1BD, 1C3, 1CF, 1D7, 1DD, 1E7, 1F3, 1F5, 1F9.

要求的就是b(x)

a(x) * b(x) = 1 mod m(x)

如何求多项式的乘法逆元呢？这里用到了扩展欧几里得定理

a(x) * b(x) + s(x) * m(x) = 1

这里拿02举例子，02对应的多项式为x，m(x)移到右边可以和右边的1消掉（这里的+是表示异或操作）