The Oxford Science Lecture Series

DR CATHERINE HOBBS

Department of Mathematical Sciences, Oxford Brookes University

"Unlocking the mystery of secret codes"

Martin Wood Lecture Theatre, Oxford, 5th December 2002

Dr Catherine Hobbs, a mathematician at Oxford Brookes University, gave a talk in the Oxford Science Lecture Series on the mathematics behind secret codes.

Dr Hobbs began by outlining what is meant by a secret code: some way of scrambling a message so that it cannot be read by unauthorised people. Usually this involves using an encryption algorithm, which may be known to everyone, and some secret information, called the key, known only to the two parties who are trying to communicate secretly. A simple example of this is the Caesar cipher, used by Julius Caesar in his military campaigns, which substituted each original letter of the message by the letter some given number along the alphabet. For example, A could be enciphered as C, B by D, and so on. The key in this case is the letter to which A has been shifted. Once we know this we can work out the shifts of all other letters.

The major problem with this method is that there are too few keys in total to give security. If an enemy captured one of Caesar's messages he could just try all the possible 25 shifts.

An apparently more secure method is the key phrase cipher, which uses a keyword to define the permutation of the letters. This seems more secure since the enemy would have difficulty guessing the keyword - there are so many possible words. But in fact, such a code is still insecure since it will preserve letter frequencies. That is, since in ordinary language some letters are more common than others (eg e is the most common letter in the English language), then if a letter is occurring frequently in the ciphertext we might guess that it represents e. Comparing other frequencies and making good guesses can quickly yield the original message and also allow us to find the keyword.

More sophisticated 'pencil and paper' ciphers were briefly outlined, eg the Playfair cipher which encrypts pairs of letters at a time. This was used in military communications up until the second World War, but is also insecure as it is susceptible to frequency analysis of pairs of letters.

The German encoding machine, Enigma, was discussed briefly. This was a portable coding machine, resembling a typewriter, which was used by the German military during World War II. It has many millions of possible keys and was belived by the Germans to be unbreakable since at the time no machines existed to try all the possible keys quickly (they were subsequently invented and led to the development of the modern computer). However, the Allies used clever mathematics, luck and mechanical techniques to break Enigma and this is believed to have shortened the course of the war.

Nowadays, secret codes are needed for other purposes than military ones. Principally, they are required to keep our electronic communications secret and to protect sensitive data such as medical and bank records.

Dr Hobbs discussed several modern methods of cryptography, including the Data Encryption Standard (DES) and the Advanced Encryption Standard (AES). These are both symmetric ciphers, in that the same key is used for enciphering and deciphering data. Their security rests in the key, not in the algorithms. Anyone can examine the algorithms and convince themselves that there are no hidden ways of revealing data. However, they both suffer from the problem of key management: in order to set up a secure communication two parties have to first agree on the secret key to use in some secure way. If the two people have not met in person, this may be hard to achieve. Also, for every pair of people communicating together, a key is required - this means a lot of keys are needed.

A solution to this problem was found in Public Key Cryptography, developed in the 1970's. A public key cipher uses two keys, a public key which can be freely distributed, and a private key which is only known to the owner. The important step in public key encryption is that it must be impossible to deduce the private key from the public key. That is what makes it safe to publish the public keys in some kind of directory. If we think of the algorithm like a letterbox, anyone can put letters into the box via the letter slot but only the person who owns the key to the box can get letters out again. The method solves the key management problems of symmetric ciphers since each user only needs 2 keys and one can communicate with someone without agreeing in advance simply by looking up their public key in the directory.

The most widely used scheme which puts this into practice is known as the RSA algorithm (after its inventors, Rivest, Shamir and Adleman). This algorithm uses the idea that while it is easy to multiply two prime numbers together to find their product, it is hard to take the product and deduce the original prime numbers, particularly if the numbers involved are very large (say 100 digits for each prime). Dr Hobbs outlined the way in which this is used to set up a pair of public and private keys so that deducing the private key from the public key is equivalent to factorising the number into primes. RSA appears to be very secure (it should take at least 40 years to break a 200 digit RSA key), but only if the problem of factorisation is genuinely difficult. At the moment this is thought to be the case but it has not been mathematically proved and it is possible that a much faster method for factorisation will be developed. In that case, RSA will no longer be secure.

Alternatives to RSA include Elliptic Curve Cryptography, which uses a similar idea as RSA but one which is not equivalent to factorisation. It can also offer good security using much shorter keys than RSA. However, more work needs to be done on this method. Dr Hobbs also mentioned the Cayley-Purser algorithm, developed as an alternative to RSA by Irish teenager Sarah Flannery during a summer placement at Baltimore Technologies, a computer security company in Dublin. This used sophisticated mathematical methods and won Sarah the European Young Scientist of the Year Award. However, it was shown to be flawed by Sarah herself and others.

Another possible alternative is Quantum Cryptography, which is a method of using quantum particles to exchange keys over insecure channels. Since quantum particles change when they are observed, eavesdroppers on the line will be able to be spotted by the legitimate parties. So far this system has been tested to a distance of 67 km, but further work is needed to make this useable in practice.

To conclude, Dr Hobbs observed that there is bound to be an increasing need for more secure codes and that this type of work will keep mathematicians and computer scientists busy for many years to come!