From encryption to Enigma

.

A few days ago I saw on TV the film “The imitation game” https://it.wikipedia.org/wiki/The_Imitation_Game , fascinated by the plot I wanted to know more about, and out came this Article.

We start from the basis of encryption, The cipher Leon Battista Alberti, https://it.wikipedia.org/wiki/Disco_cifrante designed specifically for the Vatican to send data messages to couriers, was composed of a pair of concentric circles of which the fixed outer circle, while the mobile extension. On the outer circle were the numbers 1 a 4 and the alphabet, excluding letters H, J, Q, W and Y that due to their low frequency of use would certainly have weakened the cipher.

In the outer circle so we 24 boxes with the numbers 1 a 4 and the alphabet in order, while in the inner disc, mobile, we have 24 boxes containing the letters in disorder representing the ciphertext (see figure 1).

operation: You choose a capital letter of the outer ring as a fixed index. In this example, the index B is initially subjected the s mobile circle. To indicate the alphabet change is one of four digit numbers.

Now the encoding will

At this point the presence of the with, that figure the number 2, indicates the need to move the discs carrying the z under the B.

The encryption so continue:

The text will be so syamynpfaz zmh&fohmef Another is the aid
elimination of double and spaces between words of the encrypted sentence to
make it even more secure message.

Following the Leon Battista Alberti's studies were taken up by other scholars, that, with mixed success, They sought to perfect as possible the brilliant idea of ​​ciphers polialfabetici.

MACHINES ciphers

Ciphers polialfabetici are the basis of the most famous cipher machines. The most famous ever built cryptographic machine Enigma. Such electromechanical device was the cipher machine made and used by the Third Reich in previous years and during the Second World War. The purpose of this machine was to raise the level of security and make the meaning of the messages unintelligible to unauthorized persons, the machine was worked to “mask” a message that a telegraph operator sent to another, cifrandone content. When an operator was using the machine, typed letters that made up the message on the keyboard and the internal mechanisms of the same through the ignition of

Letter equivalent transformed the text to be transmitted to another seemingly incomprehensible. The decoding makes the same machine at the disposal of the recipient. The discussion starts from the basic operation of the machine, to switch to using historical reality, up to several technical improvements and experiencers devised to solve the problems arising from them. The inventors of this

car were Arthur Scherbius e Richard Knight in 1918. The first, Electrical engineer, put into practice the knowledge acquired at the University of Hannover Ritter and realized with an electro-mechanical reproduction of the cipher by Leon Battista Alberti hard.

ENIGMA OF OPERATION

https://youtu.be/EVvrSjah9t0

The machine has the principles of modular construction, then over time it revealed the possibility of alternative fittings and consequently different operations. The basic version of the device was composed of three groups of components connected to each other with electric wires:

A) a keyboard to enter the plaintext letters;

B) exchanging unit that encrypts the turning point in the corresponding element of the cryptogram by means of a disk system;

C) viewer with various bulbs lighting up the letters indicate the corresponding ciphertext.

In practice, the operator presses the key corresponding to a letter of the plaintext, the machine processes the received electric pulse and illuminates the bulb corresponding to the encrypted letter. The most important part of the machine is the single exchanger, represented by one of 3 disks that form the exchange unit above.

This disc is characterized by 26 conductive notches input and 26 conductive notches outgoing, It is crossed by a dense network of internal wires that combine the inputs with the outputs.

The scheme of the internal wiring of the heat exchanger in practice determines a usable cipher alphabet for a simple substitution cipher in which the pressure

of a button corresponds to the lighting of a bulb indicating the corresponding letter.

The next step of the idea of ​​Scherbius provided to rotate the disk of the heat exchanger of a position after the encryption of each single letter, thus the cipher alphabet changes after each letter transforming monoalphabetic encryption in a Polyalphabetic.

The exchange unit is formed by 3 discs, they are connected two by two through the 26 conductive notches, more upstream of the three discs of the stack there is a hard disk which in turn has 26 notches each connected with the keyboard and with a system of light bulbs, while at the bottom of the stack there is a last disc said riflessore, in which the notches are connected two by two through thirteen internal wires. This means that the electrical circuit is closed each time that fights a keyboard letter, so that through the electrical contacts of the various discs each letter is encrypted seven times, It is seen that the function of riflessore is to reflect the signal back (see figure 8).

The operating rules of the other records in terms of rotation, the second was that He performed a partial rotation only after the former had taken a full turn, and likewise the third was based on the second. In this way the machine could Scherbius have 26x26x26 = 17576 replacement procedures.

We frame the ENIGMA OF OPERATION

The first parameter to be specified is the placement of the heat exchangers according to a certain structure before starting the encryption of a message, this setting was a real key (Figure 6). To encrypt a message Enigma operator would place the heat exchangers according to the daily key, the message typed on the machine keyboard and he sent by radio the result to the receiver. This typed the message encrypted on the keyboard of his Enigma machine, on which the exchangers were arranged according to the same daily key used previously, and he obtained the message clearly. The simplicity with which this operation was due precisely to the introduction of riflessore, This was one of the rapid spread of this system points, use so simple it made it suitable for anyone. The safety achieved with Enigma, He was not given the complexity of the machine, but the high number of combinations that an enemy would have to check for initial set-up. In fact assuming a key to try to minutes it would take two weeks to discover the key of a single day. All this was further improved through two substantial changes, the first change was about the exchangers that were built so as to be removable so that they can be replaced with other or exchange between them. This measure increased the number of keys to a factor of 6, because 3 interchangeable elements can be combined in 6 different ways. The second development was the insertion of a multiple socket panel between the keyboard and the first rotor (see fig. 7).

The sender through such a panel could include some cables with the plugs in order to swap two letters before placing the unit of exchange, the number of possible exchanges were six out of twenty-six letters, then the other twenty letters are not exchanged. We can, then, try to make a summary about the computational complexity of such a machine, in terms of number of key combinations which had to be generated to operate a brute-force attack: exchangers (a rotors) They could orientate each in 26 modi, then all three generated 26x26x26 = 17576 combinations; then inside the unit bitting the three exchangers could be placed in different mutual positions, summarized as follows: 123, 132, 213, 231, 312, 321. They were then allowed 6 different reciprocal positions of the rotors; Finally, with the multiple socket panel the possible combinations of 12 (6×2) letters on 26 are many (to be precise 100.391.791.500). So the total number of keys is obtained by multiplying the above possibilities:

17.576 x 6 x 100.391.791.500 = circa 10 million billion.

Despite being formed by simple elements, therefore, the combination of these latter produced a cipher machine with a high computational complexity of construction complexity is not high. Initially this invention did not obtain a large diffusion, the high cost and no real understanding of the possibilities were the main causes. In the end the German military to prevent the advantage that the Navy had English interception of their encrypted communications during World War II, They decided to adopt Enigma. In 1925 It was organized mass production, and within two decades the German armed forces had at their disposal well 30000 specimens.

THE FIRST ATTEMPT cryptanalysis: IL Cipher Office

The coalition that won the First World War lost interest in the communications of the defeated. The monitoring activity almost stopped completely in 1926, exactly when the start of using Enigma. Only Poland, caught between Germany and Russia, He is occupied to operate a constant and lasting communications monitoring action

Germany. In particular, a special office called Cipher Bureau, the Polish office figures, He took charge of the analysis of the messages and was the first working group set up to deal with the coding operated by Enigma. The work had few encouraging results, at least initially, until November 1931, thanks to an espionage work was able to produce a replica of the military version of the Enigma. The beginning of a very exhausting job as the security offered by Enigma was represented not by the machine itself, but by the very high number of combinations to be monitored daily to find the key. It was later adopted a new key for each message, that message key. This key was transmitted using the alignment key and indicated by daily repeated two times in a row at the beginning of the message, Repeat used to decode Enigma by enemies. So the message key was used to adjust the new configuration of the machine Single Post. For example, if the daily FBK was key and the key message of VHB (both indicate an orientation of the exchangers), the sender operator would VHBVHB typed as the beginning of the message in clear. By encrypting the message we put those letters would become GHUBJE (It should be noted that the first half of the string is different from the latter because Enigma automatically changed the structure of the heat exchangers after each letter). After encrypting the message key, the operator would place the exchangers of VHB and the enciphered message itself. The recipient tuned the car on FBK, the daily key, and he deciphered the first six letters of the message received, then made the key message, He would place the exchangers of VHB and could decipher the text. Following those responsible for the Cipher Bureau They decided to recruit mathematicians to do research to decipher the messages produced by Enigma. They chose these mathematical encryption organizing a course at the University of Poznan, the brightest was undoubtedly the young Marian Rejewski (figure 9).

After a short period of apprenticeship Rejewski was set to work on Enigma. The amazing thing is that within three months thanks to the lightness of the double repetition of the beginning of the communication key message you managed to get on top of the decryption of the first messages. The main repetition in the messages was the key message that was encrypted twice in succession at the beginning of each communication. This meant that the first and fourth letters were closely related to the location of the exchangers, as well as the second and fifth and third and sixth. As messages were intercepted Rejewski new material had to complete a table of correspondence. Thanks to them he managed to decrypt messages in a simple. After Rejewski was able to plan, adapting some of Enigma copies at its disposal, a device that automatizzava the pursuit of daily key quickly checking 17576 combinations to find the positions of the rotors of the exchangers. These devices were called "bombs" and, since the exchangers could be placed in six different needed six "bombs" positions that worked in parallel. As Enigma had represented automating the encryption process, so the "bombs" of Rejewski represented the automatic decryption. At the end of 1938 Poles successes in deciphering the Enigma messages suffered a heavy setback due to the introduction of new measures to increase the safety of the machine. In fact, among the 1938 and the 1939 the Germans changed the encryption rules and increased the number of rotors 3 a 5 so that the method of the Poles lost much of its effectiveness. At that time the decoding of Enigma messages by the office Polish figures were occasional.

With new exchangers the number of combinations to be passed 6 a 60 which the construction of other necessitated 54 "bomb", something that was impossible for the budget of Biuro Szyfrow. Also with the additions to the multiple socket panel exchanged letters went from twelve to twenty of twenty-bringing the number of possible keys 159 billion billion. Later because of the pressure of events when the war became more and more certain after Biuro Szyfrow decided to disclose the progress of Enigma, hitherto secret, so as to enable more powerful and rich allies like France and England, for groped to continue the work, preventing the Germans to find out how successful, so he was born the cryptanalysts of Bletchley Park Group.

BLETCHLEY PARK

In the mid 1939 the cryptanalysis studies were moved to England at a residence in the Buckinghamshire named Blechley Park. In this town it was laid the headquarters of Government Code and Cypher School (GC&CS).

The organization interior was based on a single office that dealt with a topic, then a division was called in "huts". Each hut corresponded a number and a different task, for example at the Shack 6 He competed deciphering Enigma messages. The number of people employed in the service passed the two hundred of 1939 about seven thousand of the end of the conflict. Studies at Capanna 6 were vital, considering that during the Battle of Britain the cryptanalysts were often able to provide the RAF commands the place and the time of German raids. Starting from the notions transmitted by Polish cryptanalysts, English colleagues were able to find other loopholes that facilitated the discovery of key daily, which they called "cillies". A "cilly" Enigma was a flaw not related to the construction of the machine, but to the wrong use that if it was. Many operators were using as a key message of three adjacent letters on your keyboard, which it made it easier to guess the key itself. Other errors were the work of those responsible for the compilation of ciphers that trying to make the keys difficult to predict, imposed limitations on the number of same keys. They established that no one could exchanger occupy the same position for two consecutive days and that each letter should not be confused with the one that precedes and / or follows. These measures led to a reduction of more than fifty percent of number of placements of the heat exchangers and to a considerable facilitation for English cryptoanalysts. The most critical situation is made Enigma cryptanalysis due to the continuous evolution that had the machine in its use, There was a huge effort by all employees of the CG&CS and between the employee who gave the most significant contribution to the defeat of Enigma was Alan Turing, best known for his studies of undecidable problems and its universal algorithmic solver, theoretical anticipation of the modern computers.

Turing had the great insight to establish a new method of cryptanalysis on the fact that many of the messages that were intercepted had a rather rigid structure and it often happened that messages that were transmitted periodically (such as weather forecasts) They had the same words in fixed positions. For example, the first six letters of the second line of some types of messages corresponded to the word "wetter" (weather). This constituted what in the jargon of cryptanalysts was called "crib", ie a fragment of the plaintext that can be deducted on the basis of considerations not cryptanalytic.

Turing focused on a particular crib and again discovered on chain, but they concerned the plaintext letters and encrypted text in a crib.

In figure 13 It is shown a possible crib and its concatenation. Analyzing the concatenation in the figure is possible to identify that nell'assetto "a", Enigma cipher "w" as "E", while nell'assetto "a + 1", Enigma cipher "and" how "T", Finally nell'assetto "a + 3", Enigma cifra "t" come "W". From this simple example Turing developed all the implications of the relationships within the loop and based on this designed an electrical circuit, connecting three Enigma machines with cables laid between the input of a machine and the output of the next following the logic diagram shown in figure 14.

This scheme realized an automatic verification process through the bulb that would be turned on when the correct structure was found. Note that in the figure is shown the circuit diagram of certain connections imposed in the multiple sockets panels, which at the time of cryptanalysis, it is a matter not known, then the circuit must be constructed in such a way as to nullify the effects of the panel to multiple sockets, since only necessary to connect the output of the first group of heat exchangers with the input of the second group at L1. Because this value was not known was necessary to link 26 outputs of the first group with 26 inputs of the second forming 26 circuits, each equipped with a bulb in order to highlight the closure. At the end, discovered the proper orientation of the exchangers, one of the circuits is closed causing the ignition of the bulb. But until now we have not yet considered the possibility of exchange of the rotors. We hypothesize that the exchangers mutassero orientation every second, to complete the operation of all orientations there would took five hours control, more to achieve this control we would need a certain parallelism. So if the rotors used were five and cipher machines available, containing only three with 60 combinations, it was estimated that to control all provisions

It was needed 60 groups of three machines to work in parallel. Another aspect to consider is that in order to determine the structure of the multiple socket panel was necessary to operate from cryptograms partially decrypted. We have outlined the main features of what were called the "Turing bomb", such machines had an average cost of 100000 pounds and were completely realized for the first time for the start of 1940. Each bomb was composed of twelve groups of exchangers Enigma electrically connected. The first prototype did not work very well and the completion of the building coincided with some notable variations in the use of Enigma, mostly he stopped repeating the message keys, This led to the construction of an improved version called the bombs "Agnus Dei".

This version of the Turing bomb had the opportunity to go back to a daily key in sixty minutes maximum, but its operation was not completely autonomous and independent of the staff who used. The main problem of the car was the need to start from a "crib", but it was only on a hypothesis that the cryptanalysts were, imagining that a certain word clearly would be in a certain position. In the event that there was an error in predicting the crib, it was possible to notice that error by analyzing the hypothetical plaintext and ciphertext. To understand the process we make an example, in the crib next the plain text part of the cryptogram but you have the security of having it connected to the correct letters.

The thing that could help to understand that the prediction was wrong, was the alignment between the letters, the riflessore Enigma did not allow a letter to be encrypted as herself, then the example considered, there must be a wrong alignment, since overlap an "e" in clear and an "E" encrypted. Things do not change by moving the first line of a position to the left, But making the shift to the right is an alignment permissible and which could then be used to automatically search for the key daily.

BIBLIOGRAPHY

Museum of Enigma Prof. Tom Perera Ph. D. http://w1tp.com/enigma

Marian Rejewski – An Application of the Theory of Permutations in Breaking the Enigma Cipher – 1977: http://www.impan.gov.pl/Great/Rejewski/article.html

Alan Turing's Life: http://www.turing.org.uk/

On Enigma and a method for its decryption: http://www.cs.miami.edu/home/harald/enigma/

VOTE
0 replies

Leave a Reply

Want to join the discussion?
Feel free to contribute!

Leave a Reply