代数次数的求解算法及其在SIMON-like算法中的应用-任炯炯，李航，林键，陈少真.pdf

上善若水

165

12页

0次

2022-05-24

免费下载

软件学报 ISSN 1000-9825, CODEN RUXUEW E-mail: jos@iscas.ac.cn

Journal of Software,2020,31(8):2453−2464 [doi: 10.13328/j.cnki.jos.005881] http://www.jos.org.cn

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

∗

任炯炯

1,2

李

航

1,2

林

键

1,2

陈少真

1,2

(战略支援部队信息工程大学,河南郑州 450001)

(数学工程与先进计算国家重点实验室,河南郑州 450001)

通讯作者: 任炯炯, E-mail: jiongjiong_fun@163.com

摘要: 代数次数作为布尔函数重要的密码学指标,在密码算法的设计与分析中有着重要的应用.主要研究布尔

函数代数次数的求解及其在分组密码 SIMON-like 算法中的应用.首先,在利用真值表求解代数正规型算法的基础上

建立了基于 CUDA 的并行求解架构,协同利用 CPU 和 GPU 的计算资源,极大地缩短了求解代数次数的时间,在较短

的时间内求解了 SIMON32 算法和 SIMECK32 算法任意轮数的代数正规型和代数次数;其次,在 Cube 攻击理论的基

础上,根据代数次数和超多项式取值之间的关系,设计了估计代数次数的概率算法,估计了一般 SIMON-like 算法布

尔函数的代数次数;最后,从布尔函数代数次数的角度出发,给出了 SIMON-like 算法在选择不同循环移位参数表现

的差异性,进而给出循环移位参数的选取依据.实验结果表明,SIMON 算法在原始参数下,达到最大代数次数所需的

轮数最短,原始参数具有更高的安全性.

关键词: 布尔函数;代数次数;SIMON-like 算法;CUDA;Cube 攻击;参数评估

中图法分类号: TP309

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

2453−2464. http ://www.jos.org.cn/1000-9825/5881.htm

英文引用格式: Ren JJ, Li H, Lin J, Chen SZ. Algorithms for solving algebraic degree and its applications to SIMON-like

algorithms. Ruan Jian Xue Bao/Journal of Software, 2020,31(8):2453−2464 (in Chinese). http://www.jos.org.cn/1000-9825/5881.

htm

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

REN Jiong-Jion g

1,2

, LI Hang

1,2

, LIN Jian

1,2

, CHEN Shao-Zhen

1,2

(PLA Strategic Support Force Information Engineering University, Zhengzhou 450001, China)

(State Key Laboratory of Mathematical Engineering and Advanced Computing, Zhengzhou 450001, China)

Abstra ct : 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 construct ed. The model uses th e CPU and GPU computing r esources collaboratively, which gr eatly 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 d esign choices for cyclic shift parameters are proposed. The experiment shows that SIMON has short est number of

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

Foundation item: National Cryptography Development Fund (MMJJ20180203); Open Fund of State Key Laboratory of

Mathematical Engineering and Advanced Computing (2018A03)

收稿时间: 2018-06-08; 修改时间: 2019-01-06; 采用时间: 2019-08-07

2454

Journal of Software 软件学报 Vol.31, No.8, August 2020

required rounds to reach maximum algebraic degree under original parameters, thus means that the original parameters have higher

security.

Key words: Boolean function; algebraic degree; SIMON-like algorithm; CUDA; Cube attack; parameter estimation

布尔函数作为流密码和分组密码的重要组件,广泛应用于对称密码算法的设计中.一方面,可以作为流密码

算法的非线性组合部分,产生性质好的密钥流序列;另一方面,可以作为描述分组密码非线性组件 S 盒的工具,实

现算法的混淆作用.因此,布尔函数密码学性质的好坏直接关系到密码算法的安全性.随着诸多攻击算法的相继

提出,密码学中的布尔函数理论得到了一系列重要的结果.目前,布尔函数的密码学指标主要有非线性度、相关

