Weaknesses of the Enigma cipher machine

During World War I, British intelligence agencies monitored German communications very closely, and the information revealed in Churchill's book and the British Admiralty's report was only a scratch. In fact, the telegram of Arthur Zimmermann (German Foreign Minister since 1916) that introduced the United States into World War I was deciphered by the famous British Bureau 40. In this telegram, Germany plotted a Mexican attack on the United States, which ultimately led to the United States' decision to declare war on Germany. But the British used the cover-up method so well that the Germans always thought that Mexico had leaked the secret.

After the war, Britain continued to monitor German communications and maintained a high deciphering rate. But starting in 1926, they began to receive some unintelligible information - ENIGMA was put into use. The more ENIGMA used by Germany, the more messages that Bureau 40 cannot crack. The Americans and French encountered the same situation. They were helpless with ENIGMA. Germany has since had the most reliable communications security system in the world.

The victorious countries in World War I quickly gave up their efforts to decipher this new type of code. Perhaps out of self-confidence, in their view, Germany, bound by the Treaty of Versailles, could no longer cause much harm. Seeing no need to decipher German codes, Allied cryptanalysts slackened, and their minds seemed to be becoming increasingly mediocre. In other fields of science we say that failure is the mother of success; in the field of cryptanalysis we should say that fear is the mother of success. The Franco-Prussian War created a generation of excellent cryptanalysts in France. During World War I, the British were able to decipher German communication codes. The motivation generated by the great fear of failure undoubtedly played a huge role.

History repeats itself again. Because there was one country in Europe that had this great fear of Germany—the newly independent Poland that had risen from the ashes of World War I. To the west is Germany, which is resentful of losing its old territory, while to the east is the Soviet Union, which wants to export its revolution. For Poland, intelligence on these two powerful neighbors was a matter of life and death, and Polish cryptanalysts could not be as fussy as their British, American, and French colleagues—they had to know what the two great powers were thinking. . Under this circumstance, Poland set up its own deciphering agency, the Cipher Division of the Second Bureau of the Polish Army General Staff (Biuro Szyfrow). The high efficiency of the Cryptozoology Department was clearly reflected in the Polish-Soviet War of 1919-1920. Poland, which had suffered repeated military defeats, excelled in cryptanalysis. When the Soviet army came to Warsaw, they deciphered about 400 Soviet messages in 1920. The Poles also maintained a similarly high level of efficiency in monitoring German communications to the west—until 1926, when ENIGMA came on the scene.

The Poles managed to get a commercial ENIGMA machine and roughly figured out its working principle. However, the internal wiring of the military type rotor is completely different from that of the commercial type. Without this information, it would be extremely difficult to decipher the German telegrams. The Poles tried their best, even seeking medical treatment in a hurry, and hired a "master" who was said to have clairvoyance capabilities to remotely sense the circuit diagram of the rotor in the German machine - of course, like all "masters", once they met In this kind of head-to-head matter, even the miraculous clairvoyance doesn't work.

At this time things took a turn for the better.

Hans-Thilo Schimdt (Hans-Thilo Schimdt) was born in a middle-class family in Berlin in 1888. He served as a soldier during World War I. According to the Treaty of Versailles, Germany carried out disarmament after its defeat, and Schmidt was among those laid off. After he retired from the army, he opened a small soap factory and wanted to go to sea to make some money in business. As a result, the postwar economic depression and inflation left him bankrupt. At this time, he was broke, but he still had a family to support.

Contrary to his miserable situation, his eldest brother Rudolph prospered after the war. Like Hans Tiro, he was a veteran of the First World War, but Rudolf was not laid off, but instead rose all the way up.

In the 1920s, he became the head of the German communications department, and it was he who officially ordered the use of ENIGMA in the army. Compared with his elder brother's success, Hans Tiro naturally felt that his face was dull.

But after going bankrupt, Hans-Tiro had to put down his pride and go see his elder brother and ask him to find a position for him in the government department. Rudolf found a place for his second brother in the Chiffrierstelle. This is the command center of ENIGMA, an agency specifically responsible for German cryptographic communications, and has a large amount of top-secret information. Hans-Tiro left his family in Bavaria, where the cost of living was relatively low and they could barely survive. In this way, he moved to Berlin alone, with a pitiful salary, envious and jealous of his elder brother, and deeply resented the society that abandoned him.

