Читать книгу Cryptography, Information Theory, and Error-Correction - Aiden A. Bruen - Страница 17

Cryptology is made up of two Greek words kryptos, meaning “hidden,” and lógos meaning “word.” It is defined [Bri19] as the science concerned with data communication and storage in secure and usually secret form. It encompasses both cryptography (from the Greek graphia meaning writing) and cryptanalysis or the art of extracting the meaning of a cryptogram.

Cryptography has a history that is almost as long as the history of the written word. Some four millennia ago (see [Kah67, p. 71]), an Egyptian scribe recorded in stone the first known hieroglyphic symbol substitution in the tomb of Khnumhotep II, a nobleman of the time. Although the intention in this case was to exalt the virtues of the person, rather than to send a secret message, the scribe used for the first time one of the fundamental elements used by cryptographers throughout the ages, namely substitution. He used unusual hieroglyphic symbols, known perhaps only to the elite, in place of the more common ones.

In substitution, the sender replaces each letter of a word in a message by a new letter (or sequence of letters or symbols) before sending the message. The recipient, knowing the formula used for the substitution – the secret key – is able to reconstruct the message from the scrambled text that was received. It is assumed that only the recipient and the sender know the secret key.

The other main cryptographic technique used is transposition (or permutation) in which the letters of the message are simply rearranged according to some prescribed formula which would be the secret key in that case.

The Greeks were the inventors of the first transposition cipher. The Spartans [Kah67] in the fifth century BCE, were the first recorded users of cryptography for correspondence. They used a secret device called a scytale consisting of a tapered baton around which was spirally wrapped either a strip of parchment or leather on which the message was written. When unwrapped, the letters were scrambled, and only when the strip was wrapped around an identically sized rod could the message be read.

Today, even with the advent of high‐speed computers, substitution and transposition form the fundamental building blocks of ciphers used in symmetric cryptography.

To put it in a historical perspective, asymmetric or public key cryptography was not invented until the 1970s. Exactly when it was invented, or who should take most of the credit, is an issue still in dispute. Both the NSA¹ and the CESG² have claimed priority in the invention of public key cryptography.

Cryptography has had several reincarnations in almost all cultures. Because of the necessity of keeping certain messages secret (i.e. totally unknown to potential enemies) governments, armies, ecclesiastics, and economic powers of all kinds have been associated throughout history with the development of cryptography. This trend continues today.

The Roman General Julius Caesar was the first attested user of substitution ciphers for military purposes [Kah67, p. 83]. Caesar himself recounted this incident in his Gallic Wars. Caesar found out that Cicero's station was besieged and realized that without help, he would not be able to hold out for long. Caesar had a volunteer ride ahead, with an encrypted message fastened to a spear which he hurled into the entrenchment. Basically, Cicero was told to keep up his courage and that Caesar and his legions were on their way.

In the cipher form used by Caesar, the first letter of the alphabet “A” was replaced by the fourth letter “D,” the second letter “B” by the fifth “E,” and so on. In other words, each original letter was replaced by one three steps further along in the alphabet. To this day, any cipher alphabet that consists of a standard sequence like Caesar's is called a Caesar alphabet even if the shift is different from three.

Not much mention is made of the coding abilities of Augustus Caesar, the first Emperor of Rome and nephew of Julius Caesar. His cipher involved a shift of only one letter so that for the plain text (that is the original text) A was enciphered as B.

Mention of cryptography abounds in early literature: Homer's Iliad refers to secret writing. The Kama‐sutra, the famous text book of erotics from the Indian subcontinent, lists secret writing as one of the 64 arts or yogas that women should know and practice [Kah67, p. 75]. One of the earliest descriptions of the substitution technique of encryption is given therein. One form involves the replacement of vowels by consonants and vice versa.

In Hebrew literature, there are also examples of letter substitution. The most prevalent is the atbash technique. Here the first and last, second and second last, and so on, letters of the Hebrew alphabet are interchanged. An example can be found in the Old Testament of the Bible. Kahn [Kah67, p. 77] cites Jeremiah 25: 26 and Jeremiah 51: 41, where the form “SHESHACH appears in place of Babel (Babylon).”

