< PREV | NEXT > | INDEX | SITEMAP | GOOGLE | LINKS | UPDATES | BLOG | EMAIL | $Donate? | HOME

[2.0] Refining The Art

v2.3.2 / chapter 2 of 13 / 01 oct 14 / greg goebel / public domain

* The invention of frequency analysis made simple monoalphabetic substitution ciphers much too easy to crack, and led cryptographers to design new and more formidable codes and ciphers over the next centuries; the contest between codemaker and codebreaker escalated to a higher level. In the meantime, the general public began to recognize the use of codes and ciphers, and simple cryptosystems came into popular use.


[2.1] CRYPTANALYSIS ARISES IN THE WEST
[2.2] POLYALPHABETIC SUBSTITUTION CIPHERS / THE VIGENERE CIPHER
[2.3] OTHER CIPHER REFINEMENTS
[2.4] CIPHERS GO PUBLIC

[2.1] CRYPTANALYSIS ARISES IN THE WEST

* The Arab world was well ahead of the West in cryptanalysis, but in European monasteries, monks engaged in analysis of Biblical texts kept interest in cryptology alive in the West. Their interest was provoked partly by the fact that the original Hebrew sources of the Old Testament actually include enciphered words, though more as a literary gimmick than to keep secrets. These enciphered words use a simple monoalphabetic substitution cipher known as "atbash", which involves a straightforward reversal of letters in the alphabet. For example, in English, atbash would involve exchanging "A" and "Z", then "B" and "Y", then "C" and "X", and so on. For a specific example, the Book of Jeremiah refers to the kingdom of "Sheshach", which in Hebrew script is the atbash ciphertext for "Babel".

By the 13th Century, the English polymath and monk Roger Bacon had written the first known European book to discuss cryptography, EPISTLE ON THE SECRET WORKS OF ART AND NOBILITY OF MAGIC, and by the next century ciphers were in common use by alchemists and scientists as a means of concealing their findings. These ciphers often used custom-designed symbol sets instead of letters, which were not particularly inconvenient in the days when documents were generally hand-written. Such symbol sets didn't provide much added security, since frequency analysis could crack ciphers based on them just as easily as ciphers based on ordinary letters. They still show up in modern puzzles.

By the 15th and 16th centuries, ciphers had become extremely important for diplomatic communications, and the art of frequency analysis had been reinvented in Europe. The first famous European codebreaker was Giovanni Soro, who was appointed as the Venetian cipher secretary in 1506. He earned a great reputation for cracking ciphers for Venice, the Vatican, and other Italian city-states.

The French codebreaking tradition began with Philibert Babou, who was followed by Francois Viete. Viete was so successful in cracking Spanish ciphers that the Spaniards asked the Vatican to put Viete on trial for being in league with the devil. The request led to widespread mockery of the backwardness of the Spaniards.

* Cracking ciphers by frequency analysis was still unusual in Europe. Many states continued to use simple monoalphabetic substitution ciphers, but there were cryptographers who realized the weakness of such ciphers and looked for something better.

They added codewords under a cipher, generally a only a limited number of codewords to replace a selected set of important words instead of all the possible words. This reduced the effort of creating and distributing codebooks. This scheme is known as a "nomenclator", and at least in its original form it wasn't very secure, since the codewords could be inferred from context by a clever cryptanalyst once the rest of the message was decrypted. Nomenclators were very popular until well into the 19th century, evolving to include so many entries that they became very much like codes. Early nomenclators had a one-part organization, but in time they acquired a two-part organization for greater security.

* Codemakers also used misspelt words and "nulls" in messages. Nulls involve seeding a ciphertext with unused symbols. Suppose that a cipher uses the numbers 00 through 99 to represent text. Even if numbers and punctuation are enciphered, that leaves a unused subset of numbers, and these unused numbers or nulls could be littered through the ciphertext. They were simply ignored when the text was deciphered.

Misspelt words or nulls would slow down but not stop a cryptanalyst, and governments became increasingly aware that their ciphers were no longer secure. This lesson was brought home in 1587, when Mary, Queen of Scots, was executed by Queen Elizabeth I of England. Mary was condemned on the basis of evidence obtained from enciphered messages cracked by Thomas Phelippes, in the employ of Elizabeth's Principal Secretary, Sir Francis Walsingham. Phelippes was able to crack a cipher used by Mary and conspirators who wanted to place her on the English throne, even though the cipher contained nulls and codewords. Mary was beheaded and the conspirators put to death by torture.

