THE CODEBREAKERS

by DAVID KAHN

  The alphabet square is essentially the same as the Vigenère, except that it repeats the normal alphabet on all four sides, so that the square extends 27 letters across and 27 down and has A at all four corners. Its encipherment equals that of a Vigenère with reversed alphabets. The system had been originally proposed almost 150 years before Beaufort by one Giovanni Sestri, in a book published in Rome in 1710 that had been widely ignored. But under Beaufort’s name the cipher became a standard in the repertory of cryptology, though its theoretical importance is minor.

  It has also given rise to a system called the Variant Beaufort. In this, the encipherer starts, not with the plaintext letter but with the keyletter, traces in to the plaintext letter, and then turns upward to emerge at the ciphertext. Actually, the system might better be called the Variant Vigenère, for to decipher it the clerk must perform the operation that constitutes a Vigenère encipherment: find the keyletter on the side and the ciphertext letter at the top, and run into the tableau from both until the plaintext letter is located at the junction. Vigenère and Variant Beaufort thus invert one another—the encipherment of one serves as the decipherment of the other. True Beaufort, on the other hand, is reciprocal within itself, since the same operation of starting with the known letter, tracing in to the keyletter, and rising to find the unknown works for both encipherment and decipherment.

  Two years later, an American who at the time was working for a stove and foundry firm gave, like Beaufort, the merest glance to cryptology. Like Beaufort, the result was a single short piece of work. But unlike the admiral’s, this work opened important new vistas into untrodden lands, and then sank immediately into a cryptologic obscurity as undeserved as Beaufort’s renown.

  The inventor was Pliny Earle Chase, then 39, who, after entering Harvard as a prodigy at 15, taught in Philadelphia for seven years until his health forced him into less tiring work in business. In 1861 he resumed teaching, becoming professor of natural science and then professor of philosophy and logic at Haverford College near Philadelphia. He was an absorbing lecturer, particularly in astronomy, and he collaborated on an arithmetic textbook with Horace Mann. But perhaps his most notable accomplishment was his writing more than 250 articles for scholarly magazines. Among them was the one that he penned in 1859 which covered barely three pages in the new Mathematical Monthly, but which constitutes the first published description of fractionating, or tomographic, cipher systems.

  The basis of these ciphers stretches back across the millennia to Polybius, the Greek historian of the second century B.C. who distributed the alphabet in what is even today sometimes called a “Polybius square,” but more often a “checkerboard.” Numbers at the side and top indicate the row and the column of a given letter. Similar systems have cropped up throughout cryptography. Some replace the alphabet by three symbols in groups of three (a = 111, b = 112, c = 113, d = 121, etc.), some by two in groups of five (a = 00000, b = 00001, c = 00010, etc.). But no one seems to have seen the symbols as manipulable entities instead of just as an unalterable part of the whole.

  Until Chase. He severed the coordinates from one another and subjected the resulting fractions to various cryptographic treatments. He began with a checkerboard filled out to ten columns with Greek letters:

  Chase wrote his coordinates vertically, so that his sample plaintext, Philip, appeared like this:

  He then multiplied the lower line by 9, obtaining the result:

  This he restored to literal form by resubstituting back in his checkerboard, 8 (by itself) = L, J, or T, then 16 = N, 33 = S, 39 = I, and so on, with the final ciphertext LNSIΦIX.

  Chase proposed other means of transforming the bottom row, such as adding a repeating key or giving the logarithm of the row, and pointed out that even more intricate processes might be used. “But the simpler cypher, provided it is effectual, is the better,” he wisely concludes. The Chase systems grant a fairly hermetic security; they are, besides, relatively simple to operate. Yet cryptologic history shows no one ever having used them, even though they are far superior to many systems that have seen service.

  Most remarkable of the Victorian congregation of cryptologists was the Lucasian Professor of Mathematics at Cambridge, the pioneer who enunciated the principles on which today’s huge electronic computers are based and who himself built their prototypes: Charles Babbage. Most of his cryptologic work was never published and hence never played a role in the science, but it was astonishingly advanced. He was among the first to use mathematical notations and formulas in cryptanalysis; he solved polyalphabetics at a time when the system was still regarded as “le chiffre indéchiffrable;” he appears to have been the first to solve an autokey. The few words that he wrote on the subject are pregnant with observations that bespeak an extraordinary grasp of it.

  Born in 1792, he inherited a considerable fortune from his father, a banker. This financed his many interests—studies of railways, archaeology, submarine navigation, occulting lighthouses, tree rings as an indicator of ancient climate, lock picking (for scientific purposes only), what is now known as operational research, and his long, bitter, and totally unavailing campaign against his pet hate—organ-grinders in the streets of London. Babbage was fascinated by statistical phenomena, compiling tables of mortality and logarithms, counting the proportion of letters in various texts, and measuring the pulse and breathing rate of any animals he encountered. Cryptology may have been an offshoot of his statistical interest, which also led to his lifelong attempt to apply machinery to the calculation of mathematical tables. A paper on this at 30 brought him the first gold medal of the Astronomical Society, and Babbage spent the rest of his life trying to realize his vision in his Difference and Analytical Engines. He even resigned his Cambridge professorship after seven years to devote himself more completely to them.

  His problem was that he never finished anything. With his two mathematical machines, he was forever getting new ideas and scrapping all that he had done. The government’s exasperated withdrawal of financial support (which he had largely matched out of his own pocket) because nothing concrete had been accomplished turned Babbage later in life from a social fellow of interesting conversation and a good sense of humor into a bitter man. Though he took his disappointment to the grave at 78, his ideas ultimately triumphed and, in particular, the logical structure of his Analytical Engine remains fully visible in the big electronic computers of today.

  The opening words of the short essay he published on cryptology will ring a familiar bell in the minds of amateurs who have worked until 3 a.m. on a teaser: “Deciphering is, in my opinion, one of the most fascinating of arts, and I fear I have wasted upon it more time than it deserves.” Like his acquaintances Wheatstone and Playfair, Babbage delighted in solving the enciphered personal advertisements that abounded in the newspaper “agony columns;” this may account for his further observation that “very few ciphers are worth the trouble of unravelling them.”

  Babbage is also the only person known to have suffered corporally for his cryptanalyses. It happened at school: “The bigger boys made ciphers, but if I got hold of a few words, I usually found out the key. The consequence of this ingenuity was occasionally painful: the owners of the detected ciphers sometimes thrashed me, though the fault lay in their own stupidity.”

  His reputation for cryptanalytic ability did not wane in later life, though its rewards became less punishing. In July of 1850, he solved a cipher of Henrietta Maria, queen of Charles I, though he turned down the task of solving the seven-page cryptogram of the king, instead recommending Wheat-stone, who succeeded. He solved a note in a kind of shorthand that threw some light on a historical point for the author of a life of John Flamsteed, England’s first Astronomer Royal. On April 20, 1854, barrister S. W. Kinglake wrote Babbage from Lincoln’s Inn asking for help in solving some cryptic correspondence of importance in a case. Babbage undertook the task himself, solved a sheaf of monalphabetically enciphered letters, and read such intimacies as Where is it to en
