Federal Information Processing Standards Publication 197


November 26, 2001


Announcing the


ADVANCED ENCRYPTION STANDARD (AES)


Federal Information Processing Standards Publications (FIPS PUBS) are issued by the National Institute of Standards and Technology (NIST) after approval by the Secretary of Commerce pursuant to Section 5131 of the Information Technology Management Reform Act of 1996 (Public Law 104-106) and the Computer Security Act of 1987 (Public Law 100-235).


  1. Name of Standard. Advanced Encryption Standard (AES) (FIPS PUB 197).

  2. Category of Standard. Computer Security Standard, Cryptography.

  3. Explanation. The Advanced Encryption Standard (AES) specifies a FIPS-approved cryptographic algorithm that can be used to protect electronic data. The AES algorithm is a symmetric block cipher that can encrypt (encipher) and decrypt (decipher) information. Encryption converts data to an unintelligible form called ciphertext; decrypting the ciphertext converts the data back into its original form, called plaintext.

    The AES algorithm is capable of using cryptographic keys of 128, 192, and 256 bits to encrypt and decrypt data in blocks of 128 bits.

  4. Approving Authority. Secretary of Commerce.

  5. Maintenance Agency. Department of Commerce, National Institute of Standards and Technology, Information Technology Laboratory (ITL).

  6. Applicability. This standard may be used by Federal departments and agencies when an agency determines that sensitive (unclassified) information (as defined in P. L. 100-235) requires cryptographic protection.

    Other FIPS-approved cryptographic algorithms may be used in addition to, or in lieu of, this standard. Federal agencies or departments that use cryptographic devices for protecting classified information can use those devices for protecting sensitive (unclassified) information in lieu of this standard.

    In addition, this standard may be adopted and used by non-Federal Government organizations. Such use is encouraged when it provides the desired security for commercial and private organizations.

  7. Specifications. Federal Information Processing Standard (FIPS) 197, Advanced Encryption Standard (AES) (affixed).

  8. Implementations. The algorithm specified in this standard may be implemented in software, firmware, hardware, or any combination thereof. The specific implementation may depend on several factors such as the application, the environment, the technology used, etc. The algorithm shall be used in conjunction with a FIPS approved or NIST recommended mode of operation. Object Identifiers (OIDs) and any associated parameters for AES used in these modes are available at the Computer Security Objects Register (CSOR), located at http://csrc.nist.gov/csor/ [2].

    Implementations of the algorithm that are tested by an accredited laboratory and validated will be considered as complying with this standard. Since cryptographic security depends on many factors besides the correct implementation of an encryption algorithm, Federal Government employees, and others, should also refer to NIST Special Publication 800-21, Guideline for Implementing Cryptography in the Federal Government, for additional information and guidance (NIST SP 800-21 is available at http://csrc.nist.gov/publications/).

  9. Implementation Schedule. This standard becomes effective on May 26, 2002.

  10. Patents. Implementations of the algorithm specified in this standard may be covered by

    U.S. and foreign patents.

  11. Export Control. Certain cryptographic devices and technical data regarding them are subject to Federal export controls. Exports of cryptographic modules implementing this standard and technical data regarding them must comply with these Federal regulations and be licensed by the Bureau of Export Administration of the U.S. Department of Commerce. Applicable Federal government export controls are specified in Title 15, Code of Federal Regulations (CFR) Part 740.17; Title 15, CFR Part 742; and Title 15, CFR Part 774, Category 5, Part 2.

  12. Qualifications. NIST will continue to follow developments in the analysis of the AES algorithm. As with its other cryptographic algorithm standards, NIST will formally reevaluate this standard every five years.

    Both this standard and possible threats reducing the security provided through the use of this standard will undergo review by NIST as appropriate, taking into account newly available analysis and technology. In addition, the awareness of any breakthrough in technology or any mathematical weakness of the algorithm will cause NIST to reevaluate this standard and provide necessary revisions.

  13. Waiver Procedure. Under certain exceptional circumstances, the heads of Federal agencies, or their delegates, may approve waivers to Federal Information Processing Standards (FIPS). The heads of such agencies may redelegate such authority only to a senior official designated pursuant to Section 3506(b) of Title 44, U.S. Code. Waivers shall be granted only when compliance with this standard would

    1. adversely affect the accomplishment of the mission of an operator of Federal computer system or

    2. cause a major adverse financial impact on the operator that is not offset by government- wide savings.

      Agency heads may act upon a written waiver request containing the information detailed above. Agency heads may also act without a written waiver request when they determine that conditions for meeting the standard cannot be met. Agency heads may approve waivers only by a written decision that explains the basis on which the agency head made the required finding(s). A copy of each such decision, with procurement sensitive or classified portions clearly identified, shall be sent to: National Institute of Standards and Technology; ATTN: FIPS Waiver Decision, Information Technology Laboratory, 100 Bureau Drive, Stop 8900, Gaithersburg, MD 20899- 8900.

      In addition, notice of each waiver granted and each delegation of authority to approve waivers shall be sent promptly to the Committee on Government Operations of the House of Representatives and the Committee on Government Affairs of the Senate and shall be published promptly in the Federal Register.

      When the determination on a waiver applies to the procurement of equipment and/or services, a notice of the waiver determination must be published in the Commerce Business Daily as a part of the notice of solicitation for offers of an acquisition or, if the waiver determination is made after that notice is published, by amendment to such notice.

      A copy of the waiver, any supporting documents, the document approving the waiver and any supporting and accompanying documents, with such deletions as the agency is authorized and decides to make under Section 552(b) of Title 5, U.S. Code, shall be part of the procurement documentation and retained by the agency.

  14. Where to obtain copies. This publication is available electronically by accessing http://csrc.nist.gov/publications/. A list of other available computer security publications, including ordering information, can be obtained from NIST Publications List 91, which is available at the same web site. Alternatively, copies of NIST computer security publications are available from: National Technical Information Service (NTIS), 5285 Port Royal Road, Springfield, VA 22161.


Federal Information Processing Standards Publication 197


November 26, 2001


Specification for the ADVANCED ENCRYPTION STANDARD (AES)

Table of Contents

  1. INTRODUCTION 5

  2. DEFINITIONS 5

    1. GLOSSARY OF TERMS AND ACRONYMS 5

    2. ALGORITHM PARAMETERS, SYMBOLS, AND FUNCTIONS 6

  3. NOTATION AND CONVENTIONS 7

    1. INPUTS AND OUTPUTS 7

    2. BYTES 8

    3. ARRAYS OF BYTES 8

    4. THE STATE 9

    5. THE STATE AS AN ARRAY OF COLUMNS 10

  4. MATHEMATICAL PRELIMINARIES 10

    1. ADDITION 10

    2. MULTIPLICATION 10

      1. Multiplication by x 11

    3. POLYNOMIALS WITH COEFFICIENTS IN GF(28) 12

  5. ALGORITHM SPECIFICATION 13

    1. CIPHER 14

      1. SubBytes()Transformation 15

      2. ShiftRows() Transformation 17

      3. MixColumns() Transformation 17

      4. AddRoundKey() Transformation 18

    2. KEY EXPANSION 19

    3. INVERSE CIPHER 20

      1. InvShiftRows() Transformation 21

      2. InvSubBytes() Transformation 22

      3. InvMixColumns() Transformation 23

      4. Inverse of the AddRoundKey() Transformation 23

      5. Equivalent Inverse Cipher 23

  6. IMPLEMENTATION ISSUES 25

    1. KEY LENGTH REQUIREMENTS 25

    2. KEYING RESTRICTIONS 26

    3. PARAMETERIZATION OF KEY LENGTH, BLOCK SIZE, AND ROUND NUMBER 26

    4. IMPLEMENTATION SUGGESTIONS REGARDING VARIOUS PLATFORMS 26

APPENDIX A - KEY EXPANSION EXAMPLES 27

    1. EXPANSION OF A 128-BIT CIPHER KEY 27

    2. EXPANSION OF A 192-BIT CIPHER KEY 28

    3. EXPANSION OF A 256-BIT CIPHER KEY 30

APPENDIX B – CIPHER EXAMPLE 33

APPENDIX C – EXAMPLE VECTORS 35

C.1 AES-128 (NK=4, NR=10) 35

C.2 AES-192 (NK=6, NR=12) 38

C.3 AES-256 (NK=8, NR=14) 42

APPENDIX D - REFERENCES 47


Table of Figures

Figure 1. Hexadecimal representation of bit patterns. 8

Figure 2. Indices for Bytes and Bits. 9

Figure 3. State array input and output. 9

Figure 4. Key-Block-Round Combinations. 14

Figure 5. Pseudo Code for the Cipher. 15

Figure 6. SubBytes() applies the S-box to each byte of the State. 16

Figure 7. S-box: substitution values for the byte xy (in hexadecimal format). 16

Figure 8. ShiftRows() cyclically shifts the last three rows in the State 17

Figure 9. MixColumns() operates on the State column-by-column. 18

Figure 10. AddRoundKey() XORs each column of the State with a word from the key schedule. 19

Figure 11. Pseudo Code for Key Expansion. 20

Figure 12. Pseudo Code for the Inverse Cipher. 21

Figure 13. InvShiftRows()cyclically shifts the last three rows in the State. 22

Figure 14. Inverse S-box: substitution values for the byte xy (in hexadecimal format). 22

Figure 15. Pseudo Code for the Equivalent Inverse Cipher. 25


  1. Introduction

    This standard specifies the Rijndael algorithm ([3] and [4]), a symmetric block cipher that can process data blocks of 128 bits, using cipher keys with lengths of 128, 192, and 256 bits. Rijndael was designed to handle additional block sizes and key lengths, however they are not adopted in this standard.

    Throughout the remainder of this standard, the algorithm specified herein will be referred to as “the AES algorithm.” The algorithm may be used with the three different key lengths indicated above, and therefore these different “flavors” may be referred to as “AES-128”, “AES-192”, and “AES-256”.

    This specification includes the following sections:

    1. Definitions of terms, acronyms, and algorithm parameters, symbols, and functions;

    2. Notation and conventions used in the algorithm specification, including the ordering and numbering of bits, bytes, and words;

    3. Mathematical properties that are useful in understanding the algorithm;

    4. Algorithm specification, covering the key expansion, encryption, and decryption routines;

    5. Implementation issues, such as key length support, keying restrictions, and additional block/key/round sizes.

    The standard concludes with several appendices that include step-by-step examples for Key Expansion and the Cipher, example vectors for the Cipher and Inverse Cipher, and a list of references.


  2. Definitions


    1. Glossary of Terms and Acronyms

      The following definitions are used throughout this standard: AES Advanced Encryption Standard

      Affine A transformation consisting of multiplication by a matrix followed by Transformation the addition of a vector.

      Array An enumerated collection of identical entities (e.g., an array of bytes). Bit A binary digit having a value of 0 or 1.

      Block Sequence of binary bits that comprise the input, output, State, and Round Key. The length of a sequence is the number of bits it contains. Blocks are also interpreted as arrays of bytes.

      Byte A group of eight bits that is treated either as a single entity or as an array of 8 individual bits.

      Cipher Series of transformations that converts plaintext to ciphertext using the Cipher Key.

      Cipher Key Secret, cryptographic key that is used by the Key Expansion routine to generate a set of Round Keys; can be pictured as a rectangular array of bytes, having four rows and Nk columns.

      Ciphertext Data output from the Cipher or input to the Inverse Cipher.

      Inverse Cipher Series of transformations that converts ciphertext to plaintext using the Cipher Key.

      Key Expansion Routine used to generate a series of Round Keys from the Cipher Key. Plaintext Data input to the Cipher or output from the Inverse Cipher.

      Rijndael Cryptographic algorithm specified in this Advanced Encryption Standard (AES).

      Round Key Round keys are values derived from the Cipher Key using the Key Expansion routine; they are applied to the State in the Cipher and Inverse Cipher.

      State Intermediate Cipher result that can be pictured as a rectangular array of bytes, having four rows and Nb columns.

      S-box Non-linear substitution table used in several byte substitution transformations and in the Key Expansion routine to perform a one- for-one substitution of a byte value.

      Word A group of 32 bits that is treated either as a single entity or as an array of 4 bytes.


    2. Algorithm Parameters, Symbols, and Functions

      The following algorithm parameters, symbols, and functions are used throughout this standard:

      AddRoundKey() Transformation in the Cipher and Inverse Cipher in which a Round Key is added to the State using an XOR operation. The length of a Round Key equals the size of the State (i.e., for Nb = 4, the Round Key length equals 128 bits/16 bytes).


      InvMixColumns()Transformation in

      the

      Inverse

      Cipher

      that

      is

      the

      inverse

      of

      MixColumns().

      InvShiftRows() Transformation in


      the


      Inverse


      Cipher


      that


      is


      the


      inverse


      of

      ShiftRows().

      InvSubBytes() Transformation in the Inverse Cipher that is the inverse of

      SubBytes().

      K Cipher Key.

      MixColumns() Transformation in the Cipher that takes all of the columns of the State and mixes their data (independently of one another) to produce new columns.

      Nb Number of columns (32-bit words) comprising the State. For this standard, Nb = 4. (Also see Sec. 6.3.)

      Nk Number of 32-bit words comprising the Cipher Key. For this standard, Nk = 4, 6, or 8. (Also see Sec. 6.3.)

      Nr Number of rounds, which is a function of Nk and Nb (which is fixed). For this standard, Nr = 10, 12, or 14. (Also see Sec. 6.3.)

      Rcon[] The round constant word array.

      RotWord() Function used in the Key Expansion routine that takes a four-byte word and performs a cyclic permutation.

      ShiftRows() Transformation in the Cipher that processes the State by cyclically shifting the last three rows of the State by different offsets.

      SubBytes() Transformation in the Cipher that processes the State using a non- linear byte substitution table (S-box) that operates on each of the State bytes independently.

      SubWord() Function used in the Key Expansion routine that takes a four-byte input word and applies an S-box to each of the four bytes to produce an output word.

      XOR Exclusive-OR operation.

      Exclusive-OR operation.

      Multiplication of two polynomials (each with degree < 4) modulo

      x4 + 1.

      • Finite field multiplication.


  3. Notation and Conventions


    1. Inputs and Outputs

      The input and output for the AES algorithm each consist of sequences of 128 bits (digits with values of 0 or 1). These sequences will sometimes be referred to as blocks and the number of bits they contain will be referred to as their length. The Cipher Key for the AES algorithm is a sequence of 128, 192 or 256 bits. Other input, output and Cipher Key lengths are not permitted by this standard.

      The bits within such sequences will be numbered starting at zero and ending at one less than the sequence length (block length or key length). The number i attached to a bit is known as its index and will be in one of the ranges 0 i < 128, 0 i < 192 or 0 i < 256 depending on the block length and key length (specified above).

    2. Bytes

      The basic unit for processing in the AES algorithm is a byte, a sequence of eight bits treated as a single entity. The input, output and Cipher Key bit sequences described in Sec. 3.1 are processed as arrays of bytes that are formed by dividing these sequences into groups of eight contiguous bits to form arrays of bytes (see Sec. 3.3). For an input, output or Cipher Key denoted by a, the bytes in the resulting array will be referenced using one of the two forms, an or a[n], where n will be in one of the following ranges:

      Key length = 128 bits, 0 n < 16; Block length = 128 bits, 0 n < 16; Key length = 192 bits, 0 n < 24;

      Key length = 256 bits, 0 n < 32.

      All byte values in the AES algorithm will be presented as the concatenation of its individual bit values (0 or 1) between braces in the order {b7, b6, b5, b4, b3, b2, b1, b0}. These bytes are interpreted as finite field elements using a polynomial representation:


      7

      b7 x


      6

      • b6 x


        5

      • b5 x


        4

      • b4 x


        3

      • b3 x


        2

      • b2 x


        7

        i

      • b1 x b0 bi x


      . (3.1)

      i0

      For example, {01100011} identifies the specific finite field element

      x6 x5 x 1.

      It is also convenient to denote byte values using hexadecimal notation with each of two groups of four bits being denoted by a single character as in Fig. 1.


      Bit Pattern

      Character

      0000

      0

      0001

      1

      0010

      2

      0011

      3

      Bit Pattern

      Character

      0100

      4

      0101

      5

      0110

      6

      0111

      7

      Bit Pattern

      Character

      1000

      8

      1001

      9

      1010

      a

      1011

      b

      Bit Pattern

      Character

      1100

      c

      1101

      d

      1110

      e

      1111

      f

      Figure 1. Hexadecimal representation of bit patterns.


      Hence the element {01100011} can be represented as {63}, where the character denoting the four-bit group containing the higher numbered bits is again to the left.

      Some finite field operations involve one additional bit (b8) to the left of an 8-bit byte. Where this extra bit is present, it will appear as ‘{01}’ immediately preceding the 8-bit byte; for example, a 9-bit sequence will be presented as {01}{1b}.


    3. Arrays of Bytes

      Arrays of bytes will be represented in the following form:

      a0 a1 a2 ...a15

      The bytes and the bit ordering within bytes are derived from the 128-bit input sequence

      input0 input1 input2 … input126 input127

      as follows:

      a0 = {input0, input1, …, input7}; a1 = {input8, input9, …, input15};

      a15 = {input120, input121, …, input127}.

      The pattern can be extended to longer sequences (i.e., for 192- and 256-bit keys), so that, in general,

      Input bit sequence

      0

      1

      2

      3

      4

      5

      6

      7

      8

      9

      10

      11

      12

      13

      14

      15

      16

      17

      18

      19

      20

      21

      22

      23

      Byte number

      0

      1

      2

      Bit numbers in byte

      7

      6

      5

      4

      3

      2

      1

      0

      7

      6

      5

      4

      3

      2

      1

      0

      7

      6

      5

      4

      3

      2

      1

      0

      an = {input8n, input8n+1, …, input8n+7}. (3.2) Taking Sections 3.2 and 3.3 together, Fig. 2 shows how bits within each byte are numbered.


      Figure 2. Indices for Bytes and Bits.


    4. The State

      Internally, the AES algorithm’s operations are performed on a two-dimensional array of bytes called the State. The State consists of four rows of bytes, each containing Nb bytes, where Nb is the block length divided by 32. In the State array denoted by the symbol s, each individual byte has two indices, with its row number r in the range 0 r < 4 and its column number c in the range 0 c < Nb. This allows an individual byte of the State to be referred to as either sr,c or s[r,c]. For this standard, Nb=4, i.e., 0 c < 4 (also see Sec. 6.3).

      At the start of the Cipher and Inverse Cipher described in Sec. 5, the input – the array of bytes in0, in1, … in15 – is copied into the State array as illustrated in Fig. 3. The Cipher or Inverse Cipher operations are then conducted on this State array, after which its final value is copied to the output – the array of bytes out0, out1, … out15.

      input bytes State array output bytes


      in0

      in4

      in8

      in12

      in1

      in5

      in9

      in13

      in2

      in6

      in10

      in14

      in3

      in7

      in11

      in15

      s0,0

      s0,1

      s0,2

      s0,3

      s1,0

      s1,1

      s1,2

      s1,3

      s2,0

      s2,1

      s2,2

      s2,3

      s3,0

      s3,1

      s3,2

      s3,3

      out0

      out4

      out8

      out12

      out1

      out5

      out9

      out13

      out2

      out6

      out10

      out14

      out3

      out7

      out11

      out15

      多 多


      Figure 3. State array input and output.


      Hence, at the beginning of the Cipher or Inverse Cipher, the input array, in, is copied to the State array according to the scheme:

      s[r, c] = in[r + 4c] for 0 r < 4 and 0 c < Nb, (3.3)

      and at the end of the Cipher and Inverse Cipher, the State is copied to the output array out as follows:

      out[r + 4c] = s[r, c] for 0 r < 4 and 0 c < Nb. (3.4)

    5. The State as an Array of Columns

      The four bytes in each column of the State array form 32-bit words, where the row number r provides an index for the four bytes within each word. The state can hence be interpreted as a one-dimensional array of 32 bit words (columns), w0...w3, where the column number c provides an index into this array. Hence, for the example in Fig. 3, the State can be considered as an array of four words, as follows:


      w0 = s0,0 s1,0 s2,0 s3,0

      w2 = s0,2 s1,2 s2,2 s3,2

      w1 = s0,1 s1,1 s2,1 s3,1

      w3 = s0,3 s1,3 s2,3 s3,3 .

      (3.5)


  4. Mathematical Preliminaries

    All bytes in the AES algorithm are interpreted as finite field elements using the notation introduced in Sec. 3.2. Finite field elements can be added and multiplied, but these operations are different from those used for numbers. The following subsections introduce the basic mathematical concepts needed for Sec. 5.


    1. Addition

      The addition of two elements in a finite field is achieved by “adding” the coefficients for the corresponding powers in the polynomials for the two elements. The addition is performed with

      the XOR operation (denoted by ) - i.e., modulo 2 - so that 1 1 0 , 10 1, and Consequently, subtraction of polynomials is identical to addition of polynomials.

      0 0 0 .

      Alternatively, addition of finite field elements can be described as the modulo 2 addition of corresponding bits in the byte. For two bytes {a7a6a5a4a3a2a1a0} and {b7b6b5b4b3b2b1b0}, the sum is

      {c7c6c5c4c3c2c1c0}, where each ci = ai bi (i.e., c7 = a7 b7, c6 = a6 b6, ...c0 = a0 b0).

      For example, the following expressions are equivalent to one another:

      (x6 x4 x2 x 1)

      + (x7 x 1) =

      x7 x6 x4 x 2

      (polynomial notation);


      {01010111} {10000011} = {11010100} (binary notation);

      {57} {83} = {d4} (hexadecimal notation).


    2. Multiplication

      In the polynomial representation, multiplication in GF(28) (denoted by ) corresponds with the multiplication of polynomials modulo an irreducible polynomial of degree 8. A polynomial is irreducible if its only divisors are one and itself. For the AES algorithm, this irreducible polynomial is

      m(x) x 8 x 4 x 3 x 1 , (4.1)

      or {01}{1b} in hexadecimal notation.

      For example, {57} {83} = {c1}, because

      (x 6 x 4 x 2 x 1) (x 7 x 1) =


      =

      and


      x13 x11 x 9 x8 x 7

      x 7 x 5 x 3 x 2 x

      x 6 x 4 x 2 x 1

      x13 x11 x 9 x8 x 6 x 5 x 4 x 3 1

      x13 x11 x 9 x8 x 6 x 5 x 4 x 3 1

      =

      modulo ( x8 x 4 x 3 x 1 )

      x 7 x 6 1 .

      The modular reduction by m(x) ensures that the result will be a binary polynomial of degree less than 8, and thus can be represented by a byte. Unlike addition, there is no simple operation at the byte level that corresponds to this multiplication.

      The multiplication defined above is associative, and the element {01} is the multiplicative identity. For any non-zero binary polynomial b(x) of degree less than 8, the multiplicative inverse of b(x), denoted b-1(x), can be found as follows: the extended Euclidean algorithm [7] is used to compute polynomials a(x) and c(x) such that

      b(x)a(x) m(x)c(x) 1. (4.2)

      Hence, a(x) b(x) mod m(x) 1, which means

      b 1 (x) a(x) mod m(x) . (4.3)

      Moreover, for any a(x), b(x) and c(x) in the field, it holds that

      a(x) (b(x) c(x)) a(x) b(x) a(x) c(x) .

      It follows that the set of 256 possible byte values, with XOR used as addition and the multiplication defined as above, has the structure of the finite field GF(28).


      • Multiplication by x

        Multiplying the binary polynomial defined in equation (3.1) with the polynomial x results in

        8

        b7 x

        7

        • b6 x

          6

        • b5 x

          5

        • b4 x

          4

        • b3 x

          3

        • b2 x

          2

        • b1 x

          b0 x . (4.4)

          The result

          x b(x) is obtained by reducing the above result modulo m(x), as defined in equation

          (4.1). If b7 = 0, the result is already in reduced form. If b7 = 1, the reduction is accomplished by subtracting (i.e., XORing) the polynomial m(x). It follows that multiplication by x (i.e.,

          {00000010} or {02}) can be implemented at the byte level as a left shift and a subsequent conditional bitwise XOR with {1b}. This operation on bytes is denoted by xtime(). Multiplication by higher powers of x can be implemented by repeated application of xtime(). By adding intermediate results, multiplication by any constant can be implemented.

          For example, {57} {13} = {fe} because


          thus,

          {57} {02} = xtime({57}) = {ae}

          {57} {04} = xtime({ae}) = {47}

          {57} {08} = xtime({47}) = {8e}

          {57} {10} = xtime({8e}) = {07},


          {57} {13} = {57} ({01} {02} {10})

          = {57} {ae} {07}

          = {fe}.


    3. Polynomials with Coefficients in GF(28)

      Four-term polynomials can be defined - with coefficients that are finite field elements - as:

      3

      a(x) a3 x

      2

      • a2 x

      • a1 x a0

        (4.5)

        which will be denoted as a word in the form [a0 , a1 , a2 , a3 ]. Note that the polynomials in this section behave somewhat differently than the polynomials used in the definition of finite field elements, even though both types of polynomials use the same indeterminate, x. The coefficients in this section are themselves finite field elements, i.e., bytes, instead of bits; also, the multiplication of four-term polynomials uses a different reduction polynomial, defined below. The distinction should always be clear from the context.

        To illustrate the addition and multiplication operations, let

        3

        b(x) b3 x

        2

      • b2 x

      • b1x b0

        (4.6)

        define a second four-term polynomial. Addition is performed by adding the finite field coefficients of like powers of x. This addition corresponds to an XOR operation between the corresponding bytes in each of the words – in other words, the XOR of the complete word values.

        Thus, using the equations of (4.5) and (4.6),

        3

        a(x) b(x) (a3 b3 )x

        2

        (a2 b2 )x

        (a1 b1 )x (a0 b0 )

        (4.7)

        Multiplication is achieved in two steps. In the first step, the polynomial product c(x) = a(x)

        b(x) is algebraically expanded, and like powers are collected to give


        where

        6

        c(x) c6 x

        5

      • c5 x

        4

      • c4 x

        3

      • c3 x

        2

      • c2 x

      • c1x c0

        (4.8)

        c0 a0 b0

        c1 a1 b0 a0 b1

        c2 a2 b0 a1 b1 a0 b2

        c4 a3 b1 a2 b2 a1 b3 c5 a3 b2 a2 b3

        c6 a3 b3


        (4.9)

        c3 a3 b0 a2 b1 a1 b2 a0 b3 .

        The result, c(x), does not represent a four-byte word. Therefore, the second step of the multiplication is to reduce c(x) modulo a polynomial of degree 4; the result can be reduced to a polynomial of degree less than 4. For the AES algorithm, this is accomplished with the polynomial x4 + 1, so that

        xi mod(x 4 1) xi mod 4 . (4.10)

        The modular product of a(x) and b(x), denoted by a(x) b(x), is given by the four-term polynomial d(x), defined as follows:


        with

        3

        d (x) d3 x

        2

      • d2 x

      • d1 x

        • d0

      (4.11)

      d0 (a0 b0 ) (a3 b1 ) (a2 b2 ) (a1 b3 ) d1 (a1 b0 ) (a0 b1 ) (a3 b2 ) (a2 b3 ) d 2 (a2 b0 ) (a1 b1 ) (a0 b2 ) (a3 b3 ) d3 (a3 b0 ) (a2 b1 ) (a1 b2 ) (a0 b3 )


      (4.12)

      When a(x) is a fixed polynomial, the operation defined in equation (4.11) can be written in matrix form as:

      d0

      a0

      a3 a2

      a1  b0

      d

      a a

      a a  b

      1 1 0

      3 2 1

      (4.13)

      d 2

      a2

      a1 a0

      a3  b2

        

        

      d3

      a3 a2

      a1 a0 b3

      Because

      x 4 1 is not an irreducible polynomial over GF(28), multiplication by a fixed four-term

      polynomial is not necessarily invertible. However, the AES algorithm specifies a fixed four-term polynomial that does have an inverse (see Sec. 5.1.3 and Sec. 5.3.3):

      a(x) = {03}x3 + {01}x2 + {01}x + {02} (4.14)

      a-1(x) = {0b}x3 + {0d}x2 + {09}x + {0e}. (4.15)

      Another polynomial used in the AES algorithm (see the RotWord() function in Sec. 5.2) has a0

      = a1 = a2 = {00} and a3 = {01}, which is the polynomial x3. Inspection of equation (4.13) above will show that its effect is to form the output word by rotating bytes in the input word. This means that [b0, b1, b2, b3] is transformed into [b1, b2, b3, b0].


  5. Algorithm Specification

    For the AES algorithm, the length of the input block, the output block and the State is 128 bits. This is represented by Nb = 4, which reflects the number of 32-bit words (number of columns) in the State.

    For the AES algorithm, the length of the Cipher Key, K, is 128, 192, or 256 bits. The key length is represented by Nk = 4, 6, or 8, which reflects the number of 32-bit words (number of columns) in the Cipher Key.

    For the AES algorithm, the number of rounds to be performed during the execution of the algorithm is dependent on the key size. The number of rounds is represented by Nr, where Nr = 10 when Nk = 4, Nr = 12 when Nk = 6, and Nr = 14 when Nk = 8.

    The only Key-Block-Round combinations that conform to this standard are given in Fig. 4. For implementation issues relating to the key length, block size and number of rounds, see Sec. 6.3.


    Key Length

    (Nk words)

    Block Size

    (Nb words)

    Number of Rounds

    (Nr)

    AES-128

    4

    4

    10

    AES-192

    6

    4

    12

    AES-256

    8

    4

    14

    Figure 4. Key-Block-Round Combinations.


    For both its Cipher and Inverse Cipher, the AES algorithm uses a round function that is composed of four different byte-oriented transformations: 1) byte substitution using a substitution table (S-box), 2) shifting rows of the State array by different offsets, 3) mixing the data within each column of the State array, and 4) adding a Round Key to the State. These transformations (and their inverses) are described in Sec. 5.1.1-5.1.4 and 5.3.1-5.3.4.

    The Cipher and Inverse Cipher are described in Sec. 5.1 and Sec. 5.3, respectively, while the Key Schedule is described in Sec. 5.2.


    1. Cipher

      At the start of the Cipher, the input is copied to the State array using the conventions described in Sec. 3.4. After an initial Round Key addition, the State array is transformed by implementing a round function 10, 12, or 14 times (depending on the key length), with the final round differing

      slightly from the first Nr

      Sec. 3.4.

      1 rounds. The final State is then copied to the output as described in

      The round function is parameterized using a key schedule that consists of a one-dimensional array of four-byte words derived using the Key Expansion routine described in Sec. 5.2.

      The Cipher is described in the pseudo code in Fig. 5. The individual transformations - SubBytes(), ShiftRows(), MixColumns(), and AddRoundKey() – process the State and are described in the following subsections. In Fig. 5, the array w[] contains the key schedule, which is described in Sec. 5.2.

      As shown in Fig. 5, all Nr rounds are identical with the exception of the final round, which does not include the MixColumns() transformation.

      image

      Appendix B presents an example of the Cipher, showing values for the State array at the beginning of each round and after the application of each of the four transformations described in the following sections.


      Cipher(byte in[4*Nb], byte out[4*Nb], word w[Nb*(Nr+1)])

      begin

      byte state[4,Nb]


      state = in


      AddRoundKey(state, w[0, Nb-1])

      // See Sec. 5.1.4


      for round = 1 step 1 to Nr–1

      SubBytes(state) ShiftRows(state) MixColumns(state)

      // See Sec. 5.1.1

      // See Sec. 5.1.2

      // See Sec. 5.1.3


      AddRoundKey(state, w[round*Nb, (round+1)*Nb-1])

      end for


      SubBytes(state) ShiftRows(state)

      AddRoundKey(state, w[Nr*Nb, (Nr+1)*Nb-1])


      out = state end


      Figure 5. Pseudo Code for the Cipher.1


      • SubBytes()Transformation

        The SubBytes() transformation is a non-linear byte substitution that operates independently on each byte of the State using a substitution table (S-box). This S-box (Fig. 7), which is invertible, is constructed by composing two transformations:

        1. Take the multiplicative inverse in the finite field GF(28), described in Sec. 4.2; the element {00} is mapped to itself.

        2. Apply the following affine transformation (over GF(2) ):

          b b b b b b c (5.1)

          '

          i i (i 4) mod 8 (i 5) mod 8 (i 6) mod 8 (i 7) mod 8 i

          for

          0 i 8 , where bi is the ith bit of the byte, and ci is the ith bit of a byte c with the

          value {63} or {01100011}. Here and elsewhere, a prime on a variable (e.g., b) indicates that the variable is to be updated with the value on the right.

          In matrix form, the affine transformation element of the S-box can be expressed as:



          image


          1 The various transformations (e.g., SubBytes(), ShiftRows(), etc.) act upon the State array that is addressed by the ‘state’ pointer. AddRoundKey() uses an additional pointer to address the Round Key.

          0

          1

          0

          0

          0

          1

          1

          1

          1 b0

          1

          '

          1 1 1

          0

          0

          0

          1

          1

          1 b  1

            1   

          1 1

          2

          1

          0

          0

          0

          1

          1b2 0

          3 1 1

          1

          1

          0

          0

          0

          1 b  0

            3  

          1 1

          1

          1

          1

          0

          0

          0 b4  0

              

          5 0 1

          1

          1

          1

          1

          0

          0 b5  1

          0 0

          6

          1

          1

          1

          1

          1

          0 b  1

            6   

          7 0 0

          0

          1

          1

          1

          1

          1b7 0

          b'

          b

          b'

          '

          b


          . (5.2)

          b'

          4

          '

          b

          b'

          b'

          Figure 6 illustrates the effect of the SubBytes() transformation on the State.


          image

          s0,0

          s0,1

          s0,2

          s0,3


          S-Box

          s

          '

          0,0

          s

          '

          0,1

          s

          '

          0,2

          s

          '

          0,3


          s1,0

          s1,1 s

          sr ,c


          1,2

          s1,3

          s

          '

          1,0


          '


          s

          '

          r ,c

          '

          '

          s1,1

          s

          '

          1,2


          '

          s

          '

          1,3


          '

          s2,0

          s2,1

          s2,2

          s2,3

          s2,0

          s2,1

          s2,2

          s2,3


          s3,0

          s3,1

          s3,2

          s3,3

          s

          '

          3,0

          s

          '

          3,1

          s

          '

          3,2

          s

          '

          3,3


          Figure 6. SubBytes() applies the S-box to each byte of the State.


          The S-box used in the SubBytes() transformation is presented in hexadecimal form in Fig. 7.

          For example, if

          s1,1 {53}, then the substitution value would be determined by the intersection

          of the row with index ‘5’ and the column with index ‘3’ in Fig. 7. This would result in a value of {ed}.

          s1,1 having

          y

          0

          1

          2

          3

          4

          5

          6

          7

          8

          9

          a

          b

          c

          d

          e

          f


          x

          0

          63

          7c

          77

          7b

          f2

          6b

          6f

          c5

          30

          01

          67

          2b

          fe

          d7

          ab

          76

          1

          ca

          82

          c9

          7d

          fa

          59

          47

          f0

          ad

          d4

          a2

          af

          9c

          a4

          72

          c0

          2

          b7

          fd

          93

          26

          36

          3f

          f7

          cc

          34

          a5

          e5

          f1

          71

          d8

          31

          15

          3

          04

          c7

          23

          c3

          18

          96

          05

          9a

          07

          12

          80

          e2

          eb

          27

          b2

          75

          4

          09

          83

          2c

          1a

          1b

          6e

          5a

          a0

          52

          3b

          d6

          b3

          29

          e3

          2f

          84

          5

          53

          d1

          00

          ed

          20

          fc

          b1

          5b

          6a

          cb

          be

          39

          4a

          4c

          58

          cf

          6

          d0

          ef

          aa

          fb

          43

          4d

          33

          85

          45

          f9

          02

          7f

          50

          3c

          9f

          a8

          7

          51

          a3

          40

          8f

          92

          9d

          38

          f5

          bc

          b6

          da

          21

          10

          ff

          f3

          d2

          8

          cd

          0c

          13

          ec

          5f

          97

          44

          17

          c4

          a7

          7e

          3d

          64

          5d

          19

          73

          9

          60

          81

          4f

          dc

          22

          2a

          90

          88

          46

          ee

          b8

          14

          de

          5e

          0b

          db

          a

          e0

          32

          3a

          0a

          49

          06

          24

          5c

          c2

          d3

          ac

          62

          91

          95

          e4

          79

          b

          e7

          c8

          37

          6d

          8d

          d5

          4e

          a9

          6c

          56

          f4

          ea

          65

          7a

          ae

          08

          c

          ba

          78

          25

          2e

          1c

          a6

          b4

          c6

          e8

          dd

          74

          1f

          4b

          bd

          8b

          8a

          d

          70

          3e

          b5

          66

          48

          03

          f6

          0e

          61

          35

          57

          b9

          86

          c1

          1d

          9e

          e

          e1

          f8

          98

          11

          69

          d9

          8e

          94

          9b

          1e

          87

          e9

          ce

          55

          28

          df

          f

          8c

          a1

          89

          0d

          bf

          e6

          42

          68

          41

          99

          2d

          0f

          b0

          54

          bb

          16

          Figure 7. S-box: substitution values for the byte xy (in hexadecimal format).

      • ShiftRows() Transformation

        In the ShiftRows() transformation, the bytes in the last three rows of the State are cyclically shifted over different numbers of bytes (offsets). The first row, r = 0, is not shifted.

        Specifically, the ShiftRows() transformation proceeds as follows:


        s s

        '

        r ,c r ,(c shift (r , Nb)) mod Nb

        for 0 < r < 4 and 0 c < Nb, (5.3)

        where the shift value shift(r,Nb) depends on the row number, r, as follows (recall that Nb = 4):

        shift(1,4) 1 ;

        shift(2,4) 2 ;

        shift(3,4) 3 . (5.4)

        This has the effect of moving bytes to “lower” positions in the row (i.e., lower values of c in a given row), while the “lowest” bytes wrap around into the “top” of the row (i.e., higher values of c in a given row).

        image

        Figure 8 illustrates the ShiftRows() transformation.


        ShiftRows()


        sr ,0

        sr ,1

        sr ,2

        sr ,3

        s'

        r ,0

        s'

        r ,1

        s'

        r ,2

        s'

        r ,3


        image

        image

        image

        S S ’


        s0,0

        s0,1

        s0,2

        s0,3

        s1,0

        s1,1

        s1,2

        s1,3

        s2,0

        s2,1

        s2,2

        s2,3

        s3,0

        s3,1

        s3,2

        s3,3

        s0,0

        s0,1

        s0,2

        s0,3

        s1,1

        s1,2

        s1,3

        s1,0

        s2,2

        s2,3

        s2,0

        s2,1

        s3,3

        s3,0

        s3,1

        s3,2

        image

        image

        Figure 8. ShiftRows() cyclically shifts the last three rows in the State.


      • MixColumns() Transformation

        The MixColumns() transformation operates on the State column-by-column, treating each column as a four-term polynomial as described in Sec. 4.3. The columns are considered as polynomials over GF(28) and multiplied modulo x4 + 1 with a fixed polynomial a(x), given by

        a(x) = {03}x3 + {01}x2 + {01}x + {02} . (5.5)

        As described in Sec. 4.3, this can be written as a matrix multiplication. Let

        s(x) a(x) s(x) :

        s

        '

        0,c

        02 03

        01 01 s0,c

        '

          

        s1,c 01 02 03

        01 s1,c

        for 0 c < Nb. (5.6)

        s

        '

        2,c

        01

        01 02

        03s2,c

        '

          

        s3,c

        03

        01 01

        02s3,c

        As a result of this multiplication, the four bytes in a column are replaced by the following:

        s0,c ({02}

        s0,c ) ({03}

        s1,c )

        s2,c

        s3,c

        s1,c

        s0,c ({02}

        s1,c ) ({03}

        s2,c )

        s3,c

        s2,c

        s0,c

        s1,c ({02}

        s2,c ) ({03}

        s3,c )

        s3,c

        ({03}

        s0,c )

        s1,c

        s2,c ({02}

        s3,c ).


        Figure 9 illustrates the MixColumns() transformation.


        MixColumns()


        s0,0 s1,0 s2,0 s3,0


        s0,1


        s1,1

        s2,1

        s3,1

        image

        s0,c s1,c s2,c s3,c


        s0,2

        s1,2

        s2,2

        s3,2


        s0,3 s1,3 s2,3 s3,3


        s

        '

        0,0


        s

        '

        1,0


        s

        '

        2,0


        s

        '

        3,0


        '

        s0,1

        s

        '

        0,c



        '

        s1,1

        s

        '

        1,c



        '

        s2,1

        s

        '

        2,c



        '

        s3,1

        s

        '

        3,c


        s

        '

        0,2


        s

        '

        1,2


        s

        '

        2,2


        s

        '

        3,2


        s

        '

        0,3


        s

        '

        1,3


        s

        '

        2,3


        s

        '

        3,3

        Figure 9. MixColumns() operates on the State column-by-column.


      • AddRoundKey() Transformation

        In the AddRoundKey() transformation, a Round Key is added to the State by a simple bitwise XOR operation. Each Round Key consists of Nb words from the key schedule (described in Sec. 5.2). Those Nb words are each added into the columns of the State, such that

        [s'0,c , s'1,c , s'2,c , s'3,c ] [s0,c , s1,c , s2,c , s3,c ] [wround Nbc ]

        for 0 c < Nb, (5.7)

        where [wi] are the key schedule words described in Sec. 5.2, and round is a value in the range 0 round Nr. In the Cipher, the initial Round Key addition occurs when round = 0, prior to the first application of the round function (see Fig. 5). The application of the AddRoundKey() transformation to the Nr rounds of the Cipher occurs when 1 round Nr.

        The action of this transformation is illustrated in Fig. 10, where l = round * Nb. The byte address within words of the key schedule was described in Sec. 3.1.


        s0,0

        s1,0


        s0,1 s0

        s s

        s0,c

        ,2

        s1,c

        1,1 1


        s2,1 s2

        ,2


        s0,3

        s1,3


        wl+c


        wl +1 wl

        image

        l round * Nb


        s0,0

        s

        '

        1,0



        '

        s0,1 s

        s' s

        s0,c

        s

        '

        1,c


        0,2


        '

        1,1

        '

        s2,1 s

        1,2


        s0,3

        s

        '

        1,3

        s wl

        2 wl 3

        '

        ' s ' '

        s2,0

        s3,0

        2,c


        s3,1 s3

        s3,c

        ,2 s2,3

        ,2 s3,3

        s2,0 s3,0

        '

        s3,1 s

        2,c


        s3,c


        2,2


        3,2

        s2,3 s3,3


        Figure 10. AddRoundKey() XORs each column of the State with a word

        from the key schedule.


    2. Key Expansion

      The AES algorithm takes the Cipher Key, K, and performs a Key Expansion routine to generate a key schedule. The Key Expansion generates a total of Nb (Nr + 1) words: the algorithm requires an initial set of Nb words, and each of the Nr rounds requires Nb words of key data. The resulting key schedule consists of a linear array of 4-byte words, denoted [wi ], with i in the range 0 i < Nb(Nr + 1).

      The expansion of the input key into the key schedule proceeds according to the pseudo code in Fig. 11.

      SubWord() is a function that takes a four-byte input word and applies the S-box (Sec. 5.1.1, Fig. 7) to each of the four bytes to produce an output word. The function RotWord() takes a word [a0,a1,a2,a3] as input, performs a cyclic permutation, and returns the word [a1,a2,a3,a0]. The round constant word array, Rcon[i], contains the values given by [xi-1,{00},{00},{00}], with x i-1 being powers of x (x is denoted as {02}) in the field GF(28), as discussed in Sec. 4.2 (note that i starts at 1, not 0).

      From Fig. 11, it can be seen that the first Nk words of the expanded key are filled with the Cipher Key. Every following word, wi, is equal to the XOR of the previous word, wi-1, and the word Nk positions earlier, wi-Nk. For words in positions that are a multiple of Nk, a transformation is applied to wi-1prior to the XOR, followed by an XOR with a round constant, Rcon[i]. This transformation consists of a cyclic shift of the bytes in a word (RotWord()), followed by the application of a table lookup to all four bytes of the word (SubWord()).

      It is important to note that the Key Expansion routine for 256-bit Cipher Keys (Nk = 8) is slightly different than for 128- and 192-bit Cipher Keys. If Nk = 8 and i-4 is a multiple of Nk, then SubWord() is applied to wi-1prior to the XOR.



      KeyExpansion(byte key[4*Nk], word w[Nb*(Nr+1)], Nk) begin

      word temp i = 0

      while (i < Nk)

      w[i] = word(key[4*i], key[4*i+1], key[4*i+2], key[4*i+3]) i = i+1

      end while i = Nk

      while (i < Nb * (Nr+1)] temp = w[i-1]

      if (i mod Nk = 0)

      temp = SubWord(RotWord(temp)) xor Rcon[i/Nk] else if (Nk > 6 and i mod Nk = 4)

      temp = SubWord(temp) end if

      w[i] = w[i-Nk] xor temp i = i + 1

      end while end


      Note that Nk=4, 6, and 8 do not all have to be implemented; they are all included in the conditional statement above for conciseness. Specific implementation requirements for the Cipher Key are presented in Sec. 6.1.

      Figure 11. Pseudo Code for Key Expansion.2


      Appendix A presents examples of the Key Expansion.


    3. Inverse Cipher

      The Cipher transformations in Sec. 5.1 can be inverted and then implemented in reverse order to produce a straightforward Inverse Cipher for the AES algorithm. The individual transformations used in the Inverse Cipher - InvShiftRows(), InvSubBytes(),InvMixColumns(), and AddRoundKey() – process the State and are described in the following subsections.

      The Inverse Cipher is described in the pseudo code in Fig. 12. In Fig. 12, the array w[] contains the key schedule, which was described previously in Sec. 5.2.


      image


      2 The functions SubWord() and RotWord() return a result that is a transformation of the function input, whereas the transformations in the Cipher and Inverse Cipher (e.g., ShiftRows(), SubBytes(), etc.) transform the State array that is addressed by the ‘state’ pointer.



      InvCipher(byte in[4*Nb], byte out[4*Nb], word w[Nb*(Nr+1)])

      begin

      byte state[4,Nb] state = in

      AddRoundKey(state, w[Nr*Nb, (Nr+1)*Nb-1]) // See Sec. 5.1.4


      for round = Nr-1 step -1 downto 1

      InvShiftRows(state) InvSubBytes(state)

      // See Sec. 5.3.1

      // See Sec. 5.3.2


      AddRoundKey(state, w[round*Nb, (round+1)*Nb-1])

      InvMixColumns(state) // See Sec. 5.3.3 end for


      InvShiftRows(state) InvSubBytes(state) AddRoundKey(state, w[0, Nb-1])


      out = state end


      image

      Figure 12. Pseudo Code for the Inverse Cipher.3


      • InvShiftRows() Transformation

        InvShiftRows() is the inverse of the ShiftRows() transformation. The bytes in the last three rows of the State are cyclically shifted over different numbers of bytes (offsets). The first row, r = 0, is not shifted. The bottom three rows are cyclically shifted by Nb shift(r, Nb)

        bytes, where the shift value shift(r,Nb) depends on the row number, and is given in equation (5.4) (see Sec. 5.1.2).

        Specifically, the InvShiftRows() transformation proceeds as follows:


        s s

        '

        r ,(c shift ( r , Nb)) mod Nb r ,c

        for 0 < r < 4 and 0 c < Nb (5.8)


        Figure 13 illustrates the InvShiftRows() transformation.



        image


        3 The various transformations (e.g., InvSubBytes(), InvShiftRows(), etc.) act upon the State array that is addressed by the ‘state’ pointer. AddRoundKey() uses an additional pointer to address the Round Key.


        InvShiftRows()


        sr ,0

        sr ,1

        sr ,2

        sr ,3

        s'

        r ,0

        s'

        r ,1

        s'

        r ,2

        s'

        r ,3


        image

        image

        image

        image

        S S ’


        s0,0

        s0,1

        s0,2

        s0,3

        s1,0

        s1,1

        s1,2

        s1,3

        s2,0

        s2,1

        s2,2

        s2,3

        s3,0

        s3,1

        s3,2

        s3,3

        s0,0

        s0,1

        s0,2

        s0,3

        s1,3

        s1,0

        s1,1

        s1,2

        s2,2

        s2,3

        s2,0

        s2,1

        s3,1

        s3,2

        s3,3

        s3,0

        image

        image

        Figure 13. InvShiftRows()cyclically shifts the last three rows in the State.


      • InvSubBytes() Transformation

        InvSubBytes() is the inverse of the byte substitution transformation, in which the inverse S- box is applied to each byte of the State. This is obtained by applying the inverse of the affine transformation (5.1) followed by taking the multiplicative inverse in GF(28).

        The inverse S-box used in the InvSubBytes() transformation is presented in Fig. 14:


        y

        0

        1

        2

        3

        4

        5

        6

        7

        8

        9

        a

        b

        c

        d

        e

        f


        x

        0

        52

        09

        6a

        d5

        30

        36

        a5

        38

        bf

        40

        a3

        9e

        81

        f3

        d7

        fb

        1

        7c

        e3

        39

        82

        9b

        2f

        ff

        87

        34

        8e

        43

        44

        c4

        de

        e9

        cb

        2

        54

        7b

        94

        32

        a6

        c2

        23

        3d

        ee

        4c

        95

        0b

        42

        fa

        c3

        4e

        3

        08

        2e

        a1

        66

        28

        d9

        24

        b2

        76

        5b

        a2

        49

        6d

        8b

        d1

        25

        4

        72

        f8

        f6

        64

        86

        68

        98

        16

        d4

        a4

        5c

        cc

        5d

        65

        b6

        92

        5

        6c

        70

        48

        50

        fd

        ed

        b9

        da

        5e

        15

        46

        57

        a7

        8d

        9d

        84

        6

        90

        d8

        ab

        00

        8c

        bc

        d3

        0a

        f7

        e4

        58

        05

        b8

        b3

        45

        06

        7

        d0

        2c

        1e

        8f

        ca

        3f

        0f

        02

        c1

        af

        bd

        03

        01

        13

        8a

        6b

        8

        3a

        91

        11

        41

        4f

        67

        dc

        ea

        97

        f2

        cf

        ce

        f0

        b4

        e6

        73

        9

        96

        ac

        74

        22

        e7

        ad

        35

        85

        e2

        f9

        37

        e8

        1c

        75

        df

        6e

        a

        47

        f1

        1a

        71

        1d

        29

        c5

        89

        6f

        b7

        62

        0e

        aa

        18

        be

        1b

        b

        fc

        56

        3e

        4b

        c6

        d2

        79

        20

        9a

        db

        c0

        fe

        78

        cd

        5a

        f4

        c

        1f

        dd

        a8

        33

        88

        07

        c7

        31

        b1

        12

        10

        59

        27

        80

        ec

        5f

        d

        60

        51

        7f

        a9

        19

        b5

        4a

        0d

        2d

        e5

        7a

        9f

        93

        c9

        9c

        ef

        e

        a0

        e0

        3b

        4d

        ae

        2a

        f5

        b0

        c8

        eb

        bb

        3c

        83

        53

        99

        61

        f

        17

        2b

        04

        7e

        ba

        77

        d6

        26

        e1

        69

        14

        63

        55

        21

        0c

        7d

        Figure 14. Inverse S-box: substitution values for the byte xy (in hexadecimal format).

      • InvMixColumns() Transformation

        InvMixColumns() is the inverse of the MixColumns() transformation. InvMixColumns() operates on the State column-by-column, treating each column as a four- term polynomial as described in Sec. 4.3. The columns are considered as polynomials over GF(28) and multiplied modulo x4 + 1 with a fixed polynomial a-1(x), given by

        a-1(x) = {0b}x3 + {0d}x2 + {09}x + {0e}. (5.9)

        As described in Sec. 4.3, this can be written as a matrix multiplication. Let

        s(x) a 1 (x) s(x) :


        s

        '

        0,c

        0e

        0b 0d

        09 s0,c

        '

          

        s1,c 09 0e

        0b 0d s1,c

        for 0 c < Nb. (5.10)

        '

        ,

        s2 c

        0d

        09 0e

        0b s2,c

        '    

        s3,c

        0b 0d

        09 0e s3,c

        As a result of this multiplication, the four bytes in a column are replaced by the following:

        s0,c ({0e}

        s0,c ) ({0b}

        s1,c ) ({0d} s2,c ) ({09}

        s3,c )

        s1,c

        ({09}

        s0,c ) ({0e}

        s1,c ) ({0b}

        s2,c ) ({0d}

        s3,c )

        s2,c ({0d}

        s0,c ) ({09}

        s1,c ) ({0e} s2,c ) ({0b}

        s3,c )

        s3,c

        ({0b}

        s0,c ) ({0d}

        s1,c ) ({09} s2,c ) ({0e}

        s3,c )


      • Inverse of the AddRoundKey() Transformation

        AddRoundKey(), which was described in Sec. 5.1.4, is its own inverse, since it only involves an application of the XOR operation.


      • Equivalent Inverse Cipher

        In the straightforward Inverse Cipher presented in Sec. 5.3 and Fig. 12, the sequence of the transformations differs from that of the Cipher, while the form of the key schedules for encryption and decryption remains the same. However, several properties of the AES algorithm allow for an Equivalent Inverse Cipher that has the same sequence of transformations as the Cipher (with the transformations replaced by their inverses). This is accomplished with a change in the key schedule.

        The two properties that allow for this Equivalent Inverse Cipher are as follows:


        1. The SubBytes() and ShiftRows() transformations commute; that is, a SubBytes() transformation immediately followed by a ShiftRows() transformation is equivalent to a ShiftRows() transformation immediately followed buy a SubBytes() transformation. The same is true for their inverses, InvSubBytes() and InvShiftRows.

        2. The column mixing operations - MixColumns() and InvMixColumns() - are linear with respect to the column input, which means

          InvMixColumns(state XOR Round Key) =

          InvMixColumns(state) XOR InvMixColumns(Round Key).


          These properties allow the order of InvSubBytes() and InvShiftRows() transformations to be reversed. The order of the AddRoundKey() and InvMixColumns() transformations can also be reversed, provided that the columns (words) of the decryption key schedule are modified using the InvMixColumns() transformation.

          The equivalent inverse cipher is defined by reversing the order of the InvSubBytes() and InvShiftRows() transformations shown in Fig. 12, and by reversing the order of the AddRoundKey() and InvMixColumns() transformations used in the “round loop” after first modifying the decryption key schedule for round = 1 to Nr-1 using the InvMixColumns() transformation. The first and last Nb words of the decryption key schedule shall not be modified in this manner.

          Given these changes, the resulting Equivalent Inverse Cipher offers a more efficient structure than the Inverse Cipher described in Sec. 5.3 and Fig. 12. Pseudo code for the Equivalent Inverse Cipher appears in Fig. 15. (The word array dw[] contains the modified decryption key schedule. The modification to the Key Expansion routine is also provided in Fig. 15.)


          EqInvCipher(byte in[4*Nb], byte out[4*Nb], word dw[Nb*(Nr+1)])

          begin

          byte state[4,Nb] state = in

          AddRoundKey(state, dw[Nr*Nb, (Nr+1)*Nb-1])


          for round = Nr-1 step -1 downto 1 InvSubBytes(state) InvShiftRows(state) InvMixColumns(state)

          AddRoundKey(state, dw[round*Nb, (round+1)*Nb-1]) end for


          InvSubBytes(state) InvShiftRows(state) AddRoundKey(state, dw[0, Nb-1])


          out = state end


          For the Equivalent Inverse Cipher, the following pseudo

          the end of the Key Expansion routine (Sec. 5.2):

          for i = 0 step 1 to (Nr+1)*Nb-1 dw[i] = w[i]

          end for

          code

          is added at



          for round = 1 step 1 to Nr-1

          InvMixColumns(dw[round*Nb, (round+1)*Nb-1])

          type

          end for

          // note change of


          Note that, since InvMixColumns operates on a two-dimensional array of bytes

          while the Round Keys are held in an array of words, the call to InvMixColumns in this code sequence involves a change of type (i.e. the input to InvMixColumns() is normally the State array, which is considered to be a two-dimensional array of bytes, whereas the input here is a Round Key computed as a one-dimensional array of words).


          image

          Figure 15. Pseudo Code for the Equivalent Inverse Cipher.


  6. Implementation Issues


    1. Key Length Requirements

      An implementation of the AES algorithm shall support at least one of the three key lengths specified in Sec. 5: 128, 192, or 256 bits (i.e., Nk = 4, 6, or 8, respectively). Implementations

      may optionally support two or three key lengths, which may promote the interoperability of algorithm implementations.


    2. Keying Restrictions

      No weak or semi-weak keys have been identified for the AES algorithm, and there is no restriction on key selection.


    3. Parameterization of Key Length, Block Size, and Round Number

      This standard explicitly defines the allowed values for the key length (Nk), block size (Nb), and number of rounds (Nr) – see Fig. 4. However, future reaffirmations of this standard could include changes or additions to the allowed values for those parameters. Therefore, implementers may choose to design their AES implementations with future flexibility in mind.


    4. Implementation Suggestions Regarding Various Platforms

