随着技术的不断发展进步,物联网的发展被许多国家提上了战略的高度,产业规模不断地扩大,网络应用的范围非常广。为了满足在开放网络上保证信息安全的需求,各种有效手段包括加密和签名等密码技术应运而生,现已成为信息安全的核心技术。加密算法中,分组密码因为其加密速度快,易于标准化等优点被广泛应用于数据的加密和消息的认证中。分组密码是如今许多密码系统的核心要素,是保障信息安全性和完整性的重要技术。密码算法的应用可以追溯到公元前400年,最初始的密码的应用是针对符号的,直到计算机的出现,复杂的密码计算成为可能。1949年Shannon发表的《Communication Theory of Secret System》使得密码学正式成为一门学科。在实际应用中,常采用对称加密的算法或者对称加密和非对称加密相结合的算法。而针对对称密码,根据加密方式的不同又被分为两类,也就是分组密码和流密码。其中分组密码是如今许多密码系统的核心要素,是保障信息安全性和完整性的重要技术。分组密码的研究包含了设计准则,工作模块,安全性分析,快速实现和评估等方面。其中分组密码的设计和分析是一对互相依存的矛盾体,分组密码的设计给分析提供了对象和考验,而分组密码的分析给分组密码的设计提供了新的思路,这两个方面互相促进,共同推动了分组密码的不断发展。如今Feistel结构和SPN结构是分组密码算法的主要结构,它们被大量应用在分组密码算法设计中,因此对这些结构的加密算法分析有较高的理论和实践意义。最早的分组密码研究主要是围绕着DES类的算法展开的,1990年1993年分别提出了差分密码分析和线性密码分析的方法和针对DES密码的分析结果,这两种方法如今已经成功应用于几乎所有的分组密码的分析中,逐步发展成为密码分析方法中的两个重要分支,成为分组密码的两种基本分析方式。在此之后,基于这两种密码分析方法的基本思想,又衍生出了一些新的方法,例如截断差分分析,不可能差分分析,多重线性分析,和零相关线性分析等等。线性分析作为最常用的分析方法之一,最早是由Matsui在1993年在Eurocrypt会议上提出来的,线性密码分析是一种已知明文的攻击方法,即攻击者可以获得当前密钥下的明文密文对,它的基本思想是通过寻找明文和密之间的有效线性逼近表达式,将分组密码和随即置换区分开来,在这个基础上进行恢复密钥攻击。随着密码分析的发展,发展出现了各种新的密码分析方式。2009年Hermelin等人将多维线性分析扩展到松井2算法,为之后对加密算法进行多维线性分析提供了可靠的理论依据。之后2012年Bogdanov提出的多维零相关线性分析是多维线性分析的一种,是当前分组密码分析的热点之一。在2019年中国密码学会举行的全国密码算法设计竞赛中,许多新型的分组密码被提出,其中三种新型分组密码被选为本论文的研究对象:由山东大学提出来的Raindrop,该算法共包含3种版本,Raindrop-128-128、Raindrop-128-256以及Raindrop-256-256,均采用两支的Feistel结构,他们分别应用128,256和256比特的轮密钥。轮函数包含S盒（Sbox）、行混合（MixRow）和比特级循环移位（BitRot）三种操作,它们分别是RF64,RF64和RF128,分别对128,128和256比特长度的明文进行操作。其中128bit版本的Raindrop总共有60轮,设计者在算法文档中简单给出了对128-128Raindrop的安全性分析结论:不存在32轮以及以上的有效线性路径和差分路径,不存在13轮以及以上的不可能差分,存在最长的积分区分器是7轮,最长的零相关线性逼近是10轮。冯秀涛等人提出的FBC密码,其以英文Feistel-based Block Cipher的首字母命名。该算法基于两重Feistel结构设计,它支持128比特和256比特明文分组,以及128比特和256比特的主密钥,FBC主要包含三个版本:FBC128-128,FBC128-256和FBC256-256。它的轮函数也包含了子密钥加,列变换和行变换。其中FBC-128-128的加密轮数为48轮,设计者在算法文档中给出了对它的安全性分析指导和结论:在差分分析和线性分析中,32轮时达到了安全界。在不可能差分和零相关线性分析中最大轮数的路径时7轮,而在积分分析中存在8轮的区分器。第三个是孙思维等人设计的Flux密码。它有Flux-128b-128k,Flux-128b-256k,Flux-256b-256k和Flux-128b-128k-128t四种种类,常用到的数据长度是128比特和256比特,它的轮函数采用SPN结构,而构造S-box时用的时Feistel结构。它的轮函数包含了三层操作,它们分别是非线性层S-box,行位移（ShuffleCells）和线性层Mirror。在Flux密码算法中,Flux-128b-128k总共有14轮加密,在算法文档中,设计者给出了对Flux-128b-128k的安全性分析结论:存在5轮的截断差分特征和6轮的线性特征,存在3轮的积分区分器,不可能差分路径和零相关线性路径。本文的研究对象为128比特版本的Raindrop-128-128,FBC-128-128和Flux-128b-128k。为方便起见,在文中用Raindrop,FBC和Flux简称。本论文的主要部分是搜寻三种新提出的分组密码的零相关线性逼近并且进行密钥恢复攻击。关于三种新分组密码Raindrop,FBC和Flux的密码分析,设计者在设计文档中给出了分析的指导方向,并没有给出详细的路径以及密钥恢复的复杂度分析结论。因此本论文是首次对Raindrop,FBC以及Flux分组密码进行零相关线性路径的补充寻找和进行零相关线性密码分析的讨论。同时,已经有研究者针对Raindrop和FBC进行了线性密码分析、差分密码分析和不可能差分密码分析。零相关线性密码分析作为不可能差分密码分析的对偶方法,也是是近年来比较新的密码分析方法,是密码分析的一个研究热点。因此,本文对于Raindrop,FBC和Flux的零相关线性密码分析是对这三种分组密码安全性分析工作的补全,有较大的研究意义。本文首先介绍了有关分组密码的基础知识,包括分组密码的设计原则,一个分组密码应该同时满足既难以破译,也容易实现这两个要求。设计者需要在这两者之间权衡。论文还介绍了分组密码的常见结构,包括SPN结构和Feistel结构,两者的混淆和扩散方式不同。目前出现的大多分组密码都是基于这两种类型,或者是两种结构类型的结合。文章在介绍部分还介绍了分组密码安全性分析的方法,包括分析方法的提出和发展过程,并详细介绍了本论文要用到的零相关线性密码分析的思想和原理。本篇论文的主要工作有:1.通过查阅分组密码Raindrop,FBC和Flux算法的设计文档,归纳和总结了Raindrop,FBC和Flux算法的结构特点和模块原理,绘制了三种新型分组密码的结构图,为之后搜寻分组密码算法的零相关线性逼近做铺垫。2.基于零相关线性密码分析的理论,结合分组密码Raindrop,FBC和Flux的结构特点以及算法加密流程,结合混合线性整数规划的方法,将加密算法操作包含S-box,XOR操作和分支操作等转化为限制条件,将搜寻零相关线性逼近问题转换成求解MILP问题。最后结合混合整数线性规划MILP搜索寻找了Raindrop-128-128的10轮零相关线性路径,FBC-128-128的7轮零相关线性路径和Flux-128-128的3轮零相关线性路径。这是首次对Raindrop,FBC和Flux这三种分组密码算法的零相关线性详细路径的寻找。3.分组密码算法中主要存在三种操作:XOR操作,Branching操作以及可逆函数操作。在这三种操作中线性掩码遵从特定的传播规则,在XOR操作中两个输入掩码和输出掩码是相等的,而在Branching操作中,输入掩码等于输出掩码之和,在可逆函数中,输入掩码和输出掩码同时为0或者不为0。本文建立相应的10轮的Raindrop算法模型,7轮的FBC算法模型和3轮的Flux算法模型。结合上一步搜寻到的零相关线性逼近,手动对零相关线性逼近进行推算和验证。验证结果表明搜寻到的零相关线性逼近是正确的。4.在寻找到的零相关线性逼近的前后分别再添加合适的轮数,通过猜测部分密钥,对明文进行部分加密,和对密文进行部分解密的方式,借由足够的明密文对,分别对15轮的Raindrop,11轮的FBC和5轮的Flux密码算法进行多轮的密钥恢复攻击,分析密钥恢复攻击的复杂度。本文的分析结果说明在特定的约束条件下MILP可以用于搜寻新型分组密码Raindrop,FBC和Flux的零相关线性逼近,通过手动推算证明该线性逼近是正确的,说明MILP方法在自动搜寻路径中有一定的应用前景。此外对密钥恢复算法的分析说明,可获得足够的明密文对的条件下,理论上零相关线性密码分析对于15轮的Raindrop,11轮的FBC和5轮的Flux加密算法是有效的。