0
$\begingroup$

I'm new to cryptography and found this statement in a book, which says that when having a message block of $64$ bits and using a key of $56$ bits, we will get $\frac{2^{112}}{2^{64}}=2^{48}$ candidate keys if we encrypt a given plaintext and decrypt the corresponding ciphertext (in double DES).

So, assuming that using one key, each of the $2^{64}$ plaintexts will be mapped to again $2^{64}$ ciphertexts and let's also assume that the function of encryption is such, that there are no repetitive ciphertexts, that being said, the mapping is bijective. Now, if we make a new set of ciphertexts for each key, there will be a total of $2^{56}$ (out of $2^{64}!$ possible permutations) different sets, corresponding to different mappings. My question is, where do we get the $2^{64}$ mentioned in the very first sentence? I get it that there are $2^{64}$ possible ciphertexts, but don't we get a set of $2^{56}$ ciphertexts from encryption, and also that much from decryption? So wouldn't the number of candidate keys be the number of elements of the intersection of these 2 sets?

$\endgroup$
5
$\begingroup$

My question is, where do we get the $2^{64}$ mentioned in the very first sentence?

There are a couple of equivalent ways of looking at the problem.

One way is to treat 2DES with an incorrect key as a completely random mapping; there are $2^{112}$ possible keys, and each incorrect key will map our one known plaintext block to a random ciphertext block; there are $2^{64}$ possible ciphertext blocks (of which 1 is the one which we know is valid); and hence each key will do the mapping correctly is $1 / 2^{64}$; hence the number of keys we expect to happen to get the mapping right is about $2^{112} / 2^{64}$ (as stated in the paragraph).

So wouldn't the number of candidate keys be the number of elements of the intersection of these 2 sets?

That's another, equally valid way of looking at the problem.

If we treat DES (both encrypt and decrypt) with an incorrect key as a completely random mapping, then both the set of $2^{56}$ ciphertexts from the first level encryption, and the $2^{56}$ plaintexts from the second level decryption, are completely random. There are $2^{64}$ plaintexts possible from the second level decryption, and so a specific block is a possible second level decryption with probability circa $2^{56}/2^{64} = 2^{-8}$. There are $2^{56}$ ciphertexts from the first level, and each one happens to be a possible second level decryption with probability $2^{-8}$, and so the expected size of the intersection is, wait for it..., $2^{56} \cdot 2^{-8} = 2^{48}$.

$\endgroup$
  • $\begingroup$ Should be 2^56 / 2^64 in the second paragraph. $\endgroup$ – FD_ Oct 18 '17 at 10:02
  • $\begingroup$ @FD_: no, it is correct as written. I am discussing the total number of keys that we expect to map a specific plaintext to a specific ciphertext; there are a total of $2^{112}$ keys (and hence maps), and the probability that any one map is correct is $2^{-64}$; the expected number is the product of these two. $\endgroup$ – poncho Oct 18 '17 at 13:14
  • $\begingroup$ Sorry, I think I wasn't clear enough: there's a 256 in 256/2^64 that I think should be 2^56 instead (a syntax issue). Near the end of your answer. $\endgroup$ – FD_ Oct 18 '17 at 13:23
  • $\begingroup$ @FD_: sorry, I counted paragraphs differently than you. $\endgroup$ – poncho Oct 18 '17 at 13:25
  • $\begingroup$ @FD_: actually, thank you for pointing out my typo... $\endgroup$ – poncho Oct 18 '17 at 13:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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