THE CODEBREAKERS

by DAVID KAHN

  27 × 26 × 25 × … × 2 × 1, or 10,888,869,450,418,352,160,768,000,000. Cardano heads a long line of cryptographers in erroneously placing cryptographic faith in large numbers—a line that stretches right down to today. His own example refutes his argument. Cryptanalysts do not solve monoalpha-betics—or any ciphers for that matter—by testing one key after another. With a 26-letter alphabet, 26 × 25 × … × 1, or 403,291,461,126,605,635,584,000,000, different cipher alphabets are possible. If the cryptanalyst tried one of these every second, he would need six quintillion years, or longer than the known universe has been in existence, to run through them all. Yet most monoalphabetics are solved in a matter of minutes.

  The comedy of errors and neglect that constitutes so much of the historiography of cryptology reached a climax of irony when it came to the inventor of the second and acceptable autokey system. It ignored this important contribution and instead named a regressive and elementary cipher for him though he had nothing to do with it. And so strong is the grip of tradition that, despite modern scholarship, the name of Blaise de Vigenère remains firmly attached to what has become the archetypal system of polyalphabetic substitution and probably the most famous cipher system of all time.

  Vigenère was not a nobleman. The “de” in his name simply indicates that his family came from the village of Vigenère or Viginaire. He himself was born in the village of Saint-Pouçrain, about halfway between Paris and Marseilles, on April 5, 1523. At 17, he was taken from his studies and sent to court and, five years later, to the Diet of Worms as a very junior secretary. This gave him his initiation into diplomacy, and his subsequent travels through Europe broadened his experience. At 24, he entered the service of the Duke of Nevers, to whose house he remained attached the rest of his life, except for periods at court and as a diplomat. In 1549, at 26, he went to Rome on a two-year diplomatic mission.

  It was here that he was first thrown into contact with cryptology, and he seems to have steeped himself in it. He read the books of Trithemius, Belaso, Cardano, and Porta, and the unpublished manuscript of Alberti. He evidently conversed with the experts of the papal curia, for he tells anecdotes that he could have heard only in the shoptalk of these cryptologists. There was, for example, the one about the fellow who was not at all embarrassed to ask the Cardinal du Bellay to give him the enormous sum of 2,000 écus for a cipher he had devised—but was redfaced to learn that his system had been solved in less than three hours. Vigenère left the court at 39 to pursue his interrupted studies, but in 1566 he was sent again to Rome as secretary to King Charles IX. Here he renewed his acquaintance with the cryptologic experts, and this time he appears to have been admitted to their secret chambers, for it is he who reports having seen the Great Vicar of St. Peter solve a Turkish cryptogram in six hours. Finally, in 1570, at 47, Vigenère quit the court for good, turned over his annuity of 1,000 livres a year to the poor of Paris, married the much younger Marie Varé, and devoted himself to his writing.

  He turned out some 20-odd books before he died of a throat cancer in 1596. Most of his translations and historical works have fallen into oblivion, though his Traicté des Comètes has been credited with helping to destroy the superstition that comets are fireballs flung by an angry God to warn a wicked world. But the book which is constantly cited by workers in its field is his Traicté des Chiffres, which was written in 1585 despite the distraction of a year-old baby daughter and which appeared, elegantly rubricated, in 1586, and was reprinted the following year.

  It is a curious work. In its more than 600 pages, it distilled not only much of the cryptologic lore of Vigenère’s day (with the major exception of crypt-analysis, which he called, in a quaint phrase, “un inestimable rompement de cerveau”—“a worthless cracking of the brain”), but a hodgepodge of other topics. It contained the first European representation of Japanese ideograms. It digressed into the foundations of alchemy, licit and illicit magic, the secrets of the kabbalah, the mysteries of the universe, recipes for making gold, and philosophic speculations. “All the things in the world constitute a cipher,” its author declared. “All nature is merely a cipher and a secret writing. The great name and essence of God and his wonders, the very deeds, projects, words, actions, and demeanor of mankind—what are they for the most part but a cipher?” And so on. There may be some allegorical truth to this—Pascal himself was to say that the Old Testament was a cipher—but it hardly advanced the science of cryptology.

  Despite these ramblings, the Traicté is reliable in its cryptologic information. Vigenère was scrupulous in assigning credit for material from other authors, and he quoted them accurately and with comprehension. He relished a good story, such as the one about the practical joke played on one Paulo Pancatuccio. Pancatuccio, Vigenère said, had been employed by the pope to solve documents in cipher, “in which in truth he was fairly well versed, and performed several minor miracles of the lesser kind.” Certain “bons compagnons,” wishing to humble his pride, contrived to have a letter in cipher, marked “most important,” fall into Pancatuccio’s hands. The opening words were in a very simple transposition cipher, and Pancatuccio solved it readily, only to read: “O poor wretched slave that you are to your decipherments, on which you waste all your oil and your pains, what does it profit you to eat out your heart in the quest of these vain curiosities, presuming by your laborious researches to be able to attain to the discovery of the secrets of others, which are reserved to God alone?” More in the same vein followed, ending with a challenge to see if Pancatuccio could get at the meaning of “one little letter” of the succeeding message. It was written in a complicated cipher; Vigenère thoroughly described it, but never said whether the indignant Pancatuccio even bothered to try solving it.

  Among the numerous ciphers that Vigenère discussed (such as concealing a message in a picture of a field of stars) were polyalphabetics. Each of his used a Trithemius-like tableau, though Vigenère provided for mixed alphabets at the top and the side. He listed a variety of key methods: words, phrases, lines of poetry, the date of the dispatch, progressive use of all the alphabets. He then put forth his autokey system. Like Cardano’s, it used the plaintext as the key. But it perfected Cardano’s in two ways. First, it provided a priming key. This consisted of a single letter, known to both encipherer and decipherer, with which the decipherer could decipher the first cryptogram letter and so get a start on his work. With this, he would get the first plaintext letter, then use this as the key to decipher the second cryptogram letter, use that plaintext as the key to decipher the third cryptogram letter, and so on. Secondly, Vigenère, unlike Cardano, did not recommence his key with each plaintext word, which is a weakness, but kept it running continuously.

  The system works well and affords fair guarantees of security; it has been embodied in a number of modern cipher machines.

  Vigenère also described a second autokey in which the cryptogram itself serves as the key after a priming key:

  This has the advantage of being an incoherent key but has the great disadvantage of leaving the key in full view of the cryptanalyst.

  In spite of Vigenère’s clear exposition of his devices, both were entirely forgotten and only entered the stream of cryptology late in the 19th century after they were reinvented. Writers on cryptology then added insult to injury by degrading Vigenère’s system into one much more elementary.

  The cipher now universally called the Vigenère employs only standard alphabets and a short repeating keyword—a system far more susceptible to solution than Vigenère’s autokey. Its tableau consists of a modern tabula recta: 26 standard horizontal alphabets, each slid one space to the left of the one above. These are the cipher alphabets. A normal alphabet for the plaintext stands at the top. Another normal alphabet, which merely repeats the initial letters of the horizontal ciphertext alphabets, runs down the left side. This is the key alphabet. Both correspondents must know the keyword. The encipherer repeats this above the plaintext letters until each one has a keyletter. He seek