You can imagine what happens next. If he sells top-secret information that he can easily obtain to foreign intelligence agencies, he can earn a lot of money that he is in short supply on the one hand, and on the other hand he can take revenge on the country that abandoned him. On November 8, 1931, Schmidt contacted French intelligence agents in Belgium under the alias Asche. In the hotel, he provided the French intelligence agents with two precious pieces of information about the operation of ENIGMA and the internal circuitry of the rotor. Got ten thousand marks. Relying on these two pieces of information, the allies can completely replicate a military ENIGMA machine.

But things are not as simple as imagined. To decipher the ENIGMA code, relying on this information is not enough. A German evaluation of ENIGMA wrote: "Even if the enemy obtains an identical machine, it can still ensure the confidentiality of its encryption system." Even with an ENIGMA, if the key (which is the rotor itself) is not known, (the initial direction, the mutual position between the rotors, and the connection condition of the connecting board), if you want to decipher the message, you have to try billions of combinations, which is unrealistic.

“The confidentiality of the encryption system should only be based on the confidentiality of the key and should not depend on the confidentiality of the encryption algorithm.” This is the golden rule in cryptography. The encryption algorithm can be directly an abstract mathematical algorithm, such as the general DEA and RSA algorithms, or it can be an encryption machine like ENIGMA that implements a certain algorithm or an encryption device such as an electronic chip specially used for encryption, or it can be A compiled encryption program that is executable on a computer, such as PGP (Pretty Good Privacy), which is widely used in Internet communications. Because keeping encryption algorithms secret is difficult. Adversaries can obtain algorithms, encryption devices or programs by stealing or purchasing them. If you get encryption devices or programs, you can reverse engineer them and finally get the encryption algorithm. If only the key is lost, then only the information related to this key is lost, and the confidentiality of future communications can be remedied by changing the key; but if the encryption algorithm is lost, and the confidentiality of the entire system is based on the secret of the algorithm Sexually speaking, all information encrypted by this algorithm will be exposed. Even worse, in order to keep future communications private, the encryption algorithm must be completely replaced, which means updating the encryption equipment or changing the program. This requires a lot of wealth and management resources compared to simply changing keys (large-scale replacement of encryption equipment and programs will give adversaries more opportunities to take advantage of the situation!).

As mentioned before, the design of ENIGMA made it impossible for the French who had learned its secrets to do anything. French cryptanalysts concluded that the cipher was unbreakable. They didn't even bother to copy an ENIGMA based on the intelligence they obtained.

A military cooperation agreement was signed between France and Poland. Poland has always insisted on obtaining all information about ENIGMA. Since it seemed that there was no use holding it themselves, the French handed over the information they bought from Schmidt to the Poles. Unlike the French, deciphering ENIGMA is crucial to Poland, and even a dead horse must be treated as a living horse doctor. Now they can finally take the first step.

In the information about ENIGMA provided by Schmidt, there is not only a description of the structure of ENIGMA and the internal wiring of the rotor, but also the specific regulations of the Germans using ENIGMA for encoding. Every month, the operator of each ENIGMA machine will receive a new key book for that month, which contains the keys used every day of the month. For example, the key for the first day can look like this: 1. Connection of the connection board: A/L-P/R-T/D-B/W-K/F-O/Y. 2. The order of the rotor: 2, 3, 1; the initial direction of the rotor: Q-C-W.

When the operator wants to send a message, he first finds the above information from the keybook. Then according to the above regulations, first connect the letters A and L, P and R on the connecting board with wires; then put the No. 2 rotor on the first rotor position of ENIGMA, and put the No. 3 The rotor is placed in the second position and rotor No. 1 is placed in the third position; finally, he adjusts the direction of the rotor (you can see from the photo that there is a circle of letters engraved on the side of each rotor to indicate The direction of the rotor), so that the letters Q, C and W on the three rotors are facing upwards. On the other side of the receiving party, the operator also makes the same preparations (he also has the same key book), and can then receive and decode the message.

After adjusting ENIGMA, the operator can start encrypting plaintext. But we see that there is only one key every day. If hundreds of telegrams on that day are encrypted and sent with this key, the enemy who secretly intercepts the signal will obtain a large amount of information encrypted with the same key. This is important for keeping secrets secret. Not a good sign for work. We remember that in the case of simple substitution of ciphers, if the cryptanalyst can obtain a large number of ciphertexts, they can be broken using statistical methods.

