Cipher polyalphabetic

The encryption polyalphabetic overcomes the weakness that have the encrypted monographs to analyze the frequency of letters

To prevent this have been developed based schemes encrypt blocks of letters of a certain fixed length

Vigenère cipher

The Vigenére cipher is an encryption based on different series of characters or letters of Caesar's encryption forming these characters a table, called a Vigenére table, which is used as a key

The Vigenère cipher is a cipher substitution simple polyalphabetic

The first polyalphabetic was the call encryption encryption Alberti, created by Leon Battista Alberti around 1467

To facilitate the calculations we took advantage of a metal disk that allowed you to easily switch between the different scripts available

The system of Alberti, only changing between alphabets after several words, and the changes are indicated by writing the letter of the corresponding alphabet in the encrypted message

Later, in 1508, Johannes Trithemius, in his work Poligraphia, invented the tabula recta, which is basically the table of Vigenère

Trithemius, however, only provided a progressive, rigid and predictable system for switching between alphabets

What is now known as the Vigenère cipher was originally described in 1533 by Giovan Battista Belasso in his book The figure of the Sig. who built the encryption based on the tabula recta of Trithemius, but added a key repeatedly to switch each character between the different alphabets

Blaise de Vigenère published his description of an encryption of an autoclave similar, but more robust, before the reign of Henry III of France, in 1586

Later, in the 19th century, the invention of encryption ceased to be attributed to Vigenére

The cifrado Vigenère ganó una gran reputación por ser excepcionalmente robusto

Even the writer and mathematician Charles Lutwidge Dodgson (better known as Lewis Carroll) said that the encryption Vigenère was unbreakable in the article The Alphabet Cipher for a magazine of children

In 1917, Scientific American he described the encryption Vigenère as impossible to break

This reputation was maintained until the Kasiski method resolved the encryption in the 19th century and some skilled cryptanalysts were able to break it several times in the 16th century

The cipher Vigenère is simple enough if it is used with disk encryption. The confederate States of America, for example, used a disk encryption to implement encryption Vigenère during the american Civil War

Messages confederates were little secrets, as the members of the Union used to decrypt the messages

Gilbert Vernam tried to fix the encryption (creating the encryption Vernam-Vigenère in 1918), but no matter what you do, the encryption is still vulnerable to cryptanalysis (Not to be confused with the encryption Vernam)

Throughout this article for simplicity I will use standard English alphabet 26 letters:

\tiny\begin{pmatrix} 0& 1& 2& 3& 4& 5& 6& 7& 8& 9& 10& 11& 12& 13& 14& 15& 16& 17& 18& 19& 20& 21& 22& 23& 24& 25 \\ A& B& C& D& E& F& G& H& I& J& K& L& M& N& O& P& Q& R& S& T& U& V& W& X& Y& Z \\ \end{pmatrix}

And the next box corresponding to the Vigenère cipher

The encryption can be expressed with the following formula:

M(X_i)=(X_i+K_i-1)\pmod{L}

Where X_i is the letter in position i of the text to encrypt, K_i it is the character of the corresponding key to X_i because they are in the same position, and L is the size of the alphabet. In this case L = 26

To decrypt we will perform the reverse operation:

D(C_i)=(C_i-K_i+1)\pmod{L}

Where C_i is the character at position i of cipher text, K_i comes to be the character of the corresponding key to C_i, and L the size of the alphabet

Keep in mind that the same letter in the clear text can correspond to different letters in the ciphered text

Example of Vigenère cipher

We have the following message that we want to encrypt:

C=MESSAGE SENT YESTERDAY

L = 26 because we're going to use the English alphabet

We take as key:

K = I’M BORED

It is advisable that the key is larger than the message. We put together a message and a key, repeating as many times as necessary the key

\tiny\begin{pmatrix} M& E& S& S& A& G& E& S& E& N& T& Y& E& S& T& E& R& D& A& Y \\ I& M& B& O& R& E& D& I& M& B& O& R& E& D& I& M& B& O& R& E \\ \end{pmatrix}

We go to the table of encryption, and we take the row of the first letter of the key word in the table of Vigénere and the column of the first letter of the message

The intersection of both will be the letter that will be used for encryption

We will repeat the process until you get the encrypted message

