Can you help me find a cryptanalytic way to attack a simple monoalphabetic substitution cipher algorithm?

Question

I have decided to make a project at uni that requires me to crack a monoalphabetic substitution cipher. The text is an english text with spaces. The key is a permutation of the alphabet. This isn’t some big project and it should be fairly simple to do. So, I am looking for an algorithm (doesnt have to be really fast) that is fairly simple.

I googled a bit and all the proposed algorithms like this answer to “Strategy to crack a presumed substitution cipher” are some genetic ones (i dont want to get into that) or some advanced (I mean not really basic) statistics (like here http://practicalcryptography.com/cryptanalysis/text-characterisation/quadgrams/#a-python-implementation and you need some other files).

Is there some reliable (I assume not so fast way) to crack the cipher with only the knowledge and use of the letter frequences and some list of the most lets say 10k or more english words?

I thought about it for a while and I cannot come up with a good way to make the function to rate the ciphertext (as is used in most of the algorithms). What would be a well-vetted cryptanalytic way to attack a simple monoalphabetic substitution cipher algorithm?

Answer 1

In the absence of clues, I think you might be left with trying to brute force the ciphertext. However there are ~ $26^{26}$ (maybe it's $26!$ which is still a big no) possible permutations of a 26 character alphabet. That's something that would require enormous computing power. Brute forcing then might be impractical.

You mentioned the Key is a permutation of the alphabet, the word key sort of suggests a vigenere cipher and the key length is 26 Scrambled up letters. As a general rule, Keywords are shorter. The longer the Keyword, the tougher the Vigenere cipher is going to be to crack. I'm thinking that a key word consisting of the alphabet scrambled is going to be incredibly difficult.

I'ld question what you mean when you say …The key is a permutation of the alphabet… because as a general rule, university professors set difficult problems – not impossible ones. I'm guessing, with my limited knowledge of the subject that greater clarification is needed.

The other thing you can do is carry out a frequency analysis of the letters in the ciphertext, see if there are clear differences in frequency between some letters and others.

Also look for recurring sequences of letters, the distance between these recurrences in the Vigenere is indicative of the key length. For example, some way in to the ciphertect there may be a three letter sequence like YDS if this occurs later, maybe several times, the distance between those occurences can give away the key length.

So, Three suggestions.

Frequency analysis… Recurring sequences of letters…

Get a second and third opinion from a specialist in Cryptography as I'm merely a beginner and a hobbyist.

Answer 2

Here is one simple solution which worked for me, but it is not direct 'algorithmical' way and requires some manual work before one can apply an algorithm.
Briefly, it consists of 2 steps:

1. Search for the so called 'magic' words/patterns with regular expressions.
2. From the results of 1st step, you'll have the key for some letters: mark these letters as 'discovered' and proceed with a list of specific words containing these letters and other 'unknown' letters.

So each new word found should 'discover' more letters. I was able to decipher any text (relatively big though, ideally at least 1/2 page) with this method.

Note: what are 'magic' patterns? I will not name those, but I'll give a hint: one can find these by observing the search results for sequences with specific letter repetitions. It is easier to do if one finds the space character first, and the space character is the most frequent for any (big enough) normal text.

So to decipher a text one needs only a list with specific words/patterns and deciphering will be complete in amount of step equal to the length of the word list, i.e. ca. 20 iterations.