Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
1  
See also this related question on StackOverflow. –  Douglas S. Stones Oct 5 '12 at 2:16
add comment

1 Answer 1

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}$$

share|improve this answer
    
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. –  Alan Oct 5 '12 at 1:55
1  
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)$ –  adam W Oct 5 '12 at 2:09
    
Okay, I think I got it. So {{1,0},{25,25}}^(-1) actually works out to {{1,0},{25,25}}, right? –  Alan Oct 5 '12 at 2:15
    
Yes! Also, consider that $2$ and $13$ and any multiples (basically just even numbers and the number $13$) do not have modular inverses. –  adam W Oct 5 '12 at 2:19
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.