Cryptanalysis- the study of breaking cryptosystems explained
Tags: security, computerscience
Published: 2021-08-28 12:32:42

## Introduction
Cryptanalysis is a branch of cryptography that deals studies how to break codes and cryptosystems. It creates techniques to break the ciphers, the techniques are a lot more advanced than a simple brute force attack. Modern methods to break ciphers include linear cryptanalysis and differentil cryptanalysis, which are a lot more advanced than the traditional methods of breaking ciphers, like frequency analysis and index of coincidence. Cryptanalysis also includes exploiting weaknesses in the implementation of cryptography, these type of exploits are called side-channel attacks. People who study cryptanalysis are called cryptanalysts.

### Methods of Cryptanalysis
### Frequecy Analysis
Frequency Analysis is the study of frequency of letters or group or letters in a ciphertext. This method is relatively older to the newer methods of cryptanalysis. This method is used to break classic ciphers, this method is really useful in breaking substitution ciphers. It is based on the fact that certain letters or group of letters in a specific language text occur with specific frequencies. There is a distribution of the frequencies of letters that occur in a particular language. For example: the letters `E`,`A`,`T` and `O` occur the most in a piece of text in the English language. Similarly, the letter pairs - `TH`, `ER`, `ON` and `AN` are the most common in a piece of text in the English language, these pairs are reffered to as bigrams.<br><br>

In some ciphers, the properties and patters of the plaintext is preserved in the ciphertext, and these patterns can easily be studied and then the cipher can be exploited. The ciphertext usually retains the properties of the plaintext when a single letter always gets encrypted to the same ciphertext letter, this usually occurs in substitution ciphers. This type of attack is called ciphertext-only attack. Ciphertext-only attack is the attack in which the cryptanalyst just has the access to the ciphertext and nothing else. The cryptanalyst, in some cases might also know the language of the plaintext, where the cryptanalyst can use techniques like frequency analysis and index of coincidence.<br><br>

When a plaintext is encrypted using a substition cipher, and the cryptanalyst know the actual language of the plaintext, the cryptanalys can easily find frequency distribution and sequences in the ciphertext in most cases. For example: if a ciphertext contains a high frequency of `R` in it and the plaintext language was English, the cryptanalyst would know that `R` would most probably be `E`, `T` or `A` in the plaintext as these letters occur the most in English, he would still need to try more combinations but frequency distributions make the combinations to try a lot lesser.

### Index of coincidence
Coincidence counting is a technique related to cryptography. The index of coincidence provides a probability of how likely is it to draw two matching letters by randomly selecting two letters from a given text. The probability of index of coincidence of a specific letter in a text is fully dependent on the number of times that specific letter appears in the string and it also depends on the length of the string the letter is withdrawn from. The probability of index of coincidence is 0.032(3.2%) in completely random text, it is 0.067(6.7%) for English and 0.072(7.2%) for German. The index of coincidence is (number of times that letter appears/ length of the text).

#### Applications
The index of coincidence is useful in the analysis of natural-language plaintext and the analysis of ciphertext. The coincidences in ciphertext can be caused by coincidences in the plaintext. So when coincidences in ciphertext are found, coincidences in the plaintext are also found at the same letter positions. This technique can be used to cryptanalyze the Vigenère cipher.<br><br>
Index of coincidence can help determine when two texts are written in the same language using the same alphabet. This technique was used to examine the Bible code.

### Linear Cryptanalysis
Linear cryptanalysis is a method of breaking block and stream ciphers. It is one of the two most widely used attacks on block ciphers. It is a plaintext attack. In Linear Cryptanalysis, the attacker studies the probabilistic linear relations(called linear approximations) between parity bits(bit added to a string of binary code, in the case of DES, the parity bit was added to the binary code to check if the key was indeed correctly retrieved, it was also to check whether during transmission, the wrong keys were used. These bits were used for error detection) of plaintext, the ciphertext and the secret key.

### Differential Cryptanalysis
Differential cryptanalyis is a method of breaking ciphers. It is primary applicable to block ciphers, but it is also able to break stream ciphers and cryptographic hash functions. It is the study of how differences in the information inputted can affect the output resulting in a different output than common outputs. In the case of a block cipher, it is a set of techniques for tracing the differences through the network of transformation, and finding where the cipher exhibits non-common behaviour and exploiting such properties of the cipher to recover the cryptographic key.

## Links
- [A paper on linear and differential cryptanalysis](http://www.facweb.iitkgp.ac.in/~sourav/ldc_tutorial.pdf)