Editing Advanced Encryption Standard (section)

== Description of the ciphers ==
AES is based on a design principle known as a [[substitution–permutation network]], and is efficient in both software and hardware.<ref>{{cite web |url=http://www.schneier.com/paper-twofish-final.pdf |title=The Twofish Team's Final Comments on AES Selection |display-authors=7 |author=Bruce Schneier |author2=John Kelsey |author3=Doug Whiting |author4=David Wagner |author5=Chris Hall |author6=Niels Ferguson |author7=Tadayoshi Kohno |author8=Mike Stay |date=May 2000 |url-status=live |archive-url=https://web.archive.org/web/20100102041117/http://schneier.com/paper-twofish-final.pdf |archive-date=2010-01-02}}</ref> Unlike its predecessor DES, AES does not use a [[Feistel network]]. AES is a variant of Rijndael, with a fixed [[block size (cryptography)|block size]] of 128 [[bit]]s, and a [[key size]] of 128, 192, or 256 bits. By contrast, Rijndael ''per se'' is specified with block and key sizes that may be any multiple of 32 bits, with a minimum of 128 and a maximum of 256 bits. Most AES calculations are done in a particular [[Finite field arithmetic|finite field]].

AES operates on a 4 × 4 [[column-major order]] array of 16 bytes {{math|{{var|b}}{{sub|0}},{{thinsp}}{{var|b}}{{sub|1}},{{thinsp}}...,{{thinsp}}{{var|b}}{{sub|15}}}} termed the ''state'':<ref group="note">Large-block variants of Rijndael use an array with additional columns, but always four rows.</ref>
::<math>
\begin{bmatrix}
b_0 & b_4 & b_8 & b_{12} \\
b_1 & b_5 & b_9 & b_{13} \\
b_2 & b_6 & b_{10} & b_{14} \\
b_3 & b_7 & b_{11} & b_{15}
\end{bmatrix}
</math>

The key size used for an AES cipher specifies the number of transformation rounds that convert the input, called the [[plaintext]], into the final output, called the [[ciphertext]]. The number of rounds are as follows:

* 10 rounds for 128-bit keys.
* 12 rounds for 192-bit keys.
* 14 rounds for 256-bit keys.

Each round consists of several processing steps, including one that depends on the encryption key itself. A set of reverse rounds are applied to transform ciphertext back into the original plaintext using the same encryption key.

=== High-level description of the algorithm ===

# {{mono | KeyExpansion}}{{snd}}round keys are derived from the cipher key using the [[AES key schedule]]. AES requires a separate 128-bit round key block for each round plus one more.
# Initial round key addition:
## {{mono | AddRoundKey}}{{snd}}each byte of the state is combined with a byte of the round key using [[bitwise xor]].
# 9, 11 or 13 rounds:
## {{mono | SubBytes}}{{snd}}a [[linear map|non-linear]] substitution step where each byte is replaced with another according to a [[Rijndael S-box|lookup table]].
## {{mono | ShiftRows}}{{snd}}a transposition step where the last three rows of the state are shifted cyclically a certain number of steps.
## {{mono | MixColumns}}{{snd}}a linear mixing operation which operates on the columns of the state, combining the four bytes in each column.
## {{mono | AddRoundKey}}
# Final round (making 10, 12 or 14 rounds in total):
## {{mono | SubBytes}}
## {{mono | ShiftRows}}
## {{mono | AddRoundKey}}

=== The {{mono|SubBytes}} step ===
{{Main|Rijndael S-box}}
[[Image:AES-SubBytes.svg|right|320px|thumbnail|In the {{mono | SubBytes}} step, each byte in the state is replaced with its entry in a fixed 8-bit lookup table, ''S''; ''b<sub>ij</sub>'' = ''S(a<sub>ij</sub>)''.]]
In the {{mono | SubBytes}} step, each byte <math>a_{i,j}</math> in the ''state'' array is replaced with a {{mono | SubByte}} <math>S(a_{i,j})</math> using an 8-bit [[substitution box]]. Before round 0, the ''state'' array is simply the plaintext/input. This operation provides the non-linearity in the [[cipher]]. The S-box used is derived from the [[multiplicative inverse]] over {{math|[[Finite field|GF]](2<sup>8</sup>)}}, known to have good non-linearity properties. To avoid attacks based on simple algebraic properties, the S-box is constructed by combining the inverse function with an invertible [[affine transformation]]. The S-box is also chosen to avoid any fixed points (and so is a [[derangement]]), i.e., <math> S(a_{i,j}) \neq a_{i,j} </math>, and also any opposite fixed points, i.e., <math> S(a_{i,j}) \oplus a_{i,j} \neq \text{FF}_{16} </math>.
While performing the decryption, the {{mono | InvSubBytes}} step (the inverse of {{mono | SubBytes}}) is used, which requires first taking the inverse of the affine transformation and then finding the multiplicative inverse.

=== The {{mono|ShiftRows}} step ===
[[Image:AES-ShiftRows.svg|right|320px|thumbnail|In the {{mono | ShiftRows}} step, bytes in each row of the state are shifted cyclically to the left. The number of places each byte is shifted differs incrementally for each row.]]
The {{mono | ShiftRows}} step operates on the rows of the state; it cyclically shifts the bytes in each row by a certain [[Offset (computer science)|offset]]. For AES, the first row is left unchanged. Each byte of the second row is shifted one to the left. Similarly, the third and fourth rows are shifted by offsets of two and three respectively.<ref group="note">Rijndael variants with a larger block size have slightly different offsets. For blocks of sizes 128 bits and 192 bits, the shifting pattern is the same. Row <math>n</math> is shifted left circular by <math>n-1</math> bytes.  For a 256-bit block, the first row is unchanged and the shifting for the second, third and fourth row is 1 byte, 3 bytes and 4 bytes respectively—this change only applies for the Rijndael cipher when used with a 256-bit block, as AES does not use 256-bit blocks.</ref> In this way, each column of the output state of the {{mono | ShiftRows}} step is composed of bytes from each column of the input state. The importance of this step is to avoid the columns being encrypted independently, in which case AES would degenerate into four independent block ciphers.

=== The {{mono|MixColumns}} step ===
{{main|Rijndael MixColumns}}
[[Image:AES-MixColumns.svg|right|320px|thumbnail|In the {{mono | MixColumns}} step, each column of the state is multiplied with a fixed polynomial <math>c(x)</math>.]]
In the {{mono | MixColumns}} step, the four bytes of each column of the state are combined using an invertible [[linear transformation]]. The {{mono | MixColumns}} function takes four bytes as input and outputs four bytes, where each input byte affects all four output bytes. Together with {{mono | ShiftRows}}, {{mono | MixColumns}} provides [[diffusion (cryptography)|diffusion]] in the cipher.

During this operation, each column is transformed using a fixed matrix (matrix left-multiplied by column gives new value of column in the state):

::<math>
\begin{bmatrix}
b_{0,j} \\ b_{1,j} \\ b_{2,j} \\ b_{3,j}
\end{bmatrix} = \begin{bmatrix}
2 & 3 & 1 & 1 \\
1 & 2 & 3 & 1 \\
1 & 1 & 2 & 3 \\
3 & 1 & 1 & 2
\end{bmatrix} \begin{bmatrix}
a_{0,j} \\ a_{1,j} \\ a_{2,j} \\ a_{3,j}
\end{bmatrix}
\qquad 0 \le j \le 3
</math>

Matrix multiplication is composed of multiplication and addition of the entries. Entries are bytes treated as coefficients of polynomial of order <math>x^7</math>. Addition is simply XOR. Multiplication is modulo irreducible polynomial <math>x^8+x^4+x^3+x+1</math>. If processed bit by bit, then, after shifting, a conditional [[Exclusive or|XOR]] with 1B<sub>16</sub> should be performed if the shifted value is larger than FF<sub>16</sub> (overflow must be corrected by subtraction of generating polynomial). These are special cases of the usual multiplication in <math>\operatorname{GF}(2^8)</math>.

In more general sense, each column is treated as a polynomial over <math>\operatorname{GF}(2^8)</math> and is then multiplied modulo <math>{01}_{16} \cdot z^4+{01}_{16}</math> with a fixed polynomial <math>c(z) = {03}_{16} \cdot z^3 + {01}_{16} \cdot z^2 +{01}_{16} \cdot z + {02}_{16}</math>. The coefficients are displayed in their [[hexadecimal]] equivalent of the binary representation of bit polynomials from <math>\operatorname{GF}(2)[x]</math>. The {{mono | MixColumns}} step can also be viewed as a multiplication by the shown particular [[MDS matrix]] in the [[finite field]] <math>\operatorname{GF}(2^8)</math>. This process is described further in the article [[Rijndael MixColumns]].

=== The {{mono|AddRoundKey}}  ===
[[Image:AES-AddRoundKey.svg|right|320px|thumbnail|In the {{mono | AddRoundKey}} step, each byte of the state is combined with a byte of the round subkey using the [[Exclusive or|XOR]] operation (⊕).]]
In the {{mono | AddRoundKey}} step, the subkey is combined with the state. For each round, a subkey is derived from the main [[key (cryptography)|key]] using [[Rijndael key schedule|Rijndael's key schedule]]; each subkey is the same size as the state. The subkey is added by combining of the state with the corresponding byte of the subkey using bitwise [[Exclusive or|XOR]].

=== Optimization of the cipher ===
On systems with 32-bit or larger words, it is possible to speed up execution of this cipher by combining the {{mono | SubBytes}} and {{mono | ShiftRows}} steps with the {{mono | MixColumns}} step by transforming them into a sequence of table lookups. This requires four 256-entry 32-bit tables (together occupying 4096 bytes).  A round can then be performed with 16 table lookup operations and 12 32-bit exclusive-or operations, followed by four 32-bit exclusive-or operations in the {{mono | AddRoundKey}} step.<ref>{{cite book |chapter-url=https://doi.org/10.1007%2F3-540-36400-5_13 |doi=10.1007/3-540-36400-5_13 |chapter=Efficient Software Implementation of AES on 32-Bit Platforms |title=Cryptographic Hardware and Embedded Systems - CHES 2002 |series=Lecture Notes in Computer Science |year=2003 |last1=Bertoni |first1=Guido |last2=Breveglieri |first2=Luca |last3=Fragneto |first3=Pasqualina |last4=MacChetti |first4=Marco |last5=Marchesin |first5=Stefano |volume=2523 |pages=159–171 |isbn=978-3-540-00409-7}}</ref>  Alternatively, the table lookup operation can be performed with a single 256-entry 32-bit table (occupying 1024 bytes) followed by circular rotation operations.

Using a byte-oriented approach, it is possible to combine the {{mono | SubBytes}}, {{mono | ShiftRows}}, and {{mono | MixColumns}} steps into a single round operation.<ref>{{cite web |url=https://code.google.com/p/byte-oriented-aes |title=byte-oriented-aes – A public domain byte-oriented implementation of AES in C – Google Project Hosting |access-date=2012-12-23 |url-status=live |archive-url=https://web.archive.org/web/20130720155538/http://code.google.com/p/byte-oriented-aes/ |archive-date=2013-07-20}}</ref>