替换移位模型中秘密变换的恢复方法研究

发布时间：2017-09-05 14:30

  本文关键词：替换移位模型中秘密变换的恢复方法研究

  更多相关文章： 替换移位模型 Slender集差分密码分析 Slender集线性密码分析 代数攻击 秘密S盒 秘密P盒

【摘要】：SP模型是一种重要的分组密码模型,而替换移位模型是P盒为比特移位变换的SP模型。将S盒或P盒设计为由密钥决定的秘密变换,可以显著提高密码算法的安全强度。本文利用Slender集差分分析和线性分析方法、结合多信息利用技术、最优区分器的构造技术、聚类分析技术、过滤筛选技术以及代数攻击等技术,提出了恢复替换移位模型中秘密变换的新方法,并将这些方法应用到公开S盒的替换移位模型的密钥恢复方法中,给出了恢复密钥的新方法。主要研究成果如下:1.研究了目标概率分布未知的条件下最优区分器的构造问题。给出了近似最优区分器的概念及构造方法,分析了近似最优区分器的区分效果,从理论上证明了对于几乎所有的样本序列,当数据量充分大时,目标分布未知条件下的近似最优区分器与目标分布已知条件下的最优区分器对该样本序列的判决结果一致。说明了当数据量充分大时,近似最优区分器与最优区分器的决策函数的极限是相同的。该区分方法可广泛应用于密码分析领域的区分攻击和密钥恢复攻击。2.改进了替换移位模型中恢复秘密S盒的Slender集差分分析方法。利用多信息利用技术和近似最优区分器的统计方法,给出了收集秘密S盒差分信息泄漏的新方法。该方法能综合利用多个区分特征所包含的信息泄漏,从而构造出了区分能力更强的区分器,降低了攻击所需的数据复杂度。在利用Slender集差分分析方法恢复秘密S盒的过程中,通过将Borghoff等人给出的两个过滤器作为回溯法中的约束条件,给出了正确Slender集的高效构造方法。该方法在获得一个初步分类的基础上就能对秘密S盒进行恢复,从而进一步地降低了数据复杂度。利用该方法,对一个典型的带秘密S盒的替换移位模型算法——Maya算法进行了全轮的攻击,该攻击结果是目前对带秘密S盒的替换移位模型最好的差分攻击结果。3.首次将恢复秘密S盒的差分分析方法应用到公开S盒替换移位模型的密钥恢复方法中,给出了恢复该模型密钥的新方法。在发现区分正确密钥与错误密钥的有效区分特征的基础上,利用近似最优区分方法,进而给出了一个恢复首轮密钥的Slender集差分分析方法。利用该方法,对PRESENT算法和PRINTCIPHER算法进行了攻击。对于PRESENT-80算法和PRINTCIPHER-48算法,该攻击结果是目前最好的差分分析结果。该方法为公开S盒的替换移位模型的差分分析提供了新的攻击思想和攻击技术。4.结合Slender集差分分析方法与代数攻击思想,给出了一个恢复秘密S盒的差分-代数分析的新方法。该方法将S盒的坐标函数作为未知的二元变量,借鉴Slender集差分分析方法的思路构造了两个检测错误方程过滤器,并据此构造出足够多的代数方程,通过求解方程组的方法恢复出了秘密S盒的坐标函数。该方法在时间复杂度上比Slender集差分分析方法更优,为恢复替换移位模型中的秘密S盒提供了一个新的思路与方法。5.给出了Slender集线性分析方法新的原理表述,修正和改进了替换移位模型中恢复秘密S盒的线性分析方法。利用多信息利用技术、聚类分析和加权评估等方法,修正并改进了Borghoff等人提出的Slender集线性分析方法中统计量的构造和分类方法。给出了秘密S盒正确坐标函数应满足的必要条件,并利用回溯法,通过设置相应的过滤器作为约束条件,给出了由含错分类构造出等效秘密S盒的新方法。在第一轮与最后一轮的秘密S盒相同的条件下,给出了由等效S盒恢复正确秘密S盒的快速求解算法。利用该方法对全轮的Maya算法进行了攻击,该攻击结果是目前对带秘密S盒的替换移位模型最好的线性攻击结果。6.首次将恢复秘密S盒的线性分析方法应用到公开S盒的替换移位模型。在发现正确密钥与错误密钥的有效区分特征的基础上,分别给出了恢复首轮密钥和同时恢复前两轮密钥的Slender集线性分析方法,并对PRESENT-80算法进行了实际的攻击。对于12轮的PRESENT-80算法,该方法能以322的数据复杂度,362的时间复杂度及可忽略不计的存储复杂度恢复了算法中的80比特密钥。该结果为公开S盒的替换移位模型提供了新的线性攻击手段和攻击思路。7.研究了替换移位模型中恢复秘密P盒的线性分析方法。当S盒是m比特输入时,对于P盒的重量小于等于m的输入掩码,发现了P盒的输出掩码中仅一块非零与多块非零时具有可区分的Slender集线性信息泄漏,并据此提出了对P盒的分而治之的求解方法。该方法通过对秘密P盒输出的一个m比特块对应的m个输入比特位置的穷举,再借助Slender集线性分析所利用的信息泄漏规律与构造的统计量,得到了判断秘密P盒的输入比特是否移位至下一轮中的同一个S盒的输入位置上的高效区分器,进而给出了恢复等效秘密P盒的新方法。在第一轮与最后一轮的秘密P盒相同的条件下,给出了由等效的秘密P盒确定正确秘密P盒的快速求解方法。利用该方法,对12轮带秘密P盒的替换移位模型进行了攻击,以30.82的已知明文,49.62的时间复杂度及19.282的存储复杂度恢复了秘密P盒,成功率为90%。该结果丰富了替换移位模型中秘密变换的恢复技术。
【关键词】：替换移位模型 Slender集差分密码分析 Slender集线性密码分析 代数攻击 秘密S盒 秘密P盒
【学位授予单位】：解放军信息工程大学
【学位级别】：博士
【学位授予年份】：2015
【分类号】：TN918.4
【目录】：

