Of the three young Polish recruits joining the Cipher Bureau, Rejewski was the one in whom those in charge had the most confidence. Previously he had spent a year studying advanced mathematics at a German university to prepare himself for a career as an insurance actuary. After four years in which they themselves had made no headway in solving the Enigma, the bureau elders handed Rejewski the task. In addition to the manuals received from Schmidt, all he had to work with were some scraps of paper left over from earlier attacks against the Enigma, an outmoded machine and stacks of intercepts.
Studying these meager resources, Rejewski saw that two enormously complex tasks awaited him. One was to determine the internal wiring of the Germans' military Enigma so that replicas of it could be built. The second was to find a way to match what the German operators did in setting their keys for the day.
He went at the wiring problem first. An obvious beginning, Rejewski recognized, was to reduce the number of unknowns. He concentrated on the procedures the manual set forth for German code clerks to follow in operating their Enigmas. Clerks in all units were to arrange the three rotors on their shaft in the same sequence for a given time period—at that early date, for a quarter year. The clerks also followed daily directions for turning the rotors to their assigned letters as that day's "ground setting" common to all the operators. The instructions then told the clerk the order for coupling the plugboard cables. With all the machines set uniformly, it was left to the individual operator to choose, at random, three letters—the message key—indicating the starting positions for a specific transmission. After using that day's ground setting to encipher his message key twice, the operator was ready to change his rotors to the three letters of his choice and begin encoding the message. The procedure was complicated, but it had the virtue of giving each message its own key and then concealing that key in the enciphered first sequence of six letters—the "indicator."
Rejewski's attention focused on the penultimate step of the instructions: the requirement that the operator tap in the three letters of his message key a second time. As an example, he might type in LTBLTB, and the glow lamps would light up, say, XMYRVO as the indicator to be sent over the air. The Germans' apparent intention in doubling the encipherment of the message key was to guard against garbles in transmission because of radio interference or operator error. The repeat of the three letters gave the receiving operator a second chance to set his rotors correctly in order to convert the scrambled code groups back into German.
Those six letters at the head of each message, Rejewski saw, represented a major flaw in the German system. For in each grouping of letters, the plaintext behind the first letter was the same as for the fourth, the second as for the fifth, and the third as for the sixth.
These relationships held for the entire day's transmissions. Every time an operator began the indicator with L, enciphered into X, his fourth letter was also L, this time enciphered, say, into R. By stacking a series of indicators one beneath the other, Rejewski saw ways to begin sequences of interconnected letters. If, for example, the indicators were
XMYRVO
RTLGAS
he would know that the first and fourth letters Xand R were the same in the plaintext but then, also, that in the next series beginning with an R, the plaintext letter underlying G was the same as R and X. He would link together XRG as the first links in a chain. If an additional indicator was GOVXPW, the appearance of another X, now in the fourth position, would close the loop and complete the chain. Rejewski could assume that all the cipher letters in that chain were the same plaintext letter. Some chains extended for many cipher letters, some for only a few, but in the end, by stacking the first six letters of sixty to eighty intercepts, he would fashion chains covering the whole alphabet. He would repeat the process for the second and fifth linkages and the fourth and sixth. He called the three sets of chains the "characteristics" of that setting.
From the commercial Enigma, Rejewski would have learned that the three rotors worked on different cycles. The right-hand one turned a notch every time a typewriter key was pressed. It was the "fast" rotor. Only after it had gone through an entire twenty-six-letter cycle did it trigger a move in the middle rotor, which in turn had to edge forward twenty-six times before activating the third rotor. Rejewski's quick mind seized upon the fact that while the fast rotor was going through its cycle, the other two rotors and the reflector remained fixed as a single unknown factor that could be disregarded while he solved the wiring of the fast rotor.
He also applied mathematical theory to determine that his chains of letters, his characteristics, were entirely the product of the rotors. The plug board could change the individual letters within a chain but could not alter the number of the chains or their lengths. At least for this part of the crypt-analysis, encipherment by the plugboard could be ruled out.
His characteristics told him the alphabetic substitutions performed for a given day in the six consecutive positions of the indicators. By applying numbers to his characteristics, he used them to set up six complex equations that, if he could solve them, would disclose the fast rotor's wiring sequence. When he tackled the equations, however, he was overwhelmed by too many unknowns. His Cipher Bureau superiors came to his aid. Hoping that Rejewski could solve the Enigma on his own and make the Polish program independent of external help, they had deliberately withheld much of the information they had received from Schmidt. Now they relented and, in early December 1932, gave him a copy of the daily keys for the past months of September and October.
The keys removed one of Rejewski's unknowns—the plugboard connections—and simplified his work on the rest of his equations. Yet they still resisted solution—until it occurred to him that the linkage between the typewriter keyboard and the rotor entry could be the problem. Studying the top row of letters on the typewriter keyboard—QWERTZUIO—he had thought the far-left typewriter keyboard Q connected with the first, or A, position on the input to the fast rotor, that the next letter, W, connected with B, the E with C and so on through the alphabet. This was, after all, the order of pairings in the commercial Enigma. But what if, in their military Enigmas, the Germans had decided on a different order of pairings?
If the connections were randomized, he knew, they would present an almost infinite number of variations, an all but insuperable stumbling block. But what if this was a point at which the Germans' fondness for orderliness, or a desire to make life less complicated for Enigma operators, had prevailed? What if instead of randomizing, the German planners had taken the simplistic course of arranging the connections in straight alphabetical order, keyboard letter A to the A contact on the entry rotor, BtoB and so on through the alphabet?
It turned out that was exactly what they had done. When Rejewski adjusted his equations, he later recalled, "the very first trial yielded a positive result. From my pencil, as by magic, began to issue numbers designating the wiring of drum N"—his "drum" was that rightmost rotor.
The wiring of one rotor had been converted into a known quantity. What about the other two rotors and the reflector? By a stroke of good fortune, Schmidt's two monthly key tables spanned two different calendar quarters. This meant that in the second quarter another of the three rotors was shifted into the right-hand slot. Rejewski could apply to it the same formula he had used on the first rotor. After that, he wrote, "finding the wiring in the third drum, and especially in the reflecting drum, now presented no great difficulties."
Now, with Rozycki and Zygalski assigned to help him, Rejewski was ready to turn over to the Bureau's collaborative electrical firm the details for building a working model of the Germans' military Enigma. He and his coworkers could also use Schmidt's information to begin learning how to decipher German messages.
In his reminiscences, Rejewski describes the scene that unfolded during the last days of 1932. While others were celebrating Christmas, the three young analysts, sleepy, unshaven, exhausted, but very content, placed on their superior's desk the fir
st completely decrypted German army messages enciphered by the Enigma.
Mastering the Daily Key Settings
The Poles now faced a second, equally formidable challenge. They had learned how to reconstruct the Enigma machine, but they still lacked the know-how, without relying on the uncertain largesse from the German turncoat, to determine the daily settings. The messages they had decrypted at Christmastime were from the past, using outdated keys. The test now was to find out how to unravel the current keys and decrypt ongoing traffic.
They had to deal with four keying elements: the order of the three rotors on their shaft; the three letters—one for each rotor—which were that period's "ground setting" common to all operators; the three-letter key the individual operator chose for enciphering a specific message; and the connections of the plugboard cables.
They began their attack on the key settings with the discovery that also eased the way for later analysts: German code clerks misused their machines. Whether from boredom, laziness or overconfidence in the security of their Enigmas, they took shortcuts the Poles were able to exploit.
Faced with the necessity of choosing three-letter combinations as their message keys for every message they sent, as an example, clerks frequently chose not to make random selections but to use repeated letters such as AAA or ZZZ. The letter chains Rejewski derived from indicators tipped him off when the letters of the message key included a repeat. The discovery greatly reduced the number of trials the Poles had to run through in their search for the message key.
When German intelligence officers woke up to the shortcuts the code clerks were taking and issued orders prohibiting repeated letters in key settings, Rejewski was not discouraged. He saw that he could use his letter chains the other way around and rule out any combinations that included a repeat. By the process of elimination extended over a sufficient number of messages, he arrived at the point where only the correct settings were left.
These methods, however, identified only the three rotors' top letters that showed through the windows on the Enigma's lid. They did not reveal which rotor was where. Yet there were only six possible arrangements of the rotors. Rejewski and his colleagues invented an ingenious but laborious process by which they could identify the fast rotor. They used sheets of paper with six slots cut into them marked with the letters from one of Rejewski's chains. They then slid these grilles over tables of the cipher alphabets generated by each rotor, searching for pairings of the letters. Six pairings told them which was the right-hand rotor as well as its starting position. Repeating the process enabled the Poles also to identify the middle rotor, with the remaining rotor obviously going into the third slot.
Use of these techniques was tedious and time-consuming. Rejewski realized his letter chains offered a better way. They differed with each day's setting of the Enigma. Because of the reciprocal nature of the Enigma's wiring connections, the number of chains for each rotor was limited to thirteen (twenty-six letters divided by two). One day's setting might have thirteen chains for each rotor; the next day's could be thirteen, thirteen, twelve, one, and so on through all the various possibilities. He realized that these distinctive patterns were the fingerprints for identifying each day-key. If he and his colleagues could catalog all the variations in the chains and the number of links in each chain, they would have a ready reference with which to determine the ground setting for that day's transmissions. It was a daunting task since there were six variants for the order of rotors multiplied by 17,756 different letter placements on the three rotors (26 x 26 x 26) for a total of 105,456 entries that had to be tracked down and recorded. Still, that total was far less than the billions of permutations the Germans thought they had built into their machine.
Even with all this, the Poles still did not know where the alphabet rings had been set on the rotors. This step had to be taken in order to know where the notch on each rotor was located to trigger the turnover of its neighbor. Rejewski and his colleagues observed that a great many messages began with AN (German for "To") followed by an X used as a word separator. They ran a message through all positions of the rotors in search of ANX. Finding a message with this beginning left "only" 26 x 26, or 676, ring positions to be tested for the other two rotors. That was a lot easier and faster than having to run through all 17,756 possible positions.
Measures such as these enabled the Poles to narrow their unknowns to one: the single-letter substitutions resulting from the plugboard connections. But this test was simpler because in those early days, the German code clerks were instructed to connect only six cables, producing just twelve letter substitutions. Rejewski saw that he could run a test decipherment on one of the Enigma replicas now arriving from the electrical supplier and find passages where the underlying plaintext could be discerned. An example in English could be QEPOQXONXANMQEPAIQ, which sharp eyes could translate into REPORT ON TANK REPAIR, with the plugboard substituting Q for R, X for T and M for K. Other passages revealed the remaining linkages and solved the plugboard in which the Germans placed so much faith.
By grinding through these burdensome procedures each day, the young Poles began reading the German messages and delivering to their superiors glimpses into the Reich military's plans. The process, however, used up most of the day. While that was a far cry from the endless millennia the Germans assured themselves it would take cryptanalysts to break into the Enigma, Rejewski and his mates recognized that their methods of decipherment were too slow to be of practical value. They had to improve the efficiency of the process and greatly increase its speed.
Machines to Defeat the Machine
Time was not the only problem they faced. Although the Germans were confident that their modified Enigmas were impervious to cryptanalysis, they also knew that prudent security precautions called for making changes in their systems periodically. The Poles could not rest on their laurels; they had to deal with a series of changes, each of which could make obsolete the process with which they had been succeeding.
The pressures on the young cryptanalysts were enormously increased by the ascendance of Adolf Hitler and his National Socialist Party. With their military strength on the rise, the Nazis raised an ever-mounting cry to regain their lost lands, particularly the corridor that gave Poland access to the seaport of Danzig, since it separated East Prussia from the rest of Germany.
Rejewski came up with a daring vision: to beat the machine, he and his team would create other machines that would help to find the Enigma keys far more swiftly than they could by their pencil-and-paper methods.
He turned first to that problem of developing a card index of all the 105,456 variations in the letter chains and their linkages. He conceived a device called the Cyclometer, which was designed to automate the process of identifying the characteristic cycles so that the results could be cataloged. It consisted of the interlinked elements of two Enigmas, with twenty-six glow lamps to cover the alphabet. Its function was to determine the length and number of chains in each set of characteristics for all six arrangements of the three rotors. The number of glow lamps that lit up indicated the length of a chain. When, after a year's work, the index was completed, the analysts had only to compare that day's notations on the number and lengths of the chains with the index to pin down the rotor order and settings. Developed in 1934 or '35, the Cyclometer together with the index sped the Poles' cryptanalysis efforts until November 1937.
All this work was then undone when the Germans changed the reversing reflector in the Enigma in a way that voided the Poles' catalog. Rejewski and his team started over, but it took them months to complete a new index and again succeed in decoding German communications.
In mid-September 1938 the Enigma output once more became an incomprehensible jumble. This time the Germans had made their first major change in procedures. Instead of all the operators setting their basic daily key uniformly, the code clerks were now told to choose a new basic setting for each message they transmitted. Their own three-letter choice would be sent
unenciphered at the head of the message and was to be followed by a double encipherment of the message key. Since the Poles could no longer stack indicators to form letter chains, all that painstaking work in compiling cycle indexes went out the window.
The fact that the new procedure called for the German code clerks to continue enciphering their message keys twice was fortunate. The same relative positions of plaintext letters and. cipher letters were there, providing the opportunity to link the first enciphered letter and the fourth, the second and the fifth, and the third and the sixth. Rejewski's response was to invent a new and more complex Cyclometer the Poles named after the ice cream confection they were eating at the moment Rejewski came up with the idea. The desserts, in Polish, were called "bomby," but subsequently the machines became known as "bombes." When the machines were built and began ticking away like a time bomb working its way toward an explosion, the name seemed appropriate.
Each bombe, consisting of six Enigma machines connected together, was capable of swiftly running through the entire cycle of possible permutations, looking for those relatively rare places where, in an indicator, the plaintext letter would have the identical cipher letter, as in WGYWMC. Out of the thousands of combinations, however, the bombe would locate the identical letters in all three 1-4, 2-5, and 3-6 positions. When it found this lineup, it would stop, giving the analysts the information they needed to reconstruct the daily keys.
Yet the determination of the settings did not disclose the order in which the three rotors had been inserted in their Enigma slots—an order which was now also changed daily. Rejewski proposed six bombes to try all six possible rotor sequences in one parallel process.
Codebreakers Victory Page 4