密码学作为信息安全的基石,在现代社会中发挥着非常重要的作用。分组密码算法是一类使用同一个密钥来加密和解密的密码算法,其与流密码同属于对称密码的范畴。分组密码一般采用迭代结构,运行速度快且易于实现,因此广泛运用于各种软硬件安全系统。对分组密码的安全性进行研究,有利于发现现有分组密码安全性存在的不足,并指导新的分组密码的设计。NIST征集新的美国加密标准AES的过程,以及欧洲的NESSIE工程,日本的CRYPTREC工程等使分组密码的设计和分析得到了快速发展。除此之外,随着RFID、传感器等的发展,资源限制的环境中使用的分组密码也受到了广泛的关注,因此近年来轻量级分组密码算法发展迅速。本文主要对ISO分组密码算法标准Camellia,以及轻量级分组密码算法TEA, XTEA[6]和HIGHT进行安全性分析。分组密码算法Camellia由日本NTT和三菱公司于2000年设计。该算法的分组长度为128比特,密钥长度有128比特、192比特和256比特三种,对应的轮数分别为18轮、24轮和24轮。Camellia被CRYPTREC工程推荐为日本的e-government算法,并是NESSIE工程最终选取的算法之一。此外它还由国际标准化组织(ISO)制定在国际标准ISO/IEC18033-3中。分组密码算法TEA, XTEA和HIGHT是适用于资源限制环境的轻量级分组密码算法。TEA由Needham和Wheeler于1994年提出；XTEA也是由他们设计,是TEA的改进版本。这两个算法都在Linux操作系统内核中使用,他们的运算很简单,只有模232加、左移、右移和异或。HIGHT由Hong等设计,它被韩国电信技术协会(Telecommunications Technology Association)制定为标准,并且也成为了ISO/IEC18033-3’中的标准算法。HIGHT的结构为4个并行的Feistel结构,它是标准的ARX算法,使用的运算为模28加(Addition),循环移位(Rotation)口异或(XOR)。本文中运用不可能差分分析(Impossible Differential Cryptanalysis)和中间相遇攻击(Meet-in-the-Middle Attack)对上述算法进行分析,在导师王小云教授和合作导师Bart Preeneel教授的指导下取得了以下研究结果：·分组密码算法Camellia的不可能差分分析1.带FL/FL-1的Camellia-192和Camellia-256的不可能差分分析Camellia是Feistel结构的密码算法,但每六轮有一个FL/FL-1层插入到算法中。FL和FL-4函数在固定密钥下是线性的,目的是为了增加算法的不规则性,从而增加算法的扩散作用。最近几年中,Camellia算法受到了密码学界的广泛关注。由于FL/FL-1可能会破坏不可能差分的性质,因此很多对Camellia算法的不可能差分分析都不带FL/FL-1。本文第一次提出了带FL/FL-1层的4条不可能差分路线。这些不可能差分路线的轮数为6轮,FL/FL-1层在第3轮和第4轮之间。产生这些不可能差分路线的主要原因是FL,FL-1函数前后的差分有一些限制条件,若要满足这些限制条件,则一些非零变量需要为零。例如,根据FL,FL-1函数前后的差分限制条件,我们有：b2⊕b3⊕b4⊕b5⊕b6=b2⊕b3⊕b5⊕b6这样推出b4=0,而如果事实上b4≠0,这就产生了矛盾,因此得到不可能差分路线。利用其中一条不可能差分路线,我们给出了10轮Camellia-192和11轮Camellia-256的不可能差分分析。此外我们给出了一些3轮Camellia!的性质,这些性质有利于我们提前排除错误对,降低攻击的时间复杂度。我们的攻击是第一个对带FL/FL-1的Camellia的不可能差分分析。Camellia使用了白化密钥,为了处理白化密钥对分析产生的影响,在密钥恢复过程中,我们首先恢复等价密钥,再根据密钥生成算法将主密钥恢复出来。我们的10轮Camellia-192的不可能差分分析的数据复杂度为2121个选择明文,时间复杂度为2175.3次10轮加密,存储复杂度为2126字节；11轮Camellia-256的不可能差分分析的数据复杂度为2121个选择明文,时间复杂度为2218.5次10轮加密,存储复杂度为2166字节。此外,基于Wu等给出的不带FL/FL-1的Camellia的8轮不可能差分路线[14],我们还给出了不带FL/FL-1和白化密钥的15轮Camellia-256的不可能差分分析。在该攻击中,我们充分利用了Camellia-256子密钥之间的关系；同时建立了预计算表格,用来提前排除错误对和密钥的组合,以降低时间复杂度。这些结果在发表的时候在轮数和时间复杂度上是最好的攻击结果。并且对带FL/FL-1的Camellia-192/-256的不可能差分分析结果引起了人们对分析带FL/FL-1的Camellia算法安全性的兴趣,有许多后续工作在此基础上完成[18-23]。2.自动搜索Camellia不可能差分路线的算法在上述Camellia的6轮带FL/FL-1的不可能差分路线提出之后,又有其它一些不可能差分路线被陆续提出,如文献[19,21]中的7轮不可能差分路线(FL/FL-1层在第1、2轮之间或第6、7轮之间)、文献[22]中的一定条件下的不可能差分路线等。这些不可能差分路线中FL/FL-1层所处的位置各不一样,因此我们希望设计一个统一的算法来寻找Camellia的不可能差分路线,以免遗漏可能导致更好的攻击的不可能差分路线。我们的自动搜索算法的基础是矩阵方法(Matrix Method).与矩阵方法类似,我们也采用不可能中间相遇(Miss-in-the-Middle)的方法来寻找不可能差分路线。差分的表示和矩阵方法相似,但更为简单；判断不可能差分路线产生的条件综合了所有可能产生不可能差分的情况。此外,我们还给出了处理FL/FL-1中移位的机制。由于FL/FL-l中移位的存在,一些不可能差分路线是在一定条件下成立的,如[22]中的7轮不可能差分路线。我们的算法在判断一条路线是否为不可能差分路线的同时,还给出其是否需要条件及所需条件数。利用我们的搜索算法,除了能得到上述6轮、7轮不可能差分路线外,还能得到其它一系列6、7轮不可能差分路线,这为得到更好的不可能差分分析提供了可能性。·约减轮数Camellia-256的中间相遇攻击除了上述提及的不可能差分分析外,还有一些对带FL/FL-1的Camellia的不可能差分分析[18,20.22],以及其它一些攻击如[25,26]。由于不可能差分分析的内在特点,为了能在随机概率模型下得到错误密钥下满足不可能差分路线的对,攻击者必须选取足够多的数据；因此如果想让不可能差分路线足够长,不可能差分分析一般伴随着较大的数据复杂度。文献[25]和[26]中的攻击采用了中间相遇的思想,数据复杂度较低,分别为294和256个选择明文。本文中,我们给出了一个数据复杂度仅为219个选择明文的Camellia-256的中间相遇攻击。与[25,26]一样,我们攻击的基本思想与[27]相似。首先我们推导变量x(x=0,...,255)经过7轮之后的1比特表达式。之所以推导一比特表达式,是因为Camellia与一般的基于字节的算法不同：在FL和FL-’函数中,运算是基于比特的。这样,Camellia的1比特表达式可能与1个字节的表达式所需的变量个数不同。根据这一点,我们通过预计算建立一个7轮区分器(FL/FL-1位于第5轮与第6轮之间)；该区分器由一个预计算表格构成,用于存储7轮之后所表达比特的有序序列的所有可能值。我们的区分器可以看成是[25]中6轮区分器的改进。注意到在Camellia算法中,FL/FL-1每6轮介入一次。为了保持Camellia算法的结构特点,我们在7轮区分器前面扩展1轮,后面扩展4轮,来进行12轮(第1轮到第12轮)Camellia-256的中间相遇攻击；并且攻击考虑了白化密钥的影响。我们的攻击数据复杂度为219个选择明文,时间复杂度为22312次加密。据我们所知,该结果在对Camellia-256的攻击结果中具有最低的数据复杂度；并且在对从第6n+1(n=0,1,2,3)轮开始的Camellia-256的攻击结果中,时间复杂度也是最优的。·轻量级分组密码TEA, XTEA和HIGHT的不可能差分分析在标准攻击模型(单密钥攻击,非相关密钥攻击)下Moon等给出了TEA的10轮不可能差分路线以及XTEA的12轮不可能差分路线,基于此他们对11轮TEA和14轮XTEA进行了不可能差分分析。本文给出了一个推导TEA和XTEA不可能差分路线的新方法,基本思想是利用TEA和XTEA差分扩散的单向性来推导不可能差分路线的轮数。利用该方法,我们给出了13轮TEA和14轮XTEA的不可能差分路线,并用它们来攻击17轮TEA和23轮XTEA。17轮TEA的不可能差分分析需要257个选择明文和21066次加密。对23轮XTEA,如果选择2623个明文,则攻击的时间复杂度为2114.9次加密；如果选择263个明文,时间复杂度为2105.6次加密及2106次内存读取。我们还给出了标准攻击模型下HIGHT的26轮不可能差分分析,该攻击改进了[29]中的不可能差分分析结果。在轮数和时间复杂度上,这些结果是目前对这几个算法最好的不可能差分分析结果。