The Vigenere Cipher - Cryptography Tutorial

1) Understand how to encrypt, decrypt and break the Vigenere  Cipher. 

2) Research the Internet to find 
out how Blaise de Vigenere created his cipher and how Kasiski demonstrated how to break the seemingly unbreakable cipher. 

POLYALPHABETIC CIPHERS - the attempt to disguise letter frequencies

We have learned that any Monoalphabetic Cipher can be broken. The reason: Since same plain letters are encoded to same cipher letters, the underlying letter frequencies remain unchanged. Surely, Cryptographers have tried to overcome this dilemma simply by assigning various cipher letters or symbols to same plain letters. Such ciphers are called Polyalphabetic Ciphers. I will introduce you now to the most popular of the such ciphers: The "Vigenere Cipher". Afterwards, you will learn the "Homophonic Cipher". 

The Vigenere Cipher  
The Vigenere Cipher is an improvement of the Caesar Cipher but not as secure as the unbreakable One Time Pad. What could there be in between? Recall that the Caesar Cipher encodes each plain letter by a constant shift whereas the One Time Pad shifts each plain letter depending on the corresponding keyword letter. Now, the Vigenere Cipher uses a keyword of given length repeatedly. I.e. "cat", "monopoly" or "nvsayuweqgw".
   

Exercise 1: Say the keyword is "cat", use the encoding program below and try to understand how "aaabbbcccddd" is encoded. 

 

