1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Linear Algebra Applications: Cryptography

  1. Nov 26, 2011 #1
    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?

  2. jcsd
  3. Nov 27, 2011 #2


    Staff: Mentor

    Aren't these two operations inverses of one another?
  4. Nov 27, 2011 #3
    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
  5. Nov 28, 2011 #4


    Staff: Mentor

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

    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.
  6. Nov 28, 2011 #5
    Ok, so if I invert A^-1 I would get A, right?

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

    We get:
    1 / -55
    [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!
  7. Nov 28, 2011 #6


    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
    [tex]\frac{1}{95}\begin{bmatrix} 15& -5\\ -2& 7\end{bmatrix}[/tex]
  8. Nov 28, 2011 #7


    User Avatar
    Staff Emeritus
    Science Advisor
    Homework Helper
    Education Advisor

    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)[/tex]which corresponds to "FH", not "AR".

    Am I computing this wrong or is your matrix off?
  9. Nov 28, 2011 #8
    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
  10. Nov 28, 2011 #9

    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
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook