Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

I'm trying to decrypt a message encrypted with Hill Cipher, but I don't understand how to find the determinant so it solves the equation $det * 1/det = 1 mod 26$.

The determinant for my key matrix is $62$.

share|improve this question

migrated from security.stackexchange.com Sep 10 '12 at 15:46

This question came from our site for Information security professionals.

    
I'm not sure what you're asking. It sounds like you already have the determinate, so you don't need to find it. Do you have the key matrix (used for encryption) and are trying to derive the corresponding decryption key matrix? Or are you trying to find the key matrix just using the determinate? –  B-Con Sep 10 '12 at 16:50
    
I have the key matrix and I need to find the plaintext. So I need to calculate the inverse of K. For that I have to solve this equation K × K^(-1) = I (mod 26) I have the determinant but the inverse should be calculated in the way that d × d^(-1) = 1 (mod 26). I don't know how to find d^(-1). –  maya-bf Sep 10 '12 at 17:42
1  
One problem is that 62 doesn't have an multiplicative inverse modulo 26; there is no integer K such that 62K = 1 (mod 26). That is because both 62 and 26 have two as a factor, and so 62K (mod 26) will also have two as a factor. –  poncho Sep 10 '12 at 18:03
    
Thank you @poncho I've just found that few seconds ago. Is it possible to find another key to solve the problem? –  maya-bf Sep 10 '12 at 18:11
    
Well, no, not if the discriminant is 62. One requirement that the Hill Cipher makes is that the discriminant be relatively prime to the alphabet size (in this case, 26). 62 and 26 are not relatively prime, and hence there will be multiple distinct plaintexts that will encrypt to the same ciphertext, and hence you cannot uniquely determine the plaintext from the ciphertext. –  poncho Sep 10 '12 at 18:28
show 2 more comments

1 Answer 1

up vote 3 down vote accepted

Maybe the impossibility of solving the equation system uniquely was meant to strengthen the cipher. :D If everything was done correctly, there'll be multiple solutions. When you have some idea of how the plaintext may look like, it should be easy to determine it uniquely.

During the computation you have to divide something by 62 modulo 26, which is (as already stated) impossible. However, the nominator will always be even, and for any $a$, finding a solution to

$$62 * x \equiv 2a \pmod{26}$$

is as easy as finding the unique (mod 13) solution to

$$31 * x \equiv a \pmod{13}$$

Just note that for each $x$ also $x' = x+13$ solves the original equation.

share|improve this answer
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.