I'm trying to create a hill cipher utility. One feature I want is to be able to compute the key if you have the plaintext and ciphertext.

$C$ = ciphertext matrix ($2\times 2$), $P$ = plaintext matrix $\left(2\times\frac{N}{2}\right)$, $K$ = key ($2\times 2$).

$$PK = C$$

So if I have $C$ and $P$, then $K = P^{-1}C$. How do I best find $P^{-1}$?

EDIT: It is important to note that this is all mod $26$. Sorry.

  • 1
    $\begingroup$ See also this related question on StackOverflow. $\endgroup$ – Douglas S. Stones Oct 5 '12 at 2:16

You could use the direct formula for $2 \times 2$:

$$ \pmatrix{a & b\\ c & d}^{-1} = \dfrac{1}{ad-bc}\pmatrix{d & -b\\-c & a}$$

  • $\begingroup$ The problem is that doesn't work out in with the modular. I don't know how to format this nicely, sorry. but lets say our plaintext is b,a,z,z. {{b,a}, {z,z}} = {{1,0}, {25,25}} then if we try multiplying by 1/(ad-ab) we get a fraction. That doesn't work when you are working with only discrete values. Sorry if I was not clear enough. $\endgroup$ – Alan Oct 5 '12 at 1:55
  • 1
    $\begingroup$ Yes, it would have to be the modular inverse, the extended gcd algorithm would be one way to do it. In your example, 25 is its own inverse, another example is $3^{-1} \equiv 9 (mod 26)$ since $3 \times 9 = 27 \equiv 1 (mod 26)$ $\endgroup$ – adam W Oct 5 '12 at 2:09
  • $\begingroup$ Okay, I think I got it. So {{1,0},{25,25}}^(-1) actually works out to {{1,0},{25,25}}, right? $\endgroup$ – Alan Oct 5 '12 at 2:15
  • $\begingroup$ Yes! Also, consider that $2$ and $13$ and any multiples (basically just even numbers and the number $13$) do not have modular inverses. $\endgroup$ – adam W Oct 5 '12 at 2:19

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.