I tried to work this out but I'm stuck at finding a relation between $c$ and $e(k)$:

An encryption system accepts 8 bit-blocks as input.

The encryption is done by XOR'ing the bits with an 8-bit key.

Prove that:

  1. $(m_1 ⊕ m_2) = e_k(m_1) ⊕ e_k(m_2)$

  2. There does not exist a message $m$, such that $e_k(m) = m$, except when $k$ is all 0's.

  • $\begingroup$ Well, what have you tried then? $\endgroup$ – fkraiem Dec 28 '16 at 3:54
  • $\begingroup$ I tried to copyedit your question a bit, but I'm not entirely sure what you meant by "a relation between c & e(k)" in the first paragraph. You might want to clarify that (and check that I haven't introduced any mistakes in my edit, while you're at it). $\endgroup$ – Ilmari Karonen Dec 28 '16 at 4:09

Let $k$ be the 8-bit key. Since encryption is simply done by XORin the plaintext with the key, i.e. $e_k(m) = k \oplus m$, we have:

$$e_k(m_1) \oplus e_k(m_2) = (k \oplus m_1) \oplus (k \oplus m_2).$$

Now, the thing you need to know about XOR is that it obeys the same commutative, and associative laws as normal addition, that is:

$$a \oplus b = b \oplus a$$ $$a \oplus (b \oplus c) = (a \oplus b) \oplus c$$

and it also obeys the cancellative laws:

$$a \oplus a = \bar 0$$ $$a \oplus \bar 0 = a$$

where $\bar 0$ denotes the string of all zero bits.

Using these algebraic laws, you should be able to show that the two $k$'s on the right hand side of the equation above will cancel out, leaving only $m_1 \oplus m_2$.

Similarly, you should be able to show that, if $k \oplus m = m$, then $k = \bar 0$. The easiest way is probably to observe that, if $a = b$, than $a \oplus c = b \oplus c$. Thus, you can XOR both sides of the equation $k \oplus m = m$ with $m$, and then apply the cancellative law.

| improve this answer | |

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.