NOTE: This site is obsolete. See book draft (in PDF):

The Laws of Cryptography with Java Code.

---

Overview.

The new U.S. Advanced Encryption Standard is a block cipher with block size of 128 bits, or 16 bytes. Keys for the cipher come in one of three lengths: 128, 192, or 256 bits, which is 16, 24, or 32 bytes. The algorithm is oriented toward bytes (8 bits), but there is also emphasis on what the AES specification calls words, which are arrays of 4 bytes (or 32 bits, the size of an int in Java). My Java implementation presented here tends to de-emphasize the words.

The main mathematical difficulty with the algorithm is that it uses arithmetic over the field GF(2⁸). Even the field itself only poses real difficulties with multiplication of field elements and with multiplicative inverses. These topics are covered in Section 2 below.

Otherwise, the AES algorithm is just an annoying amount of details to orchestrate, but not really difficult. Section 3 below covers the S-Boxes, while Section 4 shows how the keys are handled. Section 5 covers the remainder of the encryption algorithm, and Section 6 covers decryption.

I have implemented the algorithm following the AES specification and using B. Gladman's commentary. I haven't worried about efficiency, but mostly have just tried to produce a clear, simple, working Java program. One exception is to give Gladman's more efficient implementation of multiplication in GF(2⁸) because it is interesting (see Section 2). Gladman has produced an optimized C implementation and has a lot to say on the subject of efficient implementation, especially with methods using tables.

In order to create such a cryptosystem, one must remember that anything done by encryption must be undone during decryption, using the same key since it is a conventional (symmetric key) system. Thus the focus is on various invertible operations. One standard technique in using the key is to derive a string somehow from the key, and use xor to combine it with the emerging ciphertext. Later the same xor reverses this. Otherwise there are ``mixing'' operations that move data around, and ``translation'' (or ``substitution'') operations that replace one piece of data with another. This last operation is usually carried out on small portions of ciphertext using so-called ``S-boxes'', which define replacement strings. One set of mixing, replacements, and exclusive-or with a string derived from the key is called a round. Then there will typically be a number of rounds. The AES uses different numbers of rounds for the different key sizes according to the table below. The table uses a variable Nb for the plaintext block size, but it is always 4 words. Originally the AES was going to support different block sizes, but they settled on just one size. However, the AES people (at the NIST) recommend keeping this as a named constant in case a change is ever wanted.

Key Sizes versus Rounds
	Key  Block Size  (Nk words)	Plaintext  Block Size  (Nb words)	Number of  Rounds  (Nr)
AES-128	4	4	10
AES-192	6	4	12
AES-256	8	4	14

Remember that a word is 4 bytes or 32 bits. The names Nk, Nb, and Nr are standard for the AES. In general, I try to use the names in the AES specification, even when they do not conform to Java conventions.

The particular form of this type of algorithm, with its rounds of mixing and substitution and exclusive-or with the key, was introduced with the official release of the Data Encryption Standard (DES) in 1977 and with work preceeding the release. The DES has a block size of 64 bits and a very small key size of 56 bits. From the beginning the key size of the DES was controversial, having been reduced at the last minute from 64 bits. This size seemed at the edge of what the National Security Agency (but no one else) could crack. Now it is very easy to break, and completely insecure. The AES, with its minimum of 128 bits for a key should not be breakable by brute force attacks for a very long time, even with great advances in computer hardware.

---

Outline of the AES Algorithm.

Here is the AES algorithm is outline form, using Java syntax for the pseudo-code, and much of the AES standard notation:

Constants: int Nb = 4; // but it might change someday int Nr = 10, 12, or 14; // rounds, for Nk = 4, 6, or 8 Inputs: array in of 4*Nb bytes // input plaintext array out of 4*Nb bytes // output ciphertext array w of 4*Nb*(Nr+1) bytes // expanded key Internal work array: state, 2-dim array of 4*Nb bytes, 4 rows and Nb cols Algorithm: void Cipher(byte[] in, byte[] out, byte[] w) { byte[][] state = new byte[4][Nb]; state = in; // actual component-wise copy AddRoundKey(state, w, 0, Nb - 1); // see Section 4 below for (int round = 1; round < Nr; round++) { SubBytes(state); // see Section 3 below ShiftRows(state); // see Section 5 below MixColumns(state); // see Section 5 below AddRoundKey(state, w, round*Nb, (round+1)*Nb - 1); // Section 4 } SubBytes(state); // see Section 3 below ShiftRows(state); // see Section 5 below AddRoundKey(state, w, Nr*Nb, (Nr+1)*Nb - 1); // Section 4 out = state; // component-wise copy }

Let's go down the items in the above pseudo-code in order:

• Multiplication in GF(256): this is not mentioned explicitly above, but the individual functions use it frequently. It is described in Section 2 below.
• Nb: Right now, this is always 4, the constant number of 32-bit words that make up a block for encryption and decryption.
• Nr: the number of rounds or main iterations of the algorithm. The possible values depend on the three different possible key sizes the earlier table showed.
• in: the input block of 128 bits of plaintext, arranged as 4*Nb = 16 bytes, numbered 0 to 15 and arranged in sequence.
• out: the output block of 128 bits of ciphertext, arranged the same as in.
• state: the internal array that is worked on by the AES algorithm. It is arranged as a 4 by Nb 2-dimensinal array of bytes (that is, 4 by 4).
• w: the expanded key. The initial key is of size 4*Nk bytes (see table earlier), and this is expanded to the array w of 4*Nb*(Nr+1) = 16*(Nr+1) bytes for input to the encryption algorithm. Each round uses 4*Nb bytes, and each portion of w is used only once. (There is one extra use during sort of an extra round.) This function for expanding the key is described in Section 4 below.
• SubBytes(state): this takes each byte of the state and independently looks it up in an ``S-box'' table to substitute a different byte for it. (The same S-box table is also used in the key expansion.) Section 3 shows how the S-box table is defined and constructed.
• ShiftRows(state): this simply moves around the rows of the state array. See Section 5 below.
• MixColumns(state): this does a much more complicated mix of the columns of the state array. See Section 5 below.
• AddRoundKey(state, w, param1, param2): this takes the 4*Nb*(Nr+1) bytes of the expanded key, w, and does an exclusive-or of succesive portions of the expanded key with the changing state array. The integer values param1 and param2 take on different values during execution of the algorithm, and they give the inclusive range of columns of the expanded key that are used. My implementation of this function doesn't use these parameters, because each round just uses the next 4*Nb bytes of w. The details of this function appear in Section 4 below.

Well, that's pretty much it. Now the remaining sections just have to fill in a large number of missing details. Section 6 gives the inverse algorithm for decryption, but this is not a big problem, since the parameters and functions are either identical or similar.