S盒的可分性质分析

本文使用两种方法对S盒的可分性质进行了分析。主要针对MISTY1，Camellia，AES，SMS4，DES，GIFT，

可分性质[1]是密码学者Todo 在2015 年欧密会上提出来的，它是积分性质的推广。即使分组密码算法具有非双射函数、比特导向结构和低次数函数，也可通过可分性质构造出有效的积分区分器，这弥补了积分性质的缺憾。

可分性质一经提出， 引来无数学者的进一步研究。

Bing SUN 等人[2]证明输入集中差分元素至少有个。

Sun L 等人[3]对可分性质作了进一步的解释，引入了一种新的概念——奇偶性集合[4]，能够以简单的方式制定和表征任何秩序的可分性质。通过考虑奇偶校验集的更多属性来概括可分性质，从而在分组密码上构建区分器。还出现了另外一种新技术，即在独立考虑每个比特和整体考虑左半部和右半部之间实现折衷[5]，这实际上是时间存储复杂度和区分器精度之间的折衷。为了使用常量或子密钥传播AND 和OR运算的基于比特的可分性质，Sun L 等人[6]证明了由输入可分性质推导出已知区域总是包含在从输出可分性质派生的已知区域中。尤瑞英[7]研究了已有的积分区分器在密钥恢复过程中的表现，进一步分析了PRESENT、Serpent 和Noekeon 在积分分析下的安全性。

最初的积分攻击针对的是基于字节或字设计的分组密码。由于基于比特设计的分组密码在应用积分攻击时活跃字节的性质往往被线性变换毁坏，因此Z’aba 等人在FSE2008 上首次提出了基于比特的积分攻击方法[8]。可分性质也是在这样一个基础上推广来的。Todo 等人应用基于比特的可分性质，对全轮MISTY1 进行了积分特征的分析[9]。虽然基于比特的可分性质能找到更准确的积分特征，但它的时间复杂度和数据复杂度都很高。因此，不能将其应用于分组长度超过32 的算法。

S 盒是分组密码算法中的一个重要部件，本质上是一张替换表，对于给定的输入，通过查找该表能够得到相应的输出。S 盒对于整个密码算法的安全性十分重要，对S 盒的可分性质研究也有许多。尤其是对轻量级分组密码算法[10]中的S 盒，如Simon 家族、PRESENT 等算法。可分性质的提出者Todo 也做了对S 盒性质的搜索，主要针对MISTY1 算法，对其中的S 盒及轮函数进行了可分性质分析，发现S7存在一种退化现象，这一现象有利于降低复杂度，因此对S 盒的可分性质研究有实际意义。

本文针对现有分组密码算法中的S 盒，首先使用基于代数次数的方法，得到S 盒的一些可分性质；