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$

$\endgroup$
6
  • $\begingroup$ Sorry, but, basic linear algebra. Setup the equations and solve by Gaussian Elimination on $GF(2)$ $\endgroup$
    – kelalaka
    Jan 28 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$ Jan 28 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$
    – kelalaka
    Jan 28 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$ Feb 28 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$ Feb 28 at 4:57
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?

$\endgroup$

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.