How to decode a (Vigenère?) substitution cipher? [closed]

Question

I am trying to decode a message that I suspect has been encrypted with a Vigenère cipher:

Utl zluuocp zsc rvzu hbcp ztvibfz vrabzz utl ilry. Utlal flal cb fbaiz, qszu zbsciz. Utvu cllihl vhzb dvil v zhbf roarsou vabsci vci vabsci vci vabsci, hoyl v zeli-se rhbry. Qvry rhbzli toz lglz uoptuhg oc kaszuavuobc. Vavwlhhv rhscp ub utl avohocp ub dvocuvoc tla wvhvcrl. Qvry tskkli vci dbjli ubfvai utl wbf ftlal Vavwlhhv zubbi zuvaocp bsu bjla utl wbfzeaou. Vavwlhhv ztojlali vz utl pabse dbjli bc ub utl utabcl. Vavwlhhv, utl toz koazu dvul vci v kbadla wvadvoi bc Ubauspv, hvsptli. Ztl hvg zeavfhli oc v fvg utvu dvil tla hbby hoyl v hode avp ibhh. Utl brlvc fvz zuohh vci zohlcu vpvoc, utl bchg zbsciz tlvai flal utl ralvyocp wbvaiz vci utl zhve bk utl fvjlz vpvoczu ouz tshh. Vavwlhhv tvi zluuhli bcub utl ilry, zouuocp rabzz-hlppli fout tla wvry vpvoczu utl kbaldvzu. Utbzl ufb alvhhg val v evoa bk lxrlhhlcu zvohbaz. Sebc iozrbjlaocp utl laaba Zohjla tvi dvil, Hbsoz nsoryhg tvi utl rbby-rsd zsaplbc-rsd-eoavul ubzzli bjlawbvai. Vci kva corla ub wl vu zlv utvc zravdwhocp kba v raszu oc utl abspt-vci-usdwhl ubfc bk Ubauspv. Qvry utalf toz tlvi wvry vci kbaut jobhlcuhg, uagocp ub ztvyl utl zbsci bsu. Tl rabzzli ub utl avoh ub wluula zll toz dvulz. Tl zusry utl zubcl oc toz ebrylu vz v zflhhocp fvjl tllhli utl ilry. Qvry klhu vz utbspt utl zbcp flal vc lcuoug utvu tvi qszu fbsci ouz fvg vrabzz utl ilry vci fvz cbf tlviocp wvry bsu bjla utl fvula. Vavwlhhv ztojlali vz utl pabse dbjli bc ub utl utabcl. Utoz fvz dsrt wluula utvc uavjlhocp vz v zubfvfvg, vz tl tvi wlkbal. Ou fvz hoyl v zbcp, wsu cbu lxvruhg. Qvry vci utl ralf ilklvuli utl cbubaobsz Rveuvoc Ubaalcuz, ftbzl vcpla fvz ulaaowhl. Qvry nsoryhg qsdeli bsu bk utl fvg, ubeehocp ocub Koumfohhovd. Ftohl tl fvz ealevali kba vcbutla wvuuhl, utlg flal zhvry vci alhvxli. Kvocu ztvibfz flal rvzu sebc utl ozhvci wlhbf: tspl, whvry zvohocp ztoez, zlv dbczulaz, vci butla utocpz utvu tvsculi utl doicoptu fvulaz zlldli ub rvzrvil bjla utl tohhz. Vci utlc, utvu butla zbsci vpvoc -- utl wlvsuoksh, tvscuocp, hbjlhg, dviilcocp zbsci. Koumfohhovd pbu se kabd utl cbf-zhoeelag ilry dbal zhbfhg vci rvalkshhg. Ljlag uodl tl gvcyli ou bcl fvg, ou gvcyli ouzlhk wvry utl butla. Tl cllili ub hoptu utl hvculacz. Vz zbbc vz tl rbshi, tl fbshi koci v doaaba. Koumfohhovd pbu se kabd utl cbf-zhoeelag ilry dbal zhbfhg vci rvalkshhg. Qvry ubby oc v ille walvut, vci utl zvhu voa kohhli tod fout v tveeg kllhocp bk vijlcusal. Qvry tbozuli todzlhk se bcub utl wbf vci zfscp toz hlpz vabsci zb utvu utlg ivcphli bc loutla zoil bk utl wbfzeaou--utl hbcp ebhl utvu lxulcili bsu bjla utl fvula. Tl utbsptu ou doptu dvyl v corl eolrl bk qlflhag: dvgwl v clryhvrl ba zbdlutocp. Kvocu ztvibfz flal rvzu sebc utl ozhvci wlhbf: tspl, whvry zvohocp ztoez, zlv dbczulaz, vci butla utocpz utvu tvsculi utl doicoptu fvulaz zlldli ub rvzrvil bjla utl tohhz. Vavwlhhv, utl toz koazu dvul vci v kbadla wvadvoi bc Ubauspv, hvsptli. Utl ralf veelvali ub wl pluuocp wvry ub ouz cbadvh zlhk, vci utlc, zsiilchg, utl zbsci ocralvzli dvaylihg. Qvry fbshi tvjl utbsptu utlg tvi wllc dgzuorvhhg usacli ocub zuvuslz ok utlg flal cbu lvrt vwzlcuhg, hvcpsbabszhg, vci zohlcuhg rbcuocsocp utloa vruojouolz. Utl gbscp zvohba fvz dvyocp viqszudlcuz ub utl vzuabhvwl.

