# How to solve this decryption algorithm given the encryption algorithm?

Consider the following cryptosystem with plaintexts from the set $$M$$ and ciphertexts from the set $$S$$ with $$M = S = \{0, 1\}^4$$ . A plaintext $$P = (P_1, P_2, P_3, P_4)$$ is encrypted to a ciphertext $$C = (C_1, C_2, C_3, C_4)$$ as follows.
$$C_1 = (a P_1 + P_2) \pmod 2$$
$$C_2 = (b P_1 + c P_2) \pmod 2$$
$$C_3 = (d P_3 + e P_4) \pmod 2$$
$$C_4 = ( P_3 + f P_4) \pmod 2$$

The key is given as $$k = (a, b, c, d, e, f)\in \{0, 1\}^6$$, i.e., it holds $$C = E(k,P)$$.
a. Describe the decription algorithm.

I know that if $$C_1 = a + P_1$$ then $$P_1 = a + C_1$$. However because $$C_1$$ and $$C_2$$ use the same letters $$P_1$$ and $$P_2$$ (also in the case of $$C_3$$ and $$C_4$$), I don't know how to reverse them to get back $$P_1$$ and $$P_2$$

• Sorry, but, basic linear algebra. Setup the equations and solve by Gaussian Elimination on $GF(2)$ Jan 28, 2021 at 21:09
• @kelalaka $$\left[ \begin{array}{cccccc|c} a & 0 & 0 & 0 & 0 & 0 & P_1 \\ 0 & b & c & 0 & 0 & 0 & P_2 \\ 0 & 0 & 0 & d & e & 0 & P_3 \\ 0 & 0 & 0 & 0 & 0 & f & P_4 \end{array} \right]$$ something like this? Jan 28, 2021 at 21:16
• \begin{array}{ccccc} a & 1 & 0 & 0 & 0 & C_1\\ b & c & 0 & 0 & 0 & C_2 \\ 0 & 0 & d & e & 0 & C_3 \\ 0 & 0 & 0 & 1 & f & C_4 \end{array} See dummies.com/education/math/calculus/… Jan 28, 2021 at 21:46
• I think the better idea will be to use key $(a,b,c,d,e,f)$ as the variable vector $x$ with the last element = 1 as in $[a,b,c,d,e,f,1]^T$. Create matrix $A$ using plain texts and ciphertext is solution matrix $B$ in $Ax=B$. It will be easier to check for solvability for any plaintext matrix of the given form and any ciphertext that way. Feb 28, 2021 at 4:50
• Sorry, I completely ignored the first question. My comment above was for second question, to check for solvability. Does any key (solution) exist for any arbitrary plain-text cipher-text pair can be checked by using key as variable vector instead. Feb 28, 2021 at 4:57

Hint: what is the encryption of the plaintext $$(0, 0, 0, 0)$$? If the ciphertext is something other than $$(0, 0, 0, 0)$$, what can we infer about the plaintext about that?