Protecting Against Eavesdroppers with Symmetric Cryptography - Implementing SSL/TLS Using Cryptography and PKI - page 72

AES redefi nes the add and multiply operations for its matrix multiplication.
This means also that you don't have to worry about the thorny topic of matrix
inversion, which is fortunate because it's as complex as it looks (if not more so).
Adding in AES is actually redefi ned as XORing , which is nothing at all like
adding. Multiplying is repeated adding, just as in ordinary arithmetic, but it's
done modulo 0x1B (remember this value from the key schedule?). The speci-
fi cation refers to this as a dot product — another linear algebra term, but again
redefi ned. If your head is spinning from this mathematicalese, perhaps some
code will help.
To multiply two bytes — that is, to compute their dot product in AES — you
XOR together the xtime values of the multiplicand with the multiplier. What are
xtime values? They're the “left-shift and XOR with 0x1B on overfl ow” operation
that described the round constant in the key schedule computation. In code,
this works out to Listing 2-37.
Listing 2-37: “aes.c” dot product
unsigned char xtime( unsigned char x )
{
return ( x << 1 ) ^ ( ( x & 0x80 ) ? 0x1b : 0x00 );
}
unsigned char dot( unsigned char x, unsigned char y )
{
unsigned char mask;
unsigned char product = 0;
for ( mask = 0x01; mask; mask <<= 1 )
{
if ( y & mask )
{
product ^= x;
}
x = xtime( x );
}
return product;
}
This probably doesn't look much like multiplication to you — and, honestly,
it isn't — but this is algorithmically how you'd go about performing binary
multiplication if you didn't have a machine code implementation of it to do the
heavy lifting for you. In fact, this concept reappears in the next chapter when
the topic of arbitrary-precision binary math is examined.
Fortunately, from an implementation perspective, you can just accept that
this is “what you do” with the bytes in a column-mixing operation.