Linear Algebra Applications: Cryptography

1. Nov 26, 2011

aero_zeppelin

If any of you guys are seeing or saw this app. for linear algebra in your classes, I could use a hand...

1. The problem statement, all variables and given/known data

A Hill 2-cipher is intercepted that starts with the pairs SL HK
Find the deciphering and enciphering matrices, given that the plaintext is known to start with the word ARMY.

3. The attempt at a solution

I managed to get the deciphering matrix... but how do you get the enciphering one?

Thanks!

2. Nov 27, 2011

Staff: Mentor

Aren't these two operations inverses of one another?

3. Nov 27, 2011

aero_zeppelin

Yes, they are. I tried inverting A^-1 (the deciphering matrix) to get A (the enciphering one), but the book says different.

I got
[7 15 ]
6 5

for the deciphering matrix.

If you invert a matrix by doing
A =
[a b ]
c d

A^-1 =
[d -b ]
-c a

You'd get
[5 -15 ] right?? But the book gives another result.
-6 7

4. Nov 28, 2011

Staff: Mentor

No, that's not what you get. You are omitting a factor in your inverse. The correct formula is
$$A^{-1} = \frac{1}{ad - bc}\begin{bmatrix}d&-b \\ -c&a \end{bmatrix}$$

The fraction is 1/|A|. When you have found the inverse, check your work by multiplying A and A-1. You should get I from this product.

5. Nov 28, 2011

aero_zeppelin

Ok, so if I invert A^-1 I would get A, right?

So, inverting A^-1 =
[7 15 ]
6 5

We get:
1 / -55
x
[5 -15 ]
-6 7

Which product clearly is a fraction...

The book says the result is:
A =
[7 5]
2 15

I don't know what I'm missing here... Thanks for the help btw!

6. Nov 28, 2011

Staff: Mentor

Maybe you made a mistake in figuring out your deciphering matrix. If I work backwards from what you show as the book's answer for A, then A-1 would be
$$\frac{1}{95}\begin{bmatrix} 15& -5\\ -2& 7\end{bmatrix}$$

7. Nov 28, 2011

vela

Staff Emeritus
How'd you get the deciphering matrix?

I find "SL" corresponds to (18, 11), so with your matrix, you would get
$$\begin{pmatrix} 7 & 15 \\ 6 & 5 \end{pmatrix} \begin{pmatrix} 18 \\ 11 \end{pmatrix} = \begin{pmatrix} 291 \\ 163 \end{pmatrix} \equiv \begin{pmatrix} 5 \\ 7 \end{pmatrix} (\text{mod }26)$$which corresponds to "FH", not "AR".

Am I computing this wrong or is your matrix off?

8. Nov 28, 2011

aero_zeppelin

The deciphering matrix is right, my procedure looks fine to me and the result is the same one as in the book hehe, so I don't know what's wrong in the procedure for obtaining A, the enciphering one.

To get the deciphering matrix, you use the "intercepted" plaintext , which in this case is ARMY and put it in a matrix. Then you put the ciphertext, which in this case was given as SL HK and adjoin it to that matrix so you get the form [C l P]

Do elementary row operations (including some weird ones, like replacing numbers by their mod 26 residue) to obtain the form [ I l (A^-1)t ]

Transpose that A^-1 and you obtain the deciphering matrix! Now, to obtain the enciphering one, A ... that's where I'm stuck loll

9. Nov 28, 2011

aero_zeppelin

Well, in this case with cryptography, I think the procedure for obtaining inverses is different.

Given a matrix A, first you obtain det(A). Next you obtain its reciprocal mod 26. You use this reciprocal to do scalar multiplication with your matrix A in its "inverted form":
[d -b]
-c a]

Next, you obtain the residues mod 26 of that matrix to finally obtain A^-1