1

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.

Gilles 'SO- stop being evil'
  • 19,134
  • 4
  • 50
  • 92
Aram
  • 11
  • 2
  • I'll guess, but you should verify, that means swap 1 to 0 and 0 to 1. – ddddavidee Dec 06 '14 at 14:19
  • 2
    Give a look of Fact 7.87 of the Handbook of Applied Cryptography: http://cacr.uwaterloo.ca/hac/about/chap7.pdf – ddddavidee Dec 06 '14 at 14:26
  • 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? – fgrieu Dec 06 '14 at 17:08
  • Is this a question or a command? – John Meacham Dec 07 '14 at 01:56
  • Exercise 4 Complementation Property of DES https://courses.cs.ut.ee/2011/crypto1/www/tutorial/Tutorial1.pdf https://courses.cs.ut.ee/2011/crypto1/www/tutorial/Tutorial1_sol.pdf – HoseinGhanbari Mar 11 '21 at 10:47

0 Answers0