# [Cryptography] 128-Bit AES- Rijndael

Page 1 of 1

## 10 Replies - 9578 Views - Last Post: 24 December 2014 - 10:36 PMRate Topic:     //<![CDATA[ rating = new ipb.rating( 'topic_rate_', { url: 'https://www.dreamincode.net/forums/index.php?app=forums&module=ajax&section=topics&do=rateTopic&t=360211&amp;s=ee4161d18c7d9b531e369a6ede1f6bb5&md5check=' + ipb.vars['secure_hash'], cur_rating: 0, rated: 0, allow_rate: 0, multi_rate: 1, show_rate_text: true } ); //]]>

### #1 macosxnerd101 • • Games, Graphs, and Auctions
•     Reputation: 12657
• Posts: 45,831
• Joined: 27-December 08

# [Cryptography] 128-Bit AES- Rijndael

Posted 19 December 2014 - 07:22 PM

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)

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 Z2 (the integers modulo 2). So we start with the polynomials Z2[x]. That is, the coefficients of the polynomials are taken modulo 2. We then mod out the polynomials by x8 + x4 + x3 + x + 1. We denote this field as Z2[x]/(x8 + x4 + x3 + x + 1). Algebraists will recognize the notation as a quotient ring. Those familiar with number theory can think of x8 + x4 + x3 + x + 1 as a prime polynomial. So Z2[x]/(x8 + x4 + x3 + x + 1) is a field much in the same way that Zp (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 x9 + x. We consider its equivalence in the Rijndael field by finding y such that x9 + x = y (mod x8 + x4 + x3 + 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 x9 + x = p(x)(x8 + x4 + x3 + x + 1) + y, where p(x) is a polynomial in Z2[x] and y is in the Rijndael field. So we divide (x9 + x)/(x8 + x4 + x3 + x + 1) and take the remainder to be y.

So x9 + x = x(x8 + x4 + x3 + x + 1) + (x5 + x4 + x2).

Since addition is XOR (that is, we reduce the coefficients mod 2), adding in (x5 + x4 + x2) cancels out the extraneous terms. So we get:

x(x8 + x4 + x3 + x + 1) + (x5 + x4 + x2) = x9 + 2x5 + 2x4 + 2x2 + x.

Reducing the coefficients mod 2 leaves us with x9 + 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, Z2[x]/(x8 + x4 + x3 + 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| = x255 = x in the group. And so x254 = 1, which means that x253 = 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.
*/
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 x8 + x4 + x3 + 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 xi in the Rijndael Field. So 01010011 is equivalent to x6 + x4 + 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 x6 + x4 + x + 1 is x7 + x6 + x3 + 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
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;

//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,
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;
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
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));

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;
coeffs = new RijndaelPolynomial(14);
coeffs = new RijndaelPolynomial(11);
coeffs = new RijndaelPolynomial(13);
coeffs = new RijndaelPolynomial(9);

RijndaelPolynomial updatedPolynomials[] = new RijndaelPolynomial[this.bytes.length];

for(int i = 0; i < updatedPolynomials.length; i++){
updatedPolynomials[i] = coeffs.multiply(initial);

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 = 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, x, ..., x) 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, x, x, x },
{x, x, x, x },
{x, x, x, x },
{x, x, x, x }

}

