This question already has an answer here:

It is known that DES has the key-complementation property. That is, given any key $k$ and any message $m\in\{0,1\}^{64}$ $$\operatorname{DES}_k(m)=\overline{\operatorname{DES}_\overline k(\overline m)}$$

By using this property, show that the key search of DES can be sped up by a factor of two.


marked as duplicate by poncho, Gilles, DrLecter, fgrieu, e-sushi Dec 8 '14 at 3:46

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • $\begingroup$ I'll guess, but you should verify, that means swap 1 to 0 and 0 to 1. $\endgroup$ – ddddavidee Dec 6 '14 at 14:19
  • 2
    $\begingroup$ Give a look of Fact 7.87 of the Handbook of Applied Cryptography: cacr.uwaterloo.ca/hac/about/chap7.pdf $\endgroup$ – ddddavidee Dec 6 '14 at 14:26
  • $\begingroup$ Note: By definition $\overline x$ is the bitwise complement or bitwise NOT of $x$. $\;$ Hint: assume that you can obtain the ciphertexts for two values of plaintext: an $m$ that you know [that is: you obtain $m$ and $c=\operatorname{DES}_k(m)$ ], and an $m′$ that you choose [that is: you choose $m′$ and obtain $c′=\operatorname{DES}_k(m′)$ ]. How do you choose $m′$ so that you can test (with low odds of false positive) two values of $k$ with a single DES encryption? $\endgroup$ – fgrieu Dec 6 '14 at 17:08
  • $\begingroup$ Is this a question or a command? $\endgroup$ – John Meacham Dec 7 '14 at 1:56