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 19 schedube.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 3
3 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-l28',“AES-l92”,and “AES-256” This specification includes the following sections: 2.Definitions of terms,acronyms,and algorithm parameters,symbols,and functions; 3.Notation and conventions used in the algorithm specification,including the ordering and numbering of bits,bytes,and words; 4.Mathematical properties that are useful in understanding the algorithm; 5.Algorithm specification,covering the key expansion,encryption,and decryption routines; 6.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 2.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. 5
5 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: 2. Definitions of terms, acronyms, and algorithm parameters, symbols, and functions; 3. Notation and conventions used in the algorithm specification, including the ordering and numbering of bits, bytes, and words; 4. Mathematical properties that are useful in understanding the algorithm; 5. Algorithm specification, covering the key expansion, encryption, and decryption routines; 6. 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 2.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.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(). Cipher Key. 6
6 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 onefor-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.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 3.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 0si<128,0si<192 or 0si<256 depending on the block length and key length(specified above). 7
7 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 nonlinear 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 x 4 + 1. · Finite field multiplication. 3. Notation and Conventions 3.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)
3.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,0sn<16; Block length=128 bits,0sn<16; Key length 192 bits,0sn<24; Key length=256 bits,0sn<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,bs,b4,b3,b2,bi,bo).These bytes are interpreted as finite field elements using a polynomial representation: bax7+box+b5x5+bx+bx3+b2x2+bx+b0=>bx (3.1) i=0 For example,{01100011)identifies the specific finite field elementx+x+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.I Bit Pattern Character Bit Pattern Character Bit Pattern Character Bit Pattern Character 0000 0 0100 4 1000 8 1100 a 0001 1 0101 5 1001 9 1101 d 0010 2 0110 6 1010 a 1110 e 0011 3 0111 7 1011 b 1111 E 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(bs)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 (011b). 3.3 Arrays of Bytes Arrays of bytes will be represented in the following form: a0a1a2.a15 The bytes and the bit ordering within bytes are derived from the 128-bit input sequence inputo input inpub...input6 input7 as follows: 8
8 3.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 0 1 0 2 2 3 3 4 4 5 5 6 6 7 7 i i i b x b x b x b x b x b x b x b b x . (3.1) For example, {01100011} identifies the specific finite field element 1 6 5 x + x + x + . 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 Bit Pattern Character Bit Pattern Character Bit Pattern Character 0000 0 0100 4 1000 8 1100 c 0001 1 0101 5 1001 9 1101 d 0010 2 0110 6 1010 a 1110 e 0011 3 0111 7 1011 b 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.3 Arrays of Bytes Arrays of bytes will be represented in the following form: 0 1 2 15 a a a ...a The bytes and the bit ordering within bytes are derived from the 128-bit input sequence input0 input1 input2 … input126 input127 as follows: