【作者】 李瑞林；

【导师】 李超；

【作者基本信息】 国防科学技术大学 ， 数学， 2011， 博士

【摘要】 随着计算机网络和通信技术的飞速发展，现代社会已经步入信息时代。人们对信息的安全存储、处理和传输的需求越来越迫切，信息的安全保护问题已经显得十分突出。密码学作为信息安全领域的基石，是各类信息安全技术的基础，它由各种各样的加密算法来具体实施，并以较小的代价提供较大的安全保护。分组密码属于对称密码的一个重要分支，由于其安全、高效和易于标准化等特点，近些年已经在密码学中得到了广泛的应用，并受到了人们的极大关注。在此背景下，本文研究分组密码的分析和设计理论，主要包括如下两个部分：第一部分主要研究分组密码的分析理论，取得的相关成果包含如下三个方面：第一，研究了SPN密码算法抵抗不可能差分分析和高阶积分分析的能力。以有限域上的矩阵理论为工具，提出了刻画SPN密码算法不可能差分的一系列准则，该方法可以推广至轮函数为SPN型的其它密码结构的不可能差分分析，从而为特殊类型密码算法不可能差分的自动搜索提供了新的途径。以线性空间的直和分解理论为工具，提出了SPN密码算法的高阶积分区分扩展理论，统一了分组密码AES和ARIA算法的4轮高阶积分的寻找流程，该方法亦可推广至对各种分组密码结构的高阶积分分析，从而克服了以往该领域研究主要依赖于密码分析者经验判断的缺陷。第二，评估了一类广义非平衡Feistel结构GF-NLFSR的安全性，通过代数方法对该结构加密流程的刻画，指出该结构扩散性较弱，由此大大改进了对它的区分攻击。针对GF-NLFSR变种结构提出了一种在组件均是双射的某些密码算法中实施非满射攻击的方法，并在个人机器上对基于AES的S盒设计的Toy密码进行了实验验证。该分析方法的最大优点是数据复杂度仅为分组长度的线性函数。第三，采用面向字节的随机故障模型对SMS4算法抵抗差分故障分析的能力进行了评估，通过对轮函数为SPN型的SMS4-型广义Feistel结构的5轮差分传播性质研究，发现只需在第28轮输入的第2、第3或者第4个寄存器中导入1个单字节的随机故障，即可将穷尽搜索所需的128-bit的密钥量降为平均22.11-bit的密钥量。这表明SMS4算法针对故障攻击的免疫性较弱，因此算法在密码设备中实现时需要做出相应的防护措施。第二部分主要研究分组密码的设计理论，取得的相关成果包含如下三个方面：第一，研究了基于循环移位和异或运算设计的对合线性变换，完全给出了这类线性变换的具体表达式和计数公式，指出它们的分支数上界为4，并讨论了循环移位的参数与分支数之间的关系，从而为基于这类运算设计的线性变换提供了理论依据。第二，研究了轮函数为SPN型的MISTY结构掩码传播特性，基于“分而治之”的策略，重新给出了这类密码结构连续4r轮线性特征中活跃S盒数目的下界，统一了这类密码结构针对差分和线性密码分析的实际可证明安全界。第三，提出了MISTY结构的两种推广结构：第I类和第II类广义MISTY结构，分别给出了这两类结构抵抗差分和线性密码分析的实际可证明安全，从而为基于这两类结构设计的算法提供了理论依据。基于第II类广义MISTY结构，给出了两个高效的分组密码算法的设计框架。更多还原

【Abstract】 Oursocietyhadsteppedintoanexcellentinformationagewiththerapiddevelopmentof computer networks and communication technologies. In this environment, the securitystorage, process and transformation of information are urgent needed, thus the problem ofinformation security protection is very pressing. Cryptography is a useful and major ap-proach for security protection, which achieves the goals by various encryption algorithms,and nowadays, it had been the basis of the information security. Block ciphers belongsto the field of symmetric cryptography, it attracts more attention in recent years, due totheir features of high security, efficient implementations and easy standardizations. Underthis background, this thesis concentrates on the cryptanalysis and design methodologiesof block ciphers, and it mainly contains two parts.In the first part, we focus on the cryptanalytic methods for block ciphers, and obtainsome results that are related to the following three aspects:In the first aspect, we study the resistance of SPN ciphers against impossible differ-ential cryptanalysis and higher-order integral cryptanalysis. We adopt the matrix theoryon finite fields to propose several criteria for characterizing the existence of impossibledifferentials of SPN ciphers. This method can be extended to analyze other block cipherstructureswithSPN-typeroundfunction,andthuscanprovideusanewpotentialapproachto automatically search impossible differentials for various ciphers. We also borrow fromthelinearalgebrawiththetoolofdirectdecompositionofalinearspacetoproposeatheoryforhigher-orderintegralextensionofSPNciphers, whichunifiestheprocessforfinding4-round higher-order integrals of AES and ARIA. This method can be further generalized toanalyze the case of block cipher structures, and thus overcome the traditional approacheswith cryptanalyst’s experience and intuition. In the second aspect, we evaluate the secu-rity of a kind of generalized unbalanced Feistel network structure, called GF-NLFSR. Byalgebraic methods, the encryption characteristic can be expressed clearly, which directlydemonstrates a poor diffusion property of GF-NLFSR. Thus, the distinguishing attacks onGF-NLFSR can be significantly improved. Another contribution regarding to the securityof a variant of GF-NLFSR is the proposition of a kind of non-surjective attack, whichcan be applied to some block ciphers with bijective components. Such a kind of attack is verified through a experiment on a toy cipher based on GF-NLFSR and the sbox of AES.The most merit of this method is that its data complexity is only a linear function of theblock length. In the third aspect, we apply differential fault analysis on SMS4based onthe random byte fault model. By observing a difference propagation property of5-roundSMS4-type generalized Feistel structure with SPN round function, we show that if a ran-dombytefaultisinducedintoeitherthesecond,third,orfourthwordregisterattheinputofthe28-th round, we can break SMS4by an exhaustive search with time complexity222.11.This efficient attack implies that SMS4should be carefully protected when implementedin the products.The second part belongs to the design theory of block ciphers, and it contains thefollowing results:First, we concentrate on a kind of involutional linear transformation which is basedon the XOR of several rotations, the numeration of this kind of linear transformation isgiven and its branch number is shown to be upper bounded by4. Meanwhile, the relation-ship between the parameters of the rotations and the branch number is discussed, whichprovides a theoretical basis for the design. Then, we turn to the field of practical securityaspectsofblockcipherstructures.ThemainobjectistheMISTYstructurewithSPNroundfunction. According to the mask propagation and "divide-and-conquer" strategy, we pro-vide a new lower bound of the number of active s-boxes for consecutive4r-round linearcharacteristics of such block cipher construction, and thus unifies the practical securitybounds for this construction against differential and linear cryptanalysis. Last, we gener-alize the MISTY structure and propose two kinds of block cipher structures called Type-Iand Type-II generalized MISTY structure. For these two block cipher constructions, weprovide the proofs of their practical security against differential and linear cryptanalysis,which is the basis for the design of new block ciphers basing these structures. Accord-ingly, two efficient block cipher framework are proposed based on the Type-II generalizedMISTY structure.更多还原