代数次数的求解算法及其在SIMON-like算法中的应用
作者:
作者单位:

作者简介:

任炯炯(1995-),男,博士,讲师,主要研究领域为对称密码设计与分析;林键(1989-),男,博士生,主要研究领域为信息安全;李航(1995-),男,硕士,主要研究领域为对称密码设计与分析;陈少真(1967-),女,博士,教授,博士生导师,主要研究领域为密码学与信息安全.

通讯作者:

任炯炯,E-mail:jiongjiong_fun@163.com

中图分类号:

基金项目:

国家密码发展基金(MMJJ20180203);数学工程与先进计算国家重点实验室开放基金(2018A03)


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

Fund Project:

National Cryptography Development Fund (MMJJ20180203); Open Fund of State Key Laboratory of Mathematical Engineering and Advanced Computing (2018A03)

  • 摘要
  • |
  • 图/表
  • |
  • 访问统计
  • |
  • 参考文献
  • |
  • 相似文献
  • |
  • 引证文献
  • |
  • 资源附件
  • |
  • 文章评论
    摘要:

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

    Abstract:

    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.

    参考文献
    相似文献
    引证文献
引用本文

任炯炯,李航,林键,陈少真.代数次数的求解算法及其在SIMON-like算法中的应用.软件学报,2020,31(8):2453-2464

复制
分享
文章指标
  • 点击次数:
  • 下载次数:
  • HTML阅读次数:
  • 引用次数:
历史
  • 收稿日期:2018-06-08
  • 最后修改日期:2019-01-06
  • 录用日期:
  • 在线发布日期: 2020-08-12
  • 出版日期: 2020-08-06
您是第位访问者
版权所有:中国科学院软件研究所 京ICP备05046678号-3
地址:北京市海淀区中关村南四街4号,邮政编码:100190
电话:010-62562563 传真:010-62562533 Email:jos@iscas.ac.cn
技术支持:北京勤云科技发展有限公司

京公网安备 11040202500063号