If anyone finds an efficient mechanism for factorising huge prime numbers, security as we know it will all but come to an end. RSA and all its variants rely on such a feat being impossible to achieve.
There is a very simple means of encrypting a message which doesn't require maths or computational power to achieve. It goes something like this. Pick a favourite passage from a piece of text known to yourself and your correspondent, say, Alice in Wonderland. Then "encode" the message by sending your friend a series of numbers, each referring to the location of a letter in the source paragraph: 7, 35, 2, 8, 16, 24 etc. Upon receipt it is quite easy to decipher the code to reveal the secret message.
There is a major problem with this technique. If you were to use the same text more than once, a skilled crypto analyst could use "standard techniques" to unravel your encrypted text.
What is needed for this encryption scheme to work is an inexhaustible supply of random text. This concept is known as a one-time pad. Invented by Gilbert Vernam in 1918, it is totally secure since a suitably encoded message contains an infinite number of probable decryptions.
If I told you that "kjhsdikhosenfsonp" was an encrypted message, and that each letter in the original message was substituted in an entirely random fashion, one-to-one with those above, could you decipher the message?
The answer is a definite "no", because, if the text has no pattern to work with (it is just random gobbledegook) then the message has the same probability of being a particular message as it has with being any other. In other words, the message contains any decipherment one cares to select. The result is that, if the message can contain anything at all, its contents have no value whatsoever.
So if I were to encrypt, say, "Computer Weekly" as "htodnamdhuifnth", a possible and equally probable decipherment would be "Secret Message". The reason why everyone isn't raving about one-time pads is because you have to create a new pad for every message you send and provide your correspondent with a copy of the pad so they can decipher it, making it impractical.
Michael Rabin, professor of computer science at Harvard University, believes he has the answer. Rabin has come up with a scheme where the data required to create a one-time pad is sourced from a stream of ones and zeros being beamed down to Earth via a dedicated satellite network. This random data also comes down at a fantastic rate of gigabytes a second.
In Rabin's scheme, one-time pads are in the public domain, so you bypass the problems of generating and securely transporting them. Since there is so much data being transmitted, no one could possibly store it all.
To exchange a secret message, you just have to agree with your correspondent which bit of this data you will use as your one-time pad. This would take the form of agreeing a time to start downloading the random stream of 1s and 0s, such as 12:30pm GMT.
Of course, there is a potential flaw: that message could be intercepted. However, Rabin seems to be suggesting that he has that problem cracked too - although he can't say how just yet because there are patents pending.
Send the initial message via RSA you say? Well, OK, but suppose someone at the National Security Agency or GCHQ has cracked the factorising problem - you are out in the open again.
I have no idea what Rabin is going to reveal on this but, whatever it is, I bet it is going to be simple and brilliant.
Peet Morris is researching massively parallel/grid computing at the Computational Linguistics Group, Oxford University
Details of Rabin's solution http://people.deas.harvard.edu/~zong/hyper-enc.ps.gz
More on codes www.simonsingh.net/The_CDROM.html
Who would have thought in 1990 that the World Wide Web would become a killer internet application, transforming the way we work, play and communicate? This global revolution began when Tim Berners-Lee wrote the original World Wide Web specification at Cern in a research project designed to distribute documents.
Research work being undertaken at universities today will change the way we use IT, and Computer Weekly is on a mission to showcase the cutting-edge IT research currently being conducted in the UK that will alter the face of tomorrow.
Computer Weekly would like to hear from anyone involved in cutting-edge IT research. Each week we will feature an innovative piece of research, giving a glimpse of how IT will evolve in the coming years.
This was first published in May 2003