Assume there's an unencrypted message A, and an encrypted message B. You know that message B was encrypted using a simple XOR method of A with a private key K, resulting in message B. Thus,

B = A ⊕ K

Can I use Boolean algebra, i.e. truth tables, and sum of products to decode the key?

  • $\begingroup$ Come on guys, it's obvious he posted before finishing his question and didn't realize it or didn't know how to edit it. At least that's what I interpret as most likely assumption. $\endgroup$
    – Thomas
    Jul 1 '12 at 2:17
  • $\begingroup$ @Thomas, LOL! You're correct. I accidentally hit the add comment and walked off thinking it was still in draft. It is certainly better than FaceBook where accidentally hitting enter instead of shift-enter for a line break can lead to embarrassment and unwanted drama. $\endgroup$
    – user148298
    Jul 1 '12 at 4:20

If $K$ is random and you only know $A$ or $B$ (but not both) then, no, there is no way to infer anything about the key - this is the (in)famous one-time-pad.

If you know $A$ and $B$, then you can recover $K$ very easily. Exclusive-or has those properties:

  • $\forall n$, $~~~~ n \oplus n = 0$
  • $\forall n$, $~~~~ n \oplus 0 = n$ (identity element)
  • $\forall a, b$, $~~~~ a \oplus b = b \oplus a$ (commutativity)
  • $\forall a, b, c$, $~~~~ a \oplus b \oplus c = (a \oplus b) \oplus c = a \oplus (b \oplus c)$ (associativity)

So we can do the following:

$B = A \oplus K ~~~ \Rightarrow ~~~ A \oplus B = A \oplus (A \oplus K) = (A \oplus A) \oplus K = 0 \oplus K = K$

So $A \oplus B = K$

Viewed differently, the exclusive-or operator is invertible:

$\begin{array}{|c|c|c|} \hline \oplus &0 &1 \\ \hline 0 &0 &1 \\ 1 &1 &0 \\ \hline \end{array}$

$\begin{array}{|c|c|c|} \hline A &B &\oplus \\ \hline 0 &0 &0 \\ 0 &1 &1 \\ 1 &0 &1 \\ 1 &1 &0 \\ \hline \end{array}$

And since the truth table is symmetric, the exclusive-or operation just happens to be its own inverse, i.e. $x \oplus^{-1} y = x \oplus y$. So if we take our original equation:

$A \oplus K = B$

We can represent it as follows:

$K \oplus A = B$

And we can then undo (invert) the exclusive-or by A:

$K \oplus A \oplus^{-1} A = B \oplus^{-1} A ~~~ \Rightarrow ~~~ K = B \oplus^{-1} A$

And as we found above, this is identical to:

$K = B \oplus A = A \oplus B$

As found at the beginning.

However, this is assuming A, B and K are all the same length. If K is smaller than A and B, then it means that K will be used multiple times (repeated over the length of the plaintext, presumably). This repetition can be exploited to successfully recover K from only B provided there is enough repetition and there is enough ciphertext to work with - see Vigenere cipher.

  • $\begingroup$ Since you are being so careful and pedantic about the matter, could you add a few words of justification as to how you got from $$A \oplus K \oplus K = B \oplus K$$ to $$A = B \oplus K?$$ Haven't you used associativity (not mentioned anywhere in your answer) to regroup $(A \oplus K) \oplus K$ as $A \oplus (K \oplus K) = A \oplus 0 = A$? In fact, why bother with commutavity at all and instead just use associativity to write $$A \oplus K = B \Rightarrow A \oplus (A \oplus K) = (A \oplus A) \oplus K = 0 \oplus K = K = A \oplus B?$$ $\endgroup$ Jul 1 '12 at 12:00
  • $\begingroup$ Indeed, I was contemplating adding brackets to make it clearer. I will edit. However I felt I needed to add detail since the question seemed to focus on the aspects of boolean algebra. $\endgroup$
    – Thomas
    Jul 1 '12 at 12:13
  • $\begingroup$ Better now I hope. $\endgroup$
    – Thomas
    Jul 1 '12 at 12:29
  • 1
    $\begingroup$ Yes, better. I have proposed a further improvement as an edit that is awaiting peer review. $\endgroup$ Jul 1 '12 at 13:19
  • $\begingroup$ Approved. Your derivation has a nicer flow, thanks. $\endgroup$
    – Thomas
    Jul 1 '12 at 13:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.