Implementation variations are possible that may, in many cases, offer performance or other advantages. Given the same input key and data (plaintext or ciphertext), any implementation that produces the same output (ciphertext or plaintext) as the algorithm specified in this standard is an acceptable implementation of the AES.

Reference [3] and other papers located at Ref. [1] include suggestions on how to efficiently implement the AES algorithm on a variety of platforms.


Appendix A - Key Expansion Examples

This appendix shows the development of the key schedule for various key sizes. Note that multi- byte values are presented using the notation described in Sec. 3. The intermediate values produced during the development of the key schedule (see Sec. 5.2) are given in the following table (all values are in hexadecimal format, with the exception of the index column (i)).


    1. Expansion of a 128-bit Cipher Key

      This section contains the key expansion of the following cipher key:

      Cipher Key = 2b 7e 15 16 28 ae d2 a6 ab f7 15 88 09 cf 4f 3c

      for Nk = 4, which results in

      w0 = 2b7e1516 w1 = 28aed2a6 w2 = abf71588 w3 = 09cf4f3c


      i

      (dec)


      temp

      After

      RotWord()

      After

      SubWord()


      Rcon[i/Nk]

      After XOR

      with Rcon


      w[i–Nk]

      w[i]= temp XOR w[i-Nk]

      4

      09cf4f3c

      cf4f3c09

      8a84eb01

      01000000

      8b84eb01

      2b7e1516

      a0fafe17

      5

      a0fafe17

      28aed2a6

      88542cb1

      6

      88542cb1

      abf71588

      23a33939

      7

      23a33939

      09cf4f3c

      2a6c7605

      8

      2a6c7605

      6c76052a

      50386be5

      02000000

      52386be5

      a0fafe17

      f2c295f2

      9

      f2c295f2

      88542cb1

      7a96b943

      10

      7a96b943

      23a33939

      5935807a

      11

      5935807a

      2a6c7605

      7359f67f

      12

      7359f67f

      59f67f73

      cb42d28f

      04000000

      cf42d28f

      f2c295f2

      3d80477d

      13

      3d80477d

      7a96b943

      4716fe3e

      14

      4716fe3e

      5935807a

      1e237e44

      15

      1e237e44

      7359f67f

      6d7a883b

      16

      6d7a883b

      7a883b6d

      dac4e23c

      08000000

      d2c4e23c

      3d80477d

      ef44a541

      17

      ef44a541

      4716fe3e

      a8525b7f

      18

      a8525b7f

      1e237e44

      b671253b

      19

      b671253b

      6d7a883b

      db0bad00

      20

      db0bad00

      0bad00db

      2b9563b9

      10000000

      3b9563b9

      ef44a541

      d4d1c6f8

      21

      d4d1c6f8

      a8525b7f

      7c839d87

      22

      7c839d87

      b671253b

      caf2b8bc

      23

      caf2b8bc

      db0bad00

      11f915bc


      24

      11f915bc

      f915bc11

      99596582

      20000000

      b9596582

      d4d1c6f8

      6d88a37a

      25

      6d88a37a

      7c839d87

      110b3efd

      26

      110b3efd

      caf2b8bc

      dbf98641

      27

      dbf98641

      11f915bc

      ca0093fd

      28

      ca0093fd

      0093fdca

      63dc5474

      40000000

      23dc5474

      6d88a37a

      4e54f70e

      29

      4e54f70e

      110b3efd

      5f5fc9f3

      30

      5f5fc9f3

      dbf98641

      84a64fb2

      31

      84a64fb2

      ca0093fd

      4ea6dc4f

      32

      4ea6dc4f

      a6dc4f4e

      2486842f

      80000000

      a486842f

      4e54f70e

      ead27321

      33

      ead27321

      5f5fc9f3

      b58dbad2

      34

      b58dbad2

      84a64fb2

      312bf560

      35

      312bf560

      4ea6dc4f

      7f8d292f

      36

      7f8d292f

      8d292f7f

      5da515d2

      1b000000

      46a515d2

      ead27321

      ac7766f3

      37

      ac7766f3

      b58dbad2

      19fadc21

      38

      19fadc21

      312bf560

      28d12941

      39

      28d12941

      7f8d292f

      575c006e

      40

      575c006e

      5c006e57

      4a639f5b

      36000000

      7c639f5b

      ac7766f3

      d014f9a8

      41

      d014f9a8

      19fadc21

      c9ee2589

      42

      c9ee2589

      28d12941

      e13f0cc8

      43

      e13f0cc8

      575c006e

      b6630ca6


    2. Expansion of a 192-bit Cipher Key

      This section contains the key expansion of the following cipher key:

      Cipher Key = 8e 73 b0 f7 da 0e 64 52 c8 10 f3 2b

      80 90 79 e5 62 f8 ea d2 52 2c 6b 7b

      for Nk = 6, which results in

      w0 = 8e73b0f7 w1 = da0e6452 w2 = c810f32b w3 = 809079e5

      w4 = 62f8ead2 w5 = 522c6b7b


      i

      (dec)


      temp

      After

      RotWord()

      After

      SubWord()


      Rcon[i/Nk]

      After XOR

      with Rcon


      w[i–Nk]

      w[i]= temp XOR w[i-Nk]

      6

      522c6b7b

      2c6b7b52

      717f2100

      01000000

      707f2100

      8e73b0f7

      fe0c91f7

      7

      fe0c91f7

      da0e6452

      2402f5a5

      8

      2402f5a5

      c810f32b

      ec12068e


      9

      ec12068e

      809079e5

      6c827f6b

      10

      6c827f6b

      62f8ead2

      0e7a95b9

      11

      0e7a95b9

      522c6b7b

      5c56fec2

      12

      5c56fec2

      56fec25c

      b1bb254a

      02000000

      b3bb254a

      fe0c91f7

      4db7b4bd

      13

      4db7b4bd

      2402f5a5

      69b54118

      14

      69b54118

      ec12068e

      85a74796

      15

      85a74796

      6c827f6b

      e92538fd

      16

      e92538fd

      0e7a95b9

      e75fad44

      17

      e75fad44

      5c56fec2

      bb095386

      18

      bb095386

      095386bb

      01ed44ea

      04000000

      05ed44ea

      4db7b4bd

      485af057

      19

      485af057

      69b54118

      21efb14f

      20

      21efb14f

      85a74796

      a448f6d9

      21

      a448f6d9

      e92538fd

      4d6dce24

      22

      4d6dce24

      e75fad44

      aa326360

      23

      aa326360

      bb095386

      113b30e6

      24

      113b30e6

      3b30e611

      e2048e82

      08000000

      ea048e82

      485af057

      a25e7ed5

      25

      a25e7ed5

      21efb14f

      83b1cf9a

      26

      83b1cf9a

      a448f6d9

      27f93943

      27

      27f93943

      4d6dce24

      6a94f767

      28

      6a94f767

      aa326360

      c0a69407

      29

      c0a69407

      113b30e6

      d19da4e1

      30

      d19da4e1

      9da4e1d1

      5e49f83e

      10000000

      4e49f83e

      a25e7ed5

      ec1786eb

      31

      ec1786eb

      83b1cf9a

      6fa64971

      32

      6fa64971

      27f93943

      485f7032

      33

      485f7032

      6a94f767

      22cb8755

      34

      22cb8755

      c0a69407

      e26d1352

      35

      e26d1352

      d19da4e1

      33f0b7b3

      36

      33f0b7b3

      f0b7b333

      8ca96dc3

      20000000

      aca96dc3

      ec1786eb

      40beeb28

      37

      40beeb28

      6fa64971

      2f18a259

      38

      2f18a259

      485f7032

      6747d26b

      39

      6747d26b

      22cb8755

      458c553e

      40

      458c553e

      e26d1352

      a7e1466c

      41

      a7e1466c

      33f0b7b3

      9411f1df

      42

      9411f1df

      11f1df94

      82a19e22

      40000000

      c2a19e22

      40beeb28

      821f750a

      43

      821f750a

      2f18a259

      ad07d753


      44

      ad07d753

      6747d26b

      ca400538

      45

      ca400538

      458c553e

      8fcc5006

      46

      8fcc5006

      a7e1466c

      282d166a

      47

      282d166a

      9411f1df

      bc3ce7b5

      48

      bc3ce7b5

      3ce7b5bc

      eb94d565

      80000000

      6b94d565

      821f750a

      e98ba06f

      49

      e98ba06f

      ad07d753

      448c773c

      50

      448c773c

      ca400538

      8ecc7204

      51

      8ecc7204

      8fcc5006

      01002202


    3. Expansion of a 256-bit Cipher Key