```

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, ..., keyExpansion)
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, ..., keyExpansion)
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, state, ..., state, state, ..., state, ..., state).

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;
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));

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, ..., keyExpansion)
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, ..., keyExpansion)
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;
coeffs = new RijndaelPolynomial(14);
coeffs = new RijndaelPolynomial(11);
coeffs = new RijndaelPolynomial(13);
coeffs = new RijndaelPolynomial(9);

RijndaelPolynomial updatedPolynomials[] = new RijndaelPolynomial[this.bytes.length];

for(int i = 0; i < updatedPolynomials.length; i++){
updatedPolynomials[i] = coeffs.multiply(initial);

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, populated with 4 Word objects
*/
public State(String plaintext) {
state = new Word;

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.
*/
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;
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;
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;
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);
words.mixColumn();
System.out.println(words);
words.mixColumnInverse();
System.out.println(words);

State round = new State(new Word[]{ words, words, words, words } );

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.subBytes();
state.shiftRows();
round = new State(new Word[]{ words, words, words, words } );

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, words, words, words } );
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.mixColumnsInverse();
state.shiftRowsInverse();
state.subBytesInverse();
}

round = new State(new Word[]{ words, words, words, words } );

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)

Is This A Good Question/Topic? 1

## Replies To: [Cryptography] 128-Bit AES- Rijndael

### #2 ishkabible • • spelling expret
•      Reputation: 1747
• Posts: 5,898
• Joined: 03-August 09

## Re: [Cryptography] 128-Bit AES- Rijndael

Posted 22 December 2014 - 11:43 PM

This makes me feel slightly better about the algebra class I just finished. I got an A in it but I just thought I learned fuck all in it. Normally I don't think that topics need to be motivated by anything, I consider them interesting in their own right, but I hated my algebra course. I wasn't interested in any topic we covered. The last thing we covered were finite fields and field extensions. One of the problems on the final was finding the multiplication and addition tables for GF(8). I used Z2[x]/(x^3+x+1) and then after preforming a few of these computations wrote a program to compute these things for me. I realized that I could work with bit strings which was fun. For instance addition in GF(2^n) is always xor. We actually did go over how RSA worked briefly when going over the torient function but I found that pretty lack luster.

edit:
I'm not really following how your multiplication works at a glance but here is how I implemented it in pseudocode

```//multiply x by y where 'mod' is the bit string of the polynomial we have moded the Z[sub]2[/sub][x] by
z = 0
while(y) {
if(y & 1) z ^= x
y >>= 1
x <<= 1
}
//compute modulus
while(z >= mod) {
i = log2(z)  //get the index of the highest set bit. can be done with a fast bitwise trick
z ^= mod << (i - log2(mod))
}
return z

