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$.
$\begingroup$
$\endgroup$
7
-
$\begingroup$ 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? $\endgroup$– B-ConSep 10, 2012 at 16:50
-
$\begingroup$ 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). $\endgroup$– maya-bfSep 10, 2012 at 17:42
-
1$\begingroup$ 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. $\endgroup$– ponchoSep 10, 2012 at 18:03
-
$\begingroup$ Thank you @poncho I've just found that few seconds ago. Is it possible to find another key to solve the problem? $\endgroup$– maya-bfSep 10, 2012 at 18:11
-
$\begingroup$ 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. $\endgroup$– ponchoSep 10, 2012 at 18:28
|
Show 2 more comments
1 Answer
$\begingroup$
$\endgroup$
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.