This section contains the key expansion of the following cipher key:

Cipher Key = 60 3d eb 10 15 ca 71 be 2b 73 ae f0 85 7d 77 81

1f 35 2c 07 3b 61 08 d7 2d 98 10 a3 09 14 df f4

for Nk = 8, which results in

w0 = 603deb10 w1 = 15ca71be w2 = 2b73aef0 w3 = 857d7781

w4 = 1f352c07 w5 = 3b6108d7 w6 = 2d9810a3 w7 = 0914dff4


i

(dec)


temp

After

RotWord()

After

SubWord()


Rcon[i/Nk]

After XOR

with Rcon


w[i–Nk]

w[i]= temp XOR w[i-Nk]

8

0914dff4

14dff409

fa9ebf01

01000000

fb9ebf01

603deb10

9ba35411

9

9ba35411

15ca71be

8e6925af

10

8e6925af

2b73aef0

a51a8b5f

11

a51a8b5f

857d7781

2067fcde

12

2067fcde

b785b01d

1f352c07

a8b09c1a

13

a8b09c1a

3b6108d7

93d194cd

14

93d194cd

2d9810a3

be49846e

15

be49846e

0914dff4

b75d5b9a

16

b75d5b9a

5d5b9ab7

4c39b8a9

02000000

4e39b8a9

