论文部分内容阅读
随着计算机网络的飞速发展和移动通信技术的广泛应用，现代社会已经步入信息时代。人们对信息的安全存储、处理和传输的需求越来越迫切，关于信息安全的研究也日益得到人们的重视。密码学是研究密码系统或者信息安全的学科，它是信息安全领域的基石和各类信息安全技术的基础。现代密码体制分为对称密码体制和非对称密码体制两大类。流密码，又称为序列密码，是对称密码体制的一个重要分支，与基础的数学理论息息相关。现有流密码算法是对一次一密加密体制的模仿，不同的是，它采用的是伪随机的密钥流序列。流密码算法由于其加密速度快、实现代价低等特点，在军事、外交以及保密通信，尤其是无线通讯领域，有着广泛的应用。 对于流密码的设计与分析一直是国际密码学研究的主流。从流密码算法的结构的发展来看，传统的流密码算法大多是基于线性反馈移位寄存器(LFSR)而设计;2004年启动的eSTREAM计划产生了大量的新型流密码体制，它们不再局限于以移位寄存器为主要组件，许多新的设计思路应运而生;FSE2015上提出了一种小状态的流密码设计范例，这种设计完全摆脱了内部状态长度至少是两倍密钥长度的限制。在此背景下，本论文围绕着流密码的安全性分析以及与流密码相关的问题而展开。在流密码的安全性分析方面，本文深入研究了两类小状态流密码算法模型，并对它们分别实施了时间存储数据折中攻击和快速相关攻击。在流密码相关问题方面，本文重点研究了与译码问题密切相关的LPN问题。除此之外，本文对与流密码相关的另外两方面的问题进行了研究，研究对象分别是布尔函数的Walsh变换和伪随机序列。本文取得了以下的研究成果: 研究Sprout-类小状态流密码算法模型的时间存储数据折中攻击。我们扩展了Sprout的设计范例，得到一类流密码算法模型，称之为Sprout-类。该模型的内部状态长度低于两倍密钥长度，并且在密钥流生成(KSG)阶段使用了依赖于密钥的状态更新函数。针对Sprout-类这一模型，我们提出了一种时间存储数据折中攻击。将对模型的分析方法具体应用到Sprout算法中，结果表明，给定29+x+y比特的密钥流和[c·(2x+2y-58)·271-x-y]比特的存储空间，可在时间复杂度279-x-y内攻破Sprout.这种分析方法非常灵活，比之前所有的方法要好。对于精心选择的参数，该方法比Lallemand/Naya-Plasencia在Crypto2015上提出的方法快220，比Maitra等人和Banik的方法快220，比Esgin/Kara的方法快210并且存储空间更少。在缩减的Sprout上的实际试验证实了我们的攻击结果。 研究某类NFSR型小状态流密码算法模型的快速相关攻击。首先，我们定义了一种NFSR型小状态流密码的通用模型，它采用了一种级联结构将几个NFSR连接起来，其内部状态长度低于两倍密钥长度，并且在密钥流生成阶段使用了依赖于密钥的状态更新函数。然后，我们发现当模型中的非线性组合函数具有某种“伪线性”性质时，整个系统可被转化为一个退化的线性过滤的NFSR.进一步地，文中论证了，通过对退化子系统中得到的随机概率线性方程系统使用快速相关攻击，可以用“分而治之”的方式恢复出该模型完整的内部状态。基于这种攻击方法，我们新提出了对该类算法模型的两个设计标准。最后，我们以Fruit为研究案例，描述了对Fruit的密钥恢复攻击。我们的攻击只需要2628次Fruit加密进程和2223比特的密钥流就可以恢复出80比特的密钥，显然这打破了Fruit80比特的安全界的声明。在缩减的Fruit上的实际试验证实了我们的攻击结果。 研究并改进了LPN的求解算法。在此过程中，我们给出了首个求解单列表k-求和问题的算法，然后提出了混合模式的BKW缩减，并说明了如何灵活地计算高斯消去步骤下的矩阵乘积。新产生的LPN的求解算法具有最好的复杂度折中曲线，并威胁到了密码方案所建议的LPN实例的80比特的安全性指标。在缩减的LPN实例上的实际试验证实了我们的分析结果。 研究布尔函数的Walsh变换和它的代数正规型(ANF)之间的关系，并从布尔函数的ANF出发给出了计算小规模的点集处Walsh系数的算法。一方面，我们从迭代的角度分析了Gupta-Sarkar公式，并得到了一个计算布尔函数Walsh系数的递归关系式。另一方面，我们根据递归关系式设计出计算布尔函数在单点或小规模点集处Walsh系数的算法。实验结果表明，对于某些种类的布尔函数，我们的算法比Gupta-Sarkar算法的性能要好，并且能够处理Gupta-Sarkar算法所不能实行的一些情形。另外，对于“变元数多且单项式数少”的布尔函数，新的算法比经典的“快速Walsh变换”会更有优势。 研究伪随机序列的构造及其自相关性质。首先，基于Whiteman广义割圆类，我们构造了一类新的阶数为6的广义割圆序列。然后，针对新构造的广义割圆序列，我们从理论上计算了该类序列的自相关函数，并分析了新构造序列的自相关性质，从而得到了一些自相关函数是4-值的参数的条件。最后，我们也给出了一些使自相关函数取4/5/6-值的具体的参数实例。