Linear Algebra Applications: Cryptography

[aero_zeppelin]

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

Homework Statement

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.

The Attempt at a Solution

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

Thanks!

 

[Mark44]

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

Homework Statement

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.

The Attempt at a Solution

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

Thanks!

Aren't these two operations inverses of one another?

 

[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

 

[Mark44]

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.

 

[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!

 

[Mark44]

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

 

[vela]

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.

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?

 

[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

 

[aero_zeppelin]

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

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