Do you think IIT Guwahati certified course can help you in your career?
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.
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?
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.
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.
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
So, from this example, we can find the formula for the coincidence index.
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.
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, andWhat are basic Cryptography tools? Do upvote our blog if you find it useful.
86+ registered 