BACK_TO_TOP

[2.2] POLYALPHABETIC SUBSTITUTION CIPHERS / THE VIGENERE CIPHER

* More secure ciphers were in fact available by this time. The basic idea was devised sometime in the 1460s by a polymath from Florence, Italy, named Leon Batista Alberti. Alberti is a pivotal figure in the history of cryptology. He was the first Westerner to publish an explanation of the use of frequency analysis for breaking ciphers, and he was the first known person to suggest the concept of superencipherment, or enciphering a code. Most significantly, he was the first person to hit on the idea of enciphering a message using multiple cipher alphabets. For example, two substitution cipher alphabets could be defined and used on alternating letters of a plaintext, with all the even-numbered letters enciphered by one cipher alphabet and all the odd-numbered letters enciphered by the other.

The idea of such a "polyalphabetic substitution cipher" was refined for over a century, until a French diplomat named Blaise de Vigenere turned it into the simple and elegant cipher scheme that bears his name. A Vigenere cipher uses 26 substitution ciphers, organized using a "Vigenere square" as shown below, with some spacing added to make it legible:

        a bcd efgh ijk lmno pqr stuv wyxz

   01:  A BCD EFGH IJK LMNO PQR STUV WXYZ
   02:  B CDE FGHI JKL MNOP QRS TUVW XYZA
   03:  C DEF GHIJ KLM NOPQ RST UVWX YZAB
   04:  D EFG HIJK LMN OPQR STU VWXY ZABC
   05:  E FGH IJKL MNO PQRS TUV WXYZ ABCD
   06:  F GHI JKLM NOP QRST UVW XYZA BCDE
   07:  G HIJ KLMN OPQ RSTU VWX YZAB CDEF
   08:  H IJK LMNO PQR STUV WXY ZABC DEFG
   09:  I JKL MNOP QRS TUVW XYZ ABCD EFGH
   10:  J KLM NOPQ RST UVWX YZA BCDE FGHI
   11:  K LMN OPQR STU VWXY ZAB CDEF GHIJ
   12:  L MNO PQRS TUV WXYZ ABC DEFG HIJK
   13:  M NOP QRST UVW XYZA BCD EFGH IJKL
   14:  N OPQ RSTU VWX YZAB CDE FGHI JKLM
   15:  O PQR STUV WXY ZABC DEF GHIJ KLMN
   16:  P QRS TUVW XYZ ABCD EFG HIJK LMNO
   17:  Q RST UVWX YZA BCDE FGH IJKL MNOP
   18:  R STU VWXY ZAB CDEF GHI JKLM NOPQ
   19:  S TUV WXYZ ABC DEFG HIJ KLMN OPQR
   20:  T UVW XYZA BCD EFGH IJK LMNO PQRS
   21:  U VWX YZAB CDE FGHI JKL MNOP QRST
   22:  V WXY ZABC DEF GHIJ KLM NOPQ RSTU
   23:  W XYZ ABCD EFG HIJK LMN OPQR STUV
   24:  X YZA BCDE FGH IJKL MNO PQRS TUVW
   25:  Y ZAB CDEF GHI JKLM NOP QRST UVWX
   26:  Z ABC DEFG HIJ KLMN OPQ RSTU VWXY

        a bcd efgh ijk lmno pqr stuv wyxz

This defines 26 different Caesar shift ciphers, each of which is weak in itself but which in combination result in a much more secure cipher. 26 different mixed instead of shifted cipher alphabets could also be used to improve security, but for simplicity we'll assume Caesar shift ciphers here.

The idea in the Vigenere cipher is to use a cipher key to select different cipher alphabets in succession as letters are enciphered. Suppose Alice wants to encipher the phrase:

   use the force luke

-- with a Vigenere cipher, using the cipher keyword "WARTHOG". All she has to do is scan down the square defined above and look for the cipher alphabet starting with "W", which is be number 23 in the list. In this cipher alphabet, the letter "u" is enciphered as "Q".