9ba35411

d59aecb8

17

d59aecb8

8e6925af

5bf3c917

18

5bf3c917

a51a8b5f

fee94248

19

fee94248

2067fcde

de8ebe96

20

de8ebe96

1d19ae90

a8b09c1a

b5a9328a

21

b5a9328a

93d194cd

2678a647

22

2678a647

be49846e

98312229


23

98312229

b75d5b9a

2f6c79b3

24

2f6c79b3

6c79b32f

50b66d15

04000000

54b66d15

d59aecb8

812c81ad

25

812c81ad

5bf3c917

dadf48ba

26

dadf48ba

fee94248

24360af2

27

24360af2

de8ebe96

fab8b464

28

fab8b464

2d6c8d43

b5a9328a

98c5bfc9

29

98c5bfc9

2678a647

bebd198e

30

bebd198e

98312229

268c3ba7

31

268c3ba7

2f6c79b3

09e04214

32

09e04214

e0421409

e12cfa01

08000000

e92cfa01

812c81ad

68007bac

33

68007bac

dadf48ba

b2df3316

34

b2df3316

24360af2

96e939e4

35

96e939e4

fab8b464

6c518d80

36

6c518d80

50d15dcd

98c5bfc9

c814e204

37

c814e204

bebd198e

76a9fb8a

