Cryptanalysis Time!

Question

In the past, I've made some simple ciphers as part of larger riddles, and sometimes this has lead to puzzles coming undone in the middle. So all of you who enjoy trying to crack cryptograms with analytic techniques, here's one just for you!! Can you determine both the key used to encrypt and the original message (it will be in English) encrypted from the following ciphertext?

u axft rpalg tymh dytyaiju nffvlag tmb knrd ys, l'ie ymr pbmvzhv bf gmfdaozm oqq emqb bbu tmb qbw jqbvr tymh.

I will accept the answer that provides the key, original message, and steps for solving. If you use a program or tool to do part of it (this is not necessary, all steps can be done by hand.), that's fine, but you have to be able to explain what the tool is doing and how it determines the results. Good luck!

HINT:

First step should be determining the method of encryption. You already know enough to narrow in on this.

P.S.:
GentlePurpleRain has cracked the code, and has a detailed explanation below, but if you had success with another method, please feel free to contribute, I'd be very interested in hearing other approaches/techniques. This also helps me and others improve future cryptograms.

Answer 1

A cipher with a key immediately makes me think of a Vigenere cipher, which is probably the most common cipher employing a key.

The way a Vigenere cipher works is much like a typical Caesar cipher (which just shifts all letters a certain number of places in the alphabet), but it also employs a key, which allows each letter to be shifted a different number of places in the alphabet.

For example, if your key is SECRET and you want to encrypt the message THE MISSION STARTS AT NOON, you would assign a number to each letter of the key (A=0, B=1, etc.). Then you would shift each letter of your message that number of characters.

THE MISSION STARTS AT NOON
SEC RETSECR ETSECR ET SECR

Now T is 19 and S is 18, so we add $19 + 18 = 37$.
37 is more than 25 (= Z), so we need to "wrap around", which is the same as subtracting 26 from our result. $37-26 = 11$ = L, so the first letter of our encryption is L.

By following the same method, the second letter would be encrypted as $7 + 4 = 11$ = L, and the third as $4 + 2 = 6$ = G.

You can see that even though the first three letters of the plaintext are different (THE), two of them encrypt to the same letter (L). This makes a Vigenere cipher much harder to crack than a Caesar cipher, because a given character in the ciphertext doesn't represent the same character in the plaintext each time it appears. This also means that frequency analysis is useless, since the most frequent letter in the ciphertext might represent six different letters in the plaintext, none of which are particularly frequent.

There are still weaknesses, though. As the text gets longer, it's more likely that common words (the, and, a, etc.) will end up being encrypted by the same section of the key, and will thus end up encrypted as the same sequence of letters. By analyzing the ciphertext, we can pick out certain letter sequences that repeat multiple times. By looking at the spacing between them, we can guess at how long the key is. For example, if a certain sequence appears at positions 65, 89, 105, and 121, we might guess that the key is of length 8, because all of the distances between those numbers are divisible by 8 (24, 16, 16).

Knowing the length of the key can be very helpful, because it lets us know which parts of the message were encrypted using the same letter of the key. In a long-enough message, we can look at those letters and actually do a frequency analysis of just the letters encrypted by a single character of the key. Since they were all encrypted the same way, the more-frequent letters will probably map to the more-frequent English letters, and from that point we can make some intelligent guesses about what some words might be.

There are many online tools that can help with this kind of thing. Some try to offer a one-stop solution, which determines key length, finds the key, and decrypts the ciphertext without any input from you. These tend to be mediochre at best. Other tools will help you with one aspect of the problem. I used this tool (the FIND KEY LENGTH button) to help me determine the key length. It gave me a very high likelihood that the key was 6 characters long.

I then used this tool to do a frequency analysis based on the key length. Basically, it took the characters at position 1, 7, 13, 19, etc. (6 apart), and looked at which letters were most common. It then took the most common English letter, and determined the difference between them. It assumed that was the first letter of the key. Then it did the same with characters at positions 2, 8, 14, 20, 26, etc., and so on.

I anticipated that it would not find the exact solution, but hoped it would be able to fill in enough that I could guess what was missing.

Looking at the second suggestion it spit out, I got a key of IOXNAR and a plaintext that included the phrase NOXHONG CEN NARM QE. I thought this looked a lot like English, and guessed that it might be NOTHING CAN HARM ME. Looking at the incorrect letters, they were all at position 1 or 3 of the key, so it looked like my key was correct except for the first and third characters: 'xOxNAR`.

I did the math to figure out what letter would be required to get a plaintext of NOTHING CAN HARM ME, and determined that the first character of the key was M and the third was D, making the key MODNAR. Looks nonsensical at first, until you realize that it is simply the word RANDOM backwards!

Using that key to decipher the whole message, I got
I MUST ADMIT THAT ALTHOUGH NOTHING CAN HARM ME, I'VE HAD MOMENTS OF PARANOIA AND EVEN YOU CAN NOW SENSE THAT.

Afterward, I looked a little further through the tool's results, and realized that it had actually found the solution, at attempt #42.

Answer 2

I wanted to contribute my own approach to solving this (I had someone else choose the message and key). Note that GentlePurpleRain has the accepted answer to this question, I'm providing my own answer for academic reasons only so be sure and +1 his answer!

First I wanted to track down the key length, to limit the options of key. I noticed two repeated words, 'tmb' and 'tymh', which repeat after 42 and 72 letters respectively. This means our key length must be a factor of both of these numbers, giving us the options of 1,2,3, and 6 letters. Length 1 was easy enough to rule out, since that is just a Ceasar cipher and checking all 26 possibilities was trivial. I strongly suspected it was 3 or 6, and decided to get more information before deciding (though checking for all 2 letter possibilities is also 'feasible', since there are only ~100 letter words and <600 total combinations).

Next I noticed that there was a word of the form x'xx. As far as I could find, the only two contractions that match this form are I'll and I've. So, moving forward with the knowledge that 'l' in cipher = 'i' in message and the location of the 'l', I determined that the letter in the key at that location must have been D. So now, I had that:
*If key length=2, I have 'D-', which reduces to the difficulty of key length=1 was trivial to check via bruteforce.
*If length=3, I have '--D' which reduces to ~50 words/<600 total combinations
*If length=6, I have '--D---' which reduces to ~250 words.
At this point I could have bruteforced all ~300 word possibilities for the key, but had another idea (which was fortunate since as it turned out, the key would not have been found in my dictionary)

Whether the key is 3 or 6, we know that the letters in the 3,9,15,21,etc spot are being encrypted with the letter D. So we go backwards by 3 letters at each of those spots and now the cipher becomes (capitals are letters unencrypted as they appear in original message):

u aUft rpaIg tymh AytyaiGu nffvIag tmb Hnrd ys, I'ie ymr MbmvzhS bf gmfAaozm oNq emqb Ybu tmb Nbw jqbSr tymh.

I first focused on 'AytyaiGu' A regex showed me that only 10 words match that pattern a*****g* and of those, the word 'although' was the most likely candidate (the others being obscure fields or scientific terms). That word is conveniently long enough to give me the entirety of the key based on that guess and after seeing that the key was 'RANDOM' backwards, I was went ahead and plugged the cipher into a simple vigenere decoder tool that takes in a key, provided MODNAR, and out popped the plaintext message. Voila!