However, even after watching YouTube tutorials and reading from different websites, it still doesn't make sense to me like the Caesar cipher does. I do understand that the Vigenère cipher alternates between multiple Caesar ciphers, but I just don't understand how to decrypt it with no hints.

Could someone give me some kind of a step by step method for breaking ciphers like this?

Answer 1

This is, in fact, not a Vigenère cipher.

One clue to this is the fact that the ciphertext (which, conveniently, includes unenciphered word breaks) contains lots of repeated words like UTL, VCI, V, UB and QVRY that would be very unlikely to occur by chance in the output of a polyalphabetic cipher like Vigenère.

Another clue can be obtained by examining the letter frequency distribution of the ciphertext: while the letters of the alphabet have obviously been scrambled, sorting the letters by their frequency reveals a very similar distribution as unencrypted English text:

L: 305 #############################################################
V: 248 ##################################################
U: 246 #################################################
B: 175 ###################################
Z: 160 ################################
T: 158 ################################
C: 154 ###############################
A: 142 ############################
O: 140 ############################
H: 131 ##########################
I: 121 ########################
S:  77 ###############
R:  72 ##############
F:  63 #############
P:  63 #############
D:  49 ##########
Y:  42 ########
G:  41 ########
W:  41 ########
K:  39 ########
E:  37 #######
J:  22 ####
Q:  14 ###
X:   4 #
M:   3 #
N:   2

Both of these clues suggest that we're probably dealing with a basic monoalphabetic substitution cipher.

So, how do we break a cipher like this?

One way to get started is to guess that the three most common letters in the ciphertext (L, V and U) most likely correspond to the three most common English letters (E, T and A) in some order.

