1
$\begingroup$

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?

$\endgroup$
2
  • $\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
    Commented Jul 1, 2012 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
    Commented Jul 1, 2012 at 4:20

1 Answer 1

3
$\begingroup$

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.

$\endgroup$
7
  • $\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$ Commented Jul 1, 2012 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
    Commented Jul 1, 2012 at 12:13
  • $\begingroup$ Better now I hope. $\endgroup$
    – Thomas
    Commented Jul 1, 2012 at 12:29
  • 1
    $\begingroup$ Yes, better. I have proposed a further improvement as an edit that is awaiting peer review. $\endgroup$ Commented Jul 1, 2012 at 13:19
  • $\begingroup$ Approved. Your derivation has a nicer flow, thanks. $\endgroup$
    – Thomas
    Commented Jul 1, 2012 at 13:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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