7
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ Welcome to Cryptography, honzaik! I edited your question, trying to enhance it a bit. In case you dislike my edit, or if you think it doesn’t reflect what you initially asked, or something similar… feel free to revert my edit. $\endgroup$ – e-sushi Feb 25 '17 at 19:29
  • $\begingroup$ If it is monoalphabetic, the relative frequency will be unchanged. Whatever the most common cipher letter is in the text is likely "e" in plaintext. $\endgroup$ – Stone True Feb 27 '17 at 0:00
  • $\begingroup$ i know that. but then you still have 25! possible combinations. still too large $\endgroup$ – honzaik Feb 28 '17 at 15:17
  • 1
    $\begingroup$ @StoneTrue "most common letter is in the text is likely "e"" That is the problem, likely "e" but not necessarily. By experimenting I've seen that distribution of those [etao] letters is quite random for short texts. The only more or less reliable in this sense is the space character. $\endgroup$ – Mikhail V Mar 2 '17 at 20:52
  • $\begingroup$ Look for bigraph frequency - th, it, qu $\endgroup$ – Stone True Mar 3 '17 at 1:21
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ thanks for your response. i dont think i made myself very clear. i know how the cipher is "made". the part of the project is just to encrypt it using a permuted alphabet (key) (so 26! possible keys). and then i should be able to crack it using frequency analysis etc. i just dont want to use very sophisticated methods because that is above the "difficulty level" of this project imo. so im wondering if there is a simple way $\endgroup$ – honzaik Feb 26 '17 at 14:05
  • $\begingroup$ Why do you say it could be a Vigenere cipher? The question specifies that it's a monoalphabetic cipher, which excludes that possibility. $\endgroup$ – Joseph Sible-Reinstate Monica Feb 27 '17 at 4:20
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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