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

摘要

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

目录

封面

声明

中文摘要

英文摘要

目录

第一章 绪论

1.1 研究背景与意义

1.2 国内外研究现状

1.3 替换移位模型与带秘密变换的替换移位模型介绍

1.4 本文的主要工作和结构安排

1.5 符号约定

1.6 小结

第二章 近似最优区分器的构造与分析

2.1 区分两个随机变量的区分器介绍

2.2 两个随机变量分布全已知时的最优区分器介绍

2.3 一个随机变量分布未知时的近似最优区分器的设计与分析

2.4 小结

第三章 恢复秘密S盒的差分分析方法的改进

3.1 Slender集差分分析方法的基本原理介绍

3.2 基于多信息利用的Slender集差分信息收集新方法

3.3 正确Slender集的高效构造方法

3.4 实验结果

3.5 小结

第四章 公开S盒时恢复密钥的Slender集差分分析方法设计

4.1 利用Slender集差分分析方法恢复密钥的朴素方法

4.2 基于新的差分信息泄漏规律的密钥恢复方法

4.3 对PRESENT-80算法的攻击

4.4 对PRINTCIPHER-48算法的攻击

4.5 小结

第五章 恢复秘密S盒的差分-代数分析方法设计

5.1 基于Slender集的差分-代数攻击的基本原理

5.2 基于Slender集的代数方程组的求解方法

5.3. 小结

第六章 恢复秘密S盒的线性分析方法的修正与改进

6.1 Slender集线性分析的基本原理介绍

6.2. Slender集线性分析方法的修正与改进

6.3 由等效S盒确定秘密S盒的方法

6.4 实验结果

6.5 小结

第七章 公开S盒时恢复密钥的Slender集线性分析方法设计

7.1 恢复密钥的朴素的Slender集线性分析方法

7.2 基于新信息泄漏规律的恢复首轮密钥的方法

7.3 对PRESENT-80算法的攻击

7.4 同时恢复前两轮密钥的方法

7.5 小结

第八章 恢复秘密P盒的线性分析方法研究

8.1 恢复秘密P盒的线性分析方法的基本原理

8.2 由等效P盒确定正确秘密P盒的快速方法

8.3 实验结果

8.4 小结

第九章 结束语

致谢

参考文献

作者简历 攻读博士学位期间完成的主要工作