# Affine Cipher: what to do if the number isnt invertible over mod n? [duplicate]

I am currently solving a simple cryptanalysis problem where I need to decrypt a text file using frequency analysis. The text has been encrypted using an affine cipher over a 68 character alphabet which includes lower and upper case English letters, digits from 0 to 1, as well as those characters: ". , ; : _ \n" where _ denotes space.

Going over the frequency histogram of the text, the most frequent character is "," followed by "z". According to what I know, the most frequent character for the 68 character alphabet is space followed by "e".

Thus I end up with those two equations:

$$66a + b = 63 \bmod 68$$

$$4a + b = 25 \bmod 68$$

Which gives me:

$$62a = 38 \bmod 68$$

$$a = 38 \cdot 62^{-1} \bmod 68$$

However, 62 isn't invertible mod 68. I am quite new to cryptography so I am quite unsure if there is some method to solve this issue.

• Try to find another equation that doesn't produces a number that is not relatively prime. Mar 7 at 13:37
• @kelalaka thank you. I actually did this and managed to find the key (5,5). Can you write this as an answer so I can close the question? Mar 7 at 13:46
• How can I find the answer without knowledge of the data. You can write your answer, too. I'll upvote. Mar 7 at 13:48
• Does this answer your question? Affine Cipher Cryptanalysis another Affine plaintext attack with GCD != 1, another Decryption using affine cipher Mar 7 at 14:03

If you divide the whole equation throughly 2 you get $$31a\equiv 19\pmod {34}$$ which you can solve to get $$a\equiv 5\pmod{34}$$. This then gives two possibilities for $$a\pmod {68}$$: either 5 or 39. For these two possibilities you can then find the corresponding $$b$$ (it turns out to be 5 in both cases) and check which solution works.