serpent的差分代数分析(修改6).doc

serpent的差分代数分析(修改6).docserpent加密算法的差分代数攻击胡志华H(1•武汉大学计算机学院,武汉,430079;2湖北黄冈师范学院数学与信息科学学院,黄冈,438000)摘要研究了Serpent加密算法的差分特征,利用构造S盒代数方稈的方法,t-128的差分代数攻击方法。该方法分析8轮Serpent-128需要屮。对选择性明文,296次8轮加密和次296次8轮解密,记忆存储空间为2,,(,分组的空间来猜测8轮Serpent-128加密密钥的14位。关键词代数攻击XSLboomeran攻击Rectangle攻击中图分类号: 文献标识码:A 文章编号:2001年Nicolas和Pieprzyk设计了一个攻击Serpent和AES的代数攻击新方法-XSL(extendedSparseLinearization)攻击10他们把对Serpent和AES的密码分析简化为解多元二次方稈组问题(即MQ难题)。XSI,攻击的关键技术就算把分组密码的非线性部分用二次方程的形式描述,然麻川XSL方法将其超定并用线性化的方法求解。但是该攻击方法能否有效一直是一个开放的课题。2005年CarlosCid等人揭示了XSL?攻击木质,并指出XSL攻击对Serpent和AES构成的方稈系统无效。但^Courtois等人揭示的分组密码的非线性部件存在隐含的方稈组对密码分析提供了新的研究方向。本文分析分组密码Serpent'的非线性部件存在隐含的方程组,同时结合boomeran1'攻击、Rectangle⑸⑹攻击的技术,设计一种称为差分代数攻击的新方法。并提出8轮Serpent-'是高级加密标准的报后5个侯选算法2—,其得票仅次于AES。该算法是一个32轮SPY结构的分纽密码算法,&,一直是很多攻击方法攻击的主要目标,由于该S盒存在隐含的方稈,:令(儿,…,儿_])=Sg,...,入”-J是加进m出S盒的多输出函数’具屮无,儿w(0,1),ie(0,1・.・,加),je(0,1,...,“)。则可以构造关于石,儿的多变元系数矩阵。对于Serpent加密算法的S盒,其多输出函数为(儿,…,儿)=SCq,...,®),可以构造其大小为16x25全二元系数矩阵,该矩阵的列元素为1,兀°,…兀3歹3,兀0兀1,…,兀2兀3,,…9)‘2)’39 ,…兀3)‘3°定义2:对构造的二元系数矩阵进行线性化可以得到形如下方程的基础解系:工勺口+工0护%/+工力/力+工刪+工0/+£=0,荡0,必,£€(0,1)。我们称收稿日期:2009-11-02:湖北省教育厅优秀中青年人才项目(Q20102905).作者介绍:胡志华(1976-),男,湖北武汉人,酋士,讲师,主要研究方向为密码分析与设计。工勺佔力+工洽+工孙+"0为S盒的全二次代数方程;只含有其中一部分的方稈,我们称为部分二次代数方稈O定理1:对任意的多输出函数为(儿,…,儿)=$(%…血)的s盒,如果利用定义1和定义2构造的基础解系屮包含如下形式的方程:X时心+工认&+工0)+£=0。 ⑴则我