s the plaintext letter in the top alphabet and the key-letter in the side. Then he traces down from the top and in from the side. The ciphertext letter stands at the intersection of the column and the row. The encipherer repeats this process with all the letters of the plaintext. To decipher, the clerk begins with the keyletter, runs in along the ciphertext alphabet until he strikes the cipher letter, then follows the column of letters upward until he emerges at the plaintext letter at the top. For example:

  This system is clearly more susceptible to solution than Vigenère’s original. Nevertheless, a legend grew up that this degenerate form of Vigenère’s work was the indecipherable cipher par excellence, a legend so hardy that as late as 1917, more than half a century after it had been exploded, the Vigenère was being touted as “impossible of translation” in a journal as respected as Scientific American!

  The cryptanalysts of the time did not create the legend. They knew very well that the cipher was not “impossible of translation”—because they themselves had occasionally translated it. “I may at this point mention,” wrote Porta, “a letter of this sort sent me a while ago by a dabbler in ciphers who lived at Rome. To his surprise, I interpreted it within the very hour I received it—because the key of the message was the proverb OMNIA VINCIT AMOR, which is familiar to almost everybody.” And Giovanni Batista Argenti noted under a Porta-like cipher in his book of cipher keys:

  Qaetepeeeacszmddfictzadqgbpleaqtacui.

  (In principio erat) such is the motto or key* with which the Illustrious and Excellent Signor Iacomo Boncampagni [nephew of Pope Gregory XIII], Duke of Sora, my patron, wrote the above line in cipher and gave it to me Sunday 8 October 1581 in the Tusculana villa, telling me that it was not possible to find it out, and I quickly found out the countercipher which was of 10 alphabets and the motto. The line written above means and is this:

  Arma virumque cano troie qui primus ab oris.

  Matteo Argenti also boasted of solving a test polyalphabetic, but he may simply have been claiming his uncle’s success as his own.

  The modern Vigenère tableau

  Both the Porta and the Argenti solutions owe their success to the easily guessable nature of their keys—a common proverb in one, the first words of the Gospel of St. John in the other. The Argenti solution was further simplified by a plaintext consisting of the first line of Vergil’s Aeneid. Even without these aids, polyalphabetics might occasionally have been solved if several other conditions obtained: if the cryptograms retained original word divisions, if the cipher alphabets were normal, and if the cryptanalyst recognized that keys repeat. He could then guess at words in the plaintext and recover part of the key that would have been used; if it made sense, he would try to guess the rest of it or, failing that, try to decipher other portions of the cryptogram. Such hit-or-miss solutions were not entirely beyond the reach of the Renaissance. Porta recognized key repetition in his artificial solution: “I conclude that the key has been given three times and decide correctly that it consists of 17 letters.” And Vigenère hints at such knowledge when he comments that “the longer the key is, the more difficult it is to solve the cipher.”

  Yet the mere elimination of word divisions would greatly reduce the possibility of striking the right plaintext, and simply mixing the cipher alphabets would deny the Renaissance cryptanalyst any opportunity whatever for solution. The cryptographers of the time ran words together as standard practice, and they knew of techniques for mixing alphabets. Hence they had the power to make polyalphabetics unbreakable to their contemporaries. This explains Matteo’s paean: “The key cipher is the noblest and the greatest in the world, the most secure and faithful that never was there man who could find it out.”

  Why, then, did the nomenclator reign supreme for 300 years after Porta? Why did cryptographers not use this “noblest” and “most secure” cipher instead?

  Apparently because they disliked its slowness and distrusted its accuracy. Encipherment in a polyalphabetic system, with its need to keep track of which alphabet was in use at every point and to make sure that the ciphertext letter was taken from that alphabet, could not compare in speed with a nomenclator encipherment. A former ambassador of Louis XIV, François de Callières, declared in 1716 in his classic manual of diplomacy, De la Manière de Negocier avec les Souveraens, that unbreakability could be attained by “an infinite number of different keys” based upon “a general Model.” “I do not speak,” he added, in an apparent reference to polyalphabetics, “of certain ciphers, invented by professors in a University and upon rules of Algebra or Arithmetick; which are impractical by reason of their too great Length, and of the Difficulties in using them; but of common Cyphers which all Ministers make use of, and with which one may write a Dispatch almost as fast as with ordinary Letters.” The well-informed author of an anonymous 17th-century “Traitté de I’art de deschiffrer” in the Royal Archives at Brussels stated that chancelleries do not use polyalphabetics because it takes too long to encipher them and because the dropping of a single ciphertext letter garbles the message from that point on. In 1819, William Blair, in a superb encyclopedia article on cryptology, likewise argued that polyalphabetic substitution “requires too much time” and that “by the least mistake in writing is so confounded, that the confederate with his key shall never set it in order again.”

  One might think that cipher clerks might have corrected such garbles by trial and error, especially in those more leisurely days. But they were not cryptanalysts and may not have known, or have wanted to know, how to make the necessary trials. Serious garbles would thus render the dispatch unreadable until a courier went out and returned with a correction; thus the cipher would have prevented communication instead of safeguarding it. Garbles of just this type, so bad that messages could not be read, compelled two highly intelligent Americans, both Framers of the Constitution, to abandon the use of a polyalphabetic system.

  Although a lack of speed and a proneness to error kept polyalphabetics from supplanting the nomenclator, they cropped up now and again. The author of the “Traitté” says that they were used in Holland from time to time. On October 12, 1601, the Jesuits sent a numerical polyalphabetic with keyword CUMBRE to Peru for communications with Rome. And, despite the myth of their unbreakability, polyalphabetics were broken occasionally. The Argentis, who would not use them for regular traffic, sometimes gave them to cardinals for personal use. One such was the “cifra con mons. revmo Panicarola apresso l’illmo signor [Enrico] cardinal Caetano legato in Francia, 3 Ottobre 1589. ” Pope Sixtus V had dispatched Caetano to France to further Holy League efforts against Henry IV. The cipher’s first two alphabets, with their key letters at left, were:

  The Argentis made its two keys prudently long (FUNDAMENTA EIUS IN MONTIBIS SANCTIS and GLORIOSA DICENTUR DE TE QUIA POTENTER AGIS), assigned K, X, and Y as nulls, and attached a small nomenclator of letters with dots, macrons, or circumflexes over them. They had considered giving Panicarola a polyalphabetic whose alphabets included the ten digits and so might be considered mixed, but instead settled on this normal-alphabet one—“easier and more secure,” they said.

  It was the cipher’s undoing. The curia used it to tell Caetano in the middle of the following year that Sixtus had died—obviously news of the greatest importance. One of Henry’s Huguenot commanders, chronicling the interception of the messages, wrote that “because the letters were in double cipher* and very difficult, it was necessary to put them in the hands of Chorrin, who disentangled all that had stopped the others and in his time has not had his equal in this perfection.” Chorrin, who was a contemporary of Viète and who, from this feat alone, would appear to be his equal in ability if not in fame, also solved some other letetrs for Henry’s minister of finance, Sully.

  At about the same time, the cipherers of Elizabethan England set sail upon the uncharted seas of polyalphabeticity with Drake-like daring. They employed a Porta-like tableau to correspond with several envoys, and a Vigenère for a Mr. Asheley. Another system comprises