So we is that the encrypted message is:

M=UQTGRKHAQOHPIVBQSRRC

We can decipher the M previous

We go to the table of encryption, and we take the column of the first letter of the key word in the table of Vigénere and looking for the first letter of the message

The row of the intersection of both will be the letter that will be used in the message decryption

We will repeat the process until you get the message clear

\tiny\begin{pmatrix} I& M& B& O& R& E& D& I& M& B& O& R& E& D& I& M& B& O& R& E \\ U& Q& T& G& R& K& H& A& Q& O& H& P& I& V& B& Q& S& R& R& C \\ \end{pmatrix}

Getting the original C:

C=MESSAGESENTYESTERDAY

Encryption of Gronsfeld

The encryption of Gronsfeld emerged as an enhancement to the encryption, Vigenère, as that was susceptible to an analysis cryptic with certain conditions laid down. To evaluate some features, it was possible to define the length of the key, and then, when parsing the rows of letters, enciphered by the same row of the table, one could employ a standard method based on the frequency of certain letters of the language

The first to make a successful attack in the modification of the encryption Vigenère in 1854, was Charles Babbage, a pioneer of computing, but the analysis was released nine months later by another researcher, Friedrich Kasiski

Strange as it may seem, this helped to strengthen it, resulting in the encryption of Gronsfeld. One of the improvements was the use of the word key, which is equal to the length of the message itself, thus eliminating the possibility of a frequency analysis

However, this update brought another vulnerability: the use of text-sensitive as a key phrase, contributed to the criptoanalista statistical information about the key, serving as a track to the point of wanting to decipher the text

As it is based on the encryption Vigenère, is also a substitution encryption simple polyalphabetic. This means that using more than one alphabet cipher to put in the key the message and that it changes from one to the other as it passes from a letter of the clear text to another. That is to say that you should be a set of alphabets encrypted and a way to match each letter of the original text with one of them

The number of alphabets encryption is limited to 10, coded from 0 to 9 and the key is generated with a combination of these digits, without repetitions. Alters the frequency of the letters of the text, since for example the letter more current in English, E, is encrypted differently according to their position in the original text

Throughout this article for simplicity I will use standard English alphabet 26 letters:

\tiny\begin{pmatrix} 0& 1& 2& 3& 4& 5& 6& 7& 8& 9& 10& 11& 12& 13& 14& 15& 16& 17& 18& 19& 20& 21& 22& 23& 24& 25 \\ A& B& C& D& E& F& G& H& I& J& K& L& M& N& O& P& Q& R& S& T& U& V& W& X& Y& Z \\ \end{pmatrix}

And the next box corresponding to the encryption of Gronsfeld

this box is not the only possible one, it has been used as an offset to the first 9 prime numbers, and may use another method to create the 10 alphabets

Example of encryption of Gronsfeld

We have the following message that we want to encrypt:

C=MESSAGE SENT YESTERDAY

We take as key:

K = 1203456987

It is advisable that the key is larger than the message. We put together a message and a key, repeating as many times as necessary the key

\tiny\begin{pmatrix} M& E& S& S& A& G& E& S& E& N& T& Y& E& S& T& E& R& D& A& Y \\ 1& 2& 0& 3& 4& 5& 6& 9& 8& 7& 1& 2& 0& 3& 4& 5& 6& 9& 8& 7 \\ \end{pmatrix}

We go to the table of encryption, and we take the row of the first key number in the table of Gronsfeld and the column of the first letter of the message. The intersection of both will be the letter that will be used for encryption. We will repeat the process until you get the encrypted message

So we is that the encrypted message is:

M=PJUZLTVUBGWDGZERIFXR

We can decipher the M previous

We go to the table of encryption, and we take the row of the first key number in the table of Gronsfeld and looking for the first letter of the message. The row of the intersection of both will be the letter that will be used in the decrypted message. We will repeat the process until you get the message clear

\tiny\begin{pmatrix} 1& 2& 0& 3& 4& 5& 6& 9& 8& 7& 1& 2& 0& 3& 4& 5& 6& 9& 8& 7 \\ P& J& U& Z& L& T& V& U& B& G& W& D& G& Z& E& R& I& F& X& R \end{pmatrix}

Getting the original C:

