基于Grobner基的Rijndael-192代数攻击方案

doi:10.3969/j.issn.0372-2112.2013.05.001

电子学报 ›› 2013, Vol. 41 ›› Issue (5): 833-839.DOI: 10.3969/j.issn.0372-2112.2013.05.001

• 学术论文 • 下一篇

基于Grobner基的Rijndael-192代数攻击方案

崔杰^1,2, 黄刘生^1,3, 仲红², 杨威^1,3

1. 中国科学技术大学计算机科学与技术学院,安徽合肥 230026;
2. 安徽大学计算机科学与技术学院,安徽合肥 230039;
3. 中国科学技术大学苏州研究院,江苏苏州 215123

收稿日期:2012-05-16 修回日期:2012-08-10 出版日期:2013-05-25
- 作者简介:
- 崔杰 男,1980年生于河南淮阳,现为中国科学技术大学计算机科学与技术学院博士生,安徽大学计算机科学与技术学院讲师.研究方向为信息安全. E-mail:cuijie@mail.ustc.edu.cn
- 基金资助:
- 国家自然科学基金 (No.60903217,No.61173188,No.61173187); 中央高校基本科研业务费专项资金 (No.WK0110000027); 国家自然科学基金数学天元基金 (No.11126174); 安徽省高校自然科学研究重点项目 (No.KJ2013A017); 江苏省自然科学基金 (No.BK2011357); 安徽大学博士科研启动经费项目

Algebraic Attack on Rijndael-192 Based on Grobner Basis

CUI Jie^1,2, HUANG Liu-sheng^1,3, ZHONG Hong², YANG Wei^1,3

1. School of Computer Science and Technology,University of Scienc and Technology of China,Hefei,Anhui 230026,China;
2. School of Computer Science and Technology,Anhui University,Hefei,Anhui 230039,China;
3. Suzhou Institute for Advanced Study,University of Science and Technology of China,Suzhou,Jiangsu 215123,China

Received:2012-05-16 Revised:2012-08-10 Online:2013-05-25 Published:2013-05-25
- Supported by:
- National Natural Science Foundation of China (No.60903217, No.61173188, No.61173187); Fundamental Research Funds for the Central Universities (No.WK0110000027); National Natural Science Foundation of China Tianyuan Fund For Mathematics (No.11126174); Key Program of Natural Science Research Projrct of Colleges and Universities of Anhui Province (No.KJ2013A017); Natural Science Foundation of Jiangsu Province (No.BK2011357); Doctoral Scientific Research Foundation of Anhui Province

摘要/Abstract

摘要： 由于对Rijndael算法实施Grobner基攻击的一个关键环节是构造出其零维Grobner基,本文对Rijndael-192密码的线性变换和多变元方程系统进行了深入研究,通过选择合理的项序及变量次序,提出了Rijndael-192零维Grobner基的构造方法.文中详述了该Grobner基的构造方法,并给出了相关性质的理论证明.此外,本文提出了一种Rijndael-192的Grobner基攻击方案,攻击复杂度低于穷举攻击.

关键词: Rijndael算法, Grobner基, 代数攻击, 多变元方程系统

Abstract: Because a key step of Grobner basis attack on Rijndael is constructing its zero-dimensional Grobner basis,authors perform some particular studies on the linear transformation and the system of multivariate polynomial equations of Rijndael-192,and propose its zero-dimensional Grobner basis construction method through choosing suitable term order and variable order.After presenting the construction method of the Grobner basis,authors give the necessary theorical proves.Moreover,authors propose an algebraic attack on Rijndael-192 based on Grobner basis.Analysis suggest that the attack complexity is lower than exhaustive attack.

Key words: Rijndael algorithm, Grobner basis, Algebraic attack, Multivariate equation system

中图分类号:

TP309.7

崔杰, 黄刘生, 仲红, 等. 基于Grobner基的Rijndael-192代数攻击方案[J]. 电子学报, 2013, 41(5): 833-839.

CUI Jie, HUANG Liu-sheng, ZHONG Hong, et al. Algebraic Attack on Rijndael-192 Based on Grobner Basis[J]. Acta Electronica Sinica, 2013, 41(5): 833-839.

参考文献

