Sbox 生成原理

Aes 算法的 S 盒是定义在 $GF(2^8)$ 中，使用的不可约多项式为 $x^8+x^4+x^3+x+1$，生成方式为 $S(x)=Ax^{-1}+c$

$A=\left( \begin{array}{l} 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) c=\left( \begin{array}{l} 0 \\ 1 \\ 1 \\ 0 \\ 0 \\ 0 \\ 1 \\ 1 \\ \end{array} \right)$

在 SM4 的官方文档中，仅给出了 Sbox 盒的定义，并未给出生成方法。进行学术搜索后，在论文 Analysis of the SMS4 Block Cipher 中提到，SM4 算法的 S 盒同样定义在 $GF(2^8)$ 中。使用的不可约多项式为 $x^8+x^7+x^6+x^5+x^4+x^2+1$，生成方式为 $S(x)=A(Ax+c)^{-1}+c$

$A=\left( \begin{array}{l} 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}{l} 1 \\ 1 \\ 0 \\ 1 \\ 0 \\ 0 \\ 1 \\ 1 \\ \end{array} \right)$

SM4-SBox 生成方法

伽罗瓦域 $GF(2^8)$ 上的四则运算是基于多项式进行计算的。

加法：多项式对应项系数相加，由于每一项的系数都是在 $GF(2)$ 上进行运算，结果要对 2 取模。表现出来就是异或运算。
减法：在 $GF(2^8)$ 中，加减法最终都是异或运算。
乘法：选取不可约多项式 $x^8+x^7+x^6+x^5+x^4+x^2+1$，当出现大于 $x^8$ 的项时，将 $x^8$ 替换为 $x^7+x^6+x^5+x^4+x^2+1$
除法：除以一个多项式等价于乘它的逆元。

在将上述 Sbox 的计算公式翻译为代码时，加减法可以直接使用异或运算完成，乘除法的计算过程相对麻烦，但由于 $GF(2^8)$ 中除去 0 仅有 255 个多项式，可以打表实现：

BIT gen = 0b11110101;
BIT table[256], arc_table[256], inv_table[256];
void prepare() {
    // 使用生成元 g = x 遍历所有元素
    // 任意多项式 A, B 都可以写为 g^a, g^b 的形式
    table[0] = 1; arc_table[1] = 0;
    for (int i = 1;i < 255; ++i) {
        if (table[i - 1] & 0x80) 
            table[i] = (table[i - 1] << 1) ^ gen;
        else 
            table[i] = table[i - 1] << 1;
        arc_table[table[i]] = i;
    }
    for (int i = 1;i < 256; ++i) {
        // 首先从 g^a -> a
        // 利用 A*B = g^a * g^b = g^(a + b) = 1，定位 B
        BIT k = arc_table[i]; 
        inv_table[i] = table[(255 - k) % 255];
    }
    return ;
}

利用上述 3 个表，我们可以快速实现 $GF(2^8)$ 上的乘除法运算。

之后按照定义将 Sbox 的生成函数写出：

BIT A[] = {0b11100101, 0b11110010, 0b01111001, 0b10111100, 0b01011110, 0b00101111, 0b10010111, 0b11001011};
BIT Ax(BIT x) {
    BIT y = 0;
    for (int i = 0;i < 8; ++i) 
        if (x & (1 << (7 - i)))
            y ^= A[i]; // y = Ax
    return y ^ 0xd3; // return Ax + c
}
BIT sbox_gen(BIT x) {
    // res = A(Ax + c)^-1 + c 
    return Ax(inv_table[Ax(x)]); 
} 
int main() {
    prepare();
    for (int i = 1;i <= 256; ++i)
        printf("0x%02x%c", sbox_gen(i - 1), ",\n"[i % 16 == 0]);
    return 0;
}

运行结果如下：

0xd6,0x90,0xe9,0xfe,0xcc,0xe1,0x3d,0xb7,0x16,0xb6,0x14,0xc2,0x28,0xfb,0x2c,0x05
0x2b,0x67,0x9a,0x76,0x2a,0xbe,0x04,0xc3,0xaa,0x44,0x13,0x26,0x49,0x86,0x06,0x99
0x9c,0x42,0x50,0xf4,0x91,0xef,0x98,0x7a,0x33,0x54,0x0b,0x43,0xed,0xcf,0xac,0x62
0xe4,0xb3,0x1c,0xa9,0xc9,0x08,0xe8,0x95,0x80,0xdf,0x94,0xfa,0x75,0x8f,0x3f,0xa6
0x47,0x07,0xa7,0xfc,0xf3,0x73,0x17,0xba,0x83,0x59,0x3c,0x19,0xe6,0x85,0x4f,0xa8
0x68,0x6b,0x81,0xb2,0x71,0x64,0xda,0x8b,0xf8,0xeb,0x0f,0x4b,0x70,0x56,0x9d,0x35
0x1e,0x24,0x0e,0x5e,0x63,0x58,0xd1,0xa2,0x25,0x22,0x7c,0x3b,0x01,0x21,0x78,0x87
0xd4,0x00,0x46,0x57,0x9f,0xd3,0x27,0x52,0x4c,0x36,0x02,0xe7,0xa0,0xc4,0xc8,0x9e
0xea,0xbf,0x8a,0xd2,0x40,0xc7,0x38,0xb5,0xa3,0xf7,0xf2,0xce,0xf9,0x61,0x15,0xa1
0xe0,0xae,0x5d,0xa4,0x9b,0x34,0x1a,0x55,0xad,0x93,0x32,0x30,0xf5,0x8c,0xb1,0xe3
0x1d,0xf6,0xe2,0x2e,0x82,0x66,0xca,0x60,0xc0,0x29,0x23,0xab,0x0d,0x53,0x4e,0x6f
0xd5,0xdb,0x37,0x45,0xde,0xfd,0x8e,0x2f,0x03,0xff,0x6a,0x72,0x6d,0x6c,0x5b,0x51
0x8d,0x1b,0xaf,0x92,0xbb,0xdd,0xbc,0x7f,0x11,0xd9,0x5c,0x41,0x1f,0x10,0x5a,0xd8
0x0a,0xc1,0x31,0x88,0xa5,0xcd,0x7b,0xbd,0x2d,0x74,0xd0,0x12,0xb8,0xe5,0xb4,0xb0
0x89,0x69,0x97,0x4a,0x0c,0x96,0x77,0x7e,0x65,0xb9,0xf1,0x09,0xc5,0x6e,0xc6,0x84
0x18,0xf0,0x7d,0xec,0x3a,0xdc,0x4d,0x20,0x79,0xee,0x5f,0x3e,0xd7,0xcb,0x39,0x48

其实这样的方案在硬件实现上并无优势，朴素的实现需要将 Sbox 全部存储下来（利用 ROM），需要存储 256 份的信息。利用 $GF(2^8)$ 进行计算时，也同样需要预先打出逆元的表。

当然，这个方法也不是一无是处，如果能找到 $GF(2^8)\to GF((2^4)^2)$ 的对应方案，便可以不利用 ROM 使用纯粹的组合逻辑实现 SM4-Sbox。

这是作者第一次接触到这部分知识点，难免有疏漏或错误的地方，如果有发现还请指出。