As the finite field of $GF(2^8)$ are isomorphic to $GF((2^4)^2)$, $GF((2^2)^4)$ and $GF(((2^2)^2)^2)$, which of the fields is best suited and most efficient for 4-bit MCU and why? Would it be $GF((2^4)^2)$?


1 Answer 1


While $GF(2^8)$ is indeed isomorphic to $GF((2^4)^2)$ (and to the other fields you have mentioned), if you use the latter you will need a conversion routine to change the field representation from and to $GF(2^8)$. This will probably defeat any performance gain with the alternative representation (and I'm not sure there would be any). Another related issue is that the "nice" constants used in MixColumns (2 and 3) may not be so nice in the converted form, hurting performance when you multiply by them.

You can simply represent a $GF(2^8)$ element using two 4-bit words.

  • $\begingroup$ The appendix of (The Design of Rijndael contains a definition of a more general Rijndael variant (Rijndael-GF) on blocks of elements of $GF(2^8)$. One only needs to define the encoding on input and output to get a representation, and one specific such encoding gives the usual Rijndael on bytes. I could imagine that using $GF((2^4)^2)$ allows faster multiplication, though this would have to be checked. $\endgroup$ Feb 7, 2012 at 12:12
  • 2
    $\begingroup$ Note that AES never requires a general $GF(2^8)$ multiplication; the only $GF$ operations it does are: addition (aka XOR), multiplication by the fixed constants 2 and 3 (an LFSR shift, and a LFSR shift followed by an XOR), and $GF$ inverse. Unless you use your multiplication operation to do the inverse (and I believe there are easier ways, such as extended Euclidean), how well you can multiply is unimportant. $\endgroup$
    – poncho
    Feb 7, 2012 at 16:11
  • $\begingroup$ Let's just focused on the S-box (the most complicated operation) for now. I have learned that using composite field arithmetic and followed by extended Euclidean actually would reduce the size of the S-box. So in this case, would this method be suitable for 4-bit MCU? or using LUT tables would be a better choice? $\endgroup$
    – cLaRe
    Feb 8, 2012 at 1:11
  • $\begingroup$ Using composite field arithmetic allows you to compute an inverse by computing a single inverse in $GF(2^4)$. It seems to me that the code required to compute this would itself be greater than 256 bytes, killing any advantage over using a precomputed S-box. But it's hard to say without actually implementing it. $\endgroup$
    – Conrado
    Feb 9, 2012 at 10:32
  • $\begingroup$ @ConradoPLG: 256 bytes is a lot. Admittedly, I've never tried writing code to compute Galois field inverses on a 4-bit processor, but I'd be very surprised if it took that much space. $\endgroup$ Feb 10, 2012 at 0:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.