Next, she looks for the row starting with "A", which is number 01 in the list. This cipher alphabet is the same as the plaintext alphabet, so "s" remains "S". Enciphering the entire message in this way:

   W: cipher alphabet 23 gives  u -> Q
   A: cipher alphabet 01 gives  s -> S
   R: cipher alphabet 18 gives  e -> V
   T: cipher alphabet 20 gives  t -> M
   H: cipher alphabet 08 gives  h -> O
   O: cipher alphabet 15 gives  e -> S
   G: cipher alphabet 07 gives  f -> L
   W: cipher alphabet 23 gives  o -> K
   A: cipher alphabet 01 gives  r -> R
   R: cipher alphabet 18 gives  c -> T
   T: cipher alphabet 20 gives  e -> X
   H: cipher alphabet 08 gives  l -> S
   O: cipher alphabet 15 gives  u -> I
   G: cipher alphabet 07 gives  k -> Q
   W: cipher alphabet 23 gives  e -> A

-- gives:

   QSV MOS LKRTX SIQA

Simple frequency analysis cannot crack a Vigenere cipher, and the number of possible keys is so great that finding the right key by trial-and-error is effectively impossible.

Vigenere published a description of his cipher in 1586. Despite the simplicity and elegance of the Vigenere cipher, it was generally ignored for the next several centuries, mostly because it was regarded as too cumbersome for general use. Military forces in battle need to encipher and decipher messages quickly, and a Vigenere cipher was just too troublesome under the circumstances.

BACK_TO_TOP

[2.3] OTHER CIPHER REFINEMENTS

* Although polyalphabetic substitution ciphers were regarded as troublesome, monoalphabetic substitution ciphers were clearly too weak for any important use. Several compromises were developed.

One was the "homophonic substitution cipher", where "homophonic" means "same sound". The homophonic substitution cipher is a simple extension of the monoalphabetic substitution cipher. The basic concept is to use multiple substitution symbols for each letter, with the number of substitutions proportional to the frequency of the letter.

For example, since the letter "a" has an average frequency of about 8% in English text, then eight symbols could be used to represent "a", with the different symbols used at random in the ciphertext. In principle, a homophonic substitution cipher could be designed so that none of the symbols in the ciphertext would have a frequency greater than 1%, defeating frequency analysis.

Of course, this means that individual letters can't be used as the substitution symbols. Two-digit, or if need be three-digit, numbers can be used instead. A sample homophonic substitution cipher for English is shown below:

  a:   12  29  25  43  71  80  89  95
  b:   05  92
  c:   19  37  36
  d:   23  41  61  66  
  e:   16  30  47  59  72  83  90  60  69  88  99  00
  f:   17  49
  g:   02  31
  h:   04  45  55  63  76  82
  i:   15  34  56  97  77  86
  j:   03
  k:   11  
  l:   24  38  48  64
  m:   65  46
  n:   26  42  53  70  73  98
  o:   10  44  50  94  78  85  91
  p:   06  39
  q:   52
  r:   21  35  54  20  74  87
  s:   01  40  57  68  79  81
  t:   13  28  51  67  75  84  33  27  22
  u:   08  62  58
  v:   07
  w:   18  32
  x:   96
  y:   09  93
  z:   14

A homophonic substitution cipher is more secure than a simple monoalphabetic substitution cipher, but it is not absolutely secure. While it does tend to obscure frequency information, the patterns that letters form in text give a codebreaker fingerholds for attack. For example, in English the letter "q" is almost always followed by a "u". "Q" is rarely used in English text, and this is reflected in the table above, with only one substitution symbol for "q". In contrast, there are three substitution symbols for "u". This means the encrypted message will have distinctive symbol pairs, with one specific symbol followed by one of three other specific symbols and no others. Similar rules of letter association can help to further decrypt a homophonic substitution cipher.

* Other improved ciphers included "digraphic" ciphers, in which the substitutions were performed on pairs of letters, not single letters, resulting in 26 * 26 = 676 distinct substitutions, or even "trigraphic" ciphers, with substitutions performed on triplets of letters, for a total of 26 * 26 * 26 = 17,576 substitutions.

Another refined cipher was developed by a 17th-century French team of father and son named Antoine and Bonaventure Rossignol, who worked as cipher experts for the French monarchs Louis XIII and Louis XIV. Their "Great Cipher", as it became known because it was so hard to crack, performed substitutions on syllables, and added various other tricks to confuse a would-be codebreaker, such as including a codegroup that meant: IGNORE THE PREVIOUS CODEGROUP.

