# DES key complementation property [duplicate]

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)}$$
• 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 6 '14 at 17:08