d and You have had warnin[g] long ago of what I wished.

  During these years he was also solving polyalphabetics. The messages retained their word divisions, and Babbage seized on these to make his entries. For example, in 1846, he broke an enciphered letter from his nephew, Henry, by guessing that it began Dear Uncle and ended with nephew and Henry. The cryptogram was in Vigenère, the key SOMERSET. He demonstrated a lively appreciation of periodicity—the repetition of the key—and, replying to a public challenge, even managed to extricate the two primary keys TWO and COMBINED from a complicated invented cipher that amounted to a double encipherment in Vigenère, first-by one key, then by the other.

  “One of the most singular characteristics of the art of deciphering,” he declared in his autobiography, Passages from the Life of a Philosopher, “is the strong conviction possessed by every person, even moderately acquainted with it, that he is able to construct a cipher which nobody else can decipher. I have also observed that the cleverer the person, the more intimate is his conviction. In my earliest study of the subject, I shared in this belief, and maintained it for many years.

  Charles Babbage uses mathematics to solve a cipher

  “In a conversation on that subject which I had with the late Mr. Davies Gilbert, President of the Royal Society,” he continued, “each maintained that he possessed a cipher which was absolutely inscrutable. On comparison, it appeared that we had both imagined the same law.” This proved to be the use of each cipher letter as the key for the following plaintext letter. Both Babbage and Gilbert had independently reinvented, with a mixed alphabet, the autokey of Cardano and Vigenère—though Babbage readily admitted that “I am not sure that it may not be found in the Steganographia of Schott, or even of Trithemius.” Years later, while explaining the cipher to a friend, “an indistinct glimpse of defeating it presented itself vaguely to my imagination.” He went on to solve it, aided, no doubt, by word divisions, but achieving nevertheless the first autokey solution in history. The mixed cipher alphabet raises this to the level of a substantial accomplishment indeed.

  Babbage most strikingly demonstrated his originality of thought when he applied algebra to cryptology. His papers are filled with formulas which he used to help him solve ciphers and see their underlying structure more clearly. Unfortunately his notes are too scrappy and incomplete to give any more than a tantalizing glimpse of what he was trying to accomplish. His most imposing formula, which he jotted down on worksheets dealing with a numerical cryptogram sent him by Gilbert, is this:

  It may have been as efficacious as it is formidable, but neither an index to its symbolism nor any clue to its purpose exists.

  Babbage’s talents in cryptology appear to have been as exceptional as they were in other fields, and they were crippled by the same defect: the inability to leave off improving and to finish a work despite its imperfections. Had he published any specifics of his cryptanalyses, their insights might have upended the science. But his flaw robbed him of this distinction.

  Of the man who did explode the bomb that gouged new channels for cryptology, little more is known than the bare outline provided by his service record. This is complete if not detailed, for Friedrich W. Kasiski spent his entire professional career as an officer in East Prussia’s 33rd Infantry Regiment. Born November 29, 1805, in what was then Schlochau, West Prussia, and is now Czluchow, Poland, he enlisted in the regiment at 17. He won his commission as a second lieutenant three years later, in 1825—and did not budge out of that rank for 14 years. But he remained a first lieutenant only three years before he was promoted to captain and company commander, a post he held for nine years. He retired in 1852 with the rank of major, and though he served from 1860 to 1868 as the commander of a National Guard-like battalion, he found sufficient leisure to devote some to cryptology, for in 1863 his short but epochal book was published in Berlin by the respected house of Mittler & Sohn.

  Three quarters of Die Geheimschriften und die Dechiffrir-kunst concentrates on answering the problem that had vexed cryptanalysts for more than 300 years: how to achieve a general solution for polyalphabetic ciphers with repeating keywords. (One chapter zeros in on “The Decipherment of French Writing”—a rather ominous portent in a book dedicated to the Count Albrecht von Roon, the Prussian minister of war who molded the army that humbled France only seven years later.) The polyalphabetic solution opened the doors to the cryptology of today. But the 95-page volume seems to have stirred almost no comment at the time. Kasiski himself lost interest in cryptology. He became an avid amateur anthropologist, joining the Natural Science Society of Danzig, unearthing prehistoric graves, and reporting on his work to learned journals. (One of his scholarly articles was cited in the Encyclopaedia Britannica.) Kasiski died on May 22, 1881, almost certainty without realizing that he had wrought a revolution in cryptology.

  That revolution had begun when Kasiski seized upon a phenomenon that Porta and perhaps others had observed but not recognized. This is that the conjunction of a repeated portion of the key with a repetition in the plaintext produces a repetition in the ciphertext:

  Each time that the key RUNR engages the repeated plaintext to be, the repeated ciphertext tetragraph KIOV results. Like causes produce like effects. Similarly, when the repeated key-fragment UN operates upon the repeated th’s, the ciphertext registers repeated NU’s.

  Clearly, the keyword must repeat one or more times for a given part of it to encipher two identical bits of plaintext several letters distant from one another. The number of letters between the two resultant ciphertext repetitions will record the number of times that the keyword has repeated. The count of the interval “between” the two repetitions actually includes repeated letters. Thus the interval between the first KIOV and the second is 9, figured like this: 5 letters not repeated and 4 that are. This interval of nine results from the fact that the keyword has three letters and has repeated three times. These repetitions betray the movements of the keyword beneath the surface of the cryptogram just as the ducking of a fishing cork tells of a nibble. Analysis of the intervals between the repetitions can disclose the length of the keyword.

  Obviously, not all plaintext repeats will show up as ciphertext repetitions. The two ti’s of that is and question do not because they are enciphered by different key digraphs, nor do the st’s of is the and question. Furthermore, repetitions sometimes appear that are no more than the result of coincidence. For example, th keyed by CO will become vv in Vigenère, but so will ir keyed by NE. Two appearances of vv thus do not indubitably reflect a repetition of plaintext th. These spurious indications are usually called “accidental” repetitions in polyalphabetic cryptanalysis to distinguish them from the “true” repetitions, like KIOV.

  Accidental repetitions will naturally give some false clues about the length of the keyword. But since their effect is diffused, whereas that of the true repetitions is concentrated, the real keyword length usually shows up fairly clearly. Knowledge of how many letters are in the keyword tells how many alphabets were used in the polyalphabetic encipherment. This information permits the cryptanalyst to sort the letters of the cryptogram so that all those enciphered with the first keyletter are brought together in one group, all those enciphered with the second keyletter in another group, and so forth. Since all of the, say, e’s in the first group were converted under the influence of a single keyletter to the same ciphertext letter, all of the a’s to one ciphertext letter, and so on, each of these collections of letters constitutes a monalphabetic substitution cipher and so can be solved like one.

  An example using the following cryptogram should make this clear:

  Repetitions of three letters or more have been underlined; bigraphic ones have been ignored here as too frequent, though in shorter cryptograms they are quite valuable. The monoliteral frequency count is:

  It differs strikingly from the count of a monalphabetic substitution. All 26 letters appear several times, while several would be missing from an equally long monalphabetic cryptogram
