| 引用本文: | 彭昌勇,祝跃飞,康绯,等.AES轮变换的代数正规型及其应用.[J].国防科技大学学报,2012,34(2):14-17.[点击复制] |
| PENG Changyong,ZHU Yuefei,KANG Fei,et al.The ANFs of the component functions of AES round transformation and its application[J].Journal of National University of Defense Technology,2012,34(2):14-17[点击复制] |
|
| |
|
|
| 本文已被：浏览 7932次 下载 6655次 |
| AES轮变换的代数正规型及其应用 |
| 彭昌勇1,2, 祝跃飞1, 康绯1, 米顺强3 |
|
(1.信息工程大学 信息工程学院，河南 郑州 450002;2.信息工程大学 理学院，河南 郑州 450000;3.95833部队，北京 100081)
|
| 摘要: |
| 每个布尔函数的代数正规型(ANF)是唯一的，对于研究布尔函数有重要意义。利用Mathematica软件得到了高级加密标准的轮变换(Sbox, ShiftRow和MixColumn的复合)的128个分量函数的代数正规型。每个分量函数都是32元布尔函数,其项数在448～545，平均为496，远远小于随机32元布尔函数的平均项数231。这表明AES轮变换与随机置换有巨大偏差。得到这些ANF的时间复杂度在一个2GHz的PC机上只用几分钟。该方法优于通过真值表得到ANF的经典算法——其得到128个分量函数的时间复杂度为O(128×32×232) = O(244)。作为应用，利用得到的ANF建立了一轮AES的一个方程系统，并用Cryptominisat 2.9.0进行求解。使用Guess-and-Determine的方法，利用一个已知明密对，可以在PC机上233h内得到全部128比特密钥。 |
| 关键词: 高级加密标准 代数正规型 分组密码 符号计算 代数攻击 Cryptominisat软件 |
| DOI： |
| 投稿日期：2011-07-28 |
| 基金项目:国家863高技术计划项目（2007AA01Z471）；郑州市科技创新团队项目（10CXTD150） |
|
| The ANFs of the component functions of AES round transformation and its application |
| PENG Changyong1,2, ZHU Yuefei1, KANG Fei1, MI Shunqiang3 |
|
(1.Institute of Information Engineering, Information Engineering University, Zhengzhou 450002,China;2.Institute of Science, Information Engineering University, Zhengzhou 450000, China;3.Unit 95833，Beijing 100081,China)
|
| Abstract: |
| The Algebraic Normal Form (ANF) of a Boolean function is unique, which is very important in the research of Boolean function. The 128 ANFs of the component functions of the round transformation (the composition of Sbox, ShiftRow and MixColumn)of the Advanced Encryption Standard(AES) were obtained by using the Mathematica software. Each component function is a 32-variable Boolean function. The number of terms is between 448 and 545, and the average number is 496, which is much smaller than 231, the number of terms of a random 32-variable Boolean function. This shows a great deviation of the AES round transformation with a random permutation. The time complexity of getting the 128 ANFs of the AES round transformation is only a few minutes on a PC with a 2GHz CPU. The method is better than the classical one in computing the ANF from truth table, with total time complexity of obtaining the 128 ANFs O(128×32×232) = O(244). As an application, an equation system for 1-full round of AES was obtained by using the ANFs. The equation system was solved by using Cryptominisat 2.9.0. By the method of Guess-and-Determine, the 128 bits of keys can be recovered in less than 233hours on a PC with one known plaintext. |
| Keywords: advanced encryption standard algebraic normal form block cipher symbolic computation algebraic attack Cryptominisat software |
|
|
|
|
|