38

76a9fb8a

268c3ba7

5025c02d

39

5025c02d

09e04214

59c58239

40

59c58239

c5823959

a61312cb

10000000

b61312cb

68007bac

de136967

41

de136967

b2df3316

6ccc5a71

42

6ccc5a71

96e939e4

fa256395

43

fa256395

6c518d80

9674ee15

44

9674ee15

90922859

c814e204

5886ca5d

45

5886ca5d

76a9fb8a

2e2f31d7

46

2e2f31d7

5025c02d

7e0af1fa

47

7e0af1fa

59c58239

27cf73c3

48

27cf73c3

cf73c327

8a8f2ecc

20000000

aa8f2ecc

de136967

749c47ab

49

749c47ab

6ccc5a71

18501dda

50

18501dda

fa256395

e2757e4f

51

e2757e4f

9674ee15

7401905a

52

7401905a

927c60be

5886ca5d

cafaaae3

53

cafaaae3

2e2f31d7

e4d59b34

54

e4d59b34

7e0af1fa

9adf6ace

55

9adf6ace

27cf73c3

bd10190d

56

bd10190d

10190dbd

cad4d77a

40000000

8ad4d77a

749c47ab

fe4890d1

57

fe4890d1

18501dda

e6188d0b


58

e6188d0b