the oldest device of its type in the world. It consists of a vertical strip of stout cardboard on which is written a normal plaintext alphabet. Slits were cut in the cardboard down both sides of the alphabet, and through these slits was inserted a sheet of paper on which ten different cipher alphabets were vertically inscribed. The paper could be moved through the slits so as to bring the desired cipher alphabets against the plaintext one. This facilitated the reading of ciphertext equivalents.

  Writers on cryptology in the 1600s occasionally referred to the solution of polyalphabetics. They did so in vague terms, probably reflecting their own indefinite thinking and the loss of knowledge that let the myth of unbreakability take root. Thus Antonio Maria Cospi, secretary to the grand duke of Tuscany, mentioned in his 1639 La interpretazione delle cifre “two kinds of ciphers, some simple and some composite … the latter practically impossible to discover and decipher.” And later he wrote that “The present method may not be at all useless for the interpretation of the more difficult simple ciphers … no more than for that of double and composite ciphers.” The author of the Brussels “Traitté,” who demonstrated his capability when he solved a French royal cipher for Spain in 1676, floundered when he came to polyalphabeticity. He could only suggest the almost useless technique of trying one probable plaintext letter after another until a coherent combination appeared in the key he derived. Understandably, he did not illustrate his protracted method; the number of combinations is so great that he would be at it yet. His failure contrasts markedly with the technical mastery displayed in the rest of the treatise.