# Prove that (m1 ⊕ m2) = ek(m1) ⊕ ek(m2) for a 8-bit blocks i/p encryption system

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.

• Well, what have you tried then? – fkraiem Dec 28 '16 at 3:54
• 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). – 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.