The Code Book: The Secret History of Codes and Code-breaking. Simon Singh

known as encryption. To render a message unintelligible, it is scrambled according to a particular protocol which is agreed beforehand between the sender and the intended recipient. Thus the recipient can reverse the scrambling protocol and make the message comprehensible. The advantage of cryptography is that if the enemy intercepts an encrypted message, then the message is unreadable. Without knowing the scrambling protocol, the enemy should find it difficult, if not impossible, to recreate the original message from the encrypted text.

      Although cryptography and steganography are independent, it is possible to both scramble and hide a message to maximise security. For example, the microdot is a form of steganography that became popular during the Second World War. German agents in Latin America would photographically shrink a page of text down to a dot less than 1 millimetre in diameter, and then hide this microdot on top of a full stop in an apparently innocuous letter. The first microdot to be spotted by the FBI was in 1941, following a tip-off that the Americans should look for a tiny gleam from the surface of a letter, indicative of smooth film. Thereafter, the Americans could read the contents of most intercepted microdots, except when the German agents had taken the extra precaution of scrambling their message before reducing it. In such cases of cryptography combined with steganography, the Americans were sometimes able to intercept and block communications, but they were prevented from gaining any new information about German spying activity. Of the two branches of secret communication, cryptography is the more powerful because of this ability to prevent information from falling into enemy hands.

      In turn, cryptography itself can be divided into two branches, known as transposition and substitution. In transposition, the letters of the message are simply rearranged, effectively generating an anagram. For very short messages, such as a single word, this method is relatively insecure because there are only a limited number of ways of rearranging a handful of letters. For example, three letters can be arranged in only six different ways, e.g. cow, cwo, ocw, owc, wco, woc. However, as the number of letters gradually increases, the number of possible arrangements rapidly explodes, making it impossible to get back to the original message unless the exact scrambling process is known. For example, consider this short sentence. It contains just 35 letters, and yet there are more than 50,000,000,000,000,000,000,000,000,000,000 distinct arrangements of them. If one person could check one arrangement per second, and if all the people in the world worked night and day, it would still take more than a thousand times the lifetime of the universe to check all the arrangements.

      A random transposition of letters seems to offer a very high level of security, because it would be impractical for an enemy interceptor to unscramble even a short sentence. But there is a drawback. Transposition effectively generates an incredibly difficult anagram, and if the letters are randomly jumbled, with neither rhyme nor reason, then unscrambling the anagram is impossible for the intended recipient, as well as an enemy interceptor. In order for transposition to be effective, the rearrangement of letters needs to follow a straightforward system, one that has been previously agreed by sender and receiver, but kept secret from the enemy. For example, schoolchildren sometimes send messages using the ‘rail fence’ transposition, in which the message is written with alternate letters on separate upper and lower lines. The sequence of letters on the lower line is then tagged on at the end of the sequence on the upper line to create the final encrypted message. For example:

      The receiver can recover the message by simply reversing the process. There are various other forms of systematic transposition, including the three-line rail fence cipher, in which the message is first written on three separate lines instead of two. Alternatively, one could swap each pair of letters, so that the first and second letters switch places, the third and fourth letters switch places, and so on.

      Figure 2 When it is unwound from the sender’s scytale (wooden staff), the leather strip appears to carry a list of random letters; S, T, S, F, …. Only by rewinding the strip around another scytale of the correct diameter will the message reappear.

      Another form of transposition is embodied in the first ever military cryptographic device, the Spartan scytale, dating back to the fifth century BC. The scytale is a wooden staff around which a strip of leather or parchment is wound, as shown in Figure 2. The sender writes the message along the length of the scytale, and then unwinds the strip, which now appears to carry a list of meaningless letters. The message has been scrambled. The messenger would take the leather strip, and, as a steganographic twist, he would sometimes disguise it as a belt with the letters hidden on the inside. To recover the message, the receiver simply wraps the leather strip around a scytale of the same diameter as the one used by the sender. In 404 BC Lysander of Sparta was confronted by a messenger, bloody and battered, one of only five to have survived the arduous journey from Persia. The messenger handed his belt to Lysander, who wound it around his scytale to learn that Pharnabazus of Persia was planning to attack him. Thanks to the scytale, Lysander was prepared for the attack and repulsed it.

      The alternative to transposition is substitution. One of the earliest descriptions of encryption by substitution appears in the K

ma-s

tsy

yana, but based on manuscripts dating back to the fourth century BC. The K

ma-s

, the art of secret writing, advocated in order to help women conceal the details of their liaisons. One of the recommended techniques is to pair letters of the alphabet at random, and then substitute each letter in the original message with its partner. If we apply the principle to the Roman alphabet, we could pair letters as follows:

      Then, instead of meet at midnight, the sender would write CUUZ VZ CGXSGIBZ. This form of secret writing is called a substitution cipher because each letter in the plaintext is substituted for a different letter, thus acting in a complementary way to the transposition cipher. In transposition each letter retains its identity but changes its position, whereas in substitution each letter changes its identity but retains its position.

      The first documented use of a substitution cipher for military purposes appears in Julius Caesar’s Gallic Wars. Caesar describes how he sent a message to Cicero, who was besieged and on the verge of surrendering. The substitution replaced Roman letters with Greek letters, rendering the message unintelligible to the enemy. Caesar described the dramatic delivery of the message:

      The messenger was instructed, if he could not approach, to hurl a spear, with the letter fastened to the thong, inside the entrenchment of the camp. Fearing danger, the Gaul discharged the spear, as he had been instructed. By chance it stuck fast in the tower, and for two days was not sighted by our troops; on the third day it was sighted by a soldier, taken down, and delivered to Cicero. He read it through and then recited it at a parade of the troops, bringing the greatest rejoicing to all.

      Plain alphabet a b c d e f g h i j k l m n o p q r s t u v w x y z

      Cipher alphabet D E F G H I J K L M N O P Q R S T U V W X Y Z A B C

      Plaintext v e n i, v i d i, v i c i

      Ciphertext Y H Q L, Y L G L, Y L F L

      Figure 3 The Caesar cipher applied to a short message. The Caesar cipher is based on a cipher alphabet