My professor showed us the basics of DES, and then displayed this slide where the Complement Trick can be used as a way of cracking DES.

Could someone explain the math to me please?

enter image description here

  • $\begingroup$ I am bad at maths, and that looks like it includes things beyond the scope of my question (at least to a noob). $\endgroup$ – securityauditor May 2 '20 at 20:07
  • 1
    $\begingroup$ Does this work better? If not, do you understand what $\overline x$? is to $x$? What $E_k(m)$ is to $k$ and $m$? $\endgroup$ – fgrieu May 2 '20 at 20:12
  • $\begingroup$ I do not know what x is, and I assume x bar is the inverse? I know that E is for encrypting the message m with the key k. I also have no idea what is is showing, sorry, but I only like the clear way my professor shows it above, except this occasion where I do not understand what he means. $\endgroup$ – securityauditor May 2 '20 at 20:15
  • 4
    $\begingroup$ $\overline x$ is the bitwise complement of $x$. For all $x$ it holds $\overline{\overline{x}}=x$. Its can be shown that for all keys $k$ and all messages $m$, $\overline{E_k(m)}=E_{\overline k}(\overline m)$. This is put to use to find $k$ with twice less search work, given two plaintext/ciphertexts pair, such that the plaintext in one pair is the complement of the plaintext in the other. It works because with a single encryption under key $k$, we rule out both $k$ and $\overline k$. See the answer linked in my previous answer. $\endgroup$ – fgrieu May 2 '20 at 20:48
  • 1
    $\begingroup$ The video linked above is about complement in the context of signed arithmetic. We do not care for signed arithmetic in DES, thus this video is overkill. All there is to know about complement in the context of DES is that it takes a string of bits (here, 64-bit for e.g. $m$ or perhaps 56-bit for $k$, depending on notation), and for each of these changes a 0 to 1 and 1 to 0. E.g. $\overline{01101}=10010$ (in binary notation) $\endgroup$ – fgrieu May 3 '20 at 9:39

Browse other questions tagged or ask your own question.