Cryptoanalysis of Vigenère cipher

Information Security

Fall 2011

Lab #1

Implementing cryptanalysis of Vigenère cipher

Objective

Implement a program, which breaks Vigenère cipher.

Input data: a text file in ANSI or ASCII encoding, containing a text encrypted by Vigenère cipher of length at least 1000 characters.

Output data: the decrypted meaningful English plaintext and the key.

Deliveries

· Print your source code and test cases

· Demonstrate your working version and describe your implementation

Background

Vigenère cipher

Let us assume that the key consists of m letters, K=(K₀, K₁,.., K_m-1).

Encryption: for each plaintext letter P_i substitute: C_i = P_i+ K_{i mod m} mod 26, where i=0,1,2,...

Decryption: for each cipher text letter C_i (i=0,1,2,...), substitute: P_i = C_i- K_{i mod m} mod 26, where i=0,1,2,...

Example:

P:wearediscoveredsaveyourself

K:deceptivedeceptivedeceptive

C:zicvtwqngrzgvtwavzhcqyglmgj

Cryptoanalysis of Vigenère cipher

Consists of two steps:

· Find the key length m

· Find the key K=(K₀, K₁,.., K_m-1)

Identical strings occur in a ciphertext when the same letters of the plaintext are encrypted by the same letters of the key, thus the length of the key is always a divisor of the greatest common divisor of the distances between identical strings in the ciphertext. Therefore, to find out the length of the key:

1. Search the ciphertext for pairs of identical sequences of length at least three letters;

2. Store the distances between the starting positions of the found sequences;

3. Find the greatest common divisor of the distances, m should either be equal to it or be its divisor.

Be aware that some identical sequences can be just the result of coincidence.

After you found the length of the key m, split the ciphertext into m blocks, as follows:

B₀=C₀,C_m,C_2m,C_3m,..

B₁=C₁,C_m+1,C_2m+1,C_3m+1,..

...

B_m-1=C_m-1,C_2m-1,C_3m-1,C_4m-1,..

Compute the frequency (i.e. number of occurrences) of each letter in block B₀. Compare these frequencies to known frequencies of letters in English language (Fig. 1) and deduce the first letter of the key (K₀). Then, compute the frequency of each letter in block B₁ and find the second letter of the key K₁. Repeat this operation for blocks B_2.. B_m-1 to find the rest of the key.

After obtaining the key, decrypt the ciphertext.

The easy way to check if the decrypted text is indeed an English plaintext is to compute a so-called index of coincidence I_c, which indicates the probability that any two letters of the string are identical:

where f_i is a frequency of i th letter of the alphabet, and N is the total number of letters in the text.

English plaintext (and English plaintext, encrypted by monoalphabetic cipher) would have I_c closer to 0,065.

Useful links

1. Information about cryptoanalysis of Vigenère cipher with examples can be found here: http://www.nku.edu/~christensen/section%2012%20vigenere%20cryptanalysis.pdf

2. Vigenère cipher tool: http://www.sindark.com/NonBlog/CR/CR.html

PS Get rid of all non-letter characters (whitespace, punctuation, numbers etc.) and convert all letters to either upper or lower case before applying any analysis.

Try to figure out how you can use the index of coincidence to check if the length of the key is correct.

Дата добавления: 2015-11-14