代数次数的求解算法及其在SIMON-like算法中的应用

Algorithms for Solving Algebraic Degree and Its Applications to SIMON-like Algorithms

代数次数作为布尔函数重要的密码学指标,在密码算法的设计与分析中有着重要的应用.主要研究布尔函数代数次数的求解及其在分组密码SIMON-like算法中的应用.首先,在利用真值表求解代数正规型算法的基础上建立了基于CUDA的并行求解架构,协同利用CPU和GPU的计算资源,极大地缩短了求解代数次数的时间,在较短的时间内求解了SIMON32算法和SIMECK32算法任意轮数的代数正规型和代数次数;其次,在Cube攻击理论的基础上,根据代数次数和超多项式取值之间的关系,设计了估计代数次数的概率算法,估计了一般SIMON-like算法布尔函数的代数次数;最后,从布尔函数代数次数的角度出发,给出了SIMON-like算法在选择不同循环移位参数表现的差异性,进而给出循环移位参数的选取依据.实验结果表明,SIMON算法在原始参数下,达到最大代数次数所需的轮数最短,原始参数具有更高的安全性.

As an important cryptographic criterion of Boolean function,algebraic degree is widely used in the design and analysis of ciphers.This work mainly studies the algorithm for estimating algebraic degree of Boolean function and its applications to SIMON-like ciphers.Firstly,by analyzing the algorithm of using truth table to solve algebraic normal form,a parallel solution architecture based on CUDA is constructed.The model uses the CPU and GPU computing resources collaboratively,which greatly reduces the time for solving algebraic degree.As applications,the algebraic degree of full round function is solved for SIMON32 and SIMECK32 in a short time.Secondly,based on the Cube attack theory,a probabilistic algorithm for estimating algebraic degree is presented according to the relationship between algebraic degree and superpoly.The algorithm is applied to estimate algebraic degree of general SIMON-like ciphers.Finally,from the algebraic degree point of view,the differences of SIMON-like ciphers selecting different cyclic shift parameters are given,and then some design choices for cyclic shift parameters are proposed.The experiment shows that SIMON has shortest number of required rounds to reach maximum algebraic degree under original parameters,thus means that the original parameters have higher security.