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.

I'm implementing AES in C++, and, inspired by the way words are handled in SHA, I decided this time to handle the state as a one dimensional array of 4byte unsigned integers as opposed to a two dimensional array of bytes. To get the bytes out of each of word, I use shifts and mod. E.g. to get the first byte in state[0], I would retrieve byteA = (state[0] >> 24); and to get the second, byteB = (state[0] >> 16) % 256;

In the mix columns and substitution steps, I have to extract and replace bytes from the word, but in the shift rows and add key steps, I can operate on an entire row at once, eliminating the need for 4 extra iterations per row.

Unless this would be very specific to my implementation, I'd appreciate some input on which might be faster.

share|improve this question

2 Answers 2

One way to see it is the following: RAM is slow. Modern processors can do several operations in a single clock cycles. However, a RAM access, such as retrieving data from an array based on a computed index, has inherent latencies and concurrencies issues; in the best of cases, you can do one memory access per cycle, and the result is not available for computations until at least one or two cycles later (even if all the data is in L1 cache).

Therefore, generically, it is best to do as little array accesses as possible. Which means grabbing from each array access as much data as possible, such as a full 32-bit word instead of just one byte.

The trouble with generic comments like the one above is that they are, well, generic. Performance issues depend a lot on the involved architectures, the operational constraints, and what you want to achieve; there are several metrics of performance, such as bandwidth, latency, code size, energy consumption... So, really, you have to try. However, most people (including myself) who have tried to implement AES on 32-bit processors (like a PC or an ARM CPU) with at least a few kilobytes of L1 cache, and no hard limit on code size, have found the "32-bit word" structure to be the best -- unless you aim for an implementation which resists to cache timing attacks, in which case you have to do things quite differently, without any array at all.

To investigate the ins and outs of AES software implementation, you could do worse than perusing Brian Gladman's site which is kind of a reference on the subject.

share|improve this answer

I think what would be faster is using the hardware AES-NI instructions if those are available to you (and as a bonus, you avoid side-channel attacks, and it's much easier to implement, especially if you have intrinsics available to you, that way you don't need to go implement it in assembly).

As for your question, OpenSSL uses four 32-bit integers as the matrix, and is pretty damn fast (you can look at how they do it here). I myself tried a byte-based approach (which I basically copied from a public-domain source, see here), but it doesn't work too well, though it is a bit easier to read in my opinion...

There are a lot of tables because the Galois Field multiplications are precomputed and combined with the row/column operations, which means a single AES encryption boils down to a few exclusive-or operations (to mix the key in) and a couple table lookups per byte per round, which is really fast.

share|improve this answer
    
It occurs to me this question might be a little off-topic as it's really more about programming than the theoretical aspects of cryptography (barring side-channel analysis) but hey. –  Thomas Nov 17 '12 at 6:06
    
Thanks for the links and input! I considered that it might be more fitted for stack overflow, but I figured it was a fairly general issue specifically relating to AES, like this style choice could apply in any language anywhere. –  Dakota West Nov 17 '12 at 6:12
2  
@DakotaWest, Personally, I think the question is fine for Crypto.SE. The FAQ says "Crypto.SE is for software developers, mathematicians and others interested in cryptography.", and I think this question is fine by that criterion. –  D.W. Nov 18 '12 at 6:05

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.