分组密码的分析方法及应用研究

论文摘要

分组密码的设计与分析一直是密码学中的热点问题。从数据加密标准DES到高级数据加密标准AES,人们对分组密码的设计理论和分析理论进行了深刻的研究,理论日趋成熟。尽管征集密码标准的美国AES计划和欧洲NESSIE计划早已结束,但人们对分组密码的研究并没有因此而停止。在最近的欧洲ECRYPT计划候选序列密码算法和美国SHA3计划候选HASH函数算法中,人们大量采用了分组密码的设计思想,为了刻画这些算法的安全性,我们必须进一步对分组密码的安全性进行评估。论文首先以CLEFIA算法和SNAKE算法为例,对分组密码算法抗不可能差分密码分析的能力进行了研究。CLEFIA分组算法是Sony公司提出的一个新的分组算法,通过分析算法采用的线性变换的性质,结合“中间相遇”的方法,我们得到了新的9轮不可能差分,利用这些新的不可能差分,文章对12轮、13轮和14轮简化CLEFIA进行了攻击。攻击结果如下:12轮CLEFIA-128的数据复杂度和时间复杂度分别为2111和290;13轮CLEFIA-192的数据复杂度和时间复杂度分别为2112和2158;14轮CLEFIA-256的数据复杂度和时间复杂度分别为2112.3和2248.5。SNAKE算法是由日韩信息安全与加密会议上提出的分组密码算法。通过研究SNAKE算法线性变换的性质,文章得到了算法9轮不可能差分,利用这条不可能差分,我们对10轮、11轮和12轮简化SNAKE进行了攻击,攻击的数据复杂度分别为245、245.5和246.5,时间复杂度可忽略。这些分析结果说明,在设计密码组件的时候,为使算法能够抵抗不可能差分密码分析,必须精心设计算法的线性变换。利用有限域上的多项式理论,对SQUARE攻击的理论基础进行了研究。通过将密文看作明文的多项式函数,文章给出了SQUARE区分器的精确刻画,这使得判断SQUARE区分器存在性问题由以前经验判断转化为理论判断,为寻求密码算法新的区分器作了理论铺垫。利用代数方法,我们重新描述了Rijndael算法3轮SQUARE区分器,并设计了Parrot算法,进一步说明如何用代数方法寻找SQUARE区分器。在此基础上,文章研究了SQUARE攻击对不同结构密码算法的有效性问题。证明了当轮函数可以写成有限域上低次多项式函数时,对Feistel密码的SQUARE攻击可能失效;而对SPN密码而言,只要存在SQUARE区分器,则SQUARE攻击总是有效的。这些结果说明,S盒的选取对算法抗SQUARE攻击的能力是有影响的。在研究SQUARE攻击与其他密码分析方法的联系时,文章得到了一个算法抗插值攻击的必要条件是,这个算法必须抗SQUARE攻击,从而很多密码算法抗插值攻击的能力需要重新评估。利用代数方法,研究了插值攻击和积分攻击的原理,在此基础上,提出了如下高次积分的概念:研究发现,多项式的系数可以通过插值来计算,也可以通过计算函数在全空间上的高次积分得到,由此我们把插值攻击和积分攻击有机联系到一起。我们分析了轮函数代数次数较低的密码算法的安全性,通过分析次高项的系数,从本质上改进了对PURE密码的插值攻击结果,我们的结果显示,轮数≤22的PURE算法是现实可破的:10轮PURE密码的轮密钥可以在几秒内恢复,22轮PURE密码的轮密钥可以在150小时内恢复,这些结果第一次把对PURE密码的攻击从理论转化为现实。由于密码组件的好坏与密码算法的安全性息息相关,因此,论文讨论了非线性函数的设计问题。利用数论方法,我们证明了一类广义T函数的可逆性,进一步研究了该函数的圈性质,使得该函数作为状态转移函数,可以合理地应用到序列密码的设计中。结论如下:当mod 4,且α+ k≡C≡1 mod 2时,f（x） =αx +β（x >>> b） +γ（x >> b） + C mod 2n是单圈函数;为了增加圈长,我们推广了stop-and-go序列中的采样定理。文章还研究了有限域上置换多项式的性质,得到了一类新的置换多项式:当s = 1时,对于任意δ∈F2n,f（x） = (x2k + x +δ)s + x3∈F2n[x]均为置换多项式;当s = 22n-1 + 1,δ= 1时,f（x） = (x2k + x +δ)s + x3∈F2n[x]为置换多项式;文章进一步研究了有限域Fq上二项式的性质,指出,为置换多项式的一个必要条件为,使得判断二项式的置换性变的相对简单。文章最后讨论了密码学组件中不动点与算法安全性之间的联系,给出了一个衡量不动点数目的新指标。在新的衡量指标下,正形置换具有最少的不动点数目。对于具有自逆性质的S盒而言,我们研究了不动点与其他密码学指标的关系,而对于具有自逆性质的n维线性变换,文章指出其不动点的个数至少为2n2。

论文目录

• 摘要
• ABSTRACT
• 第一章 绪论
• 1.1 研究背景和意义
• 1.2 分组密码分析理论的研究现状
• 1.3 分组密码设计理论的研究现状
• 1.4 论文的主要结果和安排
• 第二章 不可能差分密码分析
• 2.1 不可能差分分析的基本原理
• 2.2 对CLEFIA算法的不可能差分分析
• 2.3 对SNAKE算法的不可能差分分析
• 2.4 小结
• 第三章 SQUARE攻击的数学原理
• 3.1 SQUARE攻击的基本原理
• 3.2 SQUARE区分器的数学描述
• 3.3 SQUARE攻击的有效性分析
• 3.4 SQUARE攻击与其他密码攻击方法的联系
• 3.5 小结
• 第四章 改进的插值攻击和高次积分攻击
• 4.1 插值攻击和积分攻击的基本原理
• 4.2 基本概念和数学基础
• 4.3 改进的插值攻击和高次积分攻击
• 4.4 对PURE密码攻击结果
• 4.5 小结
• 第五章 密码组件的构造及不动点性质
• 5.1 数学基础
• 5.2 一类新的单圈函数
• 5.3 置换多项式
• 5.4 密码组件不动点的刻画
• 5.5 小结
• 第六章 结论与展望
• 6.1 本文总结
• 6.2 进一步工作和展望
• 致谢
• 参考文献
• 作者攻读博士期间取得的学术成果