针对trivium型密码算法的代数攻击

《针对trivium型密码算法的代数攻击》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、第４８卷第１０期上海交通大学学报Ｖｏｌ．４８Ｎｏ．１０２０１４年１０月ＪＯＵＲＮＡＬＯＦＳＨＡＮＧＨＡＩＪＩＡＯＴＯＮＧＵＮＩＶＥＲＳＩＴＹＯｃｔ．２０１４文章编号：１００６－２４６７（２０１４）１０－１４３４－０６针对Ｔｒｉｖｉｕｍ型密码算法的代数攻击孙文龙１，２，关杰１（１．信息工程大学，郑州４５００００；２．北京卫星导航中心，北京１０００９４）摘要：为了更好地研究Ｔｒｉｖｉｕｍ算法的设计思想，选取了２个比较典型的修改Ｔｒｉｖｉｕｍ算法，连同Ｔｒｉｖｉｕｍ算法一起作为研究对象，把恢复算法的内部状态问题转化为可满足性问题，分析修改Ｔｒｉｖｉｕｍ算法抵抗代数攻击的能力．比

2、较了６种猜测策略，并且使用ＭｉｎｉＳａｔ２．０求解器求解．根据分析结果给出了Ｔｒｉｖｉｕｍ型密码算法抵抗代数攻击的安全设计建议．关键词：密码分析；代数攻击；可满足性问题；流密码中图分类号：ＴＮ９１８．１文献标志码：ＡＡｌｇｅｂｒａｉｃＡｔｔａｃｋｓｏｎＴｒｉｖｉｕｍ－ＬｉｋｅＳｔｒｅａｍＣｉｐｈｅｒｓ１,2，ＧＵＡＮＪｉｅ１ＳＵＮＷｅｎ－ｌｏｎｇ（１．ＩｎｆｏｒｍａｔｉｏｎＥｎｇｉｎｅｅｒｉｎｇＵｎｉｖｅｒｓｉｔｙ，Ｚｈｅｎｇｚｈｏｕ４５００００，Ｃｈｉｎａ；２．ＢｅｉｊｉｎｇＳａｔｅｌｌｉｔｅＮａｖｉｇａｔｉｏｎＣｅｎｔｅｒ，Ｂｅｉｊｉｎｇ１０００９４，Ｃｈｉｎａ）Ａｂ

3、ｓｔｒａｃｔ：ＴｒｉｖｉｕｍｓｔｒｅａｍｃｉｐｈｅｒｉｓｏｎｅｏｆｔｈｅｆｉｎａｌｉｓｔｓｏｆＥｕｒｏｐｅａｎｅＳＴＲＥＡＭｐｒｏｊｅｃｔ．ＩｎｏｒｄｅｒｔｏｈａｖｅａｂｅｔｔｅｒｓｔｕｄｙｏｆｔｈｅｄｅｓｉｇｎｉｄｅａｓｏｆＴｒｉｖｉｕｍ，ｔｗｏｒｅｖｉｓｅｄＴｒｉｖｉｕｍａｌｇｏｒｉｔｈｍｓｗｅｒｅｔｙｐｉｃａｌｌｙｃｈｏｓｅｎｔｏｇｅｔｈｅｒｗｉｔｈＴｒｉｖｉｕｍａｓｔｈｅｔａｒｇｅｔｓ．ＴｈｅｒｅｃｏｖｅｒｙｏｆｉｎｔｅｒｎａｌｓｔａｔｅｗａｓｃｏｎｖｅｒｔｅｄｉｎｔｏｔｈｅＳＡＴｐｒｏｂｌｅｍｔｏａｎａｌｙｚｅｔｈｅｓｅｃｕｒｉｔｙｏｆＴｒｉｖｉｕｍ－ｌｉｋｅｓ

