3
$\begingroup$

I know this question has already been asked few times but I'm struggling a bit on a problem.

I have a plaintext FRIDAY and its ciphertext PQCFKU, using $M = 2$, with corresponding integers $x = fr id ay = (5, 17),(8,3),(0,24)$ and $y = pq cf ku = (15, 16),(2,5),(10,20)$.

In order to find the key $k$:

$$\pmatrix{y1 \\y2 \\} = \pmatrix{x1 \\x2 \\}k$$ $$\pmatrix{15&16 \\2&5} = \pmatrix{5&17 \\8&3 \\}k$$

Now $x$ determinant, $det(x)$ is given by:

$$det(x)=5*3-8*17 = -121$$ and, using modulo 26: $$-121\pmod{26} = 9$$ Then, $det(x^{-1})$ is given by: $$9^{-1}\pmod{26} = 3$$

Now $X^{c}$ is: $$X^{c}=\pmatrix{3&8\\-17&5}$$ And $(X^{-1})^{T}$ is: $$(X^{-1})^{T}=\pmatrix{3&-17\\-8&5}$$

So, In order to find $k$: $$k=(\pmatrix{3&-17\\-8&5}det(x^{-1}))\pmod{26}$$ Which is: $$k=(\pmatrix{3&-17\\-8&5}3)\pmod{26}$$ $$k=\pmatrix{9&-51\\-24&15}\pmod{26}$$ $$k=\pmatrix{9&1\\2&15}$$

Now comes the problems, doing the decryption using $k$ and $pq$ I can't get $fr$ back.

If I'm not wrong:

$$x1 = (15,16)\pmatrix{9&1\\2&15}=(15*9+16*1, 15*2+16*15)=(151, 270)$$

And now, to obtain the plaintext:

$$(151, 270)\pmod{26} = (21, 10) $$

and, $$(21, 10) $$ leads to $vm$ which is clearly not $fr$

Is my reasoning wrong? Am I doing errors?

I've been scratching my head for a while but I was unable to find valid solution. Thanks in advance.

$\endgroup$
  • $\begingroup$ Not sure if it matters, but on Wikipedia the multiplication is done from the right rather than from the left (first line) $\endgroup$ – SEJPM Jan 22 '17 at 19:42
3
$\begingroup$

Actually it seems to me that you are using the wrong basis and got the key for the other way around:

Suppose you have the plain text $x_1 = \pmatrix{5\\17}$ and $x_2= \pmatrix{8\\3 \\}$ and the corresponding ciphertexts $y_1=\pmatrix{15 \\16}$ and $y_2=\pmatrix{2\\5}$ and please note how I represent those as vectors and not line matrices, then everything seems to work fine with your method:

Hill's cipher translates into: $$\pmatrix{k_{11}&k_{12}\\k_{21}&k_{22}}\times x_1 \equiv y_1 \mod 26$$ $$\pmatrix{k_{11}&k_{12}\\k_{21}&k_{22}}\times x_2 \equiv y_2 \mod 26$$

This leads to the system you are solving (but you may also represent it using 4 equations) and you get: $$\begin{cases}5k_{11}+17k_{12} &= 15\\ 5k_{21}+17k_{22} &= 16\\ 8k_{11}+3k_{12} &= 2\\ 8k_{21}+3k_{22} &= 5\end{cases}$$ Which correspond, once represented using matrices, to solving: $$\pmatrix{5&17 \\ 8&3} \times \pmatrix{k_{11}\\k_{12}} \equiv \pmatrix{15\\2} \mod 26$$ $$\pmatrix{5&17 \\ 8&3} \times \pmatrix{k_{21}\\k_{22}} \equiv \pmatrix{16\\5} \mod 26$$ Since you have computed it, you know that $$X^{-1} \equiv \pmatrix{9&1 \\2&15 \\} \mod 26$$ for $X=\pmatrix{5&17 \\8&3 \\} $.

But now, this is where it seems to me that you are doing something wrong: to get the key, you can simply solve the above equations by left-multiplying by $X^{-1}$ so that: $$ \pmatrix{k_{11}\\k_{12}} \equiv X^{-1}\times X\times \pmatrix{k_{11}\\k_{12}} \equiv X^{-1}\times y_1\equiv \pmatrix{9&1 \\ 2&15} \times \pmatrix{15\\2}\mod 26$$ and the same holds for $X^{-1}\times y_2$: $$ \pmatrix{k_{21}\\k_{22}} \equiv X^{-1}\times X\times \pmatrix{k_{21}\\k_{22}} \equiv X^{-1}\times y_2\equiv \pmatrix{9&1 \\ 2&15} \times \pmatrix{16\\5}\mod 26$$ and you end up with the key which seems to be, after computing the latest results: $$\begin{cases}k_{11}=7\\ k_{12}=8 \\k_{21}=19\\k_{22}=3\end{cases}$$ And which translates into $$K=\pmatrix{7&8\\19&3}$$ And you can check that $ay$ get encrypted into $ku$ $$ K \times \pmatrix{0\\24}\equiv \pmatrix{10\\20} \mod 26$$ But to decrypt anything, you'll need to invert the key to get: $$K^{-1}=\frac{1}{det(K)}\pmatrix{3&-8\\-19&7}\equiv 25 \pmatrix{3&-8\\-19&7} \equiv \pmatrix{23&8\\19&19} \mod 26$$ And so you can decode the $fr$ from the $pq$ by: $K^{-1}\times \pmatrix{15\\16} \equiv \pmatrix{5\\17} \mod 26$ which checks out.

This is because decoding Hill's cipher necessitate to left-multiply the cipher by the inverse of the key.

$\endgroup$
  • $\begingroup$ Thanks for the answer. Tomorrow morning I'll check it out and let you know. $\endgroup$ – AndreaM16 Jan 22 '17 at 22:20
  • $\begingroup$ I think you made an error on the four equations system: $5k_{11}+3k_{12}=2$ and $5k_{21}+3k_{22}=5$ should be $8k_{11}+3k_{12}=2$ and $8k_{21}+3k_{22}=5$. Also, I don't understand how you got $25$ from $\frac{1}{det(K)}$ since $det(K) = -131$. I'll be thankful if you explain me how. $\endgroup$ – AndreaM16 Jan 23 '17 at 9:36
  • $\begingroup$ My, I should never copy-paste anything. I did, indeed. To obtain $25$ from $\frac{1}{det(K)}$, keep in mind we are inverting it modulo $26$, so basically I have $det(K) = -131 \equiv 25 \mod 26$ and the modular inverse of $25$ is $25$. $\endgroup$ – Lery Jan 23 '17 at 18:34
  • $\begingroup$ Uhm, $-131 \mod26$ gives me $1$, that's why I don't get it. $\endgroup$ – AndreaM16 Jan 23 '17 at 18:50
  • 1
    $\begingroup$ Well $-131=-26*5-1 = 0-1=-1 \equiv 25 \mod 26$ $\endgroup$ – Lery Jan 23 '17 at 20:29

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.