1
$\begingroup$

I am using a cryptography system in which the Feistel structure and permutation cipher are combined. I am amazed by the result; decryption is so much faster than encryption. My system is working properly. Anyone can explain why this is happening. Why is decryption faster than encryption?

$\endgroup$
4
  • 2
    $\begingroup$ If you're asking why your undisclosed cryptosystem acts the way it does, well, I don't see how we can give an answer. In addition, performance measurements are tricky; might you be counting cycles during a single encrypt operation and then a single decrypt operation? If that's what you did, perhaps the decrypt benefitted from the data being in cache... $\endgroup$
    – poncho
    Jan 16 at 14:59
  • $\begingroup$ If you use your symmetric cipher in CTR mode with block cipher decryption then encryption and decryption will be just as fast :) $\endgroup$
    – Maarten Bodewes
    Jan 16 at 16:16
  • 1
    $\begingroup$ I am using ECB mode with a symmetric-key cryptosystem. I always restart the kernel before execution. Can you explain why decryption takes less time than encryption? – $\endgroup$ Jan 17 at 12:34
  • 1
    $\begingroup$ Ok, if you want a guess, the problem might be in line 42 of your program... $\endgroup$
    – poncho
    Jan 17 at 19:10

2 Answers 2

5
$\begingroup$

In CBC and CFB modes, decryption can be parallelized, but encryption cannot. That's the most common reason for decryption being faster than encryption.

But no, it is not faster to decrypt than to encrypt in all cryptography systems. The contrary is common in asymmetric cryptography (RSA encryption with the common $e=65537$ is much faster than decryption where the exponent is much larger and has more bits set), and also not unseen in symmetric cryptography. An example is the block cipher AES implemented in software, where decryption is somewhat slower than encryption, because the invMixColumns matrix as higher coefficients than MixColumns (and to a lesser degree because it's necessary to precompute subkeys).

$\endgroup$
4
  • 1
    $\begingroup$ CBC can be modified so that the encryption is somewhat parallelized. The idea is that one could choose the last ciphertext at random, then reverse the CBC mechanism to determine previous ciphertext and the IV from previous plaintext. From there, some 2x parallelism is achieved by choosing the middle ciphertext at random, then do the normal CBC going forward and the "reversed" CBC going backwards. Whether this is CPA secure is another question :) (CCA security is anyway out of the window). But intuitively, at least the underlying blockcipher should be additionally SPRP-secure. $\endgroup$ Jan 16 at 21:14
  • $\begingroup$ Now, to be fair, the above is not "CBC" mode. :) References: research.kudelskisecurity.com/2022/11/17/… $\endgroup$ Jan 16 at 21:15
  • $\begingroup$ I am using ECB mode with a symmetric-key cryosystem. Can you explain why decryption takes less time than encryption? $\endgroup$ Jan 17 at 12:32
  • $\begingroup$ @DharmendraThapa: without knowing the cryptosystem and how it is implemented, we can only make guesses. Here are some: 1) encryption uses AES in pure software, decryption uses AES with AES-NI instructions. 2) It's used essentially AES in software, except encryption and decryption are swapped 3) the plaintext is stored on a slow medium, and it's read time is included in measurements. 4) the ciphertext is read from cache rather from disk on decryption. 5) some code alignment issue slows encryption. 6) As pointed by poncho, that line 42... $\endgroup$
    – fgrieu
    Jan 17 at 12:41
2
$\begingroup$

There is a common design pattern in cryptography which yields slower decryption than encryption. In particular, given

  • a symmetric scheme $(\mathsf{KGen}_s, \mathsf{Enc}_s, \mathsf{Dec}_s)$,
  • asymmetric scheme $(\mathsf{KGen}_{as}, \mathsf{Enc}_{as}, \mathsf{Dec}_{as})$, and
  • random oracle $\mathsf{R}$ (often you need several, whatever).

One wants to build an IND-CCA KEM, where one doesn't initially assume the cryptosystems have IND-CCA-type security (and instead have IND-CPA-type security, though the actual story is more complex than this).

A common paradigm to do this is to

  • Deterministic Encryption: Set the encryption randomness to be $\mathsf{R}(m,\dots)$, where $\dots$ may contain fixed quantities that may be known to the decryptor (say the public key)

  • Reencryption: Have decryption recompute encryption using this deterministic randomness to "check" that the recieved ciphertext is the correct one, e.g. has not been modified.

There are many techniques to do this, see this for pointers. One way of viewing this is that decryption is "redoing" many parts of encryption (and sometimes key generation, I'll ignore that though). This can lead to decryption being slower. See page 17 of the Kyber reference for cycle counts suggesting this happens.

There are cryptosystems for which it is simpler to see that $\mathsf{Dec}$ is much slower than $\mathsf{Enc}$. The easiest example is ElGamal encryption. When used as an additively homomorphic cryptosystem, decryption involves computing a certain (restricted) form of discrete logarithm. The complexity of this discrete logarithm depends on the precise computation being done, but in the general case decryption can be quite hard.

$\endgroup$
2
  • 1
    $\begingroup$ @infinitezero I replaced the example of decryption calling encryption with a cryptographically motivated one. Note that it still recalls $\mathsf{Enc}$ during $\mathsf{Dec}$, e.g. this is actually often done for legitimate reasons (though I agree spelling this out was probably a good idea). $\endgroup$
    – Mark Schultz-Wu
    Jan 17 at 18:51
  • $\begingroup$ @infinitezero I am glad there are more details and references to real case where the first example naturally happens. But, there was nothing unreasonable with the text as is. I believe it should be read rather as: "Just because you took the shortest path, doesn't mean you can't take a 2h breakfast along the way". :) $\endgroup$ Jan 17 at 21:09

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