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 >> 24 ] ^ T1[(a1 >> 16) & 0xff] ^ T2[(a2 >> 8) & 0xff] ^ T3[ a3 & 0xff] ^ rk[4];
b1 = T0[ a1 >> 24 ] ^ T1[(a2 >> 16) & 0xff] ^ T2[(a3 >> 8) & 0xff] ^ T3[ a0 & 0xff] ^ rk[5];
b2 = T0[ a2 >> 24 ] ^ T1[(a3 >> 16) & 0xff] ^ T2[(a0 >> 8) & 0xff] ^ T3[ a1 & 0xff] ^ rk[6];
b3 = T0[ a3 >> 24 ] ^ T1[(a0 >> 16) & 0xff] ^ T2[(a1 >> 8) & 0xff] ^ T3[ a2 & 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