Is encryption time greater than decryption time?

Question

Is encryption time always greater than decryption time for all encryption techniques (AES / DES / RSA / DSA), or is there a mistake somewhere in my implementation?

Answer 1

It depends. Specifically, it depends on the type of cipher, and on the way it's used.

For stream ciphers like RC4, and for block ciphers like AES in CTR and OFB modes, decryption is effectively identical to encryption, and thus takes the exact same time. (Minor exception: encryption may require generating a unique nonce / IV, which might take a small amount of extra time.)

For block ciphers in CFB mode, encryption must be done sequentially (since each cipher block depends on the previous one), but decryption can be parallelized. Thus, on a multi-core implementation, CFB decryption is typically faster than encryption.

The same is also true for CBC mode, but there's an additional quirk: CBC mode decryption requires using the block cipher in inverse ("decryption") mode (CTR, OFB and CFB all use the block cipher only in forward direction, even for decryption). For some block ciphers (notably including many implementations of AES), using the cipher in the inverse direction may be somewhat slower than the forward direction e.g. due to asymmetries in the key schedule. Thus, on systems that support parallel decryption, CBC decryption is typically faster than encryption, but on systems that don't, it may be slightly slower.

Finally, for block ciphers in ECB mode (which is insecure for most purposes, and so should not be used), the only difference between encryption and decryption is the direction the block cipher is used in. Thus, as noted above, decryption may be slightly slower than encryption (although, of course, you could always decide to swap the directions if you want).

---

Of course, in modern cryptography, you really should be using an authenticated encryption mode. Many of these (like GCM, EAX, CCM, etc.) are essentially based on a combination of CTR mode and a MAC; since CTR decryption is identical to CTR encryption, and since the MAC is computed the same way in either case, the total time for encryption and decryption should be approximately the same.

That said, there are, again, some exceptions. For example, for SIV mode encryption, the MAC must be computed (to generate the synthetic IV) before encryption can begin, whereas for SIV decryption, the MAC can be computed (mostly) in parallel. Thus, for SIV mode, encryption may be up to twice as slow as decryption. (Of course, this is by wall clock time; the CPU time consumed should still be approximately the same for both directions.)

---

Finally, for asymmetric encryption (RSA, (EC)IES, etc.), the difference could really go either way.

For RSA specifically, decryption is typically slower than encryption; that's because both RSA encryption and decryption involve modular exponentiation, but whereas the public encryption exponent is normally small and fixed (usually either 3 or 2¹⁶+1 = 65,537), the secret decryption exponent is usually almost as long as the modulus. Thus, doubling the modulus size makes encryption take twice as long, but makes decryption take four times as long. Using the Chinese Remainder Theorem does speed up RSA decryption, but only by a factor of about four (as it effectively halves the size of the numbers one needs to work with) at most.

Conversely, for ECIES, encryption requires generating a random number and computing two scalar multiplications, and is thus generally slower than decryption, which only requires a single scalar multiplication.

In any case, asymmetric encryption of large messages is typically done using hybrid encryption, where the message is first encrypted using a symmetric cipher, using a random key, and the random key is then encrypted asymmetrically. Thus, for large enough messages, most of the time will be spent on symmetric encryption anyway.