Although these ciphers were much more secure than a simple monoalphabetic substitution cipher, they were not impregnable. As discussed in the previous chapter, digraphs and even trigraphs have distinctive frequency distributions in specific languages, as do syllables. By this time, most nations had acquired cryptologic bureaus, known as "Black Chambers", staffed with professional, full-time codebreakers who could spend all their time deciphering other people's mail. The best of the Black Chambers could crack almost any code or cipher in time.

The Rossignol's Great Cipher was very tough but was ultimately cracked. Many of the official records of the reign of Louis XIV were written in the Great Cipher. Eventually that cipher scheme fell into disuse and was forgotten, and nobody could read any of the records any longer. In 1890, a French army cryptographic expert named Commandant Etienne Bazeries (1846:1931) decided to try to crack the Great Cipher. He succeeded after three years of agonizing work, in one of the great epics of cryptanalysis.

BACK_TO_TOP

[2.4] CIPHERS GO PUBLIC

* By the middle of the 19th century, ciphers had become popular with the public in Britain and America. Partly this was due to the straitlaced nature of the societies of the times, particularly Victorian Britain, where young lovers had to conduct their romances in secret. Publishing ciphertext messages in the personals columns of newspapers provided a useful means of communication, and though for the most part the couples used simple monoalphabetic substitution ciphers, such means of encryption were at least reasonably secure against their parents.

Ciphers also showed up in popular fiction. In 1843, the American suspense writer Edgar Allen Poe wrote a short story called THE GOLD BUG, in which the fictional hero uses frequency analysis to crack a ciphertext that leads him to the buried treasure of the pirate Captain Kidd. Poe was actually fairly knowledgeable about codes and ciphers, and had something of a reputation as a "genius" for his ability to crack monoalphabetic substitution ciphers from ciphertexts submitted to him by readers.

Sherlock Holmes, the fictional detective genius created by Sir Arthur Conan Doyle, had among his many talents a mastery of cryptanalysis, demonstrated in stories like THE ADVENTURE OF THE DANCING MEN, where he cracks a cipher based on stickman figures. French author Jules Verne also used cryptography in his novel JOURNEY TO THE CENTER OF THE EARTH, in which an ancient parchment is deciphered and tells the heroes the path to the Earth's interior.

* In most cases, these exercises in popular cryptography are of no strong technical interest, but there is one major exception. In 1885, a pamphlet titled THE BEALE CIPHERS was printed in Lynchburg, Virginia. It told a story related to the anonymous author by a Robert Morriss, who owned the Washington Hotel in Lynchburg.

In 1820 and 1822, according to the pamphlet, a fellow named Thomas Beale checked into the Washington Hotel and made friends with Morriss. When Beale left for the second time, he left a locked box with Morriss, along with written instructions that the box contained "papers of value and importance" and that it was not to be opened for ten years. The instructions also explained to Morriss that the papers would be "unintelligible without the aid of a key", and the "key" would be given to him by some unspecified third party when the ten years had passed.

1832 came and went. Morriss heard nothing from Beale, nor from the mysterious third party. Beale had judged Morriss trustworthy and Morriss proved it by not opening the box until 1845. The box contained three ciphertext documents, consisting of lists of numbers, plus a plaintext note written by Beale.

The note explained that Beale and a number of colleagues had gone out West to Santa Fe, New Mexico. They set out north, and by accident stumbled on to a rich lode of gold. They mined a large quantity of gold, as well as some silver. Beale was entrusted to take the treasure back East and hide it for safekeeping. Beale made two such trips, burying the treasure in the Lynchburg area, and then left the enciphered documents with Morriss so that somebody would be able to arrange the distribution of the treasure to relatives if any disaster occurred to the adventurers.

Apparently such a disaster occurred, since the group vanished without a trace. Morriss puzzled with the ciphertexts for most of two decades, but in 1862 he knew he wouldn't be around much longer and told the author of the pamphlet the story. In the end, the author regretted being told of the treasure and the cipher. He spent over two decades trying to track down the Beale treasure, and reduced himself and his family to poverty in the attempt. To eliminate further temptation, he decided to write the pamphlet and make the matter public. To prevent people from harassing him, he did not name himself, and printed the pamphlet through an agent, a prominent local citizen named James B. Ward.

