S盒NPNP等价匹配算法
NPNP Equivalence Matching Algorithm for S-Boxes
贾皓珑 1曾骁 1张菊玲 2杨国武1
作者信息
- 1. 电子科技大学计算机科学与工程学院,成都 611731
- 2. 新疆财经大学网络空间安全学院,乌鲁木齐 830000
- 折叠
摘要
根据S盒和布尔函数的相关性,S盒可以看作向量布尔函数.本文在基于布尔函数的NP等价匹配算法的基础上,设计了一个基于深度优先搜索的S盒NPNP等价匹配算法,用于判断两个不同的S盒是否NPNP等价,若等价则同时计算出NPNP变换方式.此算法的深度优先搜索结构基于树,且在进入深度优先搜索之前根据规则仅生成了部分可能存在解的路径,并在计算过程中实时判断以当前结点为新起点的剩余路径是否可能存在解,若不存在就直接剪枝并回溯避免了继续计算的时间开销,故其时间复杂度取决于树结点的个数.不同于仿射变换,本文提出的算法对于判断非可逆S盒是否NPNP等价的计算复杂度与判断可逆S盒是否NPNP等价的计算复杂度一致.实验方面,本文使用现在各个密码算法中常用的S盒进行实验,实验结果证实了本文方法的有效性,且计算过程远远优于直接搜索.
Abstract
According to the correlation between S-boxes and Boolean functions,S-boxes can be re-garded as vector Boolean functions.Based on the method of Boolean NP matching,an algorithm based on depth-first search is proposed to determine whether two different S-boxes are NPNP equivalent.If the two S-boxes are equivalent,the corresponding NPNP transformations will be recovered.This searching algorithm is based on the tree structure.Before entering the depth-first search,we eliminate the paths that cannot correspond to solutions according to some necessary conditions.Whenever the algorithm visits a node,it checks whether the remaining path with the current node as the root node has a solution.If not,the algorithm directly prunes this subtree and backtrack to reduce computational cost,so the time complexity depends on the number of visited nodes on the tree.Different from affine transformation,the computational complexities of the algorithm for judging NPNP equivalence are the same regardless whether the S-box is invertible or not.Some experiments are carried out based on the commonly used S-boxes in various cryptographic algorithms,and the results show that the proposed algorithm is effective,and the calculation process is more efficient than direct search.
关键词
S盒NPNP等价匹配/布尔匹配/深度优先搜索/剪枝回溯Key words
S-box NPNP equivalent matching/Boolean matching/depth-first search/prune and backtrack引用本文复制引用
基金项目
国家自然科学基金(62172075)
成都创新科技项目(2021-YF05-02414-GX)
出版年
2024
国家科技期刊平台
NSTL
万方数据