e2757e4f

046df344

59

046df344

7401905a

706c631e


Appendix B – Cipher Example

The following diagram shows the values in the State array as the Cipher progresses for a block length and a Cipher Key length of 16 bytes each (i.e., Nb = 4 and Nk = 4).

Input = 32 43 f6 a8 88 5a 30 8d 31 31 98 a2 e0 37 07 34

Cipher Key = 2b 7e 15 16 28 ae d2 a6 ab f7 15 88 09 cf 4f 3c

The Round Key values are taken from the Key Expansion example in Appendix A.


Round

Start of

After

After

After

Round Key

Number

Round

SubBytes

ShiftRows

MixColumns

Value


32

88

31

e0

43

5a

31

37

f6

30

98

07

a8

8d

a2

34

2b

28

ab

09

7e

ae

f7

cf

15

d2

15

4f

16

a6

88

3c

input =



19

a0

9a

e9

3d

f4

c6

f8

e3

e2

8d

48

be

2b

2a

08

d4

e0

b8

1e

27

bf

b4

41

11

98

5d

52

ae

f1

e5

30

d4

e0

b8

1e

bf

b4

41

27

5d

52

11

98

30

ae

f1

e5

04

e0

48

28

66

cb

f8

06

81

19

d3

26

e5

9a

7a

