AES轮变换的代数正规型及其应用

每个布尔函数的代数正规型(ANF)是唯一的,对于研究布尔函数有重要意义.利用Mathematica软件得到了高级加密标准的轮变换(Sbox,ShiftRow和MixColumn的复合)的128个分量函数的代数正规型.每个分量函数都是32元布尔函数,其项数在448 ～ 545,平均为496,远远小于随机32元布尔函数的平均项数231.这表明AES轮变换与随机置换有巨大偏差.得到这些ANF的时间复杂度在一个2GHz的PC机上只用几分钟.该方法优于通过真值表得到ANF的经典算法——其得到128个分量函数的时间复杂度为0( 128×32 ×232)=0(244).作为应用,利用得到的ANF建立了一轮AES的一个方程系统,并用Cryptominisat 2.9.0进行求解.使用Guess-and-Determine的方法,利用一个已知明密对,可以在PC机上233h内得到全部128比特密钥.

The ANFs of the component functions of AES round transformation and its application

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,Shift Row 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 [1] 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 Cryptominis at 2.9.0[2].By the method of Guess-and-Determine,the 128 bits of keys can be recovered in less than 233 hours on a PC with one known plaintext.