AES轮变换的代数正规型及其应用
DOI:
作者:
作者单位:

作者简介:

通讯作者:

中图分类号:

基金项目:

国家863高技术计划项目(2007AA01Z471);郑州市科技创新团队项目(10CXTD150)


The ANFs of the component functions of AES round transformation and its application
Author:
Affiliation:

Fund Project:

  • 摘要
  • |
  • 图/表
  • |
  • 访问统计
  • |
  • 参考文献
  • |
  • 相似文献
  • |
  • 引证文献
  • |
  • 资源附件
  • |
  • 文章评论
    摘要:

    每个布尔函数的代数正规型(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比特密钥。

    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.

    参考文献
    相似文献
    引证文献
引用本文

彭昌勇,祝跃飞,康绯,等. 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.

复制
分享
文章指标
  • 点击次数:
  • 下载次数:
  • HTML阅读次数:
  • 引用次数:
历史
  • 收稿日期:2011-07-28
  • 最后修改日期:
  • 录用日期:
  • 在线发布日期: 2012-08-28
  • 出版日期:
文章二维码