4c

a0

88

23

2a

fa

54

a3

6c

fe

2c

39

76

17

b1

39

05

1 =



a4

68

6b

02

9c

9f

5b

6a

7f

35

ea

50

f2

2b

43

49

49

45

7f

77

de

db

39

02

d2

96

87

53

89

f1

1a

3b

49

45

7f

77

db

39

02

de

87

53

d2

96

3b

89

f1

1a

58

1b

db

1b

4d

4b

e7

6b

ca

5a

ca

b0

f1

ac

a8

e5

f2

7a

59

73

c2

96

35

59

95

b9

80

f6

f2

43

7a

7f

2 =



aa

61

82

68

8f

dd

d2

32

5f

e3

4a

46

03

ef

d2

9a

ac

ef

13

45

73

c1

b5

23

cf

11

d6

5a

7b

df

b5

b8

ac

ef

13

45

c1

b5

23

73

d6

5a

cf

11

b8

7b

df

b5

75

20

53

bb

ec

0b

c0

25

09

63

cf

d0

93

33

7c

dc

3d

47

1e

6d

80

16

23

7a

47

fe

7e

88

7d

3e

44

3b

3 =



48

67

4d

d6

6c

1d

e3

5f

4e

9d

b1

58

ee

0d

38

e7

52

85

