**Introduction to AES**

Attached is a PDF containing the contents of the tutorial, minus the code. It was typeset using LaTeX, making it easier to follow the mathematics.

AES.pdf

**(214.94K)**

Number of downloads: 389

This tutorial will introduce the AES Cryptosystem. Both theory and implementation will be provided. While many versions of AES exist, this tutorial will cover the original 128-bit AES Cryptosystem, also known as Rijndael.

The Rijndael Cryptosytem is a symmetric-key, substitution-permutation network. That is, the same key used for encrypting the plaintext is also used to decrypt the ciphertext. We generate our round keys from the provided key, and use those to modify the plaintext on each iteration. After adding in a given round key, we apply a substitution function to each byte of our modified plaintext, then permute the result. We iterate and repeat this process ten times before returning the ciphertext.

In this tutorial, I assume a certain amount of mathematical familiarity. I expect familiarity with modular arithmetic and the concept of relative primality. From this, I will introduce a cursory amount of abstract algebra necessary to use and follow this tutorial. I would strongly suggest reading through the algebra section, making careful note to pay attention to how the operations of addition and multiplication are defined. If this is your first cryptosystem and you don't have a lot of mathematical familiarity, this is probably not the best cryptosystem to work through. A textbook like Stinson or Boneh's online cryptography course are good resources for getting into cryptography.

As a last note, this cryptosystem implementation is purely for study. You should never use your own implementation of a cryptosystem in practice, for numerous security reasons.

**Preliminaries- A Brief Introduction to Algebra**

Abstract Algebra is not typically covered within a computer science program. Any algebra covered in the context of computer science usually deals with monoids and posets, as opposed to the standard trinity of groups, rings, and fields. Abstract algebra comes into play with the AES cryptosystem in defining the Rijndael Field. This field is used as the backbone of the cryptosystem. In order to understand what a field is, it is first necessary to understand a more basic structure: a group.

A group is a set of elements with a single binary operation. Let G be a group, and let * be the binary operator, which is defined as * : G x G -> G. That is, the operator is closed, or a function that takes a pair of elements from G and maps them to an element in G. The operator is also associative. That is, for any a, b, c in G, (a * b) * c = a * (b * c). We may also drop the star and simply write ab to denote the operation.

A group also has an identity element, which we denote as e. And every element in the group has an inverse. That is, for any a in the group G, there exists an a

^{-1}such that a * a

^{-1}= a

^{-1}* a = e.

This definition of a group is a bit abstract, so let's consider a couple of examples. The first example is the group (Z, +). That is, consider the integers over addition. The additive identity element is 0; that is, x + 0 = x for every integer x. Every element has an additive inverse. Take a in Z. Then a

^{-1}= -a, when dealing with addition. Associativity is trivial. Note that addition over Z is commutative. Such groups where the operation is commutative are called Abelian groups.

Consider (Z - {0}, *), the non-zero integers over multiplication. This set fails to form a group, as only +-1 are invertible over multiplication. However, (R - {0}, *), the set of non-zero real numbers, forms a group over multiplication. Since we aren't dividing by 0, we simply take 1/r as the inverse for any r in R. And so r * 1/r = 1, the multiplicative identity element.

We now define a field. A field is a set of elements with two binary operations (F, +, *). We consider 0 the additive identity and 1 the multiplicative identity. The elements over the addition operation form an Abelian group (a commutative group), and the non-zero elements over multiplication also form an Abelian group. Some common examples of fields are the real numbers, the rational numbers, the complex numbers, and the integers modulo p (for p a prime).

**Rijndael Field**

The AES cryptosystem relies on the Rijndael Field, which is a polynomial field over the field on two elements, which we denote Z

_{2}(the integers modulo 2). So we start with the polynomials Z

_{2}[x]. That is, the coefficients of the polynomials are taken modulo 2. We then mod out the polynomials by x

^{8}+ x

^{4}+ x

^{3}+ x + 1. We denote this field as Z

_{2}[x]/(x

^{8}+ x

^{4}+ x

^{3}+ x + 1). Algebraists will recognize the notation as a quotient ring. Those familiar with number theory can think of x

^{8}+ x

^{4}+ x

^{3}+ x + 1 as a prime polynomial. So Z

_{2}[x]/(x

^{8}+ x

^{4}+ x

^{3}+ x + 1) is a field much in the same way that Z

_{p}(or Z/pZ) is a field. We note the Rijndael Field has 256 elements with additive identity 0 and multiplicative identity 1. Addition of polynomials is done component-wise (as you are probably used to doing), and then we reduce the coefficients mod 2. Multiplication on the Rijndael Field is defined using polynomial multiplication.

So consider the polynomial x

^{9}+ x. We consider its equivalence in the Rijndael field by finding y such that x

^{9}+ x = y (mod x

^{8}+ x

^{4}+ x

^{3}+ x + 1).

