Accuracy was essential for Caesar and it is also required for the effective transmission of digital signals. Caesar also wanted to keep his codes to himself as do the cable and satellite broadcasting television companies who only want paying subscribers to be able make sense of their signals.

Let’s look at accuracy first. Human error or ‘noise along the line’ can always occur, and must be dealt with. Mathematical thinking allows us to construct coding systems that automatically detect errors and even make corrections.

Error detection and correction

One of the first binary coding systems was the Morse code which makes use of two symbols, dots • and dashes –. The American inventor Samuel F.B. Morse sent the first intercity message using his code from Washington to Baltimore in 1844. It was a code designed for the electric telegraph of the mid-19th century with little thought to an efficient design. In Morse code, the letter A is coded as • –, B as – •••, C as – • – • and other letters as different sequences of dots and dashes. A telegraph operator sending ‘CAB’ would send the string – • – • / • – / – •••. Whatever its merits, Morse code is not very good at error detection let alone correction. If the Morse code operator wished to send ‘CAB’, but mistyped a dot for a dash in C, forgot the dash in A and noise on the wire substituted a dash for a dot in B, the receiver getting •• – • / • / –– ••, would see nothing wrong and interpret it as ‘FEZ’.

At a more primitive level we could look at a coding system consisting of just 0 and 1 where 0 represents one word and 1 another. Suppose an army commander has to transmit a message to his troops which is either ‘invade’ or ‘do not invade’. The ‘invade’ instruction is coded by ‘1’ and the ‘do not invade’ instruction by ‘0’. If a 1 or a 0 was incorrectly transmitted the receiver would never know – and the wrong instruction would be given, with disastrous consequences.

We can improve matters by using code words of length two. If this time we code the ‘invade’ instruction by 11 and the ‘do not invade’ by 00, this is better. An error in one digit would result in 01 or 10 being received. As only 11 or 00 are legitimate code words, the receiver would certainly know that an error had been made. The advantage of this system is that an error would be detectable, but we still would not know how to correct it. If 01 were received, how would we know whether 00 or 11 should have been sent?

The way to a better system is to combine design with longer code words. If we code the ‘invade’ instruction by 111 and the ‘do not invade’ by 000 an error in one digit could certainly be detected, as before. If we knew that at most one error could be made (a reasonable assumption since the chance of two errors in one code word is small), the correction could actually be made by the receiver. For example, if 110 were received then the correct message would have been 111. With our rules, it could not be 000 since this code word is two errors away from 110. In this system there are only two code words 000 and 111 but they are far enough apart to make error detection and correction possible.

The same principle is used when word processing is in autocorrect mode. If we type ‘animul’ the word processor detects the error and corrects it by taking the nearest word, ‘animal’. The English language is not fully correcting though because if we type ‘lomp’ there is no unique nearest word; the words, lamp, limp, lump, pomp and romp are all equidistant in terms of single errors from lomp.

A modern binary code consists of code words that are blocks consisting of zeros and ones. By choosing the legitimate code words far enough apart, both detection and correction are possible. The code words of Morse code are too close together but the modern code systems used to transmit data from satellites can always be set in autocorrect mode. Long code words with high performance in terms of error correction take longer to transmit so there is a tradeoff between length and speed of transmission. Voyages into deep space by NASA have used codes that are three-error correcting and these have proved satisfactory in combating noise on the line.

Making messages secret

Julius Caesar kept his messages secret by changing around the letters of his message according to a key that only he and his generals knew. If the key fell into the wrong hands his messages could be deciphered by his enemies. In medieval times, Mary Queen of Scots sent secret messages in code from her prison cell. Mary had in mind the overthrow of her cousin, Queen Elizabeth, but her coded messages were intercepted. More sophisticated than the Roman method of rotating all letters by a key, her codes were based on substitutions but ones whose key could be uncovered by analysing the frequency of letters and symbols used. During the Second World War the German Enigma code was cracked by the discovery of its key. In this case it was a formidable challenge but the code was always vulnerable because the key was transmitted as part of the message.

A startling development in encryption of messages was discovered in the 1970s. Running counter to everything that had been previously believed, it said that the secret key could be broadcast to all and yet the message could remain entirely safe. This is called public key cryptography. The method depends on a 200 year old theorem in a branch of mathematics glorified for being the most useless of all.

Public key encryption

Mr John Sender, a secret agent known in the spying fraternity as ‘J’, has just arrived in town and wants to send his minder Dr Rodney Receiver a secret message to announce his arrival. What he does next is rather curious. He goes to the public library takes a town directory off the shelf and looks up Dr R. Receiver. In the directory he finds two numbers alongside Receiver’s name – a long one, which is 247, and a short one 5. This information is available to all and sundry, and it is all the information John Sender requires to encrypt his message, which for simplicity is his calling card, J. This letter is number 74 in a list of words, again publicly available.

Sender encrypts 74 by calculating 74⁵ (modulo 247), that is, he wants to know the remainder on dividing 74⁵ by 247. Working out 74⁵ is just about possible on a handheld calculator, but it has to be done exactly:

74⁵ = 74 × 74 × 74 × 74 × 74 = 2,219,006,624

and

2,219,006,624 = 8,983,832 × 247 + 120

so dividing his huge number by 247 he gets the remainder 120. Sender’s encrypted message is 120 and he transmits this to Receiver. Because the numbers 247 and 5 were publicly available anyone could encrypt a message. But not everyone could decrypt it. Dr R. Receiver has more information up his sleeve. He made up his personal number 247 by multiplying together two prime numbers. In this case he obtained the number 247 by multiplying p = 13 and q = 19, but only he knows this.

This is where the ancient theorem due to Leonhard Euler is taken out and dusted down. Dr R. Receiver uses the knowledge of p = 13 and q = 19 to find a value of a where 5 × a ≡ 1 modulo (p – 1)(q – 1) where the symbol ≡ means equals in modular arithmetic. What is a so that dividing 5 × a by 12 × 18 = 216 leaves remainder 1? Skipping the actual calculation he finds a = 173.

Because he is the only one who knows the prime numbers p and q, Dr Receiver is the only one who can calculate the number 173. With it he works out the remainder when he divides the huge number 120¹⁷³ by 247. This is outside the capacity of a hand held calculator but is easily found by using a computer. The answer is 74, as Euler knew two hundred years ago. With this information, Receiver looks up word 74 and sees that J is back in town.

You might say, surely a hacker could discover the fact that 247 = 13 × 19 and the code could be cracked. You would be correct. But the encryption and decryption principle is the same if Dr Receiver had used another number instead of 247. He could choose two very big prime numbers and multiply them together to get a much larger number than 247.

Finding the two prime factors of a very large number is virtually impossible – what are the factors of 24,812,789,922,307 for example? But numbers much larger than this could also be chosen. The public key system is secure and if the might of supercomputers joined together are successful in factoring an encryption number, all Dr Receiver has to do is increase its size still further. In the end it is considerably easier for Dr Receiver to ‘mix boxes of black sand and white sand together’ than for any hacker to unmix them.

the condensed idea

Keeping messages secret