免疫度、平衡性、雪崩准则和扩散准则、代数次数和代数免疫度等.文献[1−3]解决了具有最优代数免疫对称布

尔函数的构造问题;文献[4,5 ]基于有限域构造了具有最优代数免疫度、最优代数次数和高非线性度等各种良好

密码学性质的布尔函数;文献[6] 通过设计良好的算法利用计算机搜索得到兼具多种良好密码学性质的弹性布

尔函数.

在布尔函数所有的密码学指标中,代数次数是一个重要的指标.任何一个加密算法理论上均可写成关于输

入的布尔函数,若一个加密算法的布尔函数表达式或其代数次数可知,密码分析者便可利用这一条件进行区分

攻击或密钥恢复攻击.目前,在对称密码的分析中已经出现了很多直接或间接地利用布尔函数表达式及其代数

次数的攻击方法,如代数攻击

[7]

、高阶差分攻击

[8]

、C ube 攻击

[9]

和积分攻击

[10]

等.可见,对布尔函数代数次数的

研究在密码学中具有非常重要的意义.

最直接确定布尔函数代数次数的方法是通过真值表求解布尔函数的代数正规型,但通常情况下,得到一个

密码算法确切的布尔函数代数正规型并不是一件容易的事.事实上,求解代数次数并不需要知道布尔函数所有

的单项式分布,Climent 等人

[11]

根据布尔函数的 support 集推导出其代数正规型的一些性质,提出了计算布尔函

数代数次数的算法.但由于时间复杂度和存储复杂度的限制,无法广泛适用于一般密码算法代数次数的求解.后

来,随着密码分析方法的发展,相继提出了一些代数次数上界的理论估计工具.Boura 等人

[12]

利用 Walsh 谱和高

阶差分性质,给出了适用于迭代密码 Feiste l 和 SPN 型算法代数次数上界的估计.在欧密会 2015 上,Todo

[13]

提出

了一种基于分离特性构造积分区分器的方法.随后,Todo 和 Morii

[14]

将分离特性应用于分组密码算法 SIM ON,

并指出分离特性与布尔函数的推导之间存在着一定的对应关系,所以由分离特性导出指标集的性质在一定程

度上可以反映布尔函数代数次数的上界.在美密会 2017 上,Li u

[15]

提出了数值映射的方法,用来估计非线性反馈

密码算法的代数次数,并成功应用于 Trivium 等密码算法.本文主要研究布尔函数代数次数的求解算法及其在

分组密码 SIMON-like 算法中的应用.

• 首先,在利用真值表求解代数正规型算法的基础上,建立了基于 CUDA 的并行求解架构.我们利用 GPU

加速求解并存储密码算法的真值表,利用 CPU 多核并行技术和快速莫比乌斯变换求解算法的代数正

规型.作为应用,在较短的时间内求解了 SIMON32,SI MECK32 算法任意轮数的代数正规型和代数

次数.

• 其次,在 Cube 攻击理论的基础上,根据代数次数和超多项式取值之间的关系.我们将代数次数的估计问

题转化为超多项式值的求解,设计了估计代数次数的概率算法,估计了一般 SIMON-like 算法轮函数布

尔函数的代数次数.

• 最后,考虑到 SIMON 设计者并未给出轮函数循环移位常数(a,b,c)的选取依据,我们从布尔函数代数次

数的角度出发,对 SIMON-like 算法循环移位常数的选取进行分析,给出参数选择的依据.通过测试其他

参数,发现 SIMON 算法在原始参数下,达到最大代数次数所需的轮数最短,进而说明原始参数具有更

高的安全性.

本文第 1 节描述论文的预备基础知识.第 2 节给出基于 CUDA 并行架构的代数次数的求解模型及其在分

组为 32 比特的密码算法中的应用.第 3 节给出 Cu

be 攻击的理论基础和利用 Cube 变元估计代数次数的概率算

法.第 4 节从布尔函数代数次数的角度出发,对 SIMON-like 算法轮函数循环移位参数的选取进行分析.最后总结

全文.

of 12

免费下载

软件学报计算机技术

关注

评论