| 任炯炯,李航,林键,陈少真.代数次数的求解算法及其在SIMON-like算法中的应用.软件学报,2020,31(8):2453-2464 |
| 代数次数的求解算法及其在SIMON-like算法中的应用 |
| Algorithms for Solving Algebraic Degree and Its Applications to SIMON-like Algorithms |
| 投稿时间：2018-06-08 修订日期：2019-01-06 |
| DOI：10.13328/j.cnki.jos.005881 |
| 中文关键词: 布尔函数 代数次数 SIMON-like算法 CUDA Cube攻击 参数评估 |
| 英文关键词:Boolean function algebraic degree SIMON-like algorithm CUDA Cube attack parameter estimation |
| 基金项目:国家密码发展基金（MMJJ20180203）；数学工程与先进计算国家重点实验室开放基金（2018A03） |
|
| 摘要点击次数: 297 |
| 全文下载次数: 291 |
| 中文摘要: |
| 代数次数作为布尔函数重要的密码学指标，在密码算法的设计与分析中有着重要的应用.主要研究布尔函数代数次数的求解及其在分组密码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. |
|
HTML 下载PDF全文 查看/发表评论 下载PDF阅读器 |