* While the author's efforts to find the Beale treasure failed, he did at least decipher one of the three ciphertexts. He realized that it was a "book cipher", in which the numbers in the ciphertext indicate the position or "index" of words in some external document, or "keytext", such as one of the books of the Bible. The first letter of the word is the actual plaintext letter associated with the cipher index value.

For example, suppose the keytext is some book titled A DARK AND STORMY NIGHT, and the first text in the book goes as follows:

   It was a dark and stormy night.  Every now and then, the ungodly quiet
   was broken by a crash of lightning that split the darkness outside.
   Inside the house, midnight approached.

This text is indexed as follows:

   index_value     keytext_word     first_letter
   ___________     ____________     ____________

        1            It                  I
        2            was                 w
        3            a                   a
        4            dark                d
        5            and                 a
        6            stormy              s
        7            night.              n
        8            Every               e
        9            now                 n
       10            and                 a
       11            then,               t
       12            the                 t
       13            ungodly             u
       14            quiet               q
       15            was                 w
       16            broken              b
       17            by                  b
       18            a                   a
       19            crash               c
       20            of                  o
       21            lightning           l
       22            that                t
       23            split               s
       24            the                 t
       25            darkness            d
       26            outside.            o
       27            Inside              i
       28            the                 t
       29            house,              h
       30            midnight            m
       31            approached.         a
   ___________     ____________     ____________

-- and so on. Obviously this list must continue until all the letters of the alphabet are matched to an index, and of course several different indexes should be matched to one letter. If that were not the case, the book cipher would be just another simple monoalphabetic substitution cipher and extremely easy to crack, whether anyone knew what the keytext was or not. In effect, a book cipher resembles a homophonic substitution cipher.

Given this keytext, then a simple plaintext message such as:

   hide all the loot

-- becomes the ciphertext:

   29 27 4 8 18 21 21 11 29 8 21 26 26 12

The author of the pamphlet realized was that the keytext was actually the American Declaration of Independence. The deciphered text indicated that the treasure amounted to about a over a tonne of gold, about two tonnes of silver, plus a relatively small amount of jewelry that had been obtained for portability and barter. The treasure was stored in iron pots and buried in a stone-lined vault somewhere in the county of Bedford, Virginia.

* The Beale ciphers have become a cult. Since 1885 many people have spent their entire life hunting for the Beale treasure, or to decipher the other two Beale ciphertexts, which to some is the more interesting goal.

They have never been cracked. Every now and then somebody claims they have succeeded in deciphering them, but these proclamations have always turned out to be either self-delusion or sheer fraud, and anyone who makes such a claim without persuasive proof would have to expect to be treated with great skepticism.

The difficulty of cracking the Beale ciphers is due to the fact that the amount of ciphertext is so small, and if the ciphertexts are actually based on a book cipher the number of possible keytexts is unlimited. Some cryptographers believe that the Beale ciphers have been a real blessing to the field, inspiring a great deal of work and cleverness.

Of course, the whole story of the Beale ciphers has the neat flavor of a Hardy Boys mystery and smells of a hoax. One of the suspicious aspects of the story was pointed out by a ciphers hobbyist, who noticed that there were significant errors in the listing of the Declaration of Independence in the pamphlet compared to the actual text of the document, and that the cipher only worked properly if the listing in the pamphlet were used and not the actual text. In other words, the whole thing was "cooked". On the other hand, sketchy historical records do indicate the existence of a Thomas Beale whose movements seem to match those of the story, and analysis of the unbroken ciphertexts reveals patterns that are far from random.

The Beale ciphers have inspired both treasure hunters and conspiracy fanatics. Some suspect that the Beale ciphers did exist, but the author didn't put the true ciphertexts in the document, hoping that the pamphlet might reach the mysterious person who would come forward with the key so they could cut a deal for the treasure. Some believe the US National Security Agency (NSA), which handles America's codebreaking efforts, cracked the Beale ciphers a long time ago and picked up the loot for its own use; no doubt aliens show up in that story somewhere along the line as well.

The final mystery is: if the Beale ciphers are for real, what tragedy occurred to Beale and his comrades? At this late date, even if the ciphers are for real and are broken, it seems hard to believe that anyone will ever know.

BACK_TO_TOP
< PREV | NEXT > | INDEX | SITEMAP | GOOGLE | LINKS | UPDATES | BLOG | EMAIL | $Donate? | HOME