S盒NPNP等价匹配算法

根据S盒和布尔函数的相关性,S盒可以看作向量布尔函数.本文在基于布尔函数的NP等价匹配算法的基础上,设计了一个基于深度优先搜索的S盒NPNP等价匹配算法,用于判断两个不同的S盒是否NPNP等价,若等价则同时计算出NPNP变换方式.此算法的深度优先搜索结构基于树,且在进入深度优先搜索之前根据规则仅生成了部分可能存在解的路径,并在计算过程中实时判断以当前结点为新起点的剩余路径是否可能存在解,若不存在就直接剪枝并回溯避免了继续计算的时间开销,故其时间复杂度取决于树结点的个数.不同于仿射变换,本文提出的算法对于判断非可逆S盒是否NPNP等价的计算复杂度与判断可逆S盒是否NPNP等价的计算复杂度一致.实验方面,本文使用现在各个密码算法中常用的S盒进行实验,实验结果证实了本文方法的有效性,且计算过程远远优于直接搜索.