对称加密算法中4比特S盒分量布尔函数的暴力求解方法

Present算法中4X4S盒的查找表为：

Present算法中4X4S盒的ANF(代数正规型)为：

在数量众多的对称加密算法(分组加密算法(AES)，密码杂凑算法(SHA3)，序列密码算法(ZUC)，认证加密算法(ASCON)和消息鉴别算法(Keccak-MAC))中，通常使用S盒作为唯一的非线性部件。S盒作为非线性双射变换，它提供了对称加密算法所必须的混淆性，而MDS矩阵等线性变换则供了对称加密算法所必须的扩散性。常见的S盒规模为3比特，4比特，5比特，7比特，8比特和9比特。因为具有‌低计算开销、低存储需求和低功耗‌等优点，其中不大于4比特规模的S盒主要用于轻量级密码算法，例如Present，GIFT，LBLock，Midori，MIBS和LICi等。

有如下密码学指标衡量S盒的安全强度：

（1）差分均匀度(越小越好)

（2）线性度(越小越好)

（3）非线性度(越大越好)

（4）平衡性(必须满足)

（5）代数次数(越大越好)

若f为n元布尔函数，假设f有l项，则f的代数次数为l个单项式中次数的最大值。

S盒的代数次数：

设S(x)=(f0(x)，f1(x)，.....，fm-1(x))：GF(2)n→GF(2)m，则S(x)的代数次数为：

（6）代数项数(越大越好)

若f为n元布尔函数，则f的代数项数为其含有的多项式的个数。

（7）代数免疫度(越小越好)

若f为n元布尔函数，存在布尔函数g≠0使得f•g=0，则称g为f的非零零化子。

记f或者(f+1)的全体非零零化子的集合为Z0，则Z0中所有项中代数次数最小值为f的代数免疫度，记为AI(f)。

（8）相关免疫性(越小越好)

对于n元布尔函数f，如果其n个变元中的c个x与f是统计独立的，也即改变c个x的值而f的取值不变，则f为c阶相关免疫函数。

（9）雪崩效应(越接近越好)

S(x)=(f0(x)，f1(x)，.....，fm-1(x))：GF(2)n→GF(2)m满足雪崩效应，是指改变输入的1比特，大约有一半输出比特改变。

（10）严格雪崩准则(越接近越好)

S(x)=(f0(x)，f1(x)，.....，fm-1(x))：GF(2)n→GF(2)m满足严格雪崩准则，是指改变输入的1比特，每个输出比特改变的概率为1/2。

n x m (n比特输入，m比特输出) 规模的S盒可以表示为向量布尔函数F2n→F2m(m个含有n个变元的布尔函数)，安全性良好的S盒满足的密码学指标之一是其分量布尔函数的代数次数应该尽可能高和项数应该尽可能多(在保证其它指标不变的情况下)。为了直观的判断布尔函数的代数次数和项数，我们需要计算出S盒的m个分量布尔函数的ANF(代数正规型)。

传播安全知识、拓宽行业人脉——看雪讲师团队等你加入！