```

z == z ^ (mod << n) forall n because they differ (by xor addition) by a multiple of mod. so we just keep eliminating the highest bit of z with by shifting the highest bit of mod to that position and then xoring. So the loop loops for however many set bits there are above the highest set bit of the modulus.

Basically all I am doing is preforming multiplication in a much larger finite field of characteristic 2 and then moding the result down to the desired size.

edit2:
I also read that you can preform the inversion using the extended euclidean algorithm rather than Fermat's last theorem. Sounds better than performing so many multiplications.

This post has been edited by ishkabible: 23 December 2014 - 12:04 AM

### #3 macosxnerd101 • • Games, Graphs, and Auctions
•     Reputation: 12657
• Posts: 45,831
• Joined: 27-December 08

## Re: [Cryptography] 128-Bit AES- Rijndael

Posted 23 December 2014 - 12:30 AM

Algebra classes can be very cut and dry, at least the introductory material. This sounds like a cut and dry course. Did you cover automorphisms or group actions? Those are more applicable, at least to graph theory.

Quote

Basically all I am doing is preforming multiplication in a much larger finite field of characteristic 2 and then moding the result down to the desired size.

That pretty much sums up the idea, though I just perform the multiplication in Z2[x] rather than a specific field. Then mod out as necessary.

Quote

edit2:
I also read that you can preform the inversion using the extended euclidean algorithm rather than Fermat's last theorem. Sounds better than performing so many multiplications.

Yes, but it's also much harder to implement. I never felt confident with my implementation of the Extended Euclidean Algorithm over this particular field. It felt like a duck-taped solution, and so not one I wanted to present to other people. Also, it's Fermat's Little Theorem.

### #4 ishkabible • • spelling expret
•      Reputation: 1747
• Posts: 5,898
• Joined: 03-August 09

## Re: [Cryptography] 128-Bit AES- Rijndael

Posted 23 December 2014 - 05:21 PM

We did go over automorphisms. In fact we were introduced to them by adjacency automorphisms and automorhpism groups. We skipped the section in our book about group actions. I'm highly interested in type theory, computability (especially higher type computability), and certain areas of complexity theory (again namely higher type complexity theory). All of these things require a lot of topology background. Part of a good topology background is an algebra background so I took the course. I'm not sure I really should have taken it now.

I get Euler's theorem, Fermat's last theorem, Fermat's little theorem, and the Chinese remainder theorem confused constantly. I'm not super fond of number theory. Our algebra course seemed to have an overtone of number theory.

### #5 macosxnerd101 • • Games, Graphs, and Auctions
•     Reputation: 12657
• Posts: 45,831
• Joined: 27-December 08

## Re: [Cryptography] 128-Bit AES- Rijndael

Posted 23 December 2014 - 05:31 PM

You might find Godsil and Royle's Algebraic Graph Theory text to be a better overview of relevant algebra, though of course it is geared towards graph theory. Personally, I find topology to be gross. Algebra does come up a lot though, when you get into things like homology theory and homotopy theory.

Algebra is closely related to number theory, but it also comes up a lot in geometry, analysis, topology, physics, and combinatorics. If you do graduate work in math, senior level courses in algebra and real analysis are considered to be maturity courses. They are also necessary for much of what you want to do.

### #6 jon.kiparsky Reputation: 11689
• Posts: 19,866
• Joined: 19-March 11

## Re: [Cryptography] 128-Bit AES- Rijndael

Posted 23 December 2014 - 06:27 PM ishkabible, on 23 December 2014 - 07:21 PM, said:

Our algebra course seemed to have an overtone of number theory.

This is starting to not surprise me. I'm thinking these two, and maybe topology as well, are sort of like French, Italian, and Spanish. (while calculus might be more German - capable of saying everything the others can say, but always with a sort of abrupt and spurious precision and an astonishing lack of grace)

### #7 macosxnerd101 • • Games, Graphs, and Auctions
•     Reputation: 12657
• Posts: 45,831
• Joined: 27-December 08

## Re: [Cryptography] 128-Bit AES- Rijndael

Posted 23 December 2014 - 06:33 PM

Topology is more like calculus/analysis than algebra. Though really, algebra comes up a lot more in analysis than analysis does in algebra.

### #8 ishkabible • • spelling expret
•      Reputation: 1747
• Posts: 5,898
• Joined: 03-August 09

## Re: [Cryptography] 128-Bit AES- Rijndael

Posted 23 December 2014 - 08:37 PM

Yea number theory is deeply connected to algebra for sure. Lagrange's theorem and related theorems basically add an ungodly amount of structure to the understanding of factors. It basically lets one go from treating integers as very simple objects to very meaningful groups. For instance to prove that two numbers are co-prime just find two cyclic groups of respective orders and show that their direct product is cyclic; this might just give you the structure you need to show something like this. I'm not sure how fruitful this approach is but it illustrates how algebra can add structure to a problem that we might normally think has less structure. It's also a convenient source of free theorems.

I think the other class that I am going to take is probably real analysis as mentioned because I think one of the things I want to study is exact real arithmetic with computable reals. I'm beyond fascinated with the topic. I don't actually care about topology for studying manifolds or euclidean spaces or even the real numbers. Scott topologies basically lets us use topology to study computable and total functions as continuous functions (if bottom is included then continuous functions are computable and functions that never return bottom are total. if bottom is excluded then total functions are continuous functions). The real trick is that this continues up into things like functions between functions and so on where as classical computability theory only deals with functions from natural numbers to natural numbers. Also denotational semantics and domain theory can optionally take place in terms of Scott topologies. That's the basic area I have in mind.

Also if you are interested in formal logic you can get a lot of mileage out of topology. Homotopy type theory is a big field of study for instance (and one of the primary motivations of me taking the algebra course).

### #9 macosxnerd101 • • Games, Graphs, and Auctions
•     Reputation: 12657
• Posts: 45,831
• Joined: 27-December 08

## Re: [Cryptography] 128-Bit AES- Rijndael

Posted 23 December 2014 - 10:05 PM

Be careful with real analysis. One of the goals of that class is mathematical maturity, and the professors ream proofs in that class. Even if you have confidence, you will still be putting in 15-20 hours per week as you get knee-deep into the material.

### #10 ishkabible • • spelling expret
•      Reputation: 1747
• Posts: 5,898
• Joined: 03-August 09

## Re: [Cryptography] 128-Bit AES- Rijndael

Posted 24 December 2014 - 10:30 PM

Yea I'm not taking real analysis until grad school. I'll probably take topology as an undergrad but I think I'm going to stay away from things that don't apply to a very wide range of topics I might go into. I have no clue who my advisor will be but I will almost certainly be using topology regardless of what I pick. Real analysis is something I'd really only take if I got an advisor that was interested in exact real arithmetic.

### #11 macosxnerd101 • • Games, Graphs, and Auctions
•     Reputation: 12657
• Posts: 45,831
• Joined: 27-December 08

## Re: [Cryptography] 128-Bit AES- Rijndael

Posted 24 December 2014 - 10:36 PM

I would say take real analysis as a senior. That way, you're in a position to take measure theory (5000 reals) as a grad student. Having one of those courses each semester plus focusing on research will be tough as a grad student. Based on where you are going, familiarity with the subject will probably come in handy, even if you aren't working on the computable reals.

Page 1 of 1

 .related ul { list-style-type: circle; font-size: 12px; font-weight: bold; } .related li { margin-bottom: 5px; background-position: left 7px !important; margin-left: -35px; } .related h2 { font-size: 18px; font-weight: bold; } .related a { color: blue; }