• 摘要4-6
• Abstract6-15
• 第一章 绪论15-27
• 1.1 研究背景与意义15-17
• 1.2 国内外研究现状17-19
• 1.3 替换移位模型与带秘密变换的替换移位模型介绍19-22
• 1.4 本文的主要工作和结构安排22-25
• 1.4.1 主要工作与创新点22-23
• 1.4.2 论文组织结构23-25
• 1.5 符号约定25
• 1.6 小结25-27
• 第二章 近似最优区分器的构造与分析27-35
• 2.1 区分两个随机变量的区分器介绍27-29
• 2.2 两个随机变量分布全已知时的最优区分器介绍29-31
• 2.3 一个随机变量分布未知时的近似最优区分器的设计与分析31-34
• 2.4 小结34-35
• 第三章 恢复秘密S盒的差分分析方法的改进35-53
• 3.1 Slender集差分分析方法的基本原理介绍35-41
• 3.1.1 Slender集的差分信息泄漏规律介绍36-38
• 3.1.2 检测Slender集正确性的三个过滤器介绍38-41
• 3.2 基于多信息利用的Slender集差分信息收集新方法41-45
• 3.2.1 收集秘密S盒差分信息泄漏的新方法41-43
• 3.2.2 Borghoff方法、2χ -统计方法与新方法收集信息泄漏的效果对比43-45
• 3.3 正确Slender集的高效构造方法45-48
• 3.3.1 满足覆盖过滤器的单个Slender集的构造方法46-47
• 3.3.2 满足领结过滤器的多个Slender集的构造方法47-48
• 3.4 实验结果48-51
• 3.5 小结51-53
• 第四章 公开S盒时恢复密钥的Slender集差分分析方法设计53-67
• 4.1 利用Slender集差分分析方法恢复密钥的朴素方法53-54
• 4.2 基于新的差分信息泄漏规律的密钥恢复方法54-57
• 4.2.1 错误密钥下区分特征的概率分布55-56
• 4.2.2 区分正确密钥与错误密钥的新方法56-57
• 4.3 对PRESENT-80算法的攻击57-62
• 4.3.1 PRESENT密码算法的介绍58-59
• 4.3.2 对PRESENT-80算法的密钥恢复攻击59-62
• 4.4 对PRINTCIPHER-48算法的攻击62-66
• 4.4.1 PRINTCIPHER密码算法的介绍62-64
• 4.4.2 对PRINTCIPHER-48的密钥恢复攻击64-66
• 4.5 小结66-67
• 第五章 恢复秘密S盒的差分-代数分析方法设计67-79
• 5.1 基于Slender集的差分-代数攻击的基本原理68-73
• 5.1.1 基于Slender集的代数方程组的构造方法69-70
• 5.1.2 错误方程的检测方法70-73
• 5.2 基于Slender集的代数方程组的求解方法73-78
• 5.3. 小结78-79
• 第六章 恢复秘密S盒的线性分析方法的修正与改进79-99
• 6.1 Slender集线性分析的基本原理介绍80-87
• 6.2. Slender集线性分析方法的修正与改进87-94
• 6.2.1 Borghoff等人提出的Slender分类方法的缺陷与修正87-88
• 6.2.2 基于多信息利用的Slender集线性分析方法88-92
• 6.2.3 秘密S盒坐标函数的高效构造方法92-94
• 6.3 由等效S盒确定秘密S盒的方法94-96
• 6.4 实验结果96-98
• 6.5 小结98-99
• 第七章 公开S盒时恢复密钥的Slender集线性分析方法设计99-113
• 7.1 恢复密钥的朴素的Slender集线性分析方法99-101
• 7.2 基于新信息泄漏规律的恢复首轮密钥的方法101-105
• 7.3 对PRESENT-80算法的攻击105-106
• 7.4 同时恢复前两轮密钥的方法106-111
• 7.4.1 同时恢复前两轮密钥的基本原理和算法106-110
• 7.4.2 同时恢复前两轮密钥的复杂性分析110-111
• 7.5 小结111-113
• 第八章 恢复秘密P盒的线性分析方法研究113-125
• 8.1 恢复秘密P盒的线性分析方法的基本原理113-118
• 8.1.1 恢复秘密P盒的线性信息泄漏规律114-115
• 8.1.2 由2比特信息泄漏构造4比特信息泄漏的方法115-116
• 8.1.3 恢复等效秘密P盒的新方法116-118
• 8.2 由等效P盒确定正确秘密P盒的快速方法118-123
• 8.2.1 检测等效秘密P盒正确性的过滤方法构造118-119
• 8.2.2 两个过滤器的效率分析119-120
• 8.2.3 恢复等效秘密P盒的快速构造算法120-122
• 8.2.4 恢复等效秘密P盒的时间复杂度分析122-123
• 8.3 实验结果123-124
• 8.4 小结124-125
• 第九章 结束语125-127
• 致谢127-129
• 参考文献129-139
• 作者简历 攻读博士学位期间完成的主要工作139