4、ｔｒｅａｍｃｉｐｈｅｒｓａｇａｉｎｓｔａｌｇｅｂｒａｉｃａｔｔａｃｋｓ．Ｓｉｘｇｕｅｓｓｓｔｒａｔｅｇｉｅｓｗｅｒｅｔｒｉｅｄ，ａｎｄｔｈｅｎｔｈｅｅｑｕａｔｉｏｎｓｙｓｔｅｍｓｗｅｒｅｆｅｄｔｏＭｉｎｉＳａｔ２．０．Ｆｉｎａｌｌｙ，ｓｏｍｅｓｕｇｇｅｓｔｉｏｎｓｆｏｒｔｈｅｓｅｃｕｒｉｔｙｏｆＴｒｉｖｉｕｍ－ｌｉｋｅｓｔｒｅａｍｃｉｐｈｅｒｓａｇａｉｎｓｔａｌｇｅｂｒａｉｃａｔｔａｃｋｗｅｒｅｇｉｖｅｎａｃｃｏｒｄｉｎｇｔｏｔｈｅｒｅｓｕｌｔｓ．Ｋｅｙｗｏｒｄｓ：ｃｒｙｐｔａｎａｌｙｓｉｓ；ａｌｇｅｂｒａｉｃａｔｔａｃｋｓ；ｓａｔｉｓｆｉａｂｉｌｉｔｙｐｒｏｂｌｅｍ；ｓ

5、ｔｒｅａｍｃｉｐｈｅｒ符号说明：Ｋ—８０ｂｉｔ密钥，Ｋ＝［ｋ１ｋ２…ｋ８０］ｓｔ—第ｔ时刻２８８ｂｉｔ内部状态向量，＋—ＧＦ（２）上的加法运算Ｖ—８０ｂｉｔ初始向量，Ｖ＝［ｖ１ｖ２…ｓｔ＝［ｓｔ（１）ｓｔ（２）…ｓｔ（２８８）］·—ＧＦ（２）上的乘法运算ｖ８０］ｚｔ—第ｔ时刻输出的密钥流比特［１］Ｔｒｉｖｉｕｍ算法是欧洲ｅＳＴＲＥＡＭ工程码学领域研究的一个热点问题．（ＥＣＲＹＰＴＳｔｒｅａｍＣｉｐｈｅｒｐｒｏｊｅｃｔ）的最终胜选算法在安全性分析方面，由于Ｔｒｉｖｉｕｍ算法代数结之一．作为国际重要的序列密码算法，对Ｔｒｉｖｉｕｍ算构简单，已经吸引了国内外许多密码学家的关注，

6、但法的安全性与设计思想进行研究是当前甚至今后密是至今为止还没有一种攻击方法比穷举密钥攻击有收稿日期：２０１３－１２－０４基金项目：国家自然科学基金（Ｎｏ．６１２０２４９１），全军军事学研究生课题（２０１０ＪＹ０２６３－１４９）资助项目作者简介：孙文龙（１９８８－），男，河南周口市人，硕士生，研究方向：序列密码的设计与分析．Ｅ－ｍａｉｌ：ｓｗｌ＿ｃｉｐｈｅｒ＠１６３．ｃｏｍ．关杰（联系人），女，河南郑州市人，教授，研究方向：密码编码理论与技术，Ｅ－ｍａｉｌ：ｇｕａｎｊｉｅ００７＠１６３．ｃｏｍ．第１０期孙文龙，等：针对Ｔｒｉｖｉｕｍ型密码算法的代数攻击１４３５效．目前，对Ｔ

7、ｒｉｖｉｕｍ算法的攻击结果主要有区分攻［２］［３－４］［５］［６－１４］１Ｔｒｉｖｉｕｍ型密码算法描述击、线性攻击、滑动攻击、代数攻击和立［１５］方攻击等．在算法设计修改方面，基于初步的分１．１Ｔｒｉｖｉｕｍ算法描述析结果，在保持Ｔｒｉｖｉｕｍ算法设计思想的条件下，已Ｔｒｉｖｉｕｍ算法分为初始化算法和密钥流生成算有若干版本的修改Ｔｒｉｖｉｕｍ算法，主要有以下修改法两部分：在初始化阶段，系统在ｔ时刻使用特定位方案：修改密钥和ＩＶ装载机制；修改非线性反馈移置的１５ｂｉｔ内部状态更新ｔ＋１时刻的３ｂｉｔ内部状位寄存器抽头位置；根据其