Tag: vigenere cipher

Posted in Science & Nature

Cryptography: Kasiski Examination

Posted on by Jinavie

The Kasiski examination can be used to attack polyalphabetic substitution ciphers such as the Vigenère cipher, revealing the keyword that was used to encrypt the message. Before this method was devised by Friedrick Kasiski in 1863, the Vigenère cipher was considered “indecipherable” as there was no simple way to figure out the encryption unless the keyword was known. But with the Kasiski examination, even the Vigenère cipher is not safe anymore.

The Kasiski examination is based on the fact that assuming the number of letters of the keyword is n, every nth column is encoded in the same shift as each other. Simply put, every nth column can be treated as a single monoalphabetic substitution cipher that can be broken with frequency analysis. Ergo, all the cryptanalyst needs to do to convert the Vigenère cipher into a Caesar cipher is know the length of the keyword.

To find the length of the keyword, look for a string of repeated text in the ciphertext (make sure it is longer than three letters). The distance between two equal repeated strings is likely to be a multiple of the length of the keyword. The distance is defined as the number of characters starting from the last letter of the first set of strings to the last letter of the second set of strings (e.g. “abcdefxyzxyzxyzabcdef” -> “abcdef” is repeated” -> distance is “xyzxyzxyzabcdef” which is 15 letters). The reason this works is that if there is a repeated string in the plaintext and the distance between these strings is a multiple of the keyword length, the keyword letters will line up and there will be repeated strings in the ciphertext also. If the distance is not a multiple of the keyword length, even if there is a repeated string of letters in the plaintext, the ciphertext will be completely different as the keyword would not match up and be different.

It is useful recording the distance between each set of repeated strings to find the greatest common factor. The number that factors the most into all of these distances (e.g. 6 is a factor of 6, 12, 18…) is most likely the length of the keyword. Once the length of the keyword is found, then every nth letter must have been encrypted using the same letter of the keyword. Thus, by recording every nth letter in one string, you can obtain what is essentially a Caesar cipher. The Caesar cipher is then attacked using frequency analysis. Once a few of these strings (of different positions on the ciphertext) are solved, the keyword can be revealed by checking the shift key against a tabula recta (e.g. if a certain string of nth letters is found to have been shifted 3 letters each, then the corresponding letter in the keyword must be “D”, which shifts every plaintext letter by 3 in the Vigenère cipher). When the keyword is deduced, every message encrypted using that keyword can now easily be decoded by you.

Although the Kasiski examination appears to be complex, attempting to try it reveals how simple the process is. Thus, it is useful to try encrypting a message using the Vigenère cipher then trying to work out the keyword using the Kasiski examination. Much like the frequency analysis, it is an extremely useful tool in the case of needing to break a secret code.

Posted in Science & Nature

Cryptography: Vigenere Cipher

Posted on by Jinavie

It has thus been proven that the Caesar cipher, the pigpen cipher and any substitution cipher can be simply broken using frequency analysis. The basis for this is that each letter or symbol can only represent a single letter, meaning that letter frequencies (e, t, a, o…) are directly translated onto the cipher language. Ergo, by making each letter represent more than one letter, the letter frequencies can be masked and an additional level of security can be added to the cipher. This is called polyalphabetic substitution and it is the basis for a type of cipher known as the Vigenère cipher.

The cipher was first conceived in 1553 by Giovan Battista Bellaso and has been improved since. It is famous for being rather simple to use despite the difficult to decipher it at a beginner’s level. This trait earned the cipher the nickname “le chiffre indéchiffrable”, which is French for “the indecipherable cipher”.

The Vigenère cipher can be thought of a stack of Caesar ciphers (essentially a cipher within a cipher), where each letter is shifted by a variable key (in a normal Caesar shift, every letter is shifted by the same key). This is achieved by the implementation of a keyword and a table called a tabula recta. A tabula recta is simply a grid made from 26 rows of the alphabet, each row of which is made by shifting the previous one to the left. This table essentially shows all the possible outcomes of a Caesar shift.

Now, let us try encoding a message using the Vigenère cipher. The message “attack at dawn” is encoded using the keyword “nothing”. Ideally, there should be no repeating letters in the keyword for the sake of security. Therefore, if there are any repeating letters, just remove the repeated letters (e.g. “crocodile” -> “crodile”). First, repeat the keyword until it matches the number of letters of the message (e.g. “attackatdawn” is aligned with “nothingnothi”). Then, use the tabula recta to encrypt the message. The rule of thumb is “key-row, message-column”, meaning that the row of the tabula recta starting with the letter of the key is matched against the column starting with the respective letter of the message. To take the first letter as an example, the key letter is “n” and the message letter is “a”. The letter corresponding to where the “n” row and “a” column meets is “N”. If this rule is followed for each letter, the encrypted message becomes: “NHMHKXGGRTDV”. Although it takes some effort to find each letter on the table, the message becomes “indecipherable” to a beginner cryptanalyst as frequency analysis becomes useless. For example, the repeating letter “H” can represent either “t” or “a”. The longer the keyword is, the more secure the Vigenère cipher becomes.

However, the Vigenère cipher is not indecipherable. Next, we will look at a cryptanalysis method called the Kasiski examination that attacks a polyalphabetic cipher such as the Vigenère cipher to gain access to the keyword.