【相似文献】

中国期刊全文数据库 前10条

1 李贞,吕述望,王永传,王安胜;差分分析中的特征概率计算问题研究[J];电子与信息学报;2003年08期

2 李超;王文玲;胡朋松;;非线性组合序列的差分分析[J];国防科技大学学报;2006年04期

3 王薇;王小云;;CLEFIA-128/192/256的不可能差分分析(英文)[J];软件学报;2009年09期

4 刘连浩;温从剑;;AES的差分-代数攻击[J];计算机工程与应用;2010年05期

5 陈海红;;DES中S盒差分概率表的实现[J];赤峰学院学报(自然科学版);2012年03期

6 张道法,孙林红;线性分析法和差分分析法几个问题的研究[J];通信保密;1997年02期

7 黄建忠,李超;差分序列的性质及应用[J];通信技术;2003年10期

8 孔凡杰;李磊;韩文报;;Kasumi算法FI函数的差分上界分析[J];信息工程大学学报;2011年02期

9 张阳;李雄伟;陈开颜;徐徐;;基于故障注入的硬件木马设计与差分分析[J];华中科技大学学报(自然科学版);2014年04期

10 郑磊;张少武;张中亚;;模2~n数乘运算的差分性质研究[J];电子与信息学报;2011年11期

中国博士学位论文全文数据库 前5条

1 刘国强;替换移位模型中秘密变换的恢复方法研究[D];解放军信息工程大学;2015年

2 杜承航;分组密码算法ARIA的不可能差分分析和中间相遇攻击[D];山东大学;2011年

3 李申华;对称密码算法ARIA和SALSA20的安全性分析[D];山东大学;2008年

4 郭伟;混沌Hash函数安全性分析和构造[D];西南交通大学;2011年

5 张闻宇;高级加密标准的分析[D];山东大学;2007年

中国硕士学位论文全文数据库 前9条

1 温从剑;AES的差分—代数攻击研究[D];中南大学;2009年

2 陈小光;密码体制中差分分析技术研究[D];西安电子科技大学;2009年

3 李延延;Haval及部分新Hash函数的分析[D];山东师范大学;2011年

4 刘亚;分组密码Serpent的差分分析[D];山东大学;2010年

5 孙徐旭;对缩短步数的SHA-2算法的分析[D];上海交通大学;2012年

6 刘爱森;KATAN算法相关密钥的条件差分分析[D];山东大学;2014年

7 李世明;关于Hash算法SHA-1的研究与分析[D];西南大学;2013年

8 马锁堂;第三代移动通信系统中加密与认证算法的分析及仿真[D];电子科技大学;2002年

9 武金梅;对缩短步数的HASH函数算法SHA-256、SHA-512的分析[D];山东大学;2008年

，

本文编号：798561