Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
What is Vigenere Cipher?
3.
Cryptanalysis of Vigenere Cipher
4.
Determining the key length
4.1.
Index of Coincidence
4.2.
Kasiski Test 
4.3.
Friedman Test
5.
Finding the key
6.
Frequently Asked Questions
6.1.
What is a vigenere cipher?
6.2.
What is cryptanalysis?
6.3.
How many steps are required to find the key of the vigenere cipher?
6.4.
Name different methods for determining the key length.
7.
Conclusion
Last Updated: Mar 27, 2024

Cryptanalysis of Vigenere Cipher

Master Python: Predicting weather forecasts
Speaker
Ashwin Goyal
Product Manager @

Introduction

Hey Ninjas, let us learn about Cryptology. It is the science of secrecy in message transfer. It has two parts cryptography and cryptanalysis. We have learned about cryptography, which is related to the encryption and decryption of information for secured communication and data transfer. Cryptanalysis is the technique of decoding and deciphering cryptography.

introduction

In this article, we will learn about the cryptanalysis of the vigenere cipher. To start with, let us know what vigenere cipher is.

What is Vigenere Cipher?

vigenere cipher

For ease of understanding, the vigenere cipher is the better or improved version of the Caesar Cipher. If we want to compare the caesar cipher and the vigenere cipher, in the caesar cipher, the key may be a number or a character, whereas, in the vigenere cipher, the key is not just one letter but a string of letters and could be a word. 

Let us take an example; In caesar's cipher, if the key is some c, then we shift all the message characters by c characters. 

caesar cipher example

Whereas, in vigenere cipher, let the length of the string is n. Then the main idea in the vigenere cipher is to shift the first letter by s[0] characters, second by s[1] characters, third, and so on until n, then after that shift the (n+1)th character by again s[0] characters. 

vigenere cipher example
Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Cryptanalysis of Vigenere Cipher

Now, we know what a vigenere cipher is and what cryptanalysis is. So we have to decipher a cipher text made using the vigenere cipher; that is, we have to break a cipher text without having the key. There are two main steps involved in breaking a vigenere cipher. Those two are:

  • Determine the key length
  • Finding the key

Determining the key length

Our first step in deciphering the vigenere cipher is finding the length of the key. There are many ways to do this. Some of the widely used and most prominent ways are:

  • Index of Coincidence
  • Kasiski Test
  • Friedman Test

Index of Coincidence

We use the method of index of a coincidence to find whether the cipher text is monoalphabetic or polyalphabetic. The index of coincidence method deals with the probability of identicality of two letters picked randomly from the ciphertext. 

Let us understand this technique with an example.

Let us find the index of coincidence for a vigenere cipher ACDBEADEBAAECBA, assuming there are only five different letters. Then the index of coincidence will be the probability of randomly picking two identical letters. The order of letters does not matter since we do not care what the letters spell, only if they are identical. So, we start with finding ways to pick two letters from the string. Since we have 15 letters, the number of ways will be C(15,2) = 105. Now, we need to find the total number of ways to pick two identical letters. For this, we find the probability of selecting AA, BB, CC, DD, or EE. Since there are five As, the number of ways to pick two As from them is  C(5,2) = 10. Similarly, there are three Bs, two Cs, two Ds, and three Es. Thus, the index of coincidence for the ciphertext will be 

Solution to example

So, from this example, we can find the formula for the coincidence index.

Formula

Kasiski Test 

The kasiski test was brought up by a scientist named Friedrich Kasiski in 1863. While applying the technique of finding the index of coincidence, you also would have found certain patterns. Using these patterns for finding the length of the key for the message is called the kasiski test. When we analyze the ciphertext, we get some strong patterns in repetition. This test is based on these observations. We see that two identical segments of the plaintext will be encrypted to the same ciphertext whenever their occurrence in the plaintext is δ positions apart, where δ ≡ 0 (mod m). 

Conversely, when we observe two identical string segments of the ciphertext, each of length k. There is a good chance that the length of the key may also be k. Each index of the key will act as the key for the corresponding character in the plaintext string.

Friedman Test

For finding the key length, we use the technique of index of coincidence. Through the Friedman test, we can get two separate ways of finding the index of coincidence equal to each other hence finding the value of k. Here k is the assumed length of the key. We have previously learned one way to find the index of coincidence in this article. The other way for the same is assuming that the plaintext string's length is n and the length of the keyword is k. So, we divide the string into k columns and n/k rows. We then compute the index of coincidence as the probability of picking two identical characters from the same column or the probability of picking two identical letters from different columns. So we get the following formula.

Friedman test formula

Finding the key

After we know the key's length, we know the period after which we can see repetition and know the length for which we have to check. We can just club all the characters giving the same answer to i%k(i being the index of the string). After clubbing the characters, we can see the distance between them, finding the key for that index. Doing this for indexes from 0 to k-1, we will find the key to the vigenere cipher.

Frequently Asked Questions

What is a vigenere cipher?

The vigenere cipher is the improved version of the Caesar Cipher, in which the key size is some n and not 1.

What is cryptanalysis?

Cryptanalysis is deciphering the cipher text without knowing the key, that is, finding the key to decrypt the secret message. 

How many steps are required to find the key of the vigenere cipher?

A two-step procedure is required to find the key of the vigenere cipher. First, we have to find the length of the key, and after using it, we have to find the key.

Name different methods for determining the key length.

There are three prominent methods for determining the key length. They are the Index of coincidence, the kasiski test, and the Friedman test.

Conclusion

In this article, we have extensively discussed the Cryptanalysis of the Vigenere Cipher. Its steps and different methods we use for deciphering the encoded information.

We hope that this blog was useful and helped you enhance your knowledge of Cryptanalysis of the vigenere Cipher, and if you would like to learn more, check out our articles on Cryptosystems, Public Key Cryptography, and What are basic Cryptography tools? Do upvote our blog if you find it useful.

Happy Coding!

Previous article
Cryptanalysis of Substitution Cipher
Next article
Cryptanalysis of Hill Cipher
Live masterclass