This is from a cryptography book description encryption & decryption using stream ciphers
Encryption $ e(x_i) = y_i \equiv x_i + s_i mod 2$
where $x_i, y_i, s_i \in\ \{0,1\} $
Prove that
$x_i \equiv y_i + s_i mod 2$
Proof:
$ e(y_i) \equiv y_i + s_i mod2$
subsitute value of $y_i$ in the above
$e(y_i) \equiv x_i + s_i + s_i mod 2$ —- (1)
$e(y_i) \equiv x_i + 2 s_i mod 2$
$e(y_i) \equiv x_i + 0 mod 2$
$e(y_i) \equiv x_i mod 2$ Q.E.D* — (2)
I didn't understand 2 things here (1) & (2)
(1) Shouldn't (1) have been $e(y_i) \equiv x_i + s_i mod 2 + s_i mod 2$ instead of $e(y_i) \equiv x_i + s_i + s_i mod 2$
(2) How do they arrive at the Q.E.D
All that was prove in (2) was that $e(y_i) \equiv x_i mod 2$
What was required to be proven was $e(y_i) \equiv x_i + s_i mod 2$
So how is the proof completed?
Best Answer
You are given that $y_i=e(x_i)=(x_i+s_i) \pmod{2}$. Here $x_i, s_i \in \{0,1\}$ (bits) and the operation $\mod 2$ is applied to the sum of the bits $x_i$ and $s_i$.
Now we want the decryption function $d$ so that $d(y_i)=x_i$. The claim is that the encryption and decryption functions are the same, i.e. $x_i=d(y_i)=(y_i+s_i) \pmod{2}$.
So, \begin{align*} d(y_i)&=(y_i+s_i) \pmod{2}\\ &=(\overbrace{x_i+s_i}^{y_i}+s_i) \pmod{2} & \because s_i = s_i \bmod{2}\\ &=(x_i+2s_i) \pmod{2}\\ &=x_i \pmod{2}\\ &=x_i & \because x_i = x_i \bmod{2} \end{align*}