Enter keyword (use lower case letters, any length):
Plain text (no blanks or punctuation marks.)			Cipher text
Cipher text			Plain text
Answer to exercise 1: The Vigenere Cipher uses the same keyword repeatedly to determine the encoding shift of each plain letter. I.e. Plain letter "a" = 0 is shifted by "c" = 2 positions.
Exercise 2:   Encode meetmeatnoon and holiday using the keyword "cash" by hand. Afterwards, verify your answer above.
Exercise 3:   Decode zofxbsepseogjgpyfrp using the keyword ball by hand. Afterwards, verify your answer above.
Exercise 4:   Although the Vigenere Cipher partly disguises underlying letter frequencies through the polyalphabetic substitution, it does leave valuable information for an eavesdropper.  What are they? How could an eavesdropper break the Vigenere Cipher?  Read below
Cryptoanalysis of the Vigenere Cipher:  The vulnerability of the cipher is due to the periodicity of the keyword. I.e. using the keyword "cat" produces shifts of length 2 (=c) for the 1st , 4th , 7th, 10th , ... plain letter, shifts of length 0 (=a) for the 2nd , 5th , 8th , 11th ,  ... plain letter and shifts of length 19 (=t) for the 3rd , 6th , 9th , 12th , ... plain letter. Consequently, if an eavesdropper only knows the keyword length (here 3), he groups the above cipher letters into 3 categories. He then applies letter frequency analysis on each group of letters. Certainly, he will have to intercept a large piece of cipher text in order to successfully perform the frequency analysis. The remaining challenge to successfully break the Vigenere Cipher remains to determine the keyword length.  The German soldier Friedrich Wilhelm Kasiski (1805-1881) introduced a method to determine the keyword length - the so called "Kasiski-Test". I am going to show you an easy example of this method. Say, we vigenere-encode as follows:   theappleisinthecornerandthepearistheretoo (plain)  catcatcatcatcatcatcatcatcatcatcatcatcatca  (key) vhxcpinebuigvhxeokpekcnwvhxrettilvhxtemqo  (cipher) The eavesdropper has to search for repeating cipher letter combinations (i.e. "vhx"). He then counts the distances between such letter combinations (i.e. 12, 9, 21, 33). Such distances are multiples of the keyword length if same plain words happened to be encoded with the same keyword. Therefore, their greatest common divisor is the desired keyword length (i.e. 3). Assuming the keyword length is 3, letter frequency analysis is applied to the 3 groups of cipher letters. Cipher letters in  same groups stem from plain letters that were shifted by the same same number of positions, they are Caesar shifts. Thus, the most frequent cipher letter in each group is very likely the Cipher "e". Consequently, the Vigenere Cipher is broken.      Exercise 5:   Determine the keyword length of the vigenere-encoded cipher text below. Once found, try to break the encoded message. Attention: To easily find repeating letter combinations I maintained the word spacing. Therefore, blanks are encrypted (but remain blanks) and distances between repeating letter combinations are determined by incorporating the blanks in the summation process as well. I.e. The distance between the first two "wvk" is 33 and not 28. Count the spaces just like regular letters. A great help to count letters with and without spaces is "Word Count" under Tools in MS WinWord.        wvk kuur ffeshujfgsve qupsy txra wvk uxhsq kuury yxbdzrg psgqwtj nlrjhb dbj uxddnhwt akdboqu zfowwtj iumvwcmuovkm lg wvk gzxre cl vogrkq cuwzlbm cx hnh yfwkqqk cl stffeshoqu dbj rkffeshoqu wsdw tlbkwskqhn qkqhaum vqnrzgug gsiumvwsj otfwkqh hueshodb kwkucmomvkwiv ckst bgscrhctv yrzjlsxv lritg zks ucyhhzd ywcth thox fuvszwo huesh lhy wtvqxldzlct dxdwylbm yoqu shuossb b kgv oq zkfkh gqqohbz zgquadukv jhauwwi vohfujzesvofg dbj uxhsq hnh yfvuooxv ckc fcaor usgg gqqohbz uxhsq rkffeshkg zks rhnhf ootjigjsy pe hxdbyoozlbm hnh muskn gqr fcssoxlbm hnh zkfkh oqgiuwvwwuqg lb wvk hchbzlszk ihbzxfe kuuzj cl qupdawsx bkwkuuyy akvggjsy oxh jluoworom hbiumvwsj ct hnh yhbjlbm gogs dbj rkffeshkg uq zks usihwblbm gogs xgoqu ffeshujfgsvof yhfblqkv gqr dzmrfowvsv gouuuwzkay oxh sdhnhagwwidz wsikbotikv uu xxzkv zkoz ovsze o ffeshujfgsvof yhfblqk hu o psyvomh Please complete: Letter combinations such as "dbj", "wvk", "cl" and "hnh" appear often. (Can you find any others? How about "ffesh"?) The distances between consecutive ... "dbj" are 102, __ , __ . "wvk" are 33, __ , __ . "hnh" are __ , __ , __, __ , __ . "cl" are __ , __ . Their greatest common divisor is  __ .  To then figure out the keyword, we find the ...     first letter to be a Caesar shift of __ positions.     second letter to be a Caesar shift of __ positions.     third letter to be a Caesar shift of __ positions. Thus, the keyword is  ____ (numbers)  =  ____ (word) Therefore, the plain text is ???  the word cryptography comes from the greek words kryptos meaning hidden and graphein meaning writing cryptography is the study of hidden writing or the science of encrypting and decrypting text nineteenth century scholars decrypted ancient egyptian hieroglyphics when napoleons soldiers found the rosetta stone near rosetta egypt its inscription praising king ptolemy v was in three ancient languages demotic hieroglyphics and greek the scholars who could read ancient greek decrypted the other languages by translating the greek and comparing the three inscriptions in the twentieth century world of computer networks messages are digitally encrypted on the sending side and decrypted on the receiving side using cryptographic services and algorithms algorithms are mathematical techniques or rules that apply a cryptographic service to a message   Exercise 6:  Break the following Vigenere Cipher. Mvc gnxqgywa aglgghb ht Tbrbzjxg Lqfhcj wq hm dphjgws Lh Mvmfoq olw Qm Hhvl kgmv ifgoorx nkwktfw olw qxqmgrykm xrsvorbcl cd hfx fbufxgr estzgmm Mvc tsgqrbcl cd hfx Jhkck Qvvmhz bg mc ifciopx qmibxbrl dhf t pbumkcsl ahzjxuc dpxdykorhfw dphupta bb mvc Agwrjx ygr Ndnxf Lqfhcjl Ras Tbrbzjxg Lqfhcj dphupta bg wsqbulxr mc xbqnfc oq asvv tg bh bg icqlwzes mvym ekobnorxg tfc dpxdyksb hm acxh mvc obfwqlwmgg ksonwpxacghq cd hfx khgr qmfdcmwrbjc qmezczsq olw sgwtxfqbhgxg mc xlaxz bb liaa gggrbhsmwmgg tbb hm ormogg rasgk nxfqhbye ygr vopxsp umtzq Oje qvvmhz ifmzfyfg tfc rclwegsb hm rcosjhd lhswslmg tqywskbq tbb zctrckgfbd tpgewrbsq olw rasgk nxfqhbye qhqgtz tbb qgowa outfcgsql   Keyword:   TOY  Plain text: The specific mission of Antilles School is to provide St Thomas and St John with private primary and secondary education of the highest quality The function of the Lower School is to prepare students for a rigorous college preparatory program in the Middle and Upper Schools The Antilles School program is designed to ensure as much as it is possible that graduates are prepared to meet the admissions requirements of the most competitive colleges and universities to excel in such institutions and to attain their personal and career goals All school programs are designed to develop students academic and leadership abilities and their personal social and civic awareness        The Vigenere Plateau Before the computer age messages were vigenere-encoded and decoded by using the famous Vigenere Plateau below. The cipher letter is determined by the keyword column and the plaintext row. I.e. let's encode the plain letter "T" using the keyword letter "C". The intersection of the T-row with the C-column happens at letter "V", the cipher letter. Correspondingly, the plain letter can be derived from the cipher letter and the keyword. How?                          Keyword     A B C D E F G H I J K L M N O P Q R S T U V W X Y Z      B C D E F G H I J K L M N O P Q R S T U V W X Y Z A      C D E F G H I J K L M N O P Q R S T U V W X Y Z A B  P   D E F G H I J K L M N O P Q R S T U V W X Y Z A B C  l   E F G H I J K L M N O P Q R S T U V W X Y Z A B C D  a   F G H I J K L M N O P Q R S T U V W X Y Z A B C D E  i   G H I J K L M N O P Q R S T U V W X Y Z A B C D E F  n   H I J K L M N O P Q R S T U V W X Y Z A B C D E F G  t   I J K L M N O P Q R S T U V W X Y Z A B C D E F G H  e   J K L M N O P Q R S T U V W X Y Z A B C D E F G H I  x   K L M N O P Q R S T U V W X Y Z A B C D E F G H I J  t   L M N O P Q R S T U V W X Y Z A B C D E F G H I J K      M N O P Q R S T U V W X Y Z A B C D E F G H I J K L      N O P Q R S T U V W X Y Z A B C D E F G H I J K L M      O P Q R S T U V W X Y Z A B C D E F G H I J K L M N      P Q R S T U V W X Y Z A B C D E F G H I J K L M N O      Q R S T U V W X Y Z A B C D E F G H I J K L M N O P      R S T U V W X Y Z A B C D E F G H I J K L M N O P Q      S T U V W X Y Z A B C D E F G H I J K L M N O P Q R      T U V W X Y Z A B C D E F G H I J K L M N O P Q R S      U V W X Y Z A B C D E F G H I J K L M N O P Q R S T      V W X Y Z A B C D E F G H I J K L M N O P Q R S T U      W X Y Z A B C D E F G H I J K L M N O P Q R S T U V      X Y Z A B C D E F G H I J K L M N O P Q R S T U V W      Y Z A B C D E F G H I J K L M N O P Q R S T U V W X      Z A B C D E F G H I J K L M N O P Q R S T U V W X Y