# Solving Vigenère Encryption

I'm trying to crack a cypher that I believe is Vigenère encrypted and I'm currently stuck.

I calculated the key length by finding repeated sequences in the cypher and calculating the the common factors.

Word    distance factors
agzd    16       2,4,8,16
zna     92       2,4,23,46,92
zdc     54       2,3,6,9,18,27,54
csio    44       2,4,11,22,44
omy     46       2,23,46
zab     5        5


I assume the key-length is 4 as these are the once that are common factors, but from here on trying to map the correct caesar shiffre for each position I'm stuck.

Can somebody confirm that my key-length calculation has no errors which would explain why I can't solve the cypher.

Here is the cypher:

jD 2GSA 7HNA ZNA w.m. V7KXA 36HBM MKE5 /H SGP9 +R GKKJ 2I A4OTC KDBCUR. 19+R 8Y TKJ JG4 IGO6 6U4T OJ hH/BIK. 196 qFKT+9 BNJK ZD6+Q AGZD. kJ'R EaOP6 4NCR ZK 36 / AGZD6C/HOIE2D. x0ZNAC2S8IO8DI HB xX8D4D 0XK O66M 0Y MN62S 8TZABBD2Za8BI. lBJ HA+DF 6UU/ 2J /FOZDC6S8I OJ kDC8G OO 2BLCYZ O66M 0Y G 925F4 UL J2JHCTGH FHH3K

• yes pretty sure, it could be one of the following: caesar,vignere or base64 aes, It does not look like aes, and I've tried all 26 possibilities of caesar so I'm left with vignere. – vignere_solve Apr 23 '14 at 6:53

First, you should start by guessing which symbols in the ciphertext are actually enciphered, and which are simply written in plain. (Don't worry if you guess wrong, you can always make several guesses.) For a Vigenère cipher, one also needs to guess whether any non-encrypted characters should advance the key position or not (usually they do not).

For your example ciphertext, it seems likely that spaces, and probably also periods, commas and apostrophes are written in plain — they occur at places where they would in natural English text. On the other hand, the letters are certainly in cipher, and so are most likely the numbers and the plus signs and slashes too, since they seem to be scattered randomly among the words.

(A curious feature to note at this point is that the lowercase letters in the ciphertext seem to occur at places where an uppercase letter would be plausible in plain English text. This suggests that letter case may simply be trivially flipped.)

The next step I'd suggest, after initially guessing the cipher alphabet, is to compute the index of coincidence for various key lengths. In particular, if you do that for various choices of ciphertext alphabet, you'll notice that, for the alphabet consisting of letters (ignoring case), numbers, + and /, the plot of IoC (scaled here for an assumed plaintext alphabet of 26 letters) as a function of key length looks pretty striking:

 1: 0.826  ################
2: 0.816  ################
3: 0.825  ################
4: 0.781  ###############
5: 0.867  #################
6: 0.847  ################
7: 1.822  ####################################
8: 0.778  ###############
9: 0.771  ###############
10: 0.860  #################
11: 0.816  ################
12: 0.743  ##############
13: 0.786  ###############
14: 1.812  ####################################
15: 0.791  ###############
16: 0.640  ############
17: 0.803  ################
18: 0.693  #############
19: 0.734  ##############
20: 0.671  #############
21: 1.985  #######################################
22: 0.745  ##############
23: 0.840  ################
24: 0.766  ###############
25: 0.688  #############
26: 0.672  #############
27: 0.567  ###########
28: 1.669  #################################
29: 0.786  ###############
30: 0.777  ###############


Notice the sharp peaks at multiples of 7, strongly suggesting that the key is seven characters long. In particular, the IoC for those values is close to 1.7, which is considered a typical value for English text.

So let's see what happens if we assume that the key is seven characters long. We'll write down the ciphertext in seven-character blocks (omitting spaces and punctuation) and print out the character histogram of each column:

Column 1:                                 Column 2:
|
|
|            |                     |
|      |     |                     |                 |
|       |    | |   |||                     |             |   |     |   ||
|   | |||    | |   |||                     |             | | |   |||  |||
|   | |||    |||   |||  |                  |          |||| |||   |||  ||| || |
3   2 227    314   335  1                  5          1113 214   223  233 11 1
+/0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ    +/0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ

Column 3:                                 Column 4:

|                                                     |
|   |   |  ||                                             | | |             |
|   |   | |||                                             | | |   |    ||   ||
| | |   | |||  | |                                        | | |   |    ||  |||
| ||| ||| ||| |||| |                                |     | ||| | |  ||||  |||
4 214 115 344 1212 1                                1     4 415 1 3  1133  243
+/0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ    +/0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ

Column 5:                                 Column 6:
|
|                |
|          |                |
|       |          |                |  |     |    |
|   |   |    |     |              | |  |     ||   |
|   | |||    |   | |       |      | |  |     ||   ||
|     ||| |||||  ||||  | |    || |      ||| |||  | ||  |||
1     411 31225  1131  2 7    11 2      316 141  1 43  142
+/0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ    +/0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ

Column 7:
|
|   |
|   |
|   |  |
|   |  |          |
||  |  | |||      |
|   ||  || | ||||| | ||           |
1   62  71 4 22211 1 13           1
+/0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ


The first remarkable feature to note is that, even though the cipher alphabet has 26 + 10 + 2 = 38 characters, none of the columns features even half that many character. This is quite plausible, assuming that the plaintext mostly consists of letters, and keeping in mind that the English letter frequency distribution is quite skewed.

Also, the numbers seem to mostly appear in the columns whose letters are mostly from the beginning of the alphabet, suggesting that they may indeed be sorted before the letters in the cipher alphabet. (It's not so clear where the + and / characters should belong, but we can try to figure that out later.)

Finally, looking at the letter frequencies within each column, we may note some distinctive peaks. For example, in column 5 (which, conveniently, has only letters), the most common characters are G, K, O, T and Z. Shift those six places back in the alphabet, and you get A, E, I, N and T — five of the most common letters in English (only O is missing from the top six). This gives us a pretty good guess for one key value out of seven already.

Can you finish the decoding from here?

(Ps. I haven't, so my apologies if it turns out I've led you down a false trail. But I'm pretty sure I haven't.)

Pps. I did eventually solve this puzzle, and it turns out that one of the early assumptions I made above was wrong. However, you can still decode most of the text despite the wrong assumption, and, once you do, it's not hard to figure out what the mistake is.

Specifically, I was wrong about letter case being simply flipped. Instead, the correct cipher alphabet has 64 characters: AZ, az, 09, + and /, in this order. (This is, in fact, the same alphabet as used for base64 encoding.) It just happens that, with this particular alphabet and key, most lowercase letters are encrypted to uppercase ones, and vice versa.

• thank you for your effort, I'm a bit busy right now but I hope I can have a look at it soon :) – vignere_solve Apr 23 '14 at 8:45
• Hi, with you hints I was able to get a little further but something does not seem right. I'm currently at the following key: "48,1,10,32,32,4,8" And the text is slowly starting to look like english text: Examples: "CAME FROK THE 2.W. WHERE..." or "IN SNDIA IS ALMMST SEGN AS A" But it seems that if I "turn" it on one side, another part of the text always gets scrambled, I'm thinking that maybe the keylength is not correct, a little hint would be great :) – vignere_solve Apr 24 '14 at 21:00
• trying a key-length of 14 almost gets me there but I'm still thinking I'm missing something. – vignere_solve Apr 24 '14 at 21:16