e3

f6

50

a4

11

cf

2f

5e

c8

6a

28

d7

07

94

52

85

e3

f6

a4

11

cf

50

c8

6a

2f

5e

94

28

d7

07

0f

60

6f

5e

d6

31

c0

b3

da

38

10

13

a9

bf

6b

01

ef

a8

b6

db

44

52

71

0b

a5

5b

25

ad

41

7f

3b

00

4 =



e0

c8

d9

85

92

63

b1

b8

7f

63

35

be

e8

c0

50

01

e1

e8

35

97

4f

fb

c8

6c

d2

fb

96

ae

9b

ba

53

7c

e1

e8

35

97

fb

c8

6c

4f

96

ae

d2

fb

7c

9b

ba

53

25

bd

b6

4c

d1

11

3a

4c

a9

d1

33

c0

ad

68

8e

b0

d4

7c

ca

11

d1

83

f2

f9

c6

9d

b8

15

f8

87

bc

bc

5 =


f1

c1

7c

5d

00

92

c8

b5

6f

4c

8b

d5

55

ef

32

0c

a1

78

10

4c

63

4f

e8

d5

a8

29

3d

03

fc

df

23

fe

a1

78

10

4c

4f

e8

d5

63

3d

03

a8

29

fe

fc

df

23

4b

2c

33

37

86

4a

9d

d2

8d

89

f4

18

6d

80

e8

d8

6d

11

db

ca

88

0b

f9

00

a3

3e

86

93

7a

fd

41

fd

6 =



26

3d

e8

fd

0e

41

64

d2

2e

b7

72

8b

17

7d

a9

25

f7

27

9b

54

ab

83

43

b5

31

a9

40

3d

f0

ff

d3

3f

f7

27

9b

54

83

43

b5

ab

40

3d

31

a9

3f

f0

ff

d3

14

46

27

34

15

16

46

2a

b5

15

56

d8

bf

ec

d7

43

4e

5f

84

4e

54

5f

a6

a6

f7

c9

4f

dc

0e

f3

b2

4f

7 =



5a

19

a3

7a

41

49

e0

8c

42

dc

19

04

b1

1f

65

0c

be

d4

0a

da

83

3b

e1

64

2c

86

d4

f2

c8

c0

4d

fe