|
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? |
|||||
|
|
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:
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. |
|||||||||||||
|
