Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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)$?

share|improve this question
    
Just to have a link to the earlier question: Can one implement AES on 4-bit microcontroller?. (This is not a duplicate.) –  Paŭlo Ebermann Feb 7 '12 at 12:02

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.

share|improve this answer
    
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. –  Paŭlo Ebermann Feb 7 '12 at 12:12
2  
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. –  poncho Feb 7 '12 at 16:11
    
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? –  cLaRe Feb 8 '12 at 1:11
    
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. –  Conrado PLG Feb 9 '12 at 10:32
    
@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. –  Ilmari Karonen Feb 10 '12 at 0:58

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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