C=MESSAGESENTYESTERDAY

Hill cipher

This system is based on the linear algebra and is very important in the history of cryptography. It was Invented by Lester S. Hill in 1929, and was the first cryptographic system polyalphabetic working with more than three symbols simultaneously

This system is polyalphabetic because it may be that a same character in a message to be sent is encrypted in two different characters in the encrypted message

I would like to start with a very simple system that can be explained mathematically speaking using modular arithmetic. Throughout this article I will use for simplicity the alphabet in standard English 26-letter:

\tiny\begin{pmatrix} 0& 1& 2& 3& 4& 5& 6& 7& 8& 9& 10& 11& 12& 13& 14& 15& 16& 17& 18& 19& 20& 21& 22& 23& 24& 25 \\ A& B& C& D& E& F& G& H& I& J& K& L& M& N& O& P& Q& R& S& T& U& V& W& X& Y& Z \\ \end{pmatrix}

Choose an integer d that determines blocks of d elements, which will be treated as a vector of d dimensions. Randomly, we choose a matrix of d × d elements which will be the key to be used. The elements of the matrix d × d will be integers between 0 and 25, in addition the matrix M must be invertible in \mathbb{Z}^n_{26}

For the encryption, the text is divided into blocks of d elements which are multiplied by the matrix d × d. As well M\cdot P_i \equiv C \pmod{26} where we have assigned the number 0, B 1, ... , Z to 25, and \pmod{26} indicates that we should take the remainder of dividing by 26 (in C language we use the % operator ) M is the matrix d × d, C is the ciphertext and P the original

Example of Hill cipher

CODIGO we break the structure into blocks of 3 characters each (in this case d = 3), eliminating punctuation marks, if any, and we get the numerical equivalents of these letters

P_1=COD=\begin{pmatrix} 2 \\ 14 \\ 3 \end{pmatrix}, P_2=IGO=\begin{pmatrix} 8 \\ 6 \\ 14 \end{pmatrix}

We chose M=\begin{pmatrix} 5& 17& 20 \\ 9& 23& 3& \\ 2& 11& 13 \end{pmatrix} as the keys array

Before applying the encryption, we must ensure that M is invertible \mod{26}. There is a relatively simple way to find this out through the calculation of the determinant. If the determinant of the matrix is 0, or has common factors with the modulus (in the case of 26 the factors are 2 and 13), then the array cannot be used. To be 2 one of the factors of 26 many arrays may not be used (will not serve them all in that its determinant is 0, a multiple of 2 or a multiple of 13)

\det(M) = \begin{vmatrix} 5& 17& 20 \\ 9& 23& 3& \\ 2& 11& 13 \end{vmatrix} = 5 \cdot(23 \cdot 13 - 3 \cdot 11) - 17 \cdot (9 \cdot 13 - 3 \cdot 2) + 20 \cdot (9 \cdot 11 - 23 \cdot 2) =
= 1215 - 1734 + 1060 = 503

Now we check \pmod{26}:

503 = 9\pmod{26}

The matrix A is invertible in \mod{26}because 26 and 9 are coprimos

We calculate the first block:

M\cdot P_1=\begin{pmatrix} 5& 17& 20 \\ 9& 23& 3& \\ 2& 11& 13 \end{pmatrix}\cdot \begin{pmatrix} 2 \\ 14 \\ 3 \end{pmatrix} = \begin{pmatrix} 308 \\ 349 \\ 197 \end{pmatrix}

\begin{pmatrix} 308 \\ 349 \\ 197 \end{pmatrix} = \begin{pmatrix} 22 \\ 11 \\ 15 \end{pmatrix}\pmod{26}

\begin{pmatrix} 22 \\ 11 \\ 15 \end{pmatrix} = WLP

So the encrypted message block one is:

C_1=WLP

We calculate the second block:

M\cdot P_2=\begin{pmatrix} 5& 17& 20 \\ 9& 23& 3& \\ 2& 11& 13 \end{pmatrix}\cdot \begin{pmatrix} 8 \\ 6 \\ 14 \end{pmatrix} = \begin{pmatrix} 422 \\ 252 \\ 264 \end{pmatrix}

