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.

  • 1
    $\begingroup$ Try to find another equation that doesn't produces a number that is not relatively prime. $\endgroup$ – kelalaka Mar 7 at 13:37
  • $\begingroup$ @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? $\endgroup$ – Mohamed Moustafa Mar 7 at 13:46
  • $\begingroup$ How can I find the answer without knowledge of the data. You can write your answer, too. I'll upvote. $\endgroup$ – kelalaka Mar 7 at 13:48
  • 3
    $\begingroup$ Does this answer your question? Affine Cipher Cryptanalysis another Affine plaintext attack with GCD != 1, another Decryption using affine cipher $\endgroup$ – kelalaka 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.


Not the answer you're looking for? Browse other questions tagged or ask your own question.