Royal Institute Christmas Lectures 2006
The Case of the Uncrackable Code
Enigma
One of the most sophisticated encoding machines is The Enigma, used by the Germans in the Second World War. They believed it to be uncrackable, but mathematicians in Bletchley Park, north of London, did manage to crack the Enigma code.
The Enigma Machine
To put this to the test Professor Sautoy has had some sweets for the young audience locked in a safe. The combination to the safe has been encoded by the Enigma machine and this encoded message is sent to the mathematicians at Bletchley Park using Morse Code. Tony Sale, one of the Bletchley Park code-crackers is confident he can decode the message, using a Bombe machine to discover the settings used by The Enigma Machine, in about thirty minutes.
Morse Code was created 170 years ago to allow messages to be transmitted via telegraph lines. However, Morse Code is not infallible and not very suitable for interpretation by machines. So in he 1870s a Frenchman, Emile Baudot, devised a new code which consisted of 5 bits for each character and resolved many of the issues with Morse Code. Baudot Code does not solve all encoding issues as it contains no error-correcting code.
Substitution Code
Substitution Codes
Professor Sautoy displays an encoded message, shown left, which he explains uses a Substitution Code. These codes are relatively simple to break using frequency analysis. Frequency analysis recognises that certain letters occur more often in any given language and in English the most used letter is invariably "E". A simple count of the letters reveals that the character "C" appears with the greatest frequency and is most likely to have been substituted for the letter "E". Following this process it takes only a few moments to reveal the original message: "On the first day of Christmas my true love sent to me, a partridge in a pear tree". This frequency analysis reveals the true flaw in substitution codes.
The Enigma Machine works with substitution codes, but it changes the substitution pattern after every character, so a simple frequency analysis does not work.
Next we look at the public / private key encryption used to securely encode transaction on the Internet. A public key is published by the recipient which allows the sender to encrypt their message. The message however, cannot be decrypted by the public key, It requires the private key that only the recipient knows to decrypt the message. The private key is a pair of prime numbers and the public key is the product of the two private keys. So, Professor Sautoy muses, isn't it simple for a would-be hacker to split the public key and find the 2 prime numbers that can be multiplied to produce it? Theoretically yes, but in reality the numbers used as public keys are so large that the number of possible permutations is larger then the number of atoms in the Universe.
Elliptical Curve Cryptography
Elliptic Curve Cryptography is a much more sophisticated code and is being used, amongst other things, to protect the flight plans of aircraft