Although it is not known whether similar statistical methods can be used for ENIGMA, the Germans still keep an eye on it. They decided not to directly encrypt the plaintext to be sent after adjusting the ENIGMA machine to the day's key. Instead, a new key is sent first. The connection sequence of the connecting board and the rotor does not change, and is the same as the common key of the day; conversely, the initial direction of the rotor will be changed. The operator first adjusts the ENIGMA according to the day's key as described above, and then randomly selects three letters, such as PGH. He typed PGH twice on the keyboard and encrypted it into, for example, KIVBJE (notice that PGH was encrypted into different forms twice, the first time KIV and the second time BJE. This is the characteristic of ENIGMA, it is a Double substitution password). Then he wrote KIVBJE at the beginning of the message. Then he readjusted the initial directions of the three rotors to PGH, and then officially encrypted the plaintext.

In this method, each message has its own three keys representing the initial direction of the rotor. Entering the key twice is to prevent accidental sending or receiving errors and plays an error correction role. After the receiving party adjusted the ENIGMA machine according to the key of the day, he first entered the first six letters of the ciphertext, KIVBJE, and decrypted it to obtain PGHPGH, thus confirming that there was no error. Then adjust the initial directions of the three rotors to PGH, and then you can officially decrypt the remaining ciphertext.

If you do not use a different key for each message, then there will probably be thousands of messages, that is, messages of millions of letters, encrypted with the same key every day. With the method that each message has its own key, the keys encrypted on that day are only a few tens of thousands of letters, and these letters are randomly selected, which is different from the nature of meaningful messages, and it is impossible to use statistics Method deciphering.

At first glance this approach seems impeccable. But the Poles were determined and had to tear a hole in the thick armor.

Before this, cryptanalysts were usually linguistic geniuses, proficient in the analysis of linguistic features.

But since ENIGMA is a mechanical encryption device, the Cryptozoology Department of the Second Bureau of the Polish General Staff considered whether a person with a scientific mind would be more suitable for its deciphering work?

In January 1929, Professor Zdzislaw Krygowski, head of the Department of Mathematics at the University of Poznan, compiled a list of the best mathematicians in the department. , on this list, there are Marian Rejewski, Jerzy Rozycki and Henrik Zogars, who will later be called the "Three Polish Masters" of cryptography research. Henryk Zygalski. The University of Poznan was not the most famous university in Poland at the time, but it was located in southern Poland, which was German territory until 1918, so all these mathematicians could speak fluent German.

Among the three mathematicians recruited by the Cryptozoological Bureau, Rejevsky performed the best. At that time, he was a 23-year-old young man with a pair of myopic glasses and a slightly shy face. His major in college was statistics, and he planned to work in the insurance industry in the future. Perhaps before that, he had never thought that he would show off his skills in cryptanalysis. After a short period of cryptanalysis training, he devoted all his energy to cracking ENIGMA.

Rejevsky knows that "repetition is the enemy of passwords." In the ENIGMA cipher, the most obvious repetition is the first six letters of each message - it is encrypted by repeating the three-letter key twice. The Germans did not expect that this would be the weakness of the seemingly impregnable ENIGMA defense line.

The first six letters of each German cipher text are the three letters of the letter's key repeated twice, encrypted by the key of the day. For example, if the key of this letter is ULJ (which is temporarily randomly selected by the operator when starting to encrypt the plaintext), then the operator first encrypts ULJULJ with the common key of the day and obtains the encrypted sequence of six letters, for example PEFNWZ, then use ULJ as the key to encrypt the text, and finally put PEFNWZ in front of the encrypted text, and send it to the recipient via telegram.

Rejevsky received a large number of intercepted German telegrams every day, so he could get many such six-letter strings in a day, all encrypted by the same day's key. For example, he received four telegrams, and the first six letters of each telegram were: the first telegram: L O K R G M; the second telegram: M V T X Z E; the third telegram: J K T M P E; and the fourth telegram: D V Y P Z X. For each telegram, its first and fourth letters are encrypted from the same letter. Similarly, the second and fifth letters and the third and sixth letters are also encrypted from the same letter. The letters are encrypted. For example, in the first telegram, the letters L and R were encrypted from the same letter. The reason why this letter was first encrypted into L and then into R is because the rotor rotated forward three letter positions during this period.

