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
-
$\begingroup$ Just to have a link to the earlier question: Can one implement AES on 4-bit microcontroller?. (This is not a duplicate.) $\endgroup$– Paŭlo EbermannCommented Feb 7, 2012 at 12:02
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
8
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$ Commented 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$– ponchoCommented 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$– cLaReCommented 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$– ConradoCommented 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$ Commented Feb 10, 2012 at 0:58