# Deciphering a key from XOR encrypted cypher using boolean logic

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?

• 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. – Thomas Jul 1 '12 at 2:17
• @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. – 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.

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