. No one letter stands out remarkably; the two most frequent reach only 7.7 and 6.3 per cent, compared to the 12 per cent in a monalphabetic substitution. The profile shows no plateaus of high-, medium-, low-, and rare-frequency letters. Instead it descends in a gentle, even slope. These characteristics result from the dispersal of individual letter-frequencies among the several alphabets.

  With the repetitions located, Kasiski advised the cryptanalyst to “calculate the distance separating the repetitions from one another…. and endeavor to break up this number into its factors…. The factor most frequently found indicates the number of letters in the key.” Cryptanalysts usually perform this operation—now called a “Kasiski examination”—in tabular form.

  positions

  repetition first second interval factors

  YVGYS 3 283 280 2×2×2×5×7

  STY 7 281 274 2×137

  GHP 28 226 198 2×3×3x11

  ZUDLJK 52 148 96 2×2×2×2×2×3

  LEEBMMTG 99 213 114 2×3×19

  SEZM 113 197 84 2×2×3×7

  ZMX 115 163 48 2×2×2×2×3

  GEE 141 249 108 2×2×3×3×3

  The most frequent factor is 2, which appears in every instance. But since 2 must be a factor in every even interval, and since keys as short as 2 or 3 letters are extremely unlikely, cryptanalysts usually consider only lengths of and above. In the above list, 4, or 2×2, occurs in five of the eight intervals, in only one, 6 in six, 7 in two, 8 in two, 9 in two, 12 in four, and all others except multiples of these (as 18 and 24) occur but once. At first, 6 seems to be the proper choice on the basis of frequency. On second thought, however, 12 makes an even better showing, considering that a repetition has only half as many chances to show up in a period of 12 as in one of 6. But then the cryptanalyst, checking, sees that the period of 12 would make the 2×3×19 interval of LEEBMMTG an accidental one, which is exceedingly unlikely, and that a period of 6 would keep it as a key-caused repetition. He therefore returns to the period of 6. The behavior of the YVGYS repetition can only be ignored for the moment.