Invertible matrices and encryption

[Minecrazy]

First off, I apologize if I'm in the wrong thread. I wasn't really sure where to put this.

Alright, long winded question so stay with me (note: the actual question is at the end, so if you already know how to work it out, just skip ahead)! I was reading a math problem at the nsa.gov website ( http://www.nsa.gov/academia/_files/collected_learning/high_school/algebra/matrices_secret_weapon.pdf ) and they had a problem they worked out under Teacher Aid #9. First they encode a message, and that's cool. In the second half, they try to decipher the encrypted message using the inverse of the cypher.

In the page, they define it as the cipher text matrix multiplied by the decoding matrix (where the decoding matrix is the inverse of the coding matrix). Let's say the cipher text matrix is and the decoding matrix is [C]. If I multiply x[C], I get NOTHING. This isn't something that even works in my calculator. If I multiply [C]x, I get the wrong answer.

Let's take a step back. Before they did that, they multiplied what they defined as the plain text matrix (We'll define this as [D]) by what they defined as the coding matrix (We'll define this as [E]). The result of which I'll define as [F]. So [E]x[D]=[F].

So the decoding matrix, [C], is the inverse of the [E]. If I do x[E], I don't get anything useful. I'm convinced their math is wrong. If I run [E]x, I get something useless. If I run [E]x[F], I get my answer, the plain text matrix again ( [D] ).

They do a function to [F] where they run it through ((fPart([F]x(1/29)))x29 ---- The result of which they define as [A] (which we will also use -- I didn't forget the A!).

(Again, the base problem is found at ( http://www.nsa.gov/academia/_files/collected_learning/high_school/algebra/matrices_secret_weapon.pdf ) under the Teacher Aid #9 section: Polygraphic Systems )

So my question is, how do I get from [A] to [F]? How do I "reverse" what was done with the operation "((fPart([F]x(1/29)))x29" to get BACK from [A] to [F] so that I could, potentially, decrypt a message if I were only given "EYP?UQEDODRIFPU" and the inverse of the coding matrix? They're obviously missing a step.

Thanks in advance...

 

[Jameson]

Re: Trigraphing/Cryptology/Matrices/fPart(/THENSA?

Hi Minecrazy,

Welcome to MHB! :)

This isn't my area of expertise but I think I can comment on the linear algebra some. It sounds like you're fine with the encoding process but have issues with the decoding part. If we use the example in the PDF file you linked to then the cipher test matrix is a $5 \times 3$ matrix that was calculated from multiplying two other matrices and then taking all entries mod 29.

If we call $B$ the cipher test matrix and $C$ the decoding matrix (which is the inverse of the encoding matrix), then $B$ is a $5 \times 3$ matrix and $C$ is a $3 \times 3$ matrix. From the dimensions alone we can see the proper way to multiply these.

What happens when you calculate $BC$? You should get a result even if it's wrong. If you're not getting an answer then I'm guessing it's an input error or something with the calculator. Can you show us your work so we can better understand where you're at? I know this doesn't answer the questions you posed at the end of your post but when one is stuck on a problem, it's good to go back over the steps that led to the confusion.

Also, I don't understand this part of your logic:

So the decoding matrix, [C], is the inverse of the [E]. If I do x[E], I don't get anything useful.

Using the matrix names you listed, $B$ is our encrypted text that is stored in a matrix and $E$ is the inverse of $C$. However, why would you multiply the encrypted matrix by the encoding again. You need to multiply by $C$ which is $E^{-1}$.

 

[chisigma]

First off, I apologize if I'm in the wrong thread. I wasn't really sure where to put this.

Alright, long winded question so stay with me (note: the actual question is at the end, so if you already know how to work it out, just skip ahead)! I was reading a math problem at the nsa.gov website ( http://www.nsa.gov/academia/_files/collected_learning/high_school/algebra/matrices_secret_weapon.pdf ) and they had a problem they worked out under Teacher Aid #9. First they encode a message, and that's cool. In the second half, they try to decipher the encrypted message using the inverse of the cypher.

In the page, they define it as the cipher text matrix multiplied by the decoding matrix (where the decoding matrix is the inverse of the coding matrix). Let's say the cipher text matrix is and the decoding matrix is [C]. If I multiply x[C], I get NOTHING. This isn't something that even works in my calculator. If I multiply [C]x, I get the wrong answer.

Let's take a step back. Before they did that, they multiplied what they defined as the plain text matrix (We'll define this as [D]) by what they defined as the coding matrix (We'll define this as [E]). The result of which I'll define as [F]. So [E]x[D]=[F].

So the decoding matrix, [C], is the inverse of the [E]. If I do x[E], I don't get anything useful. I'm convinced their math is wrong. If I run [E]x, I get something useless. If I run [E]x[F], I get my answer, the plain text matrix again ( [D] ).

They do a function to [F] where they run it through ((fPart([F]x(1/29)))x29 ---- The result of which they define as [A] (which we will also use -- I didn't forget the A!).

(Again, the base problem is found at ( http://www.nsa.gov/academia/_files/collected_learning/high_school/algebra/matrices_secret_weapon.pdf ) under the Teacher Aid #9 section: Polygraphic Systems )

So my question is, how do I get from [A] to [F]? How do I "reverse" what was done with the operation "((fPart([F]x(1/29)))x29" to get BACK from [A] to [F] so that I could, potentially, decrypt a message if I were only given "EYP?UQEDODRIFPU" and the inverse of the coding matrix? They're obviously missing a step.

Thanks in advance...

Wellcome on MHB Minecrazy!...

First You surely knows that what is made known by 'No Such Agency' ['the Agency that doesn't exist' (Devil) ...] cannot be very 'understandable'... second what the 'teacher' didn't say is that all the computations have to be performed $\text{mod}\ 29$ and not with ordinary arithmetic!...

That means that You have to choose as coding matrix not a simple non singular matrix made of integers, but a non singular matrix such that it and its inverse are made of integers [and to find such a matrix is a non trivial task if n is 'large'(Thinking)...] and all the computation are to be performed $\text{mod}\ 29$ (Blush)...Kind regards $\chi$ $\sigma$