Exercise 1

Vigenre encryption is a poly-alphabetic substitution system developed by Blaise de Vigenre in 1586. It relies on the periodic use of several substitution alphabets exterminated by a key . To encrypt a plain text, to each character we associate a key letter to perform the offset corresponding as in encryption of Cesar .

If the length of the key l is known, recovering the clear text from the ciphertext c can be done by applying a cryptanalysis of the Csar cipher (as in exercise 1) for each sub-cipher c _i of c formed only letters whose positions are congruent to i modulo l (for i 0 , ... , l - 1). The difficulty for the cryptanalyst therefore consists in finding the length of the key .

The first method to find the length of the key is known as the Kasiski test . It is based on the fact that if two groups of letters (or polygrams) of the cipher are equal then it is probably the same polygram in the cipher plain text with the same part of the key . The key size that separates these two identical polygrammes in the encrypted will be, in most cases, a multiple of the length of the key . If there are multiple repetitions of polygrams, the greatest common divisor of the distances between them is most likely the size of the key .

The following text was obtained by applying Vigenre encryption on a French language text in which spaces have been removed :

Use Kasiski's test to determine the length of the key used and decrypt the text :

zbpuevpuqsdlzgllksousvpasfpddggaqwptdgptzweemqzrdjtddefek

eferdprrcyndgluaowcnbptzzzrbvpssfpashpncotemhaeqrferdlrlw

wertlussfikgoeuswotfdgqsyasrlnrzppdhtticfrciwurhcezrpmhtp

uwiyenamrdbzyzwelzucamrptzqseqcfgdrfrhrpatsepzgfnaffisbpv

blisrplzgnemswaqoxpdseehbeeksdptdttqsdddgxurwnidbdddplncsd