0
$\begingroup$

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.
b. Is the given system perfectly secure? Prove your answer.

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$

Improve this question
$\endgroup$
6
  • $\begingroup$ Sorry, but, basic linear algebra. Setup the equations and solve by Gaussian Elimination on $GF(2)$ $\endgroup$ Commented Jan 28, 2021 at 21:09
  • $\begingroup$ @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? $\endgroup$ Commented Jan 28, 2021 at 21:16
  • $\begingroup$ \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/… $\endgroup$ Commented Jan 28, 2021 at 21:46
  • $\begingroup$ 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. $\endgroup$ Commented Feb 28, 2021 at 4:50
  • $\begingroup$ 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. $\endgroup$ Commented Feb 28, 2021 at 4:57

1 Answer 1

Reset to default
1
$\begingroup$

Here's a hint about the second part of the question:

b. Is the given system perfectly secure? Prove your answer.

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?

Improve this answer
$\endgroup$

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.