第１４卷第２期 ２０１３年４月 信息工程大学学报 Ｊｏｕｒｎａｌ ｏｆ Ｉｎｆｏｒｍａｔｉｏｎ Ｅｎｇｉｎｅｅｒｉｎｇ Ｕｎｉｖｅｒｓｉｔｙ Ｖｏ１．１４ ＮＯ．２ Ａｐｒ．２０１３ ＤＯＩ：１０．３９６９／ｊ．ｉｓｓｎ．１６７１－０６７３．２０１３．０２．００３ ＡＲＩＡ的差分性质研究 郭建胜 ，张 磊 ，罗 伟 （１．信息工程大学，河南郑州４５０００１；２．６５０１２部队，辽宁沈阳１１０００１） 摘要：ＡＲＩＡ是韩国标准分组加密算法。有关ＡＲＩＡ的差分性质研究结果仅限设计者基于活动 ５盒数目而给出的一个理想评估上界。文章通过对算法轮函数内部结构分析，严格给出了 ＡＲＩＡ算法存在的最大单链差分转移概率，进一步考虑在多条差分路径复合的情况下，找到了 最大的两轮循环差分转移概率。结果表明，即使在考虑复合差分路径的情况下，ＡＲＩＡ对差分 分析也是安全的。 关键词：分组密码；ＡＲＩＡ；差分分析；差分特征；复合差分路径 中图分类号：ＴＮ９１８．１ 文献标识码：Ａ 文章编号：１６７１—０６７３（２０ｌ３）０２—０１４１－０７ Ｄｉｆｆｅｒｅｎｔｉａｌ Ｐｒｏｐｅｒｔｙ ｏｆ Ｂｌｏｃｋ Ｃｉｐｈｅｒ ＡＲＩＡ ＧＵ０ Ｊｉａｎ—ｓｈｅｎｇ ，ＺＨＡＮＧ Ｌｅｉ ．ＬＵ０ Ｗｅｉ （１．Ｉｎｆｏｒｍａｔｉｏｎ Ｅｎｇｉｎｅｅｒｉｎｇ Ｕｎｉｖｅｒｓｉｔｙ，Ｚｈｅｎｇｚｈｏｕ ４５０００１，Ｃｈｉｎａ；２．Ｕｎｉｔ ６５０１２，Ｓｈｅｎｙａｎｇ １１０００１，Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ：ＡＲＩＡ ｉｓ ｔｈｅ Ｋｏｒｅａｎ ｂｌｏｃｋ ｃｉｐｈｅｒ ｅｎｃｒｙｐｔｉｏｎ ｓｔａｎｄａｒｄ．Ｂｙ ｃｏｕｎｔｉｎｇ ｇｕａｒａｎｔｅｅｄ ｎｕｍｂｅｒｓ ｏｆ ａｃｔｉｖｅ Ｓ—ｂｏｘｅｓ．ｔｈｅ ｄｅｓｉｇｎｅｒｓ ｔｈｅｏｒｅｔｉｃａｌｌｙ ｅｖａｌｕａｔｅ ｔｈｅ ｉｍｍｕｎｉｔｙ ｏｆ ＡＲＩＡ ａｇａｉｎｓｔ ｄｉｆｆｅｒｅｎｔｉａｌ ａｔｔａｃｋ． Ｉｎ ｔｈｉｓ ｐａｐｅｒ，ａ ｓｔｒｉｃｔ ｄｉｆｆｅｒｅｎｔｉａｌ ｐｒｏｂａｂｉｌｉｔｙ ｒｅｓｕｌｔ ｉｓ ｐｒｏｐｏｓｅｄ ｂａｓｅｄ ｏｎ ｔｈｅ ｐｒｏｐｅｒｔｉｅｓ ｏｆ ｔｈｅ ｒｏｕｎｄ ｔｒａｎｓｆｏｒｍ ｏｆ ＡＲＩＡ．Ｍｏｒｅｏｖｅｒ，ｃｏｎｓｉｄｅｒｉｎｇ ｄｉｆｆｅｒｅｎｔ ｄｉｆｆｅｒｅｎｔｉａｌ ｔｒａｉｌｓ ｍａｙ ｃｌｕｓｔｅｒ（ｃａｕｓｉｎｇ ｄｉｆｆｅｒｅｎｔｉ— ａｌｓ ｈｕｌｌｓ），ｔｈｅ ｂｅｓｔ ２－ｒｏｕｎｄ ｃｉｒｃｕｌａｒ ｄｉｆｆｅｒｅｎｔｉａｌ ｐｒｏｂａｂｉｌｉｔｙ ｉｓ ｇｉｖｅｎ．Ｉｔ ｉｓ ｓｈｏｗｎ ｔｈａｔ ＡＲＩＡ ｉｓ ｓｅｃｕｒｅ ｔｏ ｄｉｆｆｅｒｅｎｔｉａｌ ａｔｔａｃｋ ｅｖｅｎ ｕｎｄｅｒ ｔｈｅ ｄｉｆｆｅｒｅｎｔｉａｌ ｔｒａｉｌｓ ｃｌｕｓｔｅｒｉｎｇ． Ｋｅｙ ｗｏｒｄｓ：ｂｌｏｃｋ ｃｉｐｈｅｒ；ＡＲＩＡ；ｄｉｆｆｅｒｅｎｔｉａｌ ｃｒｙｐｔａｎａｌｙｓｉｓ；ｄｉｆｆｅｒｅｎｔｉａｌ ｃｈａｒａｃｔｅｒｉｓｔｉｃ；ｄｉｆｆｅｒｅｎｔｉａｌ ｔｒａｉｌｓ ｃｌｕｓｔｅｒｉｎｇ ＡＲＩＡ¨ 是韩国研究者Ｄａｅｓｕｎｇ Ｋｗｏｎ等提出的一种分组密码算法，它采用新的代替一置换网络 （ＳＰＮ）结构，并于２００４年被韩国商业部、工业部和能源部确认为韩国标准分组密码算法。ＡＲＩＡ的分组长 度为１２８比特，密钥长度可变，可取１２８、１９２或２５６比特。在不同的密钥规模下，算法相应的轮数分别为 １２、１４和１６轮。 文献［３］首先指出了ＡＲＩＡ存在４轮不可能差分，从而给出了对６轮ＡＲＩＡ的攻击；文献［４．５］分别改 进了不可能差分分析的结果；文献［６］也首次给出针对ＡＲＩＡ的飞来去器分析；文献［１，７］在ＡＲＩＡ算法的 评估报告中给出了针对ＡＲＩＡ算法的差分分析、线性分析等安全指标。所给出的评估ＡＲＩＡ的差分分析结 果，是基于轮变换中所涉及的活动ｓ盒数目，在假设所有的Ｓ盒均取得最大差分转移概率的基础之上给出 轮函数差分转移的界限。然而，此界限仅是一个估计值，是一个理想的上界。真实的差分界限可能达不到 此界，因为不可能涉及的所有ｓ盒都取到最大差分转移概率。同时，基于活动Ｓ盒数目的评估手段，仅考 虑了单条差分链的差分转移概率，至于在多条差分路径作用下，ＡＲＩＡ的差分性能至今仍不得而知。 本文在细致分析ＡＲＩＡ轮变换中Ｓ盒和扩散层变换性质的基础上，找到了单链差分转移概率的最大 收稿日期：２０１２・１０－２８：修回日期：２０１２．１２．１３ 作者简介：郭建胜（１９７２一），男，教授，主要研究方向为应用数学。 １４２ 信息工程大学学报 值，同时给出了在复合路径作用下ＡＲＩＡ的两轮循环的最优差分转移概率。所找到的复合路径的差分转 移概率要优于理论的评估值，但也不会对算法构成威胁，这从另一个侧面说明了算法抵抗差分分析的 能力。 １ ＡＲＩＡ分组密码算法的轮变换结构 ＡＲＩＡ分组密码算法是一个ｓＰ结构分组算法，其每一层包含３个基本操作：轮密钥加变换（ＲＫ），非线 性层变换（ＳＬ）和线性层变换（ＤＬ）。算法最后一轮的线性层变换用一个轮密钥加代替。轮密钥加是中间 状态与１２８比特轮子密钥的逐位模２加，有关线性层与非线性层变换的具体设计如下。 非线性层变换（ＳＬ）将状态中的每个字节非线性的变换为另一个字节。ＡＲＩＡ在算法中使用了４个不 同的８×８的ｓ盒：ｓ。，ｓ：，ｓｆ。，ｓ ，这里５ 。，ｓ 是５。，ｓ：的逆变换。 ｓＬ变换是面向字节变换，在生成过程中，采用了与ＡＥＳ中ｓ盒类似的生成方式，通过多项式来定义有 限域ＧＦ（２。）上的运算。有限域ＧＦ（２ ）中的元素可以有多种不同的表示方法，但不同的表示方法对实现 的复杂度是有影响的。这里使用多项式表示方法，即将一个字节ｂ７ｂ ｂ ｂ ｂ，ｂ：ｂ ｂ。看作是二元域ＧＦ（２）上 的次数小于８的多项式： ６７ ＋ｂ６ ＋６５ ＋６４ ＋６３ ＋６２ ＋ｂｌ ＋ｂ０。 Ｏ ０ｌ ００ １１ １１ １ｌ １有限域ＧＦ（２ ）中的两个元素相加，和是一个多项式，其系数是两个元素对应系数的模２加。因此，两 个字节相加，其和为两个字节按比特异或（或逐位模２加）的结果，用符号０表示。有限域ＧＦ（２。）中的乘 法为模二元域ＧＦ（２）上的一个８次不可约多项式的多项式乘法。ＡＲＩＡ选择的８次不可约多项式为ｍ （ ）＝ ＋ ＋ ＋ ＋１。于是，两个字节相乘，其积为对应多项式的乘积模上二元域ＧＦ（２）上的８次不 可约多项式ｍ（ ）＝ ＋ ＋ ＋ ＋１后的结果所对应的字节。Ｊｓ 和Ｉｓ 的生成方式用符号分别表示为 Ｓ ：ＧＦ（２。）－－－＊ＧＦ（２。）， 卜÷４・ 一 ６≥口。 １ Ｏ ０ ０ ｌ １ １ １ １ １ ０ ０ ０ １ １ １ ｌ ｌ １ ０ ０ ０ ｌ ｌ １ １ ｌ １ ０ Ｏ ０ １ Ａ＝ １ １ １ １ １ ０ ０ ０ ｌ １ ｌ Ｏ ０ ０ １ １１ ｌ ０ Ｏ ０ １ １ ０ １ ００ ｌ０ ｌ０ ０ １ １ １ １ １ ０ ０ ０ ０ １ １ １ １ １ Ｓ２：ＧＦ（２ ）－－，ＧＦ（２ ）， ・Ｘ２４７①６。 Ｂ＝ ， ｂ＝ 至于生成的ｓ盒具体值，可参考文献［１］。 将１２８比特的中间状态写成图１（ａ）中４×４的矩阵表示形式。每一轮非线性层变换ｓＬ将使用１６个 并置的ｓ盒。将并置的Ｓ盒，写成矩阵形式如图１（ｂ）、（Ｃ）的形式，构成两种不同的类型ｓＬ变换。 ＳＬ１＝ＳｌＳ２ｓｉ１ ｓｉ１ ＳｌＳ２ｓ ｌ ｓｉｌ ＳｔＳ２ｓ ｌ Ｓｉｌ Ｓ１Ｓ２ｓ ｌ ｓｉｌ， 乩２＝｜ｓ ５ ＳｔＳ２ Ｓｌ－。．ｓ 。Ｓ１Ｓ２ Ｓｌ－ ．ｓ Ｓ１Ｓ２ ｓｉ ｜ｓ ’ＳｌＳ２。 第２期 郭建胜等：ＡＲＩＡ的差分性质研究 １４３ 加密过程中交替使用这两种类型，在奇数轮使用ｓ￡ ，偶数轮使用ｓ ：，即奇数轮时，第０，４，８，１２字节 使用Ｓ。，第１，５，９，１３字节使用Ｊｓ：，第２，６，１０，１４字节使用ｓ ～，第３，７，１１，１５字节使用ｓ ；偶数轮时，第 ０，４，８，１２字节使用 １＿ ，第１，５，９，１３字节使用 。，第２，６，１０，１４字节使用 。，第３，７，１ １，１５字节使用５：。 Ｏ ４ ８ １２ ｌ Ｓ一 ｆ１ ５ ９ １ ３ ｓ２ Ｓ２ ｓ ｓ ’ ２ ６ １０ １４ Ｓ Ｉ Ｓｌ ３ ７ Ｉ１ １５ ｓ ｔ ｓ ２ ２ Ｓ２ （ａ）中间状态的矩阵表示形式 （ｂ）奇数轮ＳＬ． （ｃ）偶数轮 ，Ｊ： 图１ ＡＲＩＡ中间状态及非线性层的两类变换 ＡＲＩＡ在线性层变换（ＤＬ）中使用了二元域上面向字节的线性变换，ＤＬ是ＧＦ（２ ） 一ＧＦ（２ ） 的一 个映射： （ ｏ， ｌ，…， １５）卜＿÷（Ｙ０，Ｙ１，…，Ｙｌ５）， Ｙ０ ３① ４ ｘ６① ８① ９０ 】３① … ２＝ ｌ０ ４④ ６① １０④ １ｌ０ ｌ２０ ｌ５’ ｙ】＝ ２① ５ ｘ７ ｘ８① ９ｏ Ｊ２ ｘ ３＝Ｘｏ④ ５④ｚ７ｏ ｌ０① ｌｌ① １ ３① １４， ｙ４＝Ｘｏ０ ２④ ５ ｘ８① １１④ １４① Ｉ５’ Ｙ６＝ ｏ０ ２① ７ ｘ９① ｌ０ ｘ１２０ ｙ８＝Ｘｏ① ｌｏ ４④ ７ ｘ１０① １３０ ｌ５， ｙｌｏ＝Ｘ２① ３① ５０ ６① ８ ｘ１３０ ｌ５， Ｙ５： １ ０ ３０ ４ ｘ９① １ｏ① １４④ ｌ５， ｙ７＝ １ ｏ ３０ ６ ｘ８① １１④ １２ ｘ Ｙ９＝ ０ｏ ｌｏ ５ｏ ６① １１① １２ ｘ１４， ｙ Ｊｌ＝Ｘ２ ｘ３ ｘ４０ ７① ９ ｘｌ２ ｘｌ４， Ｉ２＝ １① ２① ６０ ７０ ９０ １１④ ｌ２， ｙｌ４：ｘｏ④ ３① ４ｏ ５① ９① １１０ １４， １３＝ｘｏ① ３④ ６０ ７① ８① １０① Ｙ１５＝ ｌ① ２① ４０ ５① ８ ｘ１ｏ① １５。 由于在本文的分析过程中不涉及密钥生成算法，有关密钥生成算法的描述及算法的其它设计细节参 考文献［１］。 ２ ＡＲＩＡ轮变换的相关性质 ２．１ 非线性层变换的性质 定义１ 函数／：｛０，１｝ 一｛０，１｝ 的差分转移概率定义为 １ Ｐｒ（ 一卢），＝ ＃｛ ‘ ｛０，１｝ ：厂（ ｏ ） ）＝卢｝， 最大转移概率定义为 １ ｍａｘ Ｐｒ（ —＋卢），＝者＃｛ ∈｛０，１｝ （ ０ ） ）厂（ ）：卢｝。 分析Ｓ盒的生成方式，通过计算机模拟，可得８×８的Ｓ盒Ｓ。，Ｓ：，Ｓ ，Ｓ 。的如下性质。 性质１ Ｓ。，Ｓ：，Ｓ１－ ，５ 的最大差分转移概率为２。。。，次大差分转移概率为２～，不存在其它的非零差 分转移概率。 性质２对任意的一个非零输入差分值，Ｓ ，Ｓ ，Ｓ ～，Ｓ 都存在与之对应的的非零输出差分值使得其 ，差分转移概率为２～。即对于不同的Ｓ盒非零输入差分 。， ：， ， ，分别存在唯一的非零输出差分卢 卢：， ，， ，使得 Ｐｒ（ Ｉ ）ｓ．＝Ｐｒ（ ２ ２）ｓ ＝Ｐｒ（０／３ ３）ｓ ＝Ｐｒ（０／４ ４）ｓ ＝２＿。。。 ， 性质３ 当输入差分值为１９７，输出差分值为１９７时，ｓ ，ｓ，－ 差分转移概率为２～，Ｓ ，ｓ 的差分转移 概率为０．即 １４４ 信息工程大学学报 Ｐｒ（１９７—１９７）Ｓ１＝Ｐｒ（１９７ １９７）ｓ一 ＝２～， ｌ Ｐｒ（１９７—１９７）Ｓ２＝Ｐｒ（１９７ １９７）ｓ—ｔ＝０。 ２ 性质４ 当输入差分值为９０，输出差分值为９０时，Ｊｓ ，ｓ 差分转移概率为２一，Ｓ ，Ｓ， 差分转移概率 为０，即 Ｐｒ（９０—９０）Ｓ２＝Ｐｒ（９０—９０） ：２～， ２ ＰＴ（９０—９０）ｓ，＝Ｐｒ（９０—９０） 一１＝０。 １ 性质５ 当非零输入差分值 ＃９０和１９７时，Ｓ ，ｓ。，．ｓ ，ｓ 存在且仅存在唯一的一个Ｓ盒可以使其 输出差分转移概率达到最大。 ２．２线性层变换的性质 定义２ 设Ｘ＝（ 。， 一， ），这里 ＥＧＦ（２。），０≤ ≤１５。令 ’＝Ｘ 代表差分值，差分重量为 差分值中所有非０的状态字节的个数。输入输出差分重量为输入差分重量与输出差分重量之和。 定义３（分支数）… 设Ｐ：（（０，１） ） 一（（０，１） ） 是线性双射，则称 ＤＰ＝ｒａｉｎ｛ （ ）＋＇ｔＯ（卢）：Ｐｒ（ ） ：Ｉ，Ｏｔ≠０｝ 为Ｐ的差分分支数。其中，Ｐｒ（ ） 是Ｐ的差分转移概率，即 １ Ｐｒ（ — 』Ｂ） ＝ ＃｛ ∈（｛０，１｝ ） ：Ｐ（ ０ ）①Ｐ（ ）＝』臼｝。 二 ＡＲＩＡ的分支数为８…，下面分析两轮ＡＲＩＡ的最大差分转移概率形式。根据线性层的结构，每个线 性层变换的输出均是７个输入字节的模２加。当输入各个字节差分值相等时，出现偶数次的输入将会相 互抵消，此时导致输出差分值非零的个数最少。应用分支数理论，两轮变换所涉及的ｓ盒数目最少，此时 对应的差分转移概率最大。以下分析均考虑输入各字节差分值相等的情况。 根据输入差分重量的不同，可以将ＡＲＩＡ的加密输入差分分为７个表１ ＡＲＩＡ的不同加密输入类型及计数 类型，具体如表ｌ所示。 以类型Ⅳ举例说明表Ｉ的含义，在类型Ⅳ中，４—４表示输入差分重 量为４，输出差分重量也为４，计数值２０４表示输入差分重量为４，输出差 分重量也为４的情况有２０４个。 ３ ＡＲＩＡ的两轮最优循环差分概率 接下来分析两轮的循环差分链，即分析ｎ一６一。的最优差分转移概 率。根据表１中各类型的分布，类型Ⅳ的情况最多，并且在此种情况可以取得两轮最优的差分概率。下面 给出表１中类型Ⅳ的差分性质，其它情况依次类似给出。 ３．１ 输入类型Ⅳ的两轮最优循环差分概率 考虑每次的非线性变换中所涉及的不同ｓ盒，不考虑同一ｓ盒的使用个数。当输入输出差分重量为 Ⅳ类型时，其输入差分重量为４，输出差分重量也为４。根据非零字节所要通过的Ｓ盒类型，亦即写成图１ 中４×４的矩阵形式，按行重量的分布，将２０４种情况分为４种形式： ｆ２２ ｆ４ ｒ２２ ＠４－－￣１１１１；＠２２一｛【２１１；＠１１１１ ｛２２；＠２１１一｛２１１。 １１１１ 【ｌ１１１ 其中，形式①表示第１轮的非线性层输入涉及４个同一ｓ盒，经过一轮变换后，第２轮的非线性层涉及４ 个不同Ｓ盒（Ｓ ，Ｓ：，Ｓ１－ ，ｓ ）。举例说明，当第２，６，１０，１４字节输入差分非零时，第１轮非线性层涉及４ 个ｓ ，经过线性层变换之后，经过第２轮非线性层时涉及Ｓ ，５ ，５ ，．ｓ 这４个不同的ｓ盒。其变换过程 如图２所示。其它情况以此类推。 第２期 郭建胜等：ＡＲＩＡ的差分性质研究 １４５ 图２差分传递形式 引理１ 当输入差分符合形式①时，两轮循环差分链的最大差分转移概率为 Ｐｒ＝２一 。＋１９ ｘ ２一 。 证明通过计算机模拟，当输入差分为形式①时，其可能的情况有４种。在输人第１轮涉及一类ｓ 盒，第２轮涉及４类ｓ盒，即｜ｓ ，ｓ：，ｓ。 和Ｊｓ ～。固定非零输入差分，得到其所有可能的输出差分值，分析 这些可能输出差分值在下一轮作为输入差分时，经过相应的Ｊｓ盒变换后，又回到输入差分的个数。在单链 差分最大的条件下，符合要求的数目最多有２１个，即有２条链达到最大差分，其它１９条链差分均为次大 差分。此时的对应的差分转移概率即为 Ｐｒ：２×（２一 ） ×２一 Ｘ（２一’） ＋１９×（２一 ） ×（２一’） ：２一 。＋１９×２ ５６。 由以上分析可知，当输入差分符合形式①时，两轮循环差分链的最大差分转移概率为 Ｐｒ＝２一 。＋１９×２一 。 引理２ 当输入差分符合形式②时，两轮循环差分链的最大差分转移概率为 Ｐｒ＝２一 。＋２一如。 证明 ①当输入差分为形式②中２２—２２时，通过计算机模拟，此类情况有１２种。因为当输入值为 ９０或１９７时，才同时有两类ｓ盒的差分转移概率同时达到最大值。在这１２种情况中，考虑同时使得两类 Ｊｓ盒差分转移概率达到最大的情况，此时的单链差分转移概率才达到最大值。经过分析可得，当输入差分 在第８，１０，１２，１４字节处输入差分为１９７时，或输入差分在第９，１０，１３，１５字节处输入差分为９０时，此时 的单链差分转移概率均达到最大，即 Ｐｒ…（１９７—１９７—１９７） ＝（２ ） ×（２ ） ＝２“ ； Ｐｒ…（９０—９０ ９０），＝（２ ） ×（２ ） ＝２ 。。 下面考虑在复合路径下最大差分转移概率。当输入差分为１９７，输出差分为其它值，再经过ｓ盒后输 出差分值为１９７这类情况的计数。经过程序验证，此时最多有６４个。类似地，在第１轮输入差分为９０，第 ２轮输出也为９０时，此时最多有５７个。从而复合路径下最大的差分转移概率为 Ｐｒ…（１９７ ？－－￣１９７）＝（２一 ） ×（２一 ） ＋６４×（２一’） ｘ（２’ ） ＝２一 。＋２一 。。 ⑨当输入差分为形式②中２２—２１１时，通过计算机模拟，此类情况有４９种。第１轮输入涉及两类ｓ 盒，经过一轮变换后，涉及３类ｓ盒。在第１轮经过非线性层时，根据Ｓ盒的特性可知，其可能出现两种情 况：④一类Ｊｓ盒达到最优差分，另一类．ｓ盒达到次大差分；＠两类ｓ盒都达到次大差分概率。 在第２轮经过非线性层时，利用Ｊｓ盒的性质进行筛选，可能出现的情况有：＠２个ｓ盒达到最优的差分， 其它５盒为次大差分；＠１个．ｓ盒达到最优差分，另３个ｓ盒达到次大差分；＠４个ｓ盒均为次大差分。 根据以上分析，可能出现的单链差分情况有：第１轮为上述情况＠，第２轮为上述情况＠，此时差分 概率为２ ；第１轮为上述情况＠，第２轮为上述情况＠，此时差分概率为２ ；第１轮为上述情况＠， 第２轮为上述情况＠，此时差分概率为２ ；第１轮为上述情况＠，第２轮为上述情况＠，此时差分概率 为２ ；第１轮为上述情况＠，第２轮为上述情况◎，此时差分概率为２ 。 下面分析在输入差分值给定的情况下可能的复合差分链。当输入差分值取遍，通过计算机模拟，分析 其可能输出差分值中使最优单链差分出现最多的复合链最多有３８个，其中最大单链差分出现３次，其它 ．ｓ盒的差分均取次大差分。从而差分转移概率的上界为 Ｐｒ￣＜３ ｘ２一 ＋３５ ｘ２。 。 ①当差分为形式②中２２—１１１１时，通过计算机模拟，此类情况有１１个。第１轮输入涉及两类ｓ盒， ｌ４６ 信息工程大学学报 经过一轮变换后，涉及４类ｓ盒。在第１轮经过非线性层时，根据｜ｓ盒的特性可知，其可能出现两种情况： 一类 盒中的两个 盒全部达到最优差分，其它的 盒达到次大差分；两类 盒都达到次大差分概率。 在第２轮经过非线性层时，利用Ｓ盒的性质进行筛选，可能出现的情况有：１个ｓ盒达到最优的差分， 其它Ｓ盒为次大差分；４个ｓ盒均为次大差分。 从而单链的最优差分转移概率为 Ｐｒ＝（２一 ） Ｘ（２一 ） ×２一 Ｘ（２一’） ＝２一 。。 下面分析在输入差分值给定的情况下可能的复合差分链。当输入差分值取遍，通过计算机模拟，分析 其可能输出差分值中使最优单链差分出现最多的复合链最多有２１个，其中最大单链差分出现２次，其它 情况为Ｓ盒均取次大差分。上述单链差分中最大值，从而差分转移概率的上界为 Ｐｒ≤２×２一 。＋１９ ｘ ２ ＝２一 ＋１９×２ 由以上分析可知，当输入差分符合形式②时，两轮循环差分链的最大差分转移概率为 Ｐｒ…（１９７＿÷？－－－．１９７）＝２ ＋２ 。。 引理３ 当输入差分符合形式③时，两轮循环差分链的最大差分转移概率为 Ｐｒ＝２一 ＋１９ Ｘ２一 。 证明 ①当差分为形式③中１１１１—４时，通过计算机模拟，此类情况只有４种。其对应的差分输入 即为引理１中４一ｌ１１１对应的差分输出。根据对称性，由引理１中４—１１１１的证明，求得此时的最大差分 转移概率为Ｐｒ＝２。。＋１９ Ｘ２ 。 ⑨当差分为形式③中１１１ ｌ一２２时，通过计算机模拟，此类情况只有１１种。依据引理２中①的证明， 得到其对应的最大差分转移概率上界为Ｐｒ≤２ ＋１９×２ 。 ①当差分为形式③中１１１Ｉ－－－．１１１１时，通过计算机模拟，此类情况有１６种。输入第１轮涉及４类｜ｓ 盒，第２轮涉及４类Ｓ盒ｓ ，ｓ ，Ｊｓ。 和．ｓ 。。。根据Ｓ盒的特性可知，对通过每轮．ｓ盒的概率可能出现３种 情况：在第ｌ轮可以让２个ｓ盒全部达到最优差分，此情况的概率为２ 。；１个５盒达到最优差分，其它类 型Ｊｓ盒均为次大差分，此情况的概率为２Ｉ２ ；４个Ｓ盒都达到次大差分概率，此情况的概率为２ 。从而， 单链差分最大为Ｐｒ＝（２ ） Ｘ（２ ） Ｘ（２。） Ｘ（２ ） ＝２ 。。 下面分析在输人差分值给定的情况下可能的复合差分链。当输入差分值取遍，通过计算机模拟，分析 其可能输出差分值中使最优单链差分出现最多的复合链最多有２１个，其中最大单链差分出现２次，其它 情况为５盒均取次大差分。上述单链差分中最大值，从而差分转移概率的上界为 Ｐｒ≤２ Ｘ２一 ＋１９×２一 ＝２一 ＋１９×２一 由以上分析可知，当输入差分符合形式③时两轮循环差分链的最大差分转移概率为 Ｐｒ＝２一 。＋１９ Ｘ ２一 。 引理４ 当输人差分符合形式④时，两轮循环差分链的最大差分转移概率为 Ｐｒ≤２一 。＋４１×２一 。 证明 ①当差分为形式④中２１１—２２时，通过计算机模拟，此类情况只有４９种。根据引理２中⑧的 证明，此时的最大差分转移概率上界：Ｐｒ≤３ Ｘ２。 ＋３５×２。。。 ⑨当差分为形式④中２ｌ１—２１１时，通过计算机模拟此类情况有４８种。第１轮输入涉及３类ｓ盒，第 ２轮输入也涉及３类Ｓ盒。根据Ｊｓ盒的特性可知，通过Ｓ盒变换时，有４种情况：３个５盒全部达到最优差 分，另一个ｓ盒达到次大差分；２个．ｓ盒都达最优差分，其它２个．ｓ盒达到次大差分；１个Ｊｓ盒达到最优差 分，其它３个ｓ盒达到次大差分；４个ＪＳ盒均为次在差分。经过两轮变换，求得单链的最优差分转移概率： Ｐｒ：ｆ ２一 ）。Ｘ ２一 Ｘ（２ ） ×２～＝２ 。。 下面分析在输入差分值给定的情况下可能的复合差分链。当输入差分值取遍，通过计算机模拟，其可 能出现的复合链最多有４２个，从而差分转移概率为 Ｐｒ≤２一 。＋４１×２一 。 由以上分析可知，当输入差分符合形式④时，两轮循环差分链的最大差分转移概率为Ｐｒ≤２ 。＋４１ ×２一 第２期 郭建胜等：ＡＲＩＡ的差分性质研究 １４７ 定理１ 在输入差分为类型ＩＶ时，两轮循环差分链的最大差分转移概率为 Ｐｒ＝２一 。＋２一∞。 证明 依据上述引理１，引理２，引理３及引理４的证明，显然可以得出。 ３．２输入类型Ｉ的两轮最优循环差分概率 当输入输出差分重量为Ｉ类型时，其输入差分重量为１，输出差分重量也为７。输入第１轮涉及一类 Ｊｓ盒，第２轮涉及４类Ｊｓ盒ｓ。，ｓ ，ｓ 和ｓ：～。分析单链差分最优的情况：第１轮．ｓ盒取最大差分概率，第 ２轮有２个Ｊｓ盒取最大差分概率，其它５个Ｓ盒取次大差分概率，此时的单链差分转移概率为 Ｐｒ＝２ ×（２ ） Ｘ（２ ） ＝２ 。 固定非零输入差分，分析其所有可能的输出差分值，分析这些可能输出差分值在下一轮作为输入差分 时，经过相应的Ｓ盒变换后，又回到输入差分的个数。在满足单链差分转移概率最大的情况下，求出这１６ 种情况下的使得复合链数目最多有２３个，其中有２条单链差分转移概率达到最大，其它复合链差分概率 均为次大差分。此时对应的差分转移概率上界为 Ｐｒ≤２ ｘ ２一 ＋１９×２一 ｘ（２一 ） ＝２一 ＋１９×２一 。 ３．３ 输入类型Ⅱ的两轮最优循环差分概率 当输入差分重量为２，输出差分重量为６时，输入第１轮涉及２类 盒。第２轮涉及４类Ｓ盒，分析单 链差分最优的情况：第１轮１个ｓ盒取最大差分，另１个ｓ盒取次大差分，第２轮有２个Ｓ盒取最大差分， 其它４个Ｓ盒取次大差分，此时差分转移概率为 Ｐｒ＝２一 ｘ２一 ｘ（２一 ） ｘ（２一 ） ＝２一 。 考虑复合链的情况，类似于输入差分重量为１输出差分重量为７的分析。此时对应的差分转移概率 上界为 Ｐｒ≤２×２一 ＋１９×（２一 ） ×（２一’） ＝２一 ＋１９×２一 ３．４ 输入类型Ⅲ的两轮最优循环差分概率 当输入差分重量为３，输出差分重量为５时，输入第１轮涉及３类 盒。第２轮涉及３类 盒，分析单 链差分最优的情况：第１轮１个Ｓ盒取最大差分，另２个Ｓ盒取次大差分，第２轮有３个．ｓ盒取最大差分， 其它２个．ｓ盒取次大差分，此时单链差分移概率为 Ｐｒ＝２一 ×（２一’） ×（２一 ） ×（２一’） ：２一 。 考虑复合链的情况。对所有可能的输入差分通过计算机模拟，其可能输出差分值中使最优单链差分 出现最多的复合链最多有３８个，其中最大单链差分出现３次，其它｜ｓ盒的差分均取次大差分。此时对应 的差分转移概率上界：Ｐｒ≤３×２ 。＋３５×２ 。 对于输入类型Ｖ，Ⅵ，Ⅶ的情况，由上述分析，根据对称性，可以类似求出相应的两轮循环差分转移概 率的上界。综上所述，可得如下定理２。 定理２ 两轮ＡＲＩＡ的复合循环差分链的最优差分转移概率为 Ｐｒ…＝２“ ＋２。。，其形式为Ｐｒ…（１９７一？－－￣１９７）。 基于所求出的ＡＲＩＡ的两轮循环差分概率，可以给出６轮ＡＲＩＡ的差分概率界限。与文献［１］中的结 果相比，本文的结果是“紧凑”的，是可以达到的。 ４ 结束语 ＡＲＩＡ的设计者依据分支数理论，利用ＡＲＩＡ的５盒最优差分转移概率为２ 和线性层分支数为８，从 理论上给出了两轮ＡＲＩＡ的最优单链差分转移概率界限为２ 。本文通过具体分析Ｓ盒差分值输入，结 合线性层的结构，在考虑复合差分链的情况下，两轮ＡＲＩＡ的最优循环差分转移概率为２“。＋２ Ｉ５。。其结 果与理论分析的相差不大。从一个侧面说明了ＡＲＩＡ的设计很好地控制复合差分链的概率值。根据差分 分析与线性分析之间的相关性，相信ＡＲＩＡ对线性分析也是免疫的。 （下转第１５２页） １５２ 信息工程大学学报 ２０１３缸 待于进一步研究。 ４ 结束语 本文提出了一种基于ＵＯＶ方案的改进多变量签名方案。原始的ＵＯＶ方案具有特殊的结构，使得在 计算签名时具有很高的效率，但是其特殊的结构使得该方案受到秩攻击的破解。本文对ＵＯＶ方案的中心 映射进行了改进，重新构造了中心映射，使得秩攻击对改进方案不再有效；Ｉ￣Ｂ，－ｔ，改进方案同样易于计算并 且效率很高。 参考文献： ［１］Ｄｉｎｇ ＪＴ，Ｓｃｈｍｉｄｔ Ｄ．Ｍｕｌｔｉｖａｒｉａｔｅ ｐｕｂｌｉｃ ｋｅｙ ｃｒｙｐｔｏｓｙｓｔｅｍｓ［Ｍ］．ＵＳＡ：Ｓｐｒｉｎｇｅｒ，２００６． ［２］Ｓｈｏｒ Ｐ．Ｐｏｌｙｎｏｍｉａｌ—ｔｉｍｅ ａｌｇｏｒｉｔｈｍｓ ｆｏｒ ｐｒｉｍｅ ｆａｃｔｏｒｉｚａｔｉｏｎ ａｎｄ ｄｉｓｃｒｅｔｅ ｌｏｇａｒｉｔｈｍｓ ｏｎ ａ ｑｕａｎｔｕｍ ｃｏｍｐｕｔｅｒ［Ｊ ３．ＳＩＡＭ Ｊｏｕｒｎａｌ ｏｎ Ｃｏｍｐｕｔｉｎｇ，１９９９，２６（５）：１４８４—１５０９． ［３］Ｋｉｐｎｉｓ Ａ，Ｐａｔａｒｉｎ Ｊ，Ｇｏｕｂｉｎ Ｌ．Ｕｎｂａｌａｎｃｅｄ ｏｉｌ ａｎｄ ｖｉｎｅｇａｒ ｓｉｇｎａｔｕｒｅ ｓｃｈｅｍｅｓ［Ｃ］／／Ａｄｖａｎｃｅｓ ｉｎ Ｃｒｙｐｔｏｌｏｇｙ－－ＥＵＲＯＣＲＹＰＴ ９９．１９９９：２０６・２２２． ［４］Ｄｉｎｇ ＪＴ，Ｓｃｈｍｉｄｔ Ｄ．Ｒａｉｎｂｏｗ，ａ Ｎｅｗ Ｍｕｌｔｉｖａｒｉａｂｌｅ Ｐｏｌｙｎｏｍｉａｌ Ｓｉｇｎａｔｕｒｅ Ｓｃｈｅｍｅ［Ｊ］．Ａｐｐｌｉｅｄ Ｃｒｙｐｔｏｇｒａｐｈｙ ａｎｄ Ｎｅｔｗｏｒｋ Ｓｅ． ｅｕｒｉｔｙ，２００５，ＬＮＣＳ ３５３１：１６４－１７５． ［５］Ｋｉｐｎｉｓ Ａ，Ｓｈａｍｉｒ Ａ．Ｃｒｙｐｔａｎａｌｙｓｉｓ ｏｆｔｈｅ Ｏｉｌ Ｖｉｎｅｇａｒ ｓｉｇｎａｔｕｒｅ ｓｃｈｅｍｅ［Ｃ］／／Ａｄｖａｎｃｅｓ ｉｎ Ｃｒｙｐｔｏｌｏｇｙ－－ＣＲＹＰＴＯ９８．１９９８： ２５７．２６６． ［６］Ｄｉｎｇ ＪＴ，Ｈｕ Ｌ，Ｙａｎｇ ＢＹ，ｅｔ ａ１．Ｎｏｔｅ Ｏｌｌ ｄｅｓｉｇｎ ｃｒｉｔｅｒｉａ ｆｏｒ Ｒａｉｎｂｏｗ－ｔｙｐｅ ｍｕｌｔｉｖａｒｉａｔｅｓ［ＥＢ／ＯＬ］．［２００６－０９－０５］．ｈｔｔｐ：／／ ｅｐｒｉｎｔ．ｉａｅｒ．ｏｒｓ／２００６／３０７． ［７］Ｄｉｎｇ ＪＴ，Ｙａｎｇ ＢＹ，Ｃｈｅｎ ＣＨ，ｅｔ ａ１．Ｎｅｗ ｄｉｆｅｒｅｎｔｉａｌ－ａｌｇｅｂｒａｉｃ ａｔｔａｃｋｓ ａｎｄ ｒｅｐａｒａｍｅｔｒｉｚａｔｉｏｎ ｏｆ Ｒａｉｎｂｏｗ［Ｊ］．Ａｐｐｌｉｅｄ Ｃｒｙｐ— ｔｏｇｒａｐｈｙ ａｎｄ Ｎｅｔｗｏｒｋ Ｓｅｃｕｒｉｔｙ，２００８，ＬＮＣＳ ５０３７：２４２－２５７． ［８］Ｔｈｏｍａｅ Ｅ，Ｗｏｌｆ Ｃ．Ｓｏｌｖｉｎｇ ｕｎｄｅｒｄｅｔｅｒｍｉｎｅｄ ｓｙｓｔｅｍｓ ｏｆ ｍｕｌｔｉｖａｒｉａｔｅ ｑｕａｄｒａｔｉｃ ｅｑｕａｔｉｏｎｓ ｒｅｖｉｓｉｔｅｄ［Ｊ］．Ｐｕｂｌｉｃ Ｋｅｙ Ｃｒｙｐｔｏｇｒａ— ｐｈｙ・ＰＫＣ，２０１２，ＬＮＣＳ ７２９３：１５６・１７１． ［９］Ｙａｎｇ ＢＹ，Ｃｈｅｎ ＪＭ．Ａｌｌ ｉｎ ｔｈｅ ＸＬ ｆａｍｉｌｙ，Ｔｈｅｏｒｙ ａｎｄ ｐｒａｃｔｉｃｅ［Ｃ］／／Ｉｎｆｏｒｍａｔｉｏｎ Ｓｅｃｕｒｉｔｙ ａｎｄ Ｃｒｙｐｔｏｌｏｇｙ—ＩＣＩＳＣ ２００４．２００５， ３５０６：６７－８６． ｏ●＜＞●０●＜＞●＜＞●＜＞●＜＞●＜＞●＜＞●＜＞●＜＞●＜＞●＜＞●＜＞●＜ ●ｏ●＜＞●＜＞●０●＜ ●＜＞●＜＞●＜＞●＜＞●Ｃ ●＜＞●＜＞●００＜＞●＜＞●ｃ＇●＜＞●０●ｏ●＜＞●＜＞●０●＜＞●ｏ●＜＞●＜＞●＜，●＜＞●０●＜＞●ｏ●＜ ●０● （上接第１４７页） 参考文献： ［１］ Ｋｗｏｎ Ｄ，Ｊ Ｋｉｍ，Ｐａｒｋ Ｓ，ｅｔ ａ１．Ｎｅｗ ｂｌｏｃｋ ｃｉｐｈｅｒ：ＡＲＩＡ【Ｃ］／／Ｉｎｆｏｒｍａｔｉｏｎ Ｓｅｃｕｒｉｔｙ ａｎｄ Ｃｒｙｐｔｏｌｏｇｙ一１ＣＩＳＣ ２００３．ＬＮＣＳ ２９７１， ２００３：４３２－４４５． ［２］ Ｎａｔｉｏｎａｌ Ｓｅｃｕｒｉｔｙ Ｒｅｓｅａｒｃｈ Ｉｎｓｔｉｔｕｔｅ，Ｓｐｅｃｉｆｉｃａｔｉｏｎ ｏｆＡＲＩＡ，Ｖｅｒｓｉｏｎ １．０［ＥＢ／ＯＬ］．［２００５－０１－０２］．ｈｔｔｐ：／／ｗｗｗ．ｎｓｒｉ．ｒｅ．ｋｒ／ ＡＲＩＡ／ｄｏｃ／ＡＲＩＡ—ｓｐｅｃｉｆｉｃａｔｉｏｎ—ｅ．ｐｄｆ． ｎｌｉｎｇ，Ｚｈａｎｇ Ｗｅｎｔａｏ，Ｆｅｎｇ Ｄｅｎｇｇｕｏ．Ｉｍｐｏｓｓｉｂｌｅ ｄｉｆｆｅｒｅｎｔｉａｌ ｃｒｙｐｔａｎａｌｙｓｉｓ ｏｆ ｒｅｄｕｃｅｄ—ｒｏｕｎｄ ＡＲＩＡ ａｎｄ Ｃａｍｅｌｌｉａ［Ｊ］． ［３］ Ｗｕ ＷｅＪｏｕｒｎａｌ ｏｆ Ｃｏｍｐｕｔｅｒ Ｓｃｉｅｎｃｅ ａｎｄ Ｔｅｃｈｎｏｌｏｇｙ，２００７，２２（３）：４４９－４５６． Ｒｕｉｌｉｎ，Ｓｕｎ Ｂｉｎｇ，Ｚｈａｎｇ Ｐｅｎｇ，ｅｔ ａ１．Ｎｅｗ ｉｍｐｏｓｓｉｂｌｅ ｄｉｆｆｅｒｅｎｔｉａｌ ｅｒｙｐｔａｎａｌｙｓｉｓ ｏｆ ＡＲＩＡ［ＥＢ／ＯＬ］．［２００８－０５—２９］．ｈｔ一 ［４］ Ｌｉｔｐ：／／ｅｐｒｉｎｔ．ｉａｃｒ．ｏｒｓ／２００８／２２７．ｐｄｆ． Ａ和Ｓａｌｓａ２０的安全性分析［Ｄ］．山东： 山东大学，２００８． ［５］ 李申华．对称密码算法ＡＲＩｅｉｓｃｈｍａｎｎ，Ｍｉｃｈａｅｌ Ｇｏｒｓｋｉ，Ｓｔｅｆａｎ Ｌｕｃｋｓ．Ａｔｔａｃｋｉｎｇ ｒｅｄｕｃｅｄ ｒｏｕｎｄｓ ｏｆ ｔｈｅ ＡＲＩＡ ｂｌｏｃｋ ｃｉｐｈｅｒ［ＥＢ／ＯＬ］．［２００９－０７一 ［６］ Ｅｗａｎ Ｆｌ０９］．ｈｔｔｐ：／／ｅｐｒｉｎｔ，ｉａｃｒ．ｏｒ／２００９／３３４．ｐｄｆｓ． ［７］Ａｌｅｘ Ｂｉｙｒｕｋｏｖ，Ｃｈｒｉｓｔｏｐｈｅ Ｄｅ Ｃａｎｎｉｅｒｅ，Ｊｏｓｅｐｈ Ｌａｎｏ，ｅｔ ａ１．Ｓｅｃｕｒｉｔｙ ａｎｄ ｐｅｒｆｏｒｍａｎｃｅ ａｎａｌｙｓｉｓ ｏｆ ＡＲＩＡ［ＥＢ／ＯＬ］．［２００３一 Ｏ１－０７］．ｈｔｔｐ：／／ｈｏｍｅｓ．ｅｓａｔ．ｋｕｌｅｕｖｅｎ．ｂｅ／｛｝＼ｓｉｍ￥＼ａｂｉｒｙｕｋｏ／ＡＲＩＡ－ＣＯＳＩＣｒｅｐｏｒｔ．ｐｄｆ． ［８］吴文玲，冯登国，张文涛．分组密码的设计与分析［Ｍ］．２版．北京：清华大学出版社，２００９：２５０・２５１．