Symmetric cryptography is about algorithms that use the same keyword to encrypt and decrypt information. These algorithms, also called ciphers, are efficient to encrypt high volumes of data. The goal of this type of algorithm is to achieve confusion and diffusion in the encrypted text. In this way, the results seem to be random.
Cryptographic algorithms in use nowadays, are the evolution of the symmetric cyphers used in classic cryptography. The principles and objectives of classical and modern cryptography are still the same, even though in classic cryptography the encryption was manually and in modern cryptography, we use software and computers.
In this article, we will study 5 classical cryptographic algorithms. Also, we will highlight the security principles and how they work, to facilitate their understanding and also the modern cryptographic algorithms.
Substitution and transposition
In general, security in symmetric encryption is achieved by combining two techniques.:
- Substitution: To substitute a symbol with another one. After this, we will get an encrypted text that is not legible. Through this process, we achieved confusion in the encrypted text.
- Transposition: In this case, we change the position of symbols in the ciphertext. Therefore, the resulting text will have the same symbols but in a different order. By doing this, we achieve diffusion, or in other words, we disarrange the symbols or characters in the encrypted text.
Once we apply the two techniques together, the resulting text should have a random appearance of symbols that does not make any sense. Also, it must be hard to discover a pattern in the symbols. The latest one is a characteristic that will avoid cryptographers to make cryptanalysis.
Polybius cipher
The Polybius square was a device intended to have applications in cryptography, steganography, and telegraphy. It uses a square to determine the symbols that will be used to substitute the plain text.
Let’s see the following example.
The encryption process is as follows: each letter from the plain text is substituted by the respective row-column pair.
For instance, “HI” will become “23 24”.
As you can see, this is a very simple algorithm. It is also insecure as it can be broken by frequency analysis.
Another way to use this technique is using a key. When you use a key, the letters on the square will change their order.
For instance, if we want to use the key “KEY”, we add these letters at the beginning of the square (where ABC is) and we move the other letters forward on the square. Just make sure that you don’t repeat K, E and Y. The rest of the process is the same.
The Playfair cipher works in a similar way, the main difference is that symbols are substituted by other symbols, instead of by the coordinates (row-column) in the table.
Another substitution method is the Caesar cipher. This method was used by Julius Caesar to communicate with his army.
Caesar cipher
This technique consists in substituting every letter in the plain text, by the letter that stand three places later in the alphabet.
See an example below.
In this example, a is replaced by D (the third letter after a in the English alphabet), d by E, c by F and so on.
If we have to substitute the y letter, we count the letters that are left, in this case only 1, and we start again from the beginning (letter a). As you can see from the example y is substituted by B.
Another example:
We can also do this type of substitution with the remainder of the division operation (a.k.a mod).
We use the following formula:
c = (m +3) mod 26, where m is the position on the alphabet of the plain letter and c will be the corresponding letter in the encrypted text.
When we write a program that implements this type of algorithms, the mod operation is very important, so we don’t get an “Out of range” exception.
Find the python implementation of the Caesar cipher and a full explanation in this post.
Monoalphabetic algorithms cryptanalysis
In the previous algorithms, every symbol from the plain text is substituted by the same symbol in the cypher text. In other words, a will be always substituted by d (in the case of Caesar cipher).
This creates a weakness in the ciphertext because an attacker can find the pattern and then, obtain the plain text. Which is something we must avoid at all costs.
Letters usually appear with a certain frequency depending on the language. Therefore, the cipher can be easily broken by counting how many times the symbol appears in the encrypted text and you will find out what is the letter in the plain text. To use this fact, you need to know in what language the plain text was written, because different languages have different frequencies for the same letter.
The longer the text the better the possibility to decrypt the message using frequency analysis.
Polyalphabetic cryptographic algorithms
To mitigate the vulnerability of the monoalphabetic ciphers, we can use a key. The use of this key will allow us to use different substitutions as we go through the plain text.
This is a technique called polyalphabetic ciphers.
One example of such algorithm is the Vignére Cipher.
Vigenére ciper
This cipher uses the following formula:
Ci = (pi + kimod m)mod 26 ,
where pi is the plain letter at position i, ki is the letter of the key at position i, and m is the number of letters in (the length of) the key. 26 is the number of letters in the English alphabet, if you use a different alphabet, then you change this number accordingly.
If you compare this formula, with the one we used in the Caesar cipher, we are basically applying a different Caesar cipher to each letter in the plain text.
You can also use the following formula for the decryption process:
pi = (Ci – kimod m) mod 26
Description of the cipher
In this algorithm, we are seeing a new concept: a key. This key must be kept secret and we use it to encrypt and decrypt.
In this case, the algorithm is of public knowledge, and we only must keep the key secret. This is the same approach used in modern cryptography.
Important note: For we to say a cryptographic system is secure, we should assume that the person who wants to break the system knows the algorithms, parameters, how it works and if that person does not have the key, it won’t be able to decrypt the message.
Vigenére ciper example
We want to encrypt the plain text “save yourself” using the key “code”.
Let’s use the same alphabet we use for the example of the Caesar cipher: the English alphabet.
Steps to encrypt the text:
- We make the length of the key the same as the plain text by repeating it as many times as necessary.
- We encrypt the first letter (s) using the first symbol of the key (c). So, we “move” the letter s (18), as many positions as indicated by letter c (2). In other words, we change s by u.
- The second letter of the plain text (a) is encrypted using the second letter of the key (o). In this case, we substitute a by o. Notice we moved a (position 0) 14 positions (the number indicated by o).
- We continue until there are no more letters to transform in the plain text.
As you can see, we are basically applying the Caesar cipher several times, with different shifts according to the corresponding letter on the key.
The previous fact will have as a result different encrypted symbols for the same plain text letter.
A short example, plain text “Eve”, key “her” (for simplicity, we are not differentiating lower-case and upper-case letters). The first E will be shifted 7 (h position) times and the second one will be shifted 17 times (r position).
This process makes the algorithm less weak because cryptanalysis is more difficult.
To decrypt the message, we follow a similar process, we shift to the left according to the key.
pi = (Ci – kimod m) mod 26
Notice that the mod operation (reminder of the division), takes care of cases where the shift is greater than the letters that appear after or before the letter we want to substitute.
The result of the operation n mod 26, is always a number between 0 and 26.
Substitution algorithm categories
The following diagram shows several substitution algorithms divided by categories.
Enigma machine marked the change from classic to modern cryptography. Enigma was a machine used by Germans during the second world war.
To break its code, it was necessary to create another machine. The mathematician Alan Turin played a crucial role in creating such a machine, marking what is probably the most important discovery in the history of Computer Science, the Turing Machine.
Transposition algorithms
In this section, we will study two transposition algorithms.
Scytale
“From indirect evidence, the scytale was first mentioned by the Greek poet Archilochus, who lived in the 7th century BC. Other Greek and Roman writers during the following centuries also mentioned it, but it was not until Apollonius of Rhodes (middle of the 3rd century BC) that a clear indication of its use as a cryptographic device appeared.” Source Wikipedia
This cipher consists in using a cylinder and a strip to write the message.
Once the text is encrypted, you will need a cylinder with the same diameter (as the one used for the encryption).
In this case, we can say that the key is the diameter of the cylinder.
Column permutations
To use this method, we first write the message in a table. Then, we change the order of the columns and write the text in the columns as a line of the encrypted text.
The key in this case is the number of rows and columns and the order that we choose them.
Let’s see the following example.
Message: Save yourself
| 1 | 2 | 3 | 4 | 5 | 6 |
| s | a | v | e | y | |
| o | u | r | s | e | l |
| f |
key: 3,5,1,4,6,2
Steps to encrypt the message
- We use column 3 as the first text in the encrypted text: vr
- Column 5: e
- and so on.
The resulting encrypted message is vresofesylau
To decrypt the message, we follow the inverse process. Create an empty table, first complete column 3, then 5, and so on.
Conclusions
There are several methods that we can use to encrypt information manually. The main techniques are substitution and transposition.
Several algorithms have been developed within each of the previous categories.
The more secure the algorithm, the more complexity. With complexity, it comes more effort to use and apply each algorithm. The same applies to modern cryptography.
A more secure algorithm requires more computational (or manual) effort. This means it needs more resources to be used. What we need is to determine how much security we need according to our environment and the nature of the information.
The previous algorithms can be used together. It will bring more security and more complexity as well.
For instance, you can encrypt with Vigenére (using a key), then enter the result in a permutation table and apply Caesar cipher to the resulting text. To decrypt you follow the inverse order. Each time you apply one algorithm, the confusion and diffusion increase and therefore the security also increases.
To apply several cipher layers is a technique used in modern cryptography to strengthen the method against cryptanalysis.
Classic cyphers are not really used nowadays, because computers can break the code easily.
However, modern cryptographic algorithms work in a similar way, substituting and transposing bits to achieve a high level of confusion and diffusion in a similar way that was done in classic cryptographic algorithms.
Understanding these principles will make easier the study of current algorithms used in symmetric cryptography.