AES S盒
原理
AES的S盒是定义在$GF(2^8)$（不可约多项式$x^8+x^4+x^3+x+1$），其表达式为$S(x) = Ax^{-1}+c$，具体如下：
$$
\begin{equation}
\left(
\begin{array}{c}
s_7 \\
s_6 \\
s_5 \\
s_4 \\
s_3 \\
s_2 \\
s_1 \\
s_0 \\
\end{array}
\right)=
\left(
\begin{array}{cccccccc}
1 & 1 & 1 & 1 & 1 & 0 & 0 & 0\\
0 & 1 & 1 & 1 & 1 & 1 & 0 & 0\\
0 & 0 & 1 & 1 & 1 & 1 & 1 & 0\\
0 & 0 & 0 & 1 & 1 & 1 & 1 & 1\\
1 & 0 & 0 & 0 & 1 & 1 & 1 & 1\\
1 & 1 & 0 & 0 & 0 & 1 & 1 & 1\\
1 & 1 & 1 & 0 & 0 & 0 & 1 & 1\\
1 & 1 & 1 & 1 & 0 & 0 & 0 & 1\\
\end{array}
\right)
\end{equation}\cdot
\left(
\begin{array}{c}
x_7 \\
x_6 \\
x_5 \\
x_4 \\
x_3 \\
x_2 \\
x_1 \\
x_0 \\
\end{array}
\right)+
\left(
\begin{array}{c}
0 \\
1 \\
1 \\
0 \\
0 \\
0 \\
1 \\
1 \\
\end{array}
\right)
$$
该表示是将一个字节（8 bits）看成$GF(2^8)$上的一个元素。将$GF(2^8)$看成向量空间，其上任何一个元素均可由该向量空间的一组基表示。在AES的定义使用多项式基:假设$A$为多项式$x^8+x^4+x^3+x+1$的根，即$A^8+A^4+A^3+A+1=0$。那么任何一个元素$x$可以表示为$x = x_7A^7+x_6A^6+x_5A^5+x_4A^4+x_3A^3+x_2A^2+x_1A+x_0$
生成
下面我们尝试利用pyfinite生成 AES 的 S 盒。
from pyfinite import ffield
gen = 0b100011011
F = ffield.FField(8, gen, useLUT=0) # 这里一定要写useLUT=0，不然会出问题。。。
A = [0b10001111, 0b11000111, 0b11100011, 0b11110001, 0b11111000, 0b01111100, 0b00111110, 0b00011111]
def aes_sbox_gen(x):
'''
输入x，输出S(x)
'''
x_inv = F.Inverse(x)
y = 0
for i, a in enumerate(A):
if(x_inv&(1<<(7-i))):
y ^= a # 若该bit为1，则异或相应列
return y^0x63
sbox = []
for i in range(256):
sbox.append(aes_sbox_gen(i)) # 生成sbox
SM4 S盒
生成
在SM4官方文档中，仅仅给出了S盒的定义。进行学术搜索，发现各个论文上对SM4 S盒的生成方法描述各有不同。比较靠谱的一篇描述为S-box Optimization for SM4 Algorithm，结合GMSSL中关于SM4 bitslice的实现sm4_bs.c，我们可以得出：SM4 S盒同样定义在$GF(2^8)$上。与AES有所不同，该$GF(2^8)$采用的不可约多项式为$x^8+x^7+x^6+x^5+x^4+x^2+1$，生成方式为$S(x) = A(Ax+c)^{-1}+c$，其中：
$$
\begin{equation}
A = \left(
\begin{array}{cccccccc}
1 & 1 & 0 & 1 & 0 & 0 & 1 & 1\\
1 & 1 & 1 & 0 & 1 & 0 & 0 & 1\\
1 & 1 & 1 & 1 & 0 & 1 & 0 & 0\\
0 & 1 & 1 & 1 & 1 & 0 & 1 & 0\\
0 & 0 & 1 & 1 & 1 & 1 & 0 & 1\\
1 & 0 & 0 & 1 & 1 & 1 & 1 & 0\\
0 & 1 & 0 & 0 & 1 & 1 & 1 & 1\\
1 & 0 & 1 & 0 & 0 & 1 & 1 & 1\\
\end{array}
\right),
c = \left(
\begin{array}{c}
1 \\
1 \\
0 \\
1 \\
0 \\
0 \\
1 \\
1 \\
\end{array}
\right)
\end{equation}
$$
SM4的S盒生成也是采用了多项式基的表示，同AES。
from pyfinite import ffield
gen = 0b111110101
F = ffield.FField(8, gen, useLUT=0) # 这里一定要写useLUT=0，不然会出问题。。。
A = [0b11100101, 0b11110010, 0b01111001, 0b10111100, 0b01011110, 0b00101111, 0b10010111, 0b11001011]
def sm4_sbox_gen(x):
'''
输入x，输出S(x)
'''
y = 0
for i, a in enumerate(A):
if(x&(1<<(7-i))):
y ^= a # 若该bit为1，则异或相应列, y=Ax
y ^= 0xd3
y_inv = F.Inverse(y) # (Ax+c)^(-1)
z = 0
for i, a in enumerate(A):
if(y_inv&(1<<(7-i))):
z ^= a # 若该bit为1，则异或相应列, z=A(Ax+c)^(-1)
return z^0xd3
sbox = []
for i in range(256):
sbox.append(sm4_sbox_gen(i)) # 生成sbox