\begin{pmatrix} 422 \\ 252 \\ 264 \end{pmatrix} = \begin{pmatrix} 6 \\ 18 \\ 4 \end{pmatrix}\pmod{26}

\begin{pmatrix} 6 \\ 18 \\ 4 \end{pmatrix} = GSE

So the encrypted message block one is:

C_2=GSE

We add both messages encrypted to obtain the encrypted message C:

C=WLPGSE

We can decipher the C above, the method is the same, but we need to calculate M^{-1}. To do this we calculate from this formula:

M^{-1}=C^t\cdot (\det(M))^{-1}

Where C^t is the matrix of cofactors of M transposed and (\det(M))^{-1} should be done as \mod{26}, which in this case is 3 since:

9\pmod{26} \cdot 3\pmod{26}=27 \pmod{26}=1 \pmod{26}

We calculate the cofactors of M

C_{1 1}= + \begin{vmatrix} 23& 3 \\ 11& 13 \end{vmatrix} C_{1 2}= - \begin{vmatrix} 9& 3 \\ 2& 13 \end{vmatrix} C_{1 3}= + \begin{vmatrix} 9& 23 \\ 2& 11 \end{vmatrix}

C_{2 1}= - \begin{vmatrix} 17& 20 \\ 11& 13 \end{vmatrix} C_{2 2}= + \begin{vmatrix} 5& 20 \\ 2& 13 \end{vmatrix} C_{2 3}= - \begin{vmatrix} 5& 17 \\ 2& 11 \end{vmatrix}

C_{3 1}= + \begin{vmatrix} 17& 20 \\ 23& 3 \end{vmatrix} C_{3 2}= - \begin{vmatrix} 5& 20 \\ 9& 3 \end{vmatrix} C_{3 3}= + \begin{vmatrix} 5& 17 \\ 9& 23 \end{vmatrix}

C=\begin{pmatrix} 266& -111& 53 \\ -1& 25& -21& \\ -409& 165& -38 \end{pmatrix} C^t= \begin{pmatrix} 266& -1& -409 \\ -111& 25& 165 \\ 53& -21& -38 \end{pmatrix}

Now we apply the formula in reverse:

M^{-1}=C^t\cdot (\det(M))^{-1}=\begin{pmatrix} 266& -1& -409 \\ -111& 25& 165 \\ 53& -21& -38 \end{pmatrix} \cdot 3=\begin{pmatrix} 798& -3& -1227 \\ -333& 75& 495 \\ 159& -63& -114 \end{pmatrix}

M^{-1}\pmod{26}=\begin{pmatrix} 798& -3& -1227 \\ -333& 75& 495 \\ 159& -63& -114 \end{pmatrix} \pmod{26} =\begin{pmatrix} 18& 23& 21 \\ 5& 23& 1 \\ 3& 15& 16 \end{pmatrix}

We calculate the first block:

M\cdot P_1=\begin{pmatrix} 18& 23& 21 \\ 5& 23& 1& \\ 3& 15& 16 \end{pmatrix}\cdot \begin{pmatrix} 22 \\ 11 \\ 15 \end{pmatrix} = \begin{pmatrix} 964 \\ 378 \\ 471 \end{pmatrix}

\begin{pmatrix} 964 \\ 378 \\ 471 \end{pmatrix} = \begin{pmatrix} 2 \\ 14 \\ 3 \end{pmatrix}\pmod{26}

\begin{pmatrix} 2 \\ 14 \\ 3 \end{pmatrix} = COD

So the encrypted message block one is:

P_1=COD

We calculate the second block:

M\cdot P_2=\begin{pmatrix} 18& 23& 21 \\ 5& 23& 1& \\ 3& 15& 16 \end{pmatrix}\cdot \begin{pmatrix} 6 \\ 18 \\ 4 \end{pmatrix} = \begin{pmatrix} 606 \\ 448 \\ 352 \end{pmatrix}

\begin{pmatrix} 606 \\ 448 \\ 352 \end{pmatrix} = \begin{pmatrix} 8 \\ 6 \\ 14 \end{pmatrix}\pmod{26}

\begin{pmatrix} 8 \\ 6 \\ 14 \end{pmatrix} = IGO

So the encrypted message block one is:

P_2=IGO

We add both messages encrypted to obtain the encrypted message C:

P=CODIGO