In Jeremiah 51: 41, the phrase with SHESHACH is immediately followed by one using “Babylon.” To quote:

How is SHESHACH taken!

And the praise of the whole earth seized!

How is Babylon become an astonishment

Among the nations!

Through Aramaic paraphrases of the Bible, it is clear that SHESHACH is the same as Babel. With the atbash technique, the second letter of the Hebrew alphabet “b” or beth becomes the repeated SH or SHIN, the next to last letter in the alphabet. Similarly, the “l” of lamed, becomes the hard ch, or kaph of SHESHACH. Since Babylon appears below, the use of atbash here was not to actually hide the word but perhaps just a way for the scribe to leave a trace of himself in the work he was copying.

The first people to clearly understand the principles of cryptography and to elucidate the beginnings of cryptanalysis were the Arabs [Kah67]. While Europe was in the Dark Ages, Arab arts and science flourished and scholars studied methods of cryptanalysis, the art of unscrambling secret messages without knowledge of the secret key. A complete description of this work, however, was not published until the appearance of the multivolume Subh al‐a'sha by about 1412.

European cryptology was being developed around this time in the Papal States and the Italian city‐states [Kah67]. The first European manual on cryptography (c1379) was a compilation of ciphers by Gabriele de Lavinde of Parma, who served Pope Clement VII. The Office of Cipher Secretary to the Pope was created in 1555. The first incumbent was Triphon Bencio de Assisi. But considerably before this in 1474, Cicco Simonetta wrote a manuscript that was entirely devoted to cryptanalysis.

Cryptanalysis was to have tragic consequences for Mary, Queen of Scots. It was the decipherment of a secret message to Anthony Babington supposedly planning an insurrection against Elizabeth I [Lea96] that resulted in her tragic end. Having obtained this evidence, Sir Francis Walshingham, the head of Queen Elizabeth's secret service, sent his agent back to Fotheringay Castle, to intercept and copy more of Mary's secret messages with the result that Mary and all her coconspirators were finally arrested. As a result of the trial, all were executed but only Mary was beheaded. Walshingham later claimed that his agents had found the keys to as many as 50 different ciphers in Mary's apartments. (There has long been a conjecture that Mary was actually innocent and that the evidence was planted to remove this inconvenient rival to the English throne.)

The architect, Leon Battista Alberti born in Florence in 1404, is known as “the Father of Western Cryptology.” In 1470, he published Trattati in Cifra, in which he described the first cipher disk. His technique led to a generalization of the Caesar cipher, using several shifted alphabets instead of just one alphabet. This gave rise to the so‐called Vigenère cipher discussed in Chapter 2. (This is actually a misattribution as de Vigenère worked on auto‐key systems).

In 1563, the Neapolitan, Giovanni Battista Porta published his De Furtivis Literarum Notis on cryptography, in which he formalized the division of ciphers into transposition and substitution.

Moving up several centuries, we find that cryptography was widely used in the American Civil War. The Federal Army [Bri97] made extensive use of transposition ciphers in which a key word indicated the order in which columns of the array were to be read and in which the elements were either plain text words or codeword replacements for plain text. Because they could not decipher them, the Confederacy, sometimes in desperation, published Union ciphers in newspapers appealing for readers to help with the cryptanalysis. To make matters worse for the Confederate Army, the Vigenère cipher which they themselves used was easily read by the Union Army.

Kahn reports [Kah67, p. 221] that a Vigenère tableau was found in the room of John Wilkes Booth after President Lincoln was shot. Because there was actually no testimony regarding any use of the cipher, could this have been a convenient method of linking Booth and the seven Southern sympathizers with the Confederate cause?

Lyon Playfair, Baron of St. Andrews, recommended a cipher invented in 1854 by his friend Charles Wheastone, to the British government and military. The cipher was based in a digraphic³ substitution table and was known as the Playfair Cipher. The main difference when compared with a simple substitution cipher is that characters are substituted two at a time. Substitution characters depend on the positions of the two plain text characters on a secret square table (the key) whose entries are the characters of the alphabet less the letter “J.”

