1
$\begingroup$

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.

Improve this question
$\endgroup$
5
  • $\begingroup$ I'll guess, but you should verify, that means swap 1 to 0 and 0 to 1. $\endgroup$
    – ddddavidee
    Dec 6, 2014 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, 2014 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, 2014 at 17:08
  • $\begingroup$ Is this a question or a command? $\endgroup$
    – John Meacham
    Dec 7, 2014 at 1:56
  • $\begingroup$ Exercise 4 Complementation Property of DES courses.cs.ut.ee/2011/crypto1/www/tutorial/Tutorial1.pdf courses.cs.ut.ee/2011/crypto1/www/tutorial/Tutorial1_sol.pdf $\endgroup$
    – HoseinGhanbari
    Mar 11, 2021 at 10:47

0

Reset to default

Browse other questions tagged or ask your own question.