[1] Daemen J,Rijmen V.AES proposal:Rijndael .the First Advanced Encryption Standard Candidate Coference .USA,NIST,1998.1-45.
[2] 魏悦川,孙兵,李超.对Rijndael-256算法新的积分攻击[J].电子学报,2011,39(2):476-480. Wei Y C,Sun B,Li C.New integral attack on Rijndael-256[J].Acta Electronical Sinica,2011,39(2):476-480.(in Chinese)
[3] Faugère J C,Gianni P,Lazard D,Mora T.Efficient computation of zero-dimensional gröbner bases by change of ordering[J].Journal of Symbolic Computation,1993,16:329-344.
[4] Courtois N T,Pieprzyk J.Cryptanalysis of block ciphers with overdefined systems of equations .LACR eprint server:www.iacr.org,April 2002.
[5] Yu SASAKI.Known-key attacks on rijndael with large blocks and strengthening shiftrow parameter[J].IEICE TRANSACTIONS on Fundamentals of Electronics,Communications and Computer Sciences,2012,E95-A (1):21-28.
[6] Carlos Cid,Gaetan Leurent.An analysis of the XSL algorithm[J].Lecture Notes in Computer Science,2005,3788:333-345.
[7] Robshaw M J B,Murphy S.Comments on the security of the AES and the XSL technique .http://www.cosic.esat.kuleuven.ac.be/nessie/reports/,May 2007.
[8] Johannes Buchmann,Andrei Pyshkin,Ralf-Philipp Weinmann.A zero-dimensional Grobner basis for AES-128[J].Lecture Notes in Computer Science,2006,4047:78-88.
[9] Satrajit Ghosh,Abhijit Das.An improvement of linearization-based algebraic attacks[J].Lecture Notes in Computer Science,2011,7011:157-167.
[10] Z'aba M.R,Wong K,Dawson E,et al.Algebraic analysis of small scale LEX-BES .Malaysia,Proceedings of International Cryptology Conference 2010 .Melaka:Universiti Teknikal Malaysia Melaka,2010.77-82.
[11] Ajwa I A,Liu Zhoujun,Wang Paul.Grobner bases algorithm .http://www.cm.mcs.kent.edu/reports/ 1995/gb.pdf,June 2,2007.
[12] Zhou Yongbin,Wu Wenling,Xu Nannan,Feng Dengguo.Differential fault attack on camellia[J].Chinese Journal of Electronics,2009,18(1):13-19.
[13] Johannes Buchmann,Andrei Pyshkin,Ralf-Philipp Weinmann.Block ciphers sensitive to Grobner basis attacks[J].Lecture Notes in Computer Science,2006,3860:313-331.
[14] Thomas Becker,Volker Weispfenning.Grobner Bases-A Computational Approach to Commutative Algebra[M].New York/Berlin:Springer-Verlag,1991.
[15] Faugère,Jean-Charles.A new efficient algorithm for computing Grobner bases without reduction to 0 F5 .the 2002 international symposium on Symbolic and algebraic computation .Lille:ACM,2002.44-60.
[16] 刘景伟,韦宝典.AES S盒的密码特性分析[J].西安电子科技大学学报,2004,31(2):255-259. Liu J W,Wei B D.Analysis of the cryptographic properties of the AES S-box[J].Journal of Xidian University,2004,31(2):255-259.(in Chinese)
[17] Jean-Charles Faugère,Antoine Joux.Algebraic Cryptanalysis of Hidden Field Equation (HFE) Cryptosystems Using Gröbner Bases . Advances in Cryptology-CRYPTO 2003 .California:Springer-Verlag,2003.LNCS 2729.44-60.

基于Grobner基的Rijndael-192代数攻击方案

Algebraic Attack on Rijndael-192 Based on Grobner Basis

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 6

编辑推荐

Metrics

[1]	祁传达, 俞迎达. 一类布尔函数零化子的代数次数[J]. 电子学报, 2012, 40(6): 1177-1179.
[2]	王秋艳;金晨辉. 多输出布尔函数与布尔函数代数免疫阶之间的关系[J]. 电子学报, 2011, 39(1): 124-127.
[3]	谢佳;王天择. 寻找布尔函数的零化子[J]. 电子学报, 2010, 38(11): 2686-2690.
[4]	张文英, 武传坤, 于静之. 密码学中布尔函数的零化子[J]. 电子学报, 2006, 34(1): 51-54.
[5]	张增辉;成礼智. 具有任意正则阶的M-带对称正交小波设计[J]. 电子学报, 2004, 32(7): 1094-1098.
[6]	肖国镇;白恩健;刘晓娟. AES密码分析的若干新进展[J]. 电子学报, 2003, 31(10): 1549-1554.