Finding y is quite similar to modular arithmetic in the integers. Consider 8 = z (mod 3). To find z, we divide 8/3 and consider the remainder, which is 2. That is 8 = 2(3) + 2. So 8 = 2 (mod 3). Similarly, we seek to write x

^{9}+ x = p(x)(x

^{8}+ x

^{4}+ x

^{3}+ x + 1) + y, where p(x) is a polynomial in Z

_{2}[x] and y is in the Rijndael field. So we divide (x

^{9}+ x)/(x

^{8}+ x

^{4}+ x

^{3}+ x + 1) and take the remainder to be y.

So x

^{9}+ x = x(x

^{8}+ x

^{4}+ x

^{3}+ x + 1) + (x

^{5}+ x

^{4}+ x

^{2}).

Since addition is XOR (that is, we reduce the coefficients mod 2), adding in (x

^{5}+ x

^{4}+ x

^{2}) cancels out the extraneous terms. So we get:

x(x

^{8}+ x

^{4}+ x

^{3}+ x + 1) + (x

^{5}+ x

^{4}+ x

^{2}) = x

^{9}+ 2x

^{5}+ 2x

^{4}+ 2x

^{2}+ x.

Reducing the coefficients mod 2 leaves us with x

^{9}+ x, as desired. So this is exactly like working with integer division and modular arithmetic in a number theory context.

I offer this implementation of an element in the Rijndael Field, with the class RijndaelPolynomial. Operations of addition, multiplication, and inversion are used. In order to calculate the multiplicative inverse, we use Lagrange's Theorem or an analogue of Fermat's Little Theorem. By definition of a field, Z

_{2}[x]/(x

^{8}+ x

^{4}+ x

^{3}+ x + 1) - {0} forms an Abelian group over multiplication. Since we exclude the zero element, the group has order (cardinality) 255 elements. Hence, for any element in the multiplicative group, x

^{|G|}= x

^{255}= x in the group. And so x

^{254}= 1, which means that x

^{253}= x

^{-1}over multiplication.