One of those letters, V, occurs several times in the ciphertext as a single-letter word (in fact, it's the only letter that occurs so). The most common single-letter word in English is the indefinite article "a", so we might guess that the ciphertext letter V probably corresponds to the plaintext letter A.

Meanwhile, the other two most common letters, L and U, occur together in the most common word in the ciphertext, UTL. As the most common word in English is the definite article "the", and as we've already guessed that L and U probably correspond to E and T (since V is A), it seems very likely that UTL in fact means "the".

This already gives us the following partial cipher alphabet:

plaintext:   abcdefghijklmnopqrstuvwxyz
ciphertext:  V   L  T           U

We might even go out on a limb, and guess that the very common three-letter ciphertext word VCI, which starts with the known plaintext letter A, might correspond to the common three-letter conjunction "and". But at this point, it's probably a good idea to just try to decode some of the ciphertext using the partial alphabet we've guessed, just to see if it looks reasonable. Doing this, we get something like:

the ZettOnP ZSn RaZt HBnP ZhadBFZ aRABZZ the deRY. theAe FeAe nB FBAdZ, QSZt ZBSndZ. that needHe aHZB Dade a ZHBF ROARSOt aABSnd and aABSnd and aABSnd, ...

(Here, the uppercase letters are still undecrypted, while the lowercase ones have been decrypted according to our partial cipher alphabet.)

At this point, we can just start guessing at the partially decrypted words. For example, "theAe" is probably "there", so A would be R, and "needHe" might be "needle", making H correspond to L, and so on.

Continuing in this manner (and occasionally checking to see if the resulting partial decryption still makes sense), it should be possible to work out the complete cipher alphabet. I'll leave completing this task as an exercise, since that's what this is presumably meant to be. I did verify, though, that it is indeed possible to decrypt the entire message in this manner, and that the guesses I've made above for the decryptions of various ciphertext letters are, in fact, correct. (Note that this will not always be the case in general; sometimes, you do need to backtrack and try different guesses if it turns out that the decrypted message makes no sense after all.)

Answer 2

Pre requisite : understand how Vigenère cipher works (basically it is a Cesar cipher where the key change at each character).

Breaking a Vigenère Cipher text is decomposed into 3 steps :

1. Find the key length possibles lengths by observing occurrences.

2. Frequency analysis to retrieve the key.

3. Breaking the cipher text.

---

Find the key length possibles lengths by observing occurrences.

I will go in details for the firsts parts as the rest is similar to breaking a Cesar cipher.

The idea is to observe occurrences, a divisor of the distance between them is likely to be the length of the key.

I'll will use the following example to give you a hint of how this works :

Utl zluuocp zsc rvzu hbcp ztvibfz vrabzz utl ilry. Utlal flal cb fbaiz, qszu zbsciz. Utvu cllihl vhzb dvil v zhbf roarsou vabsci vci vabsci vci vabsci, hoyl v zeli-se rhbry.

The first thing you must see is that all the sentences start with Utl, the use of spaces helps a lot, the probability it matches The is quite big. (This gives you a big hint of what might be the 3 first substitutions used by the key).

Because we have space and punctuation, the questions that you have to ask yourself is : Do the spaces, comma and dots count in the key rotation ? Do the key start at each sentence beginning (unlikely but that might be a possibility).

1. Suppose that punctuation does not count and Key does not restart. If we remove spaces et al and observe the occurrences : the distance between the Utl first is 41, a prime number. Hence the key must be 41 character long in that case. If we observe the second occurrence of Ut, the distance is only 26 whose divisor are 2; 13 and 26. Unlikely.

2. Suppose that punctuation does count and Key does not restart. If we count them, the distance between Utl is 51 whose divisors are : 3; 17 and 51. If we observe the second occurrence of Ut, the distance is only 33 whose divisor are 3; 11 and 33. Therefore because 3 is a common divisor, it is likely to be the key length. We can also observe the sequence : vabsci vci vabsci vci vabsci. The distance between the vabsci is 11, which is prime, therefore the key length is 11. Contradiction

3. Suppose that punctuation does not count and Key does restart. We can also observe the sequence : vabscivcivabscivcivabsci. The distance between the vabsci is 9, whose divisor are 3 and 9. The distance between the civ is 3. Therefore it is likely that the key length is 3 (or 9). In this case.

4. Suppose that punctuation does count and Key does restart. We can also observe the sequence : vabsci vci vabsci vci vabsci. The distance between the vabsci is 11, which is prime, therefore the key length is 11. The difference between the vci is also 11. Which would confirm the idea.

To sum up we have the following possibilities :

• Key does restart, punctuation off : 3 ; 9.
• Key does restart, punctuation on : 11.

Remark: in the event where there would not be punctuation in the cipher text, it would be simpler as we would not have to consider such cases and just be under the 3rd assumption.

---

Frequency analysis to retrieve the key.

Lets assume : Key does restart, no punctuation and key length is 3. Therefore we can separate the cipher into 3 blocks (because key length is supposed 3), here for the first sentence :

Cipher text : Utlzluuocpzscrvzuhbcpztvibfzvrabzzutlilry
  1st subst : U  z  u  p  c  z  b  z  i  z  a  z  l  r
  2nd subst :  t  l  o  z  r  u  c  t  b  v  b  u  i  y
  3rd subst :   l  u  c  s  v  h  p  v  f  r  z  t  l

Therefore character of a list ($1^{st}, 2^{nd} or 3^{rd}$) uses the same substitution alphabet (1 substitution alphabet per list !). This is basically a Cesar cipher per list. Therefore a simple frequency analysis will break it.

links : Frequency analysis, Retrieving the key

PS: Should you have any questions, comments, edits, please do. :)