Enigma algorithm
In this community, I found many articles about the well-known Enigma encryption machine, but none of them described the detailed algorithm for its work. Surely many will say that it does not need to be advertised - I hope that it will be useful for someone to find out about it. How did it all start? During the First World War, the Playfair cipher was very popular. Its essence was that the letters of the Latin alphabet were written in a square of 5x5, after which the letters of the original alphabet were divided into pairs. Further, using the square as the key, these bigrams were replaced by others according to a certain algorithm. The advantage of this cipher was that it did not require additional devices, and, as a rule, by the time the message was decrypted, it was no longer relevant. Another way to secret writing was Jefferson's coder.
This device consisted of a certain number of disks strung on a single axis (usually there were 36 disks). Each of them was divided into 26 parts, each of which denoted a letter. The letters on the disks were arranged randomly. The operator, by rotating the dial, would type in the desired message, and then rewrite another line. The person who received this message should have exactly the same device with the exact same arrangement of letters. Both methods were relatively good for those times, but given that humanity has entered the 20th century, it became necessary to mechanize the encryption process. In 1920, the Dutch inventor Alexander Koch invented the first rotary encryption machine. Then, German inventors received a patent for it, who improved it and put it into production, called “Enigma” (from Greek. - Mystery). Thus, this machine was acquired by many companies that wanted to keep their correspondence secret. This was the whole genius of Enigma - everyone knew the encryption algorithm, but no one could find the right key, since the number of possible combinations exceeded 15 quadrillion. If you want to know how the Enigma was hacked, I advise you to read Simon Singh’s book The Book of Ciphers. Summarizing all the above, I want to say that the Enigma cipher was a certain mixture of the Jefferson coder and Caesar cipher.
')
So let's get down to learning the algorithm. On this site there is a very good simulator, which in an accessible and visual form shows the whole process entirely. Let's look at the principle of the three-rotor Enigma. It had three compartments for accommodating three rotors and an additional compartment for accommodating the reflector. In total, during the Second World War, eight rotors and four reflectors were manufactured, but at the same time exactly as much as the machine was designed. Each rotor had 26 sections, which corresponded to a separate letter of the alphabet, as well as 26 contacts for interaction with neighboring rotors. As soon as the operator clicked on the desired letter, the electrical circuit was closed, as a result of which an encrypted letter appeared. The circuit was closed at the expense of the reflector.
The figure shows an illustration of pressing the “A” key followed by decoding into the letter “G”. After entering the letter, the rightmost rotor moved forward, thereby changing the key. So how was one letter replaced with another? As I said before, eight different rotors were designed for the Enigma. Within each of these, 26 different commutations were installed. Here is a detailed specification for each of them. For example, if the letter “N” entered the input of the first rotor, then the output should be only “W” and no other letter is greater. Had this letter on the second rotor, it would have already been transformed into “T”, etc. That is, each rotor performed a clear task in terms of communication. And what role did the rings play? Consider the following example. Install rotors III, II, and I, and the order of the rings is “C”, “U”, and “Q”.
Press the "A" key. The rightmost rotor will turn forward one step, that is, the letter “Q” will turn into “R”. The rotor in the middle will also turn forward on the letter “V”, but I will tell about this a little later. So, our letter “A” begins the journey from the first compartment, in which the rotor I is installed and on which the letter “R” is already displayed. Already before entering the first rotor, the letter undergoes its first transformation, namely: addition with the letter “R” modulo 26. In fact, this is Caesar's cipher. If you number all the letters from 0 to 25, then the letter "A" will be just the same zero. Hence, the result of the addition will be the letter "R". Further, we all know that in the first compartment is the rotor I, and in its design it is incorporated that the letter “R” always goes into “U”. Now in line the second compartment with the rotor II. Again, before hitting the second rotor, now the letter “U” changes in a slightly different algorithm: the difference between the values of the subsequent rotor and the previous one is added to it. I will explain. On the second rotor, the letter “V” awaits us, and on the previous one, “R”, the difference is four letters, and they are added to our letter “U”. Therefore, on the second rotor comes the letter "Y". Further, according to the table, we find that in the second rotor the letter “Y” corresponds to “O”. Then again we look at the difference between the letters "C" and "V" - it is equal to seven. So, we shift the letter “O” by seven positions and get “V”. In the rotor III "V" goes to "M". Before getting to the reflector, the letter “C” is subtracted from our letter, transforming it into the letter “K”. Next comes the reflection. If you notice, large cyclic groups form in each rotor, for example: (A - E - L - T - P - H - Q - X - R - U), and in the reflector they are divided into pairs: (A - Y) (B - R) (C - U), etc. This is done so that later it can be decrypted. Suppose that a reflector B is installed, in which “K” is replaced with “N” (and vice versa). Half way passed. Now we again add the value of the letter "C", thereby obtaining the letter "P". Here, on the contrary, in the line of the third rotor we find the “P” and look, in pressing which letter it would appear. This is the letter "H". Conversion in the third rotor is complete. Now the difference between the letters “C” and “V”, that is, seven, is subtracted from this letter. We get the letter "A". In the second rotor, it goes into itself, so leave it unchanged. Next, subtract the difference between the letters "V" and "R", that is, the four, and we get the letter "W". In the first rotor, its conversion back is mapped to the letter “N”. It remains only to subtract from it the letter "R" and get the desired letter "W". As you can see, the algorithm of the machine was not as difficult as it seemed. To improve the cipher, the Germans introduced a patch panel, which allowed the letters to be interchanged in pairs. If we combine the letters “Q” and “W”, then entering the same “A” we would get “Q”, since in fact it should be “W”, but it is replaced by the letter “Q”. Here is the attached chart of action.
It remains only to tell about the displacement of the rotors relative to each other. The right-hand rotor always turned when the key was pressed one step. For example, for rotor I, this position is equal to the letter "R". That is why in our example the second rotor turned: the first rotor went through the letter "R". Further, having passed through a certain position, the right rotor set in motion the left one step. In more advanced models, the left rotor scrolled two or even three times.
In conclusion, I will say that here are collected some materials on cracking Enigma, which may be useful. I hope that this article is useful to someone.
This device consisted of a certain number of disks strung on a single axis (usually there were 36 disks). Each of them was divided into 26 parts, each of which denoted a letter. The letters on the disks were arranged randomly. The operator, by rotating the dial, would type in the desired message, and then rewrite another line. The person who received this message should have exactly the same device with the exact same arrangement of letters. Both methods were relatively good for those times, but given that humanity has entered the 20th century, it became necessary to mechanize the encryption process. In 1920, the Dutch inventor Alexander Koch invented the first rotary encryption machine. Then, German inventors received a patent for it, who improved it and put it into production, called “Enigma” (from Greek. - Mystery). Thus, this machine was acquired by many companies that wanted to keep their correspondence secret. This was the whole genius of Enigma - everyone knew the encryption algorithm, but no one could find the right key, since the number of possible combinations exceeded 15 quadrillion. If you want to know how the Enigma was hacked, I advise you to read Simon Singh’s book The Book of Ciphers. Summarizing all the above, I want to say that the Enigma cipher was a certain mixture of the Jefferson coder and Caesar cipher.
')
So let's get down to learning the algorithm. On this site there is a very good simulator, which in an accessible and visual form shows the whole process entirely. Let's look at the principle of the three-rotor Enigma. It had three compartments for accommodating three rotors and an additional compartment for accommodating the reflector. In total, during the Second World War, eight rotors and four reflectors were manufactured, but at the same time exactly as much as the machine was designed. Each rotor had 26 sections, which corresponded to a separate letter of the alphabet, as well as 26 contacts for interaction with neighboring rotors. As soon as the operator clicked on the desired letter, the electrical circuit was closed, as a result of which an encrypted letter appeared. The circuit was closed at the expense of the reflector.
The figure shows an illustration of pressing the “A” key followed by decoding into the letter “G”. After entering the letter, the rightmost rotor moved forward, thereby changing the key. So how was one letter replaced with another? As I said before, eight different rotors were designed for the Enigma. Within each of these, 26 different commutations were installed. Here is a detailed specification for each of them. For example, if the letter “N” entered the input of the first rotor, then the output should be only “W” and no other letter is greater. Had this letter on the second rotor, it would have already been transformed into “T”, etc. That is, each rotor performed a clear task in terms of communication. And what role did the rings play? Consider the following example. Install rotors III, II, and I, and the order of the rings is “C”, “U”, and “Q”.
Press the "A" key. The rightmost rotor will turn forward one step, that is, the letter “Q” will turn into “R”. The rotor in the middle will also turn forward on the letter “V”, but I will tell about this a little later. So, our letter “A” begins the journey from the first compartment, in which the rotor I is installed and on which the letter “R” is already displayed. Already before entering the first rotor, the letter undergoes its first transformation, namely: addition with the letter “R” modulo 26. In fact, this is Caesar's cipher. If you number all the letters from 0 to 25, then the letter "A" will be just the same zero. Hence, the result of the addition will be the letter "R". Further, we all know that in the first compartment is the rotor I, and in its design it is incorporated that the letter “R” always goes into “U”. Now in line the second compartment with the rotor II. Again, before hitting the second rotor, now the letter “U” changes in a slightly different algorithm: the difference between the values of the subsequent rotor and the previous one is added to it. I will explain. On the second rotor, the letter “V” awaits us, and on the previous one, “R”, the difference is four letters, and they are added to our letter “U”. Therefore, on the second rotor comes the letter "Y". Further, according to the table, we find that in the second rotor the letter “Y” corresponds to “O”. Then again we look at the difference between the letters "C" and "V" - it is equal to seven. So, we shift the letter “O” by seven positions and get “V”. In the rotor III "V" goes to "M". Before getting to the reflector, the letter “C” is subtracted from our letter, transforming it into the letter “K”. Next comes the reflection. If you notice, large cyclic groups form in each rotor, for example: (A - E - L - T - P - H - Q - X - R - U), and in the reflector they are divided into pairs: (A - Y) (B - R) (C - U), etc. This is done so that later it can be decrypted. Suppose that a reflector B is installed, in which “K” is replaced with “N” (and vice versa). Half way passed. Now we again add the value of the letter "C", thereby obtaining the letter "P". Here, on the contrary, in the line of the third rotor we find the “P” and look, in pressing which letter it would appear. This is the letter "H". Conversion in the third rotor is complete. Now the difference between the letters “C” and “V”, that is, seven, is subtracted from this letter. We get the letter "A". In the second rotor, it goes into itself, so leave it unchanged. Next, subtract the difference between the letters "V" and "R", that is, the four, and we get the letter "W". In the first rotor, its conversion back is mapped to the letter “N”. It remains only to subtract from it the letter "R" and get the desired letter "W". As you can see, the algorithm of the machine was not as difficult as it seemed. To improve the cipher, the Germans introduced a patch panel, which allowed the letters to be interchanged in pairs. If we combine the letters “Q” and “W”, then entering the same “A” we would get “Q”, since in fact it should be “W”, but it is replaced by the letter “Q”. Here is the attached chart of action.
It remains only to tell about the displacement of the rotors relative to each other. The right-hand rotor always turned when the key was pressed one step. For example, for rotor I, this position is equal to the letter "R". That is why in our example the second rotor turned: the first rotor went through the letter "R". Further, having passed through a certain position, the right rotor set in motion the left one step. In more advanced models, the left rotor scrolled two or even three times.
In conclusion, I will say that here are collected some materials on cracking Enigma, which may be useful. I hope that this article is useful to someone.
Source: https://habr.com/ru/post/217331/
All Articles