From the fact that L and R are encrypted from the same letter, Rejewski has a clue to determine the initial position of the rotor. When the rotor is in this initial position, the letters L and R are closely related in a sense. The large number of intercepted messages every day could give many of these close connections, allowing Rejevsky to eventually determine the initial position of the rotor. In the second, third, and fourth telegrams above, we see that M and p>If Rejevsky can get enough telegrams every day, he can complete the above relationship table:

The fourth letter: FQHPLWOGBMVRXUYCZITNJEASDK

Based on this alone Corresponding to the table, Rejewski still had no way of knowing the common key for the day. But he knew that this form was determined by the common key of the day, and only by it.

If the keys are different, then the table should also be different - so, is there a way to deduce the common key for that day from this correspondence table? Rejewski took a closer look at such tables. Starting from the letter A, it is corresponding to F; and F is corresponding to W in this table, and then it is corresponding to A. We are back to the first letter, so there is a cycle of letters. Circle A→F→W→A. If all letters are considered, Rejewski can write out all the cycles of this correspondence table: A→F→W→A.

The 3-letter cycle B→Q→Z→K→V→E→L→R→I→B; the 9-letter cycle C→H→G→O→Y→D →P→C; 7-letter cycle J→M→X→S→T→N→U→J.

Here we only consider the correspondence table formed by the first and fourth letters of the 7-letter cycle. Similarly, for the correspondence table formed by the second and fifth letters, and the third and sixth letters, we can also write a similar letter cycle. Since the key is different every day, Rejewski gets different loops.

Rejewski observed that these loops vary in length. This gave him an important inspiration: Although these loops are caused by the key of the day, that is, the position of the rotor, their initial direction, and the substitution of letters on the connecting plate, the number of loops in each group and the number of each loop are The length of the circulation loop is only determined by the position of the rotors and their initial orientation, and has nothing to do with the exchange of letters on the connecting plate!

Assume that in the above example, the letters S and G on the terminal board are originally connected by a wire. The position of the rotors and their initial orientation remain unchanged. If this connecting line is removed and the letters T and K are connected together, the corresponding table of the first and fourth letters will become:

The first letter: ABCDEFGHIJKLMNOPQRSTUVWXYZ, the fourth letter: FQHPLWKSBMNRXUYCZIOVJEAGDT (the original G corresponds to O, and S corresponds to T. After removing the connection between G and S, G corresponds to T, but T is connected to K by a new connection, so G ultimately corresponds to K. Other affected letters are H, K, S, T, X, and Z). The cycle table becomes: A→F→W→A.

The 3-letter cycle B→Q→Z→T→V→E→L→R→I→B; the 9-letter cycle C→H→S→O→Y→D →P→C; 7-letter cycle J→M→X→G→K→N→U→J.

The letters in some of the seven-letter loops have changed, but the number of loops remains four, and the length of each loop has not changed. Applying the theory of permutation transformation, Rejevsky can rigorously prove mathematically that this is true for any change in connection.

This is a very significant development. We know that if we want to forcibly try all the keys to crack the ciphertext, we have to try as many as one hundred billion keys; but ENIGMA's huge number of keys are mainly provided by the connection board. If we only consider There are only 105,456 possibilities for the position of the rotors and their initial orientation. Although this is still a large number, it is already achievable to test all possibilities.

The Poles copied the ENIGMA prototype based on the information provided by Hans-Tiro Schmidt. By 1934, they had more than a dozen Polish-made ENIGMAs. Rejewski and his colleagues worked in front of ENIGMA every day, testing different positions and initial directions of the rotor one after another, and then generated corresponding letter correspondence tables and constructed corresponding letter cycles, and recorded them .

For example, one of the records can be like this: There are 4 loops in the correspondence table between the first and fourth letters, with lengths of 3, 9, 7, and 7 respectively;

The second and fifth letters There are 4 loops in the correspondence table, with lengths of 2, 3, 9, and 12 respectively;

There are 5 loops in the correspondence table for the third and sixth letters, with lengths of 5, 5, and 5 respectively. , 3, 8;

