AES finite field multiplication on Logic Gates « The Hardware Side of Cryptography

18 February 2008

AES finite field multiplication on Logic Gates

Filed under: encryption, logic gate — Tags: AES, Finite Multiplication, Galois Field, Logic Gates, Mix Column, Rijndael — edipermadi @ 5:13 am

Have you ever think about doing AES (Rijndael) finite field multiplication in hardware instead of software. If that so, you got the same question as me. I was wondering how to do AES (Rijndael) finite field multiplication on Logic Gates. After long path way through google. Finally, i found an idea on how to solve this problem. It was just circular left shift by one and conditional XOR by certain constant. Sounds nice and fun.

My previous was about implementing finite field mltiplication bt two, but here i expanded it into full 8 bit by 8 bit finite field multiplication for AES (Rijndael). Hopefully, if you are the one that questioning about how to implement galois field or finite field multiplication of AES (Rijndael) algorithm on hardware (especially logic gates), you will find this picture satisfy and answer your question. All of this picture is only to show you how to do C = (A x B) mod N. where N here is x⁸ + x⁴ + x³ + x¹ + 1 or simply 0×1b. Just for that simple equation, we gone through this complicated path .

If you mad enough, you can expand this picture to universal finite field multiplication, not only for AES, but for any finite field multiplication. Thats gonna be cool. If you got it, you can easily implement RSA encryption using logic gates. Isn’t that mad enough .

You can freely use and redistribute this picture under the term of GNU Public License v3.0.

Note : I just expanded this picture from my previous post about galois field.

PROOFING AND BENCHMARK

To proof that my circuit work well, lets compare theoretical and real result. If they are the same, means the circuit is OK. For picture, lets define “1″ as RED and “0″ as BLUE.

For theoretical part, Lets do this :

(0×8c x 0×57) mod 0×1b = … ?
0×8c = 10001100 = (0×80 + 0×08 + 0×04)
0×57 = 01010111

(0×8c x 0×57) = (0×57 x 0×04) + (0×57 x 0×0 + (0×57 x 0×80)

Lets go further step by Step

(0×57 x 0×01) = 0×57
(0×57 x 0×02) = 10101110 = 0xae
(0×57 x 0×04) = 01011100 ^ 00011011 = 01000111 = 0×47
(0×57 x 0×0 = 10001110 = 0×8e
(0×57 x 0×10) = 00011100 ^ 00011011 = 00000111 = 0×07
(0×57 x 0×20) = 00001110 = 0×0e
(0×57 x 0×40) = 00011100 = 0×1b
(0×57 x 0×80) = 00111000 = 0×38

Previously, we stated that:
(0×8c x 0×57) = (0×57 x 0×80) + (0×57 x 0×0 + (0×57 x 0×04)

Hence:

(0×8c x 0×57) = 0×47 ^ 0×8e ^ 0×38 = 0xf1

Testing Screenshot: