Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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?

share|improve this question
    
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
add comment

1 Answer

up vote 2 down vote accepted

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.

share|improve this answer
    
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
1  
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
show 2 more comments

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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