/** * @(#)RijndaelPolynomial.java * * @author Michael Levet * @version 1.00 2014/06/09 * * This class models a polynomial element in the * Rijndael Field (the field of polynomials over Z_{2} * mod x^8 + x^4 + x^3 + x + 1). This class is immutable, * and supports the field operations of polynomial addition, * polynomial multiplication, and element inversion within the field. */ public class RijndaelPolynomial{ /** * An integer, whose bits represent the coefficients * of the RijndaelPolynomial */ private int value; /** * @param value The polynomial element in the Rijndael field * @throws IllegalArgumentException if value > 0b100011011 or value < 0 */ public RijndaelPolynomial(int value){ if(value > 0b100011011 || value < 0){ throw new IllegalArgumentException("You entered a value outside of the Rijndael Field: " + value); } this.value = value; } /** * @return int The polynomial value */ public int getValue(){ return this.value; } /** * @pre other != null * @post this.value is unchanged * @return RijndaelPolynomial The result of the polynomial addition. * Note that the resulting element represents a polynomial in the Rijndael Field. * That is, addition is a closed operation on the Rijndael Field. */ public RijndaelPolynomial add(RijndaelPolynomial other){ return new RijndaelPolynomial((this.value ^ other.value)); } /** * Performs polynomial multiplication and returns a new RijndaelPolynomial * @return RijndaelPolynomial */ public RijndaelPolynomial multiply(RijndaelPolynomial other){ int result = 0; int thisValue = this.value; int otherValue = other.value; boolean carry = false; //there are at 8 bits per polynomial for(int i = 0; i < 8; i++){ //if there is a set bit at the ith position //in the other polynomial, do a multiplication on that //position if((otherValue & 1) > 0){ result ^= thisValue; } //if there is an x^8 coefficient carry = (thisValue & 0x80) > 0; thisValue <<= 1; //replace it with x^4 + x^3 + x + 1 if(carry){ thisValue ^= 0x001B; } otherValue >>= 1; } //return a new polynomial, keeping only the last 8 bits return new RijndaelPolynomial(result & 0b11111111); } //uses an analogue of Fermat's Little Theorem to invert //the polynomial in the field public RijndaelPolynomial invert(){ RijndaelPolynomial temp = new RijndaelPolynomial(this.value); for(int i = 0; i < 253; i++){ temp = temp.multiply(this); } return temp; } }

The main takeaway with the Rijndael Field is that it works basically like polynomial addition and multiplication as we are used to it. The coefficients are all 0 or 1, and no element in the field has degree greater than 7. The Rijndael Field then has the added constraint of working like the integers modulo n. Instead of applying mod n, for n an integer, we mod out by x

^{8}+ x

^{4}+ x

^{3}+ x + 1.

**Key Expansion**

The Key Expansion phase takes the 128-bit key and expands it to get the eleven round keys for each of the ten rounds of the cryptosystem. We apply a round key prior to the start of the first round. Each round key consists of four words, with each word equivalent to four bytes. The procedure is simple enough, but a bit cumbersome.

We consider the keySchedule as an array of 44 words. The first word consists of the first four bytes of the key. The second word consists of the second four bytes. We continue this for the third and fourth words.

To generate the rest of the keySchedule, we use the following algorithm. The rotateAndSub() method is not very complicated, and I will provide the RCON constants array later.

private void expandKey(){ for(int i = 4; i < words.length; i++){ //get the (i-1)st word Word temp = new Word(); temp.setBytes(words[i-1].getBytes()); //apply an affine transformation to every 4th byte if(i % 4 == 0){ temp.rotateAndSub(); temp = temp.xor(RCON[i/4 - 1]); } words[i] = words[i - 4].xor(temp); } }

So essentially, we take the i-1 and i-4 Words and XOR them together. The result is the ith Word in the keySchedule. Every fourth word is also run through the rotateAndSub() method, then XOR'd with a given RCON constant.

The rotateAndSub() method begins by moving the front byte to the back, and then applying the subByte() method to each byte. The subByte() method accepts a byte of the form (a_7, a_6, a_5, ..., a_0). This byte as treated as a polynomial in the Rijndael Field. The a_i element is the coefficient of x

^{i}in the Rijndael Field. So 01010011 is equivalent to x

^{6}+ x

^{4}+ x + 1. The subByte() algorithm can also be viewed as an Affine Transformation, given below:

The next step is to calculate the multiplicative inverse of the element in the Rijndael Field, so long as the byte is non-zero. The inverse of x

^{6}+ x

^{4}+ x + 1 is x

^{7}+ x

^{6}+ x

^{3}+ x, which is equivalent to the binary string 11001010. We then convert the inverse polynomial back to binary and add the vector c = (01100011) to it, with c_7 starting at the far-left.

I provide the following subByte() implementation:

/** * @param s The short representation of the byte * @return short The byte after substitution */ private short subByte(short s){ //the idea is to construct a representation of this //byte in the Rijndael Field, then to get its inverse //as a binary string, padding with leading 0's as necessary RijndaelPolynomial poly = new RijndaelPolynomial(s); poly = poly.invert(); String binaryString = Integer.toBinaryString(poly.getValue()); while(binaryString.length() < 8){ binaryString = "0" + binaryString; } char[] temp = binaryString.toCharArray(); //based on the ordering of the elements, element 0 //should be at for(int i = 0; i < temp.length/2; i++){ char t = temp[i]; temp[i] = temp[temp.length - 1 - i]; temp[temp.length - 1 - i] = t; } int[] result = new int[temp.length]; for(int i = 0; i < temp.length; i++){ result[i] = temp[i] - '0'; result[i] += temp[(i + 4) % temp.length] - '0'; result[i] += temp[(i + 5) % temp.length] - '0'; result[i] += temp[(i + 6) % temp.length] - '0'; result[i] += temp[(i + 7) % temp.length] - '0'; result[i] += SUB_BYTES_CONSTANT[i]; result[i] %= 2; } String str = ""; for(int i = 0; i < result.length/2; i++){ int t = result[i]; result[i] = result[result.length - 1 - i]; result[result.length - 1 - i] = t; } for(int i = 0; i < result.length; i++){ str += result[i]; } return Short.parseShort(str, 2); }

Finally, I include the entire KeyExpansion class. This class is runnable with a sample Key to expand and the result included.

package aes; /** * @(#)KeyExpansion.java * @author Michael Levet * * @version 1.00 2014/06/09 * * This class handles the key schedule for the 128-bit AES * cryptosystem. */ import java.math.BigInteger; import java.util.Arrays; public class KeyExpansion { /** * The 128-bit key to expand */ private String key; private static final Word[] RCON = { new Word(getBytes("01000000")), new Word(getBytes("02000000")), new Word(getBytes("04000000")), new Word(getBytes("08000000")), new Word(getBytes("10000000")), new Word(getBytes("20000000")), new Word(getBytes("40000000")), new Word(getBytes("80000000")), new Word(getBytes("1B000000")), new Word(getBytes("36000000")) }; /** * The array to hold the key-schedule */ private Word[] words; /** * @param key A hex-String representation of the key * @post The key schedule is correctly stored into this.words */ public KeyExpansion(String key){ this.key = key; words = new Word[44]; //get the first 4 Words by partitioning the key into fourths for(int i = 0; i < 4; i++){ String substring = key.substring(8*i, 8*i + 8); short[] bytes = getBytes(substring); words[i] = new Word(bytes); } expandKey(); } /** * @return Words[] The Key Schedule */ public Word[] getWords(){ return words; } /** * @param byteString The hex-string from which to extract the bytes * @return short[] The byteString represents bytes in hex. The short[] contains those bytes. * Note- Java bytes are signed, so it is necessary to use short values here so as not to lose * precision. */ private static short[] getBytes(String byteString){ int byteCount = byteString.length()/2; short[] bytes = new short[byteCount]; for(int i = 0; i < byteCount; i++){ bytes[i] = Short.parseShort(byteString.substring(2*i, 2*i+2), 16); } return bytes; } /** * @pre this.key represents a 128-bit key * @post this.words contains the key schedule */ private void expandKey(){ for(int i = 4; i < words.length; i++){ //get the (i-1)st word Word temp = new Word(); temp.setBytes(words[i-1].getBytes()); //apply an affine transformation to every 4th byte if(i % 4 == 0){ temp.rotateAndSub(); temp = temp.xor(RCON[i/4 - 1]); } words[i] = words[i - 4].xor(temp); } } /* Key Schedule for 2B7E151628AED2A6ABF7158809CF4F3C: [2b7e1516, 28aed2a6, abf71588, 09cf4f3c, a0fafe17, 88542cb1, 23a33939, 2a6c7605, f2c295f2, 7a96b943, 5935807a, 7359f67f, 3d80477d, 4716fe3e, 1e237e44, 6d7a883b, ef44a541, a8525b7f, b671253b, db0bad00, d4d1c6f8, 7c839d87, caf2b8bc, 11f915bc, 6d88a37a, 110b3efd, dbf98641, ca0093fd, 4e54f70e, 5f5fc9f3, 84a64fb2, 4ea6dc4f, ead27321, b58dbad2, 312bf560, 7f8d292f, ac7766f3, 19fadc21, 28d12941, 575c006e, d014f9a8, c9ee2589, e13f0cc8, b6630ca6] */ public static void main(String[] args){ KeyExpansion expansion = new KeyExpansion("2B7E151628AED2A6ABF7158809CF4F3C"); System.out.println("Words: " + Arrays.toString(expansion.getWords())); System.out.println(expansion.getWords().length); } }

And the Word class, which contains methods relevant to both encryption and decryption. We will cover many of these methods further into the tutorial.

package aes; /** * * @author Michael Levet * @date 11/09/2014 * * This class models a Word as part of the key schedule. Each word is composed * of 4 bytes for the 128-bit AES cryptosystem. */ public class Word { private static final byte[] SUB_BYTES_CONSTANT = new byte[]{1, 1, 0, 0, 0, 1, 1, 0}; private static final byte[] SUB_BYTES_INVERSE_CONSTANT = new byte[]{1, 0, 1, 0, 0, 0, 0, 0}; /** * The bytes for this Word */ private short[] bytes; public Word() { } /** * @param bytes The bytes for this Word */ public Word(short[] bytes) { this.bytes = bytes; } /** * @return short[] A new array whose elements are equal to those of * this.bytes * @post this.bytes is unchanged to prevent unintended tampering of the * state of this Object */ public short[] getBytes() { short[] result = new short[bytes.length]; System.arraycopy(bytes, 0, result, 0, result.length); return result; } /** * @param bytes The bytes for this Word */ public void setBytes(short[] bytes) { this.bytes = bytes; } /** * @post The bytes in this.bytes have been reorded and revalued based on the * rotateBytes() and subWord() methods defined below */ public void rotateAndSub() { rotateBytes(); subWord(); } /** * @post The bytes have been shifted to the left by one index, with the * first element (at index 0) moved to the end of the array */ private void rotateBytes() { short temp = bytes[0]; for (int i = 1; i < bytes.length; i++) { bytes[i - 1] = bytes[i]; } bytes[bytes.length - 1] = temp; } /** * The subWord() method applies the subByte() method to each byte in * this.bytes */ public void subWord() { for (int i = 0; i < bytes.length; i++) { bytes[i] = subByte(bytes[i]); } } /** * Runs the subByteInverse() algorithm on each byte in the Word */ public void subWordInverse() { for (int i = 0; i < bytes.length; i++) { bytes[i] = subByteInverse(bytes[i]); } } /** * @param s The short representation of the byte * @return short The byte after substitution */ private short subByte(short s) { //the idea is to construct a representation of this //byte in the Rijndael Field, then to get its inverse //as a binary string, padding with leading 0's as necessary RijndaelPolynomial poly = new RijndaelPolynomial(s); poly = poly.invert(); String binaryString = Integer.toBinaryString(poly.getValue()); while (binaryString.length() < 8) { binaryString = "0" + binaryString; } char[] temp = binaryString.toCharArray(); //based on the ordering of the elements, element 0 //should be at for (int i = 0; i < temp.length / 2; i++) { char t = temp[i]; temp[i] = temp[temp.length - 1 - i]; temp[temp.length - 1 - i] = t; } int[] result = new int[temp.length]; for (int i = 0; i < temp.length; i++) { result[i] = temp[i] - '0'; result[i] += temp[(i + 4) % temp.length] - '0'; result[i] += temp[(i + 5) % temp.length] - '0'; result[i] += temp[(i + 6) % temp.length] - '0'; result[i] += temp[(i + 7) % temp.length] - '0'; result[i] += SUB_BYTES_CONSTANT[i]; result[i] %= 2; } String str = ""; for (int i = 0; i < result.length / 2; i++) { int t = result[i]; result[i] = result[result.length - 1 - i]; result[result.length - 1 - i] = t; } for (int i = 0; i < result.length; i++) { str += result[i]; } return Short.parseShort(str, 2); } /** * @param s * @return s The integer value representing the polynomial from the * subByteInverse() algorithm */ private short subByteInverse(short s) { String binaryString = Integer.toBinaryString(s); while (binaryString.length() < 8) { binaryString = "0" + binaryString; } char[] temp = binaryString.toCharArray(); //based on the ordering of the elements, element 0 //should be at the end for (int i = 0; i < temp.length / 2; i++) { char t = temp[i]; temp[i] = temp[temp.length - 1 - i]; temp[temp.length - 1 - i] = t; } int[] result = new int[temp.length]; for (int i = 0; i < temp.length; i++) { //result[i] = temp[i] - '0'; result[i] += temp[(i + 2) % temp.length] - '0'; result[i] += temp[(i + 5) % temp.length] - '0'; result[i] += temp[(i + 7) % temp.length] - '0'; result[i] += SUB_BYTES_INVERSE_CONSTANT[i]; result[i] %= 2; } for (int i = 0; i < result.length / 2; i++) { int t = result[i]; result[i] = result[result.length - 1 - i]; result[result.length - 1 - i] = t; } String str = ""; for (int i = 0; i < result.length; i++) { str += result[i]; } short value = Short.parseShort(str, 2); RijndaelPolynomial poly = new RijndaelPolynomial(value); return (short) poly.invert().getValue(); } /** * @post Each byte of this Word has been modified according to the mixColumn * algorithm */ public void mixColumn() { RijndaelPolynomial x = new RijndaelPolynomial(2); //binary 10 == x RijndaelPolynomial xplus1 = new RijndaelPolynomial(3); //binary 11 == x + 1 RijndaelPolynomial initial[] = new RijndaelPolynomial[this.bytes.length]; for (int i = 0; i < initial.length; i++) { initial[i] = new RijndaelPolynomial(this.bytes[i]); } RijndaelPolynomial updatedPolynomials[] = new RijndaelPolynomial[this.bytes.length]; for (int i = 0; i < updatedPolynomials.length; i++) { updatedPolynomials[i] = initial[i].multiply(x); updatedPolynomials[i] = updatedPolynomials[i].add(initial[(i + 1) % 4].multiply(xplus1)); updatedPolynomials[i] = updatedPolynomials[i].add(initial[(i + 2) % 4]).add(initial[(i + 3) % 4]); this.bytes[i] = (short) updatedPolynomials[i].getValue(); } } /** * Applies the mixColumnInverse() linear transformation. */ public void mixColumnInverse(){ RijndaelPolynomial[] initial = new RijndaelPolynomial[this.bytes.length]; for (int i = 0; i < initial.length; i++) { initial[i] = new RijndaelPolynomial(this.bytes[i]); } RijndaelPolynomial[] coeffs = new RijndaelPolynomial[4]; coeffs[0] = new RijndaelPolynomial(14); coeffs[1] = new RijndaelPolynomial(11); coeffs[2] = new RijndaelPolynomial(13); coeffs[3] = new RijndaelPolynomial(9); RijndaelPolynomial updatedPolynomials[] = new RijndaelPolynomial[this.bytes.length]; for(int i = 0; i < updatedPolynomials.length; i++){ updatedPolynomials[i] = coeffs[0].multiply(initial[0]); updatedPolynomials[i] = updatedPolynomials[i].add( initial[1].multiply(coeffs[1]) ); updatedPolynomials[i] = updatedPolynomials[i].add( initial[2].multiply(coeffs[2]) ); updatedPolynomials[i] = updatedPolynomials[i].add( initial[3].multiply(coeffs[3]) ); this.bytes[i] = (short)updatedPolynomials[i].getValue(); rotateRight(coeffs); } } /** * @param array The array to rotate to the right by 1 shift */ private void rotateRight(RijndaelPolynomial[] array){ RijndaelPolynomial temp = array[array.length - 1]; for(int i = array.length - 1; i > 0; i--){ array[i] = array[i - 1]; } array[0] = temp; } /** * @param Word other The word with which to XOR this * @return Word The result of this XOR other */ public Word xor(Word other) { short[] result = new short[(int) Math.max(bytes.length, other.bytes.length)]; short[] op1 = (bytes.length > other.bytes.length) ? bytes : other.bytes; short[] op2 = (op1 == bytes) ? other.bytes : bytes; int difference = op1.length - op2.length; System.arraycopy(op1, 0, result, 0, difference); for (int j = difference; j < result.length; j++) { result[j] = (short) (op1[j] ^ op2[j - difference]); } return new Word(result); } public String toString() { String result = ""; for (int i = 0; i < bytes.length; i++) { String temp = Integer.toString(bytes[i], 16); result += (temp.length() < 2) ? "0" + temp : temp; } return result; } }

**Encryption Algorithm**

Now it is time to examine the encryption algorithm. We accept a 128-bit key along with a 128-bit plaintext message to encrypt. Let the plaintext message x = (x[0], x[1], ..., x[15]) be the byte representation, where each x[i] is a byte of the plaintext message.

From the byte representation of x, we construct a 4x4 array called State as follows:

State = { {x[0], x[4], x[8], x[12] }, {x[1], x[5], x[9], x[13] }, {x[2], x[6], x[10], x[14] }, {x[3], x[7], x[11], x[15] } }

The idea now is that we add each round key to State, where addition is the XOR operation. Then each byte of State is permuted using the SubBytes algorithm, and then we rearrange the rows and columns of State. The algorithm exactly, is as follows:

encrypt(plaintext, key) keyExpansion := expand(key) //get the array of 44 Words state := convertToMatrix(plaintex) //construct 4x4 array RoundKey := array(keyExpansion[0], ..., keyExpansion[3]) state := state XOR RoundKey for i = 1 to 9 subBytes(state) shiftRows(state) mixColumns(state) RoundKey := array(keyExpansion[4i], ..., keyExpansion[4i + 3]) state := state XOR RoundKey end for subBytes(state) shiftRows(state) RoundKey := array(keyExpansion[40], ..., keyExpansion[43]) state := state XOR RoundKey return format(state)

The final ciphertext is assembled from the 4x4 array state in the same way that it is constructed. The first column consists of the first four bytes; the second column the second four bytes; etc.

So: ciphertext = (state[0][0], state[1][0], ..., state[3][0], state[0][1], ..., state[3][1], ..., state[3][3]).

Now let's step through each portion of the algorithm. We have already covered key expansion. So the first important step is to add the round key. Each round key is formed from four consecutive Words, which are column vectors. We then add the two matrices component-wise using an XOR operation.

The next step is the shiftRows() step. It takes the current state matrix and shifts the elements in the ith row i elements to the left. So row 0 is unchanged, row 1 has its elements shifted to the left by one slot, etc. Below is the following implementation of shiftRows(), contained in the State class.

/** * Shifts the ith row to the left by i positions. */ public void shiftRows() { for (int i = 1; i < state.length; i++) { shiftRow(i); } } /** * @param i The index of the row * @post Shifts the ith row to the left by i elements */ private void shiftRow(int i) { if (i <= 0 || i > 3) { return; } short[] temp = new short[4]; for (int j = 0; j < state.length; j++) { temp[j] = state[j].getBytes()[i]; } for (int j = 0; j < i; j++) { shiftRowByOne(temp); } for (int j = 0; j < state.length; j++) { short[] bytes = state[j].getBytes(); bytes[i] = temp[j]; state[j].setBytes(bytes); } }

Finally, consider the mixColumns() operation. We use the following matrix below and set State := M * State.

The mixColumn() operation appears in the Word class above:

/** * @post Each byte of this Word has been modified according to the mixColumn * algorithm */ public void mixColumn() { RijndaelPolynomial x = new RijndaelPolynomial(2); //binary 10 == x RijndaelPolynomial xplus1 = new RijndaelPolynomial(3); //binary 11 == x + 1 RijndaelPolynomial initial[] = new RijndaelPolynomial[this.bytes.length]; for (int i = 0; i < initial.length; i++) { initial[i] = new RijndaelPolynomial(this.bytes[i]); } RijndaelPolynomial updatedPolynomials[] = new RijndaelPolynomial[this.bytes.length]; for (int i = 0; i < updatedPolynomials.length; i++) { updatedPolynomials[i] = initial[i].multiply(x); updatedPolynomials[i] = updatedPolynomials[i].add(initial[(i + 1) % 4].multiply(xplus1)); updatedPolynomials[i] = updatedPolynomials[i].add(initial[(i + 2) % 4]).add(initial[(i + 3) % 4]); this.bytes[i] = (short) updatedPolynomials[i].getValue(); } }

**Decryption**

The AES cryptosystem is a symmetric-key cryptosystem. That means in the decryption algorithm works by running the encryption algorithm essentially in reverse. Each of the operations addRoundKey(), mixColumns(), shiftRows(), and subBytes() needs to be inverted. The addRoundKey() method operates using the XOR operation, which is its own inverse. The shiftRowsInverse() step is just as trivial. We simply rotate each row to the right to undo the left-shift from the encryption algorithm.

So the general algorithm for decryption is:

decrypt(ciphertext, key) keyExpansion := expand(key) //get the array of 44 Words state := convertToMatrix(ciphertex) //construct 4x4 array RoundKey := array(keyExpansion[40], ..., keyExpansion[43]) state := state XOR RoundKey shiftRowsInverse(state) subBytesInverse(state) for i = 9 to 1 RoundKey := array(keyExpansion[4i], ..., keyExpansion[4i + 3]) state := state XOR RoundKey mixColumnsInverse(state) shiftRowsInverse(state) subBytesInverse(state) end for RoundKey := array(keyExpansion[0], ..., keyExpansion[3]) state := state XOR RoundKey return format(state)

Let's now examine each of the inverse operations:

**Sub Byte Inverse**

Much like the original subByte() algorithm, the subByteInverse() is an affine transformation, given by the following matrix equation:

I offer the following implementation (in the Word class), which evaluates this affine transformation. The constant array used is provided in the Word class as well, and corresponds to the vector being XOR'd with the linear transformation.

/** * @param s * @return s The integer value representing the polynomial from the * subByteInverse() algorithm */ private short subByteInverse(short s) { String binaryString = Integer.toBinaryString(s); while (binaryString.length() < 8) { binaryString = "0" + binaryString; } char[] temp = binaryString.toCharArray(); //based on the ordering of the elements, element 0 //should be at the end for (int i = 0; i < temp.length / 2; i++) { char t = temp[i]; temp[i] = temp[temp.length - 1 - i]; temp[temp.length - 1 - i] = t; } int[] result = new int[temp.length]; for (int i = 0; i < temp.length; i++) { //result[i] = temp[i] - '0'; result[i] += temp[(i + 2) % temp.length] - '0'; result[i] += temp[(i + 5) % temp.length] - '0'; result[i] += temp[(i + 7) % temp.length] - '0'; result[i] += SUB_BYTES_INVERSE_CONSTANT[i]; result[i] %= 2; } for (int i = 0; i < result.length / 2; i++) { int t = result[i]; result[i] = result[result.length - 1 - i]; result[result.length - 1 - i] = t; } String str = ""; for (int i = 0; i < result.length; i++) { str += result[i]; } short value = Short.parseShort(str, 2); RijndaelPolynomial poly = new RijndaelPolynomial(value); return (short) poly.invert().getValue(); }

**Mix Columns Inverse**

The mixColumnsInverse() algorithm is given by the following linear transformation. Note that each number in the square matrix corresponds to an element in the Rijndael field. We convert each number in the square matrix to binary, and the binary representation corresponds to a polynomial in the Rijndael field. So the vectors are over the Rijndael field (addition is XOR and multiplication is polynomial multiplication where the coefficients are reduced mod 2).

I offer the following implementation (also in the Word class):

public void mixColumnInverse(){ RijndaelPolynomial[] initial = new RijndaelPolynomial[this.bytes.length]; for (int i = 0; i < initial.length; i++) { initial[i] = new RijndaelPolynomial(this.bytes[i]); } RijndaelPolynomial[] coeffs = new RijndaelPolynomial[4]; coeffs[0] = new RijndaelPolynomial(14); coeffs[1] = new RijndaelPolynomial(11); coeffs[2] = new RijndaelPolynomial(13); coeffs[3] = new RijndaelPolynomial(9); RijndaelPolynomial updatedPolynomials[] = new RijndaelPolynomial[this.bytes.length]; for(int i = 0; i < updatedPolynomials.length; i++){ updatedPolynomials[i] = coeffs[0].multiply(initial[0]); updatedPolynomials[i] = updatedPolynomials[i].add( initial[1].multiply(coeffs[1]) ); updatedPolynomials[i] = updatedPolynomials[i].add( initial[2].multiply(coeffs[2]) ); updatedPolynomials[i] = updatedPolynomials[i].add( initial[3].multiply(coeffs[3]) ); this.bytes[i] = (short)updatedPolynomials[i].getValue(); rotateRight(coeffs); } }

**Appendix**

I include below my implementations:

The State class:

/* * To change this template, choose Tools | Templates * and open the template in the editor. */ package aes; /** * * @author Michael Levet */ public class State { /** * Each State is a 4x4 array of bytes. * So we treat each Word as a column vector. */ protected Word[] state; /** * @pre plaintext.length == 32 * @param plaintext The text to convert into Words * @post state is a new Word[4], populated with 4 Word objects */ public State(String plaintext) { state = new Word[4]; for (int i = 0; i < 4; i++) { String substring = plaintext.substring(8 * i, 8 * i + 8); short[] bytes = getBytes(substring); state[i] = new Word(bytes); } } /** * @param words The column vectors for this state * @throws IllegalArgumentException if we don't have 4 Words */ public State(Word[] words) { if (words.length != 4) { throw new IllegalArgumentException("There must be exactly 4 Words. You passed: " + words.length + " Words."); } this.state = words; } /** * @param round The round key with which to XOR this. * The XOR operations are performed element-wise. */ public void addRoundKey(State round) { for (int i = 0; i < state.length; i++) { state[i] = state[i].xor(round.state[i]); } } /** * Runs the subByte algorithm on each Word */ public void subBytes() { for (Word w : state) { w.subWord(); } } /** * Inverts the subByte() method. */ public void subBytesInverse(){ for(Word w: state){ w.subWordInverse(); } } /** * Shifts the ith row to the left by i positions. */ public void shiftRows() { for (int i = 1; i < state.length; i++) { shiftRow(i); } } /** * Shifts row i to the right by i steps. Evaluates each row. */ public void shiftRowsInverse(){ for(int i = 1; i < state.length; i++){ shiftRowInverse(i); } } /** * @param i The number of times to shift the row to the right by 1. Also corresponds to the row. */ private void shiftRowInverse(int i){ if(i <= 0 || i > 3){ return; } short[] temp = new short[4]; for (int j = 0; j < state.length; j++) { temp[j] = state[j].getBytes()[i]; } for (int j = 0; j < 4 - i; j++) { shiftRowByOne(temp); } for (int j = 0; j < state.length; j++) { short[] bytes = state[j].getBytes(); bytes[i] = temp[j]; state[j].setBytes(bytes); } } /** * @param i The index of the row * @post Shifts the ith row to the left by i elements */ private void shiftRow(int i) { if (i <= 0 || i > 3) { return; } short[] temp = new short[4]; for (int j = 0; j < state.length; j++) { temp[j] = state[j].getBytes()[i]; } for (int j = 0; j < i; j++) { shiftRowByOne(temp); } for (int j = 0; j < state.length; j++) { short[] bytes = state[j].getBytes(); bytes[i] = temp[j]; state[j].setBytes(bytes); } } /** * @param temp The array to shift to the left by 1 */ private void shiftRowByOne(short[] temp) { short value = temp[0]; for (int j = 1; j < temp.length; j++) { temp[j - 1] = temp[j]; } temp[temp.length - 1] = value; } /** * Applies the mixColumn algorithm to each word */ public void mixColumns() { for(Word w: state){ w.mixColumn(); } } /** * Inverts the mixColumn() operation for each Word */ public void mixColumnsInverse(){ for(Word w:state){ w.mixColumnInverse(); } } /** * @return A string representation of the state represented by concatenating each Word */ public String toString() { String result = ""; for(Word w: state){ result += w.toString(); } return result; } /** * @param byteString The hex-string from which to extract the bytes * @return short[] The byteString represents bytes in hex. The short[] * contains those bytes. Note- Java bytes are signed, so it is necessary to * use short values here so as not to lose precision. */ private static short[] getBytes(String byteString) { int byteCount = byteString.length() / 2; short[] bytes = new short[byteCount]; for (int i = 0; i < byteCount; i++) { bytes[i] = Short.parseShort(byteString.substring(2 * i, 2 * i + 2), 16); } return bytes; } }

The CryptoManager class:

package aes; import java.util.Arrays; /** * * @author Michael Levet */ public class CryptoManager { public static String encrypt(String plaintext, String key){ KeyExpansion expansion = new KeyExpansion(key); State state = new State(plaintext); Word[] words = expansion.getWords(); System.out.println(words[0]); words[0].mixColumn(); System.out.println(words[0]); words[0].mixColumnInverse(); System.out.println(words[0]); State round = new State(new Word[]{ words[0], words[1], words[2], words[3] } ); state.addRoundKey(round); for(int i = 1; i < 10; i++){ state.subBytes(); state.shiftRows(); state.mixColumns(); Word[] temp = { words[4 * i], words[4 * i + 1], words[4 * i + 2], words[4 * i + 3] }; round = new State(temp); state.addRoundKey(round); } state.subBytes(); state.shiftRows(); round = new State(new Word[]{ words[40], words[41], words[42], words[43] } ); state.addRoundKey(round); return state.toString(); } public static String decrypt(String ciphertext, String key){ KeyExpansion expansion = new KeyExpansion(key); State state = new State(ciphertext); Word[] words = expansion.getWords(); State round = new State(new Word[]{ words[40], words[41], words[42], words[43] } ); state.addRoundKey(round); state.shiftRowsInverse(); state.subBytesInverse(); for(int i = 9; i > 0; i--){ Word[] temp = { words[4 * i], words[4 * i + 1], words[4 * i + 2], words[4 * i + 3] }; round = new State(temp); state.addRoundKey(round); state.mixColumnsInverse(); state.shiftRowsInverse(); state.subBytesInverse(); } round = new State(new Word[]{ words[0], words[1], words[2], words[3] } ); state.addRoundKey(round); return state.toString(); } }

And a sample:

package aes; /** * * @author Michael Levet */ public class AES { /** * @param args the command line arguments */ public static void main(String[] args) { String ciphertext = CryptoManager.encrypt("0123456789ABCDEF123456789ABCDEF0", "2B7E151628AED2A6ABF7158809CF4F3C"); System.out.println("Ciphertext: " + ciphertext); String plaintext = CryptoManager.decrypt(ciphertext, "2B7E151628AED2A6ABF7158809CF4F3C"); System.out.println("Plaintext: " + plaintext); } }

I have attached my code in a ZIP file for those interested.

AES.zip

**(31.5K)**

Number of downloads: 210