Different ways/algorithms for implementing AES I have seen a couple software implementations of the Advanced Encryption Standard. They are pretty much straight forward, i.e. they are implemented exactly the same way as the AES is described. This makes an implementation of AES very easy to achieve. Nevertheless I was wondering if there are other ways of implementing it? Other algorithms for achieving a faster or more secure implementation?

For example, with ECC I know that there are different algorithms for implementing the point multiplication (double-and-add, double-and-add-always, Montgomery Algorithm). 

So, are there different algorithms for implementing AES?
To my knowledge there are at least 4 ways to implement AES.

I. lookup tables

For simple blocs, lookup tables are fast but they are sensible to timings 
attacks.

Here is an example of lookup table implementation:

b0 = T0[ a0 &gt;&gt; 24 ] ^ T1[(a1 &gt;&gt; 16) &amp; 0xff] ^ T2[(a2 &gt;&gt;  8) &amp; 0xff] ^ T3[ a3 &amp; 0xff] ^ rk[4];
b1 = T0[ a1 &gt;&gt; 24 ] ^ T1[(a2 &gt;&gt; 16) &amp; 0xff] ^ T2[(a3 &gt;&gt;  8) &amp; 0xff] ^ T3[ a0 &amp; 0xff] ^ rk[5];
b2 = T0[ a2 &gt;&gt; 24 ] ^ T1[(a3 &gt;&gt; 16) &amp; 0xff] ^ T2[(a0 &gt;&gt;  8) &amp; 0xff] ^ T3[ a1 &amp; 0xff] ^ rk[6];
b3 = T0[ a3 &gt;&gt; 24 ] ^ T1[(a0 &gt;&gt; 16) &amp; 0xff] ^ T2[(a1 &gt;&gt;  8) &amp; 0xff] ^ T3[ a2 &amp; 0xff] ^ rk[7];


II. With Inversion in $GF(2)[X]$

One can represent a polynomial of degree 7 in $GF(2)[X]$ by a number in $GF(2^8)$. (2.1.4 Polynomials over a Field, p. 13, The Design of Rinjdael) or in other word a byte.

By going back to the initial definition, one can implement subBytes is such way and have it potentially protected against timing attacks.

III. Bit sliced

Wait! This is slow as hell!

In order to gain speed, we can have a look at a bit sliced version. Bit slicing is basically writing an hardware implementation in software, considering that each bit is a different input and operations as gates applied at the same time. 

In 2007 Matsui and Nakajima propose a bit-sliced implementation of AES-CTR, about 30% faster than the table lookup version. It uses 128 bits vector registers and computes 128 blocs of AES at the same time.
The only draw back is that you need 2kB of data to encrypt to benefit from the speed up. But that is still useful in the case of HDD encryption ...

Two years later P. Schwabe and E. Käsper implement another version 20% faster and that does not have this 2kB requirement.

IV. But I need more SPEED !

In 2010, Intel provides a hardware AES instruction.

aesenc xmm1, xmm3   % xmm1 - data, xmm3 - key


Which leads to:

# Encrypt the block.
pxor       %xmm5,  %xmm0
aesenc     %xmm6,  %xmm0
aesenc     %xmm7,  %xmm0
aesenc     %xmm8,  %xmm0
aesenc     %xmm9,  %xmm0
aesenc     %xmm10, %xmm0
aesenc     %xmm11, %xmm0
aesenc     %xmm12, %xmm0
aesenc     %xmm13, %xmm0
aesenc     %xmm14, %xmm0
aesenclast %xmm15, %xmm0


source

V. More readings:

Implementing AES 2000-2010: performance and security challenges by Emilia Käsper

How can bit slicing be constant time, when Mix Columns is in the cipher