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

Clc Number:

Fund Project:

  • Article
  • |
  • Figures
  • |
  • Metrics
  • |
  • Reference
  • |
  • Related
  • |
  • Cited by
  • |
  • Materials
  • |
  • Comments
    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.

    Reference
    Related
    Cited by
Get Citation
Share
Article Metrics
  • Abstract:
  • PDF:
  • HTML:
  • Cited by:
History
  • Received:July 28,2011
  • Revised:
  • Adopted:
  • Online: August 28,2012
  • Published:
Article QR Code