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.
algorithm. As with its this standard every five
NIST will continue to follow developments in the analysis of the AES other cryptographic algorithm standards, NIST will formally reevaluate
years.
possible threats reducing the security provided through the use of this review by NIST as appropriate, taking into account newly available
Both this standard and
standard will undergo
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
a. adversely affect the accomplishment of the mission of an operator of Federal computer system or
b. cause a major adverse financial impact on the operator that is not offset by government- wide savings.
ii
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.
iii
iv
1. 2.
3.
4.
5.
Federal Information Processing Standards Publication 197
November 26, 2001
Specification for the ADVANCED ENCRYPTION STANDARD (AES)
Table of Contents INTRODUCTION…………………………………………………………………………………………………………………………… 5
DEFINITIONS ……………………………………………………………………………………………………………………………….. 5
2.1 GLOSSARY OF TERMS AND ACRONYMS…………………………………………………………………………………………….. 5
2.2 ALGORITHM PARAMETERS, SYMBOLS, AND FUNCTIONS……………………………………………………………………… 6
NOTATION AND CONVENTIONS………………………………………………………………………………………………… 7
3.1 INPUTS AND OUTPUTS ……………………………………………………………………………………………………………………. 7
3.2 BYTES …………………………………………………………………………………………………………………………………………. 8
3.3 ARRAYS OF BYTES ………………………………………………………………………………………………………………………… 8
3.4 THE STATE …………………………………………………………………………………………………………………………………… 9
3.5 THE STATE AS AN ARRAY OF COLUMNS………………………………………………………………………………………….. 10
MATHEMATICAL PRELIMINARIES …………………………………………………………………………………………. 10
4.1 ADDITION…………………………………………………………………………………………………………………………………… 10
4.2 MULTIPLICATION ………………………………………………………………………………………………………………………… 10
4.2.1 Multiplication by x ……………………………………………………………………………………………………………… 11
8
4.3 POLYNOMIALS WITH COEFFICIENTS IN GF(2 ) …………………………………………………………………………………. 12
ALGORITHM SPECIFICATION………………………………………………………………………………………………….. 13
5.1 CIPHER ………………………………………………………………………………………………………………………………………. 14
5.1.1 SubBytes()Transformation……………………………………………………………………………………………… 15
5.1.2 ShiftRows() Transformation ………………………………………………………………………………………….. 17
5.1.3 MixColumns() Transformation ………………………………………………………………………………………… 17
5.1.4 AddRoundKey() Transformation …………………………………………………………………………………….. 18
5.2 KEY EXPANSION …………………………………………………………………………………………………………………………. 19
5.3 INVERSE CIPHER………………………………………………………………………………………………………………………….. 20
5.3.1 InvShiftRows() Transformation ……………………………………………………………………………………. 21
5.3.2 InvSubBytes() Transformation ……………………………………………………………………………………… 22
5.3.3 InvMixColumns() Transformation………………………………………………………………………………….. 23
5.3.4 Inverse of the AddRoundKey() Transformation ………………………………………………………………….. 23
5.3.5 Equivalent Inverse Cipher …………………………………………………………………………………………………… 23
6. IMPLEMENTATION ISSUES ………………………………………………………………………………………………………. 25
6.1 KEY LENGTH REQUIREMENTS ……………………………………………………………………………………………………….. 25
6.2 KEYING RESTRICTIONS ………………………………………………………………………………………………………………… 26
6.3 PARAMETERIZATION OF KEY LENGTH, BLOCK SIZE, AND ROUND NUMBER …………………………………………. 26
6.4 IMPLEMENTATION SUGGESTIONS REGARDING VARIOUS PLATFORMS………………………………………………….. 26
APPENDIX A – KEY EXPANSION EXAMPLES …………………………………………………………………………………… 27
A.1 EXPANSION OF A 128-BIT CIPHER KEY……………………………………………………………………………………………. 27
A.2 EXPANSION OF A 192-BIT CIPHER KEY……………………………………………………………………………………………. 28
A.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
2
Figure 1.
Figure 2.
Figure 3.
Figure 4.
Figure 5.
Figure 6.
Figure 7.
Figure 8.
Figure 9.
Table of Figures
Hexadecimal representation of bit patterns………………………………………………………… 8 Indices for Bytes and Bits. ………………………………………………………………………………. 9 State array input and output. ……………………………………………………………………………. 9 Key-Block-Round Combinations……………………………………………………………………. 14 Pseudo Code for the Cipher. ………………………………………………………………………….. 15 SubBytes() applies the S-box to each byte of the State. ……………………………….. 16 S-box: substitution values for the byte xy (in hexadecimal format). ………………….. 16 ShiftRows() cyclically shifts the last three rows in the State ………………………… 17 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 Figure11. PseudoCodeforKeyExpansion……………………………………………………………………..20 Figure12. PseudoCodefortheInverseCipher…………………………………………………………………21 Figure 13. InvShiftRows()cyclically shifts the last three rows in the State. ………………….. 22 Figure14.InverseS-box: substitutionvaluesforthebytexy(inhexadecimalformat)………….22 Figure 15. Pseudo Code for the Equivalent Inverse Cipher………………………………………………… 25
3
4
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 AES
Affine Transformation
Array Bit Block
Byte
are used throughout this standard: Advanced Encryption Standard
A transformation consisting of multiplication by a matrix followed by the addition of a vector.
An enumerated collection of identical entities (e.g., an array of bytes).
A binary digit having a value of 0 or 1.
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.
A group of eight bits that is treated either as a single entity or as an array of 8 individual bits.
5
Cipher
Cipher Key
Ciphertext Inverse Cipher
Key Expansion Plaintext Rijndael
Round Key
State
S-box
Word
Series of transformations that converts plaintext to ciphertext using the 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.
Data output from the Cipher or input to the Inverse Cipher.
Series of transformations that converts ciphertext to plaintext using the Cipher Key.
Routine used to generate a series of Round Keys from the Cipher Key. Data input to the Cipher or output from the Inverse Cipher.
Cryptographic algorithm specified in this Advanced Encryption Standard (AES).
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.
Intermediate Cipher result that can be pictured as a rectangular array of bytes, having four rows and Nb columns.
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.
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.
6
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 4
x +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).
7
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:
Keylength=128bits, 0£n<16; Blocklength=128bits, 0£n<16; Keylength=192bits, 0£n<24;
Keylength=256bits, 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
i=0
For example, {01100011} identifies the specific finite field element x6 + x5 + x +1.
bx7 +bx6 +bx5 +bx4 +bx3 +bx2 +bx+b = 76543210
bxi . i
(3.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.
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: a0a1a2...a15
The bytes and the bit ordering within bytes are derived from the 128-bit input sequence input0 input1 input2 ... input126 input127
as follows:
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
8
a0 = {input0, input1, ..., input7}; a1 = {input8, input9, ..., input15};
M
a15 = {input120, input121, ..., input127}.
The pattern can be extended to longer sequences (i.e., for 192- and 256-bit keys), so that, in
general,
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.
3.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
��
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] for0£r<4 and 0£c
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.
5.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.
2
the transformations in the Cipher and Inverse Cipher (e.g., ShiftRows(), SubBytes(), etc.) transform the
The functions SubWord() and RotWord() return a result that is a transformation of the function input, whereas State array that is addressed by the ‘state’ pointer.
20
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) // See Sec. 5.3.1 InvSubBytes(state) // See Sec. 5.3.2 AddRoundKey(state, w[round*Nb, (round+1)*Nb-1])
InvMixColumns(state)
end for
InvShiftRows(state)
InvSubBytes(state)
AddRoundKey(state, w[0, Nb-1])
out = state
end
// See Sec. 5.3.3
Figure 12. Pseudo Code for the Inverse Cipher.3 5.3.1 InvShiftRows()Transformation
InvShiftRows()istheinverseoftheShiftRows()transformation. Thebytesinthelast 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).
(5.8)
Specifically, the InvShiftRows() transformation proceeds as follows: s’ =s for0