After all 105456 rotor positions and initial directions are recorded, it will be easier to decipher the ciphertext generated by ENIGMA. First, we must obtain enough telegrams of the day to construct a letter correspondence table and write the letter cycles; then retrieve the corresponding rotor position and initial direction from the record table based on the number of cycles and their length: this is the key of the day (The condition of the connection board is unknown). The number and length of cycles can be regarded as the "fingerprint" of the key - by establishing a key "fingerprint" file, Rejewski can find the day's key in a timely manner. By separating the state of the rotor from the state of the connecting plate, Rejevsky greatly simplified the task of deciphering ENIGMA. It took a full year to build such a file, and the work was so hard that sometimes the staff's fingers were bruised.

It must be pointed out that the above introduction to Rejevsky’s work is extremely simplistic, and only the most important ideas are introduced in the form of examples. Rejevsky's analysis of ENIGMA is one of the most important achievements in the history of cryptanalysis. The entire work is strictly mathematical (solving equations about permutation matrices) and is by no means included in the examples cited above. For example, after finding the rotor status of the day's key, you also need to find the connection board status before you can truly decode the ciphertext. In addition, the circuits in the rotor in ENIGMA are not always fixed. Rejevsky's theory allows the internal wiring state of the rotor to be deduced from the ciphertext and key. Even the intelligence provided by Schmidt did not clearly indicate the internal wiring status of the rotor. One of Rejevsky's important tasks was to successfully determine that the letters on the military ENIGMA rotor were arranged in alphabetical order, rather than in alphabetical order as in the commercial version. That way, the letters are arranged in the order they appear on the keyboard. It should also be pointed out that Rejevsky's colleagues, especially two other mathematicians, Rozoki and Zogarski, also made important contributions in the deciphering work. Zogalski also designed a method to quickly query the status of the rotor corresponding to a certain type of letter cycle by drilling holes in paper.

With the efforts of Rejewski and his colleagues, the Polish intelligence service successfully mastered a large amount of German intelligence in the following years. It is estimated that in more than six years from January 1933 to September 1939, the Polish side deciphered nearly 100,000 German messages. The most important of them was the resumption of German military forces in the Sudetenland region. Deployed intelligence, which is a great threat to Poland's security. The cracking of ENIGMA is top secret even within the leadership of the Second Bureau of the General Staff. Officers will receive intelligence labeled "Wicher" (the code name for deciphering ENIGMA operations). They are told that this intelligence is absolutely reliable, but The source is top secret. In 1934, Nazi German Field Marshal Hermann Goering visited Warsaw. He had no doubt that the Poles had his secrets. As he and senior German officials laid wreaths at the Tomb of the Unknown Soldier near the Polish code station, Rejewski was watching them through his office window, ecstatic that he had access to their most secret communications.

When the Germans made a slight change to the ENIGMA rotor wiring, the key "fingerprint" file that took a year to build became useless. But Rejewski and Rozowski had a better idea. Based on ENIGMA, they designed a machine that can automatically verify all 26*26*26=17576 rotor directions. In order to test all possible position arrangements of the three rotors at the same time, 6 identical machines are needed (so that You can try all 17576*6=105456 rotor positions and initial directions).

All six ENIGMAs and other equipment designed to work together form a machine about one meter high that can find the key of the day within two hours. Rozocchi named it "La Bomba" (La Bomba), probably because of the deafening sound it made when running; but some people also say that the idea of ??building such a machine came from Rejevsky once having a meal called "La Bomba" in a restaurant. "The ice cream comes to mind. In any case, the Bomb mechanized cryptanalysis and was a natural response to ENIGMA's mechanical encryption.

For most of the 1930s, Rejevsky and his colleagues were constantly engaged in the search for keys and, from time to time, repairing malfunctioning "bombs." What they didn't know was that in the drawer of Major Gwido Langer, the head of the Cipher Division, there was already what they were racking their brains trying to find.

In fact, after providing two extremely important pieces of information about ENIGMA, Hans-Tiro Schmidt continued to provide intelligence about German communications to French intelligence agencies. In the seven years after 1931, he contacted French intelligence agents twenty times, each time providing a number of German communication code books, which recorded the keys used for each day of the month. President Hans-Tiro Schmidt provided the password for thirty-eight months. Major Rangel obtained these codebooks through Captain Guistav Bertrand, head of the French Code Division ("Second Section"). If Rejevsky could know these codes in advance, it would undoubtedly save a lot of time and carry out other equally important deciphering work.