In 1894, Captain Alfred Dreyfus of the French military was accused of treason and sent to Devil's Island, because his hand writing resembled that of an encrypted document that offered military information to Germany. To prove his innocence, the note had to be cryptanalyzed. To be certain that the decipherers' work was correct, an army liaison officer with the Foreign Ministry managed to elicit another similarly encrypted note in which the contents were known to him. The plain text then showed that Dreyfus had not written the encrypted document, but it took several more years before he was to “receive justice, re‐instatement and the Legion of Honour” [Kah67, p. 262].

Early in the twentieth century, Maugborne and Vernam put forth the basis for the cipher known as the one‐time pad. Although – as was proven later by Shannon – this cipher is effectively unbreakable, its use is somewhat restricted because, in practice, a random key that is as long as the message must be generated and transmitted securely from A to B. Soviet spies used this cipher, and it is said that the phone line between Washington and Moscow was protected with a one‐time pad during the Cold War era.

Edward Hugh Hebern [Bri97] of the United States invented the first electric contact rotor machine. In 1915, he experimented with mechanized encryption by linking two electric typewriters together using 26 wires to randomly pair the letters. In turn, this led to the idea of rotors which could not only mechanize substitution, but also alphabet shifts as well. The function of the rotor was to change the pairing of letters by physically changing the distribution of electric contacts between the two typewriters. By 1918, he had built an actual rotor‐based encryption machine.

At about the same time (1918–1919) three other inventors, the German Arthur Scherbius, the Dutchman Hugo Koch and the Swede Arvid Damm were filing patents of rotor‐based encryption machines. The Scherbius idea, which included multiple rotors, materialized in the first commercial models having four rotors, ENIGMA A and ENIGMA B in 1923. Ironically, Hebern only filed for patent protection in 1921, received one in 1924 and lost a patent interference case against International Business Machines in 1941. Later modifications to the Scherbius machine including a reflector rotor, and three interchangeable rotors were implemented by the Axis Forces during World War II.

Rotor‐based machines give the possibility to implement poly‐alphabetic substitution ciphers⁴ with very long keys or cycles in a practical way. With the advantage of mechanization, the ability of widespread deployment of cryptographic stations and widespread use became a reality. This translated into a larger volume of messages (potentially all messages) being encrypted. However, the increase in traffic gave more cipher text for cryptanalysts to analyze and the probability of operators making a deadly mistake in the management of keys was multiplied.

The timely breaking of the ENIGMA cipher by the Allies was due in part to inherent weaknesses in the encryption machine, mismanagement of keys by the operators and lots of mechanized, analytical work. The cipher was first broken, using only captured cipher text and a list of daily keys obtained through a spy, by the Polish mathematician Marian Rejewski. One of the important players in the mechanization of ensuing breaks was the English mathematician Alan Turing, who also contributed to the establishment of the basis for what is today called Computation Theory.

As a side note, after World War II, many of the ENIGMA machines captured by the Allies were sold to companies and governments in several countries.

Another very interesting cryptographic technique of a different kind was used by the US military in the Pacific campaign in World War II. Secret military messages were encrypted by translating them from English to the Navajo language. For decryption at the other end, of course, the Navajo was translated back into English. Some words describing military equipment did not exist in the original Navajo language, but substitutes were found. For example “tanks and planes” were described using the Navajo words for “turtles and birds.” To avoid the possibility of the enemy getting a handle of the code, the whole system was committed – by means of an intensive training program – to the memory of the translators or “Code Talkers.” This code was never broken.

Immediately after World War II, Shannon was publishing his seminal works on information theory. Almost simultaneously, thanks to the efforts of Ulam, von Neumann, Eckert, and Mauchly another key technological development was starting to make strident progress, the introduction of the newly invented digital computer as a mathematical tool [Coo87].

Figure 1.1 (a) Claude E. Shannon, Theseus, and the maze (see Section 1.4). (b) Claude E. Shannon.

Source: Reused with permission of Nokia Corporation and AT&T Archives.

Because of the importance of his contributions to the issues in this book, we present here a brief biography of Shannon, before finishing the chapter with a review of modern developments (Figure 1.1).