密码分析是一门研究利用特殊手段解密未知密码信息的学科。其中,差分分析是一种通过选择明文进行密码分析的攻击（分析）方式。日本密码学家Matsui（松井）于1995年发明了 Matsui算法,该算法长期以来都是差分分析自动化的主要方法——其主要贡献是攻破了 1 6轮的DES加密算法。相较于MILP（混合整数线性规划）等依托数学分析工具的自动化搜索方式,Matsui算法更加注重于加密算法本身的结构特性,因此可以得到更高的正确率。从具体步骤来讲,Matsui算法首先预估每轮的大致概率作为分支界定条件的经验值,然后从经过计算的实际值推导出最后一轮的最大差分概率,并更新经验值。换句话说,第n轮的实际差分特性概率要依据前n-1轮得到的实际最大差分特征概率。每一轮经验值的更新,将被用于提高分支界定条件,以减少穷举分支可能性的次数。MILP则是对加密算法核心线性和非线性部分进行数学建模,依据线性规划模型的约束条件,对分支进行筛选。上述两种方法最大的区别在于动态和静态剪支:动态剪支能够在保证正确性的前提加速搜索,而静态剪支则需要在正确性和速度之间进行权衡。总而言之,尽管Matsui算法拥有正确率高的优点,但其搜索耗时多,正确率和时间的比值低,通用性较差。因此,本文的目的是通过优化Matsui算法,使其在保证正确率的前提下,尽可能缩短计算时间,提高比值,从而推动该算法的广泛使用。本文将就Matsui算法以下几点进行优化:（1）通用化:由于Matsui算法和密码算法的结合过于紧密。针对不同结构的算法构建,相比MILP更为复杂,例如Matsui算法对SPN结构等含有S盒的结构非常适用,但对于其他非线性结构而言并不友好。因此,我们像MILP一样抽出算法的核心部分,将框架和核心进行分离,以适用于大多数密码算法,并且通用算法能够进行局部并行。（2）并行化:本文将Matsui算法并行化,与GPU进行结合,以保证计算的效率。为了适用于不同的算法框架,并行方法主要分为全局并行优化和局部并行优化。CUDA的局限性导致不能达到最理想的优化是提出多种算法模型的原因。（3）优化剪支条件以及引入混合计算理念:本文对并行化Matsui算法的分支界定条件进行研究,以保证能在并行限制的情况下对算法的动态剪支进行最大化的保留,加入一定静态剪支以提升计算速度。并且分析了影响算法计算速度的几点因素,使用混合计算提高了从小规模数据到大规模数据的计算速度。（4）正对PRESENT第一轮输入进行替换,将S盒的输出作为输入,可以在保证正确率的同时,大幅度提高计算速度。本文的主要工作包括:（1）对Matsui算法进行分析和研究在差分分析计算中,Matsui算法能够高效的对16轮DES进行攻破。但是随着现代密码的复杂性不断的提高,导致差分分析的混淆程度也相应提升,以往单纯的基于CPU的Matsui算法编程并不能高效地作用在一些较为复杂的加密算法。本文针对DES,PRESENT,TWINE三种经典的轻量级算法,在保证三者的输入方式,分支界定条件完全符合Matsui算法的情况下,仅找出最大差分特征概率,分别作用于Matsui算法进行对比。我们认为如果某轮的最大差分特征概率小于穷举的概率,则认为该轮能被攻破。TWINE和PRESENT都能攻破14轮。在结构上,DES和TWINE都为Feistel结构（其中的F函数包括S盒）且都只有8个S盒,PRESENT为SPN结构但拥有16个S盒,DES和PRESENT都为连续的S盒结构,DES的置换为初始置换和最后的逆置换.而TWINE和PRESENT除了最后一轮,每轮都需要置换。本工作研究的主要目标在于不同算法结构中哪些因素对每轮最大差分特征概率的影响最大。并得出了以下结论:1)当S盒的数量较多,输入计算的数据量较大,因此花费的时间也较多,PRESENT是明显的代表。当S盒算法变得复杂,分支界定效果变差,剪支数量变少,同样也会花费许多时间。DES的研究已经在Matsui一文中详尽描述,本文不做过多赘述。TWINE实际上花费的时间较少,我们猜测是由于其结构简单。2)对比王美琴的14轮结果中,其第10轮的最大差分特征概率为2-42的路径,而我们使用PRESENT算法找到了最大差分特征概率为2-41的路径。而DES算法和TWINE算法的每轮最大差分特征概率均和原文结果一致。（2）5个算法模型及其理论这部分是本文的核心内容,主要分为通用模型,全局并行模型,局部并行模型,循环模型和混合计算模型。我们将非常详细地去阐述这部分的每一步优化,从时间复杂度到理论模型,再到实际的代码实现。虽然每块的工作量都很大,但是因为是相关联的,我们将放在一起分为两章,第一部分为理论构建,第二部分为实验和结论。通用算法实际上是对Matsui算法的封装,我们提取了加密算法的核心部分,并从大框架中分离。将Matsui算法的主要逻辑和加密算法的核心内容解耦,成为了通用算法,能够针对不同算法进行快速修改。由于解耦的关系,通用算法能够适用于局部并行模型。为了提高计算速度,对Matsui算法和通用模型进行了并行优化,提出了 4种模型的方式,分为全局并行,局部并行,循环并行和混合计算。全局模型和局部模型各有利弊,主要差异包括加密算法S盒数量、差分分布表和每轮最大差分特征概率。前两者都是每轮最大差分特征概率的主要影响因素,但线性部分例如置换也会有一定的影响。S盒数量和每轮最大差分特征概率影响输入数据的数量,S盒数量越多,概率差值越大则全局并行更有优势。差分分布表和每轮最大差分特征概率影响每个S盒的分支情况,越不均匀,概率差值越大则分支越多,局部并行占有优势。局部并行比全局并行的更大的一个优势在于能够全局更新最大差分特征概率,提高后续计算的剪支效果,提高速度。全局并行的实际时间等于最多分支的一个输入所花费的时间,其中每个输入之间相对独立,局部更新最大差分特征概率。第三种为两种并行方式的混合,理论上可行且最优,但是在实际实现的过程中,由于CUDA本身的限制,即不能动态传值,无论在CPU还是GPU,都必须预先分配好内存空间,否则编译失败。最后阐述了一种基于混合计算的模型,意图在CPU计算和GPU计算之间找到一个平衡点。因为使用GPU去处理少量数据反而浪费很多时间在数据传输上。（3）基于PRESENT的算法实现以及实验实验和论证部分,是基于PRESENT对Matsui算法模型和本文提出的5种算法模型进行实现和比较。通过对输入条件,分支界定条件,算法实现模型和上界预估值进行控制变量,进行了大量数据的比较,得出了一些结论:通用算法是对于Matsui算法的封装,因此从理论到实际都会花费更多时间搜索,大约是升15%—35%。后续并行结果的对比则是Matsui算法全局并行和Matsui算法进行对比,通用算法的全局和局部并行和通用算法进行对比。总体来说Matsui算法的全局并行化在一般的轮数能提升30%-40%的效率,通用算法全局并行化则能提升升20%-35%。特别在第五轮和最后一轮,全局并行的优势非常明显。由于可能的输入数量为71833800,Matsui原始算法是无法在有限时间内计算的,而通用算法的全局并行只需要52.66s和653.12s,Matsui算法的全局并行只需要44.53s和464.12s,效果非常显著。对于大部分轮数,通用算法的局部并行比其全局并行要快一点,提升了升30%-40%。但第五轮虽然能算出,但是时间上依旧要1000多秒。接着验证不同的分支界定条件,理论上限制越多,效果越好。从时间上来说确实如此,但是存在一定的隐患。当限制S盒数量小于等于3时,第十轮的所有分支都会被减去,包括了正确的分支。因此,意图求取全部的正确结果,需要放宽剪支条件。S盒数量小于等于4时,是在正确率和速度上达成了一个平衡。混合计算是为了解决算法前几轮计算量小而导致GPU传输时间大于计算时间的问题。我们通过改变输入的数量,找到了一个平衡点:对于算法的某几轮,其通过CPU计算时间小于2s,则用CPU计算,大于则GPU计算效果较好。对于PRESENT来说,5轮之前以及某节点分支数量小于256的情况,使用CPU计算较好。4轮之后大体也有升5%-10%的提速。使用dy的输入方式普遍适用于大部分加密算法,尤其是S盒所为输入。这样也弥补了局部并行的短板,特别是在第五轮,第十二轮盒第十四轮,输入分支较多的情况下,有明显的提高,针对PRESENT而言,对比最原始的Matsui算法,时间缩短了几十倍。PRESENT优化模型涵盖以下特点:1)使用dy作为输入;2)使用通用算法的局部并行模型;3)保证正确率的情况下优化剪支条件;4)使用混合计算。最后结果是,大部分轮数的计算速度有大幅度的提高。其中并行化和使用dy作为输入对速度的影响最大。最后,我们对未来进行了展望。出于严谨,我们应该进行更多的实验。将每个模型作用在不同的加密算法上进行对比实验。并且可以制作成类似MILP的工具,更加便利地提供给密码分析者使用。