But Major Rangel felt that Rejewski's team should get used to working alone so that they could also decipher ENIGMA when the codebook was not available in the future. We do not know whether Rejevsky would have been able to have the important work described above without such pressure since 1931.

The Polish Cipher Bureau's deciphering capabilities reached their limit in December 1938, and the Germans strengthened ENIGMA's encryption capabilities. Two optional rotors are added to each ENIGMA machine. It turns out that there are 6 different arrangements of the three rotors. There are 5*4*3=60 ways to select three of the five rotors and install them into the machine. This means that to achieve the original efficiency, 60 machines in the "bomb" must be running at the same time, instead of the original 6. The cost of building such a "bomb" was fifteen times the total budget of the Cryptozoological Service! In January 1939, the number of wires on the connector board was increased from six to ten, leaving only six letters that would not be swapped. The total number of keys has reached 159 trillion, which is 15900 times the original number.

Although the Polish mathematicians succeeded in deducing the wiring status in the fourth and fifth rotors, Rejewski also proved that ENIGMA was not as German or Allied cryptanalysts imagined. It was so indestructible, but his method finally didn't work. At this time, Major Rangel should have taken out the code book provided by Schmidt from his drawer - but just when the Germans were increasing the number of rotors, Schmidt stopped communicating with the French intelligence agency. For seven years, Schmidt continued to provide the Poles with keys that they could decipher on their own. The Poles desperately needed these keys, but they could no longer get them.

This is a fatal blow to Poland. Because ENIGMA was not only a means of German secret communications, but also the key to Hitler's "blitzkrieg". The so-called "blitzkrieg" is a large-scale and rapid coordinated operation. Armored units, infantry, and artillery must be able to communicate quickly and confidentially. Not only that, the ground force's attack must also be supported by a group of Stuka bombers, and there must also be reliable means of communication between them. The power of blitzkrieg lies in: rapid attack guaranteed by fast communication.

If Poland did not have access to German communications, it was hopeless to resist a German invasion, which now seemed likely to happen within months.

On April 27, 1939, Germany tore up the non-aggression pact with Poland and invaded the Sudetenland; anti-Polish voices in Germany continued to rise. Under this circumstance, Major Rangel decided to tell his colleagues about the deciphering method of ENIGMA, which until now has been kept secret from the Allies, so that after Poland was invaded, the Allies with greater manpower, material and financial resources could continue to crack down on Regeffs. based research methods.

Major Langer called his British and French counterparts and invited them to come to Warsaw to urgently discuss matters related to ENIGMA. The British and French cryptanalysis experts arrived at the headquarters of the Polish Cryptographic Service and had no idea what medicine the Poles were selling. Ironically, the language used to communicate in this meeting was...German - the only language understood by all three parties present. Major Ranger led them to a room where there was something covered by a black cloth. When the black cloth was lifted, the British and French cryptanalysts were stunned. What appeared before them was a Rejevsky "bomb". When they heard about Rejewski's method of deciphering ENIGMA, they realized that Poland was at least ten years more advanced than any country in the world in cryptanalysis. The French were particularly surprised. They thought that the information they had received was of little use, so they generously passed it on to the Poles, but they kept it secret from the Poles. The gratitude of the British and French cryptanalysts to their Polish colleagues was beyond words. Up to that time, they had made no progress in deciphering the German ciphers.

Major Rangel’s final surprise to the British and French cryptanalysis experts was to announce that he would give them two replicas of ENIGMA and the drawings of the "bomb". They were designed by Bertrand of the French Cryptographic Department (he was a major). ) to Paris via diplomatic parcel. On a ferry crossing the English Channel were two seemingly ordinary passengers: British writer Sacha Guitry and his wife, actress Yvonne Printemps. But hidden in their suitcase was Britain's top secret at the time: an ENIGMA made in Poland. In order to avoid the eyes and ears of the ubiquitous German spies, ENIGMA came to the UK, where its complete destruction awaited it.

Two weeks later, on September 1, 1939, Hitler launched the "Blitzkrieg" to invade Poland. On September 17, the Soviet Union invaded Poland. On September 28, the German army occupied Warsaw and Poland ceased to exist.