Twinkle, twinkle, little tube
This article first appeared in Personal Computer World magazine, August 1999.
There's a radically new kind of computer on the horizon. It's about the size of a bottle of whisky, computes with light, and cracks codes in the twinkle of an eye.
The ultimate success of e-commerce rests on having rock-solid encryption, and the most promising technology is public-key cryptography. The idea is that everyone is issued with two keys: one is the "public" key, freely announced; the other is the "private" key a closely guarded secret.
For example, if Alice wants to send a message to Bob (in cryptographic circles, Alice and Bob are always sending each other secret messages), she looks up Bob's published public key, encrypts her message with it, and sends it to Bob. When Bob gets the message, he decodes it using his secret private key. Anyone can send Bob a secure, encrypted message, but only Bob, who alone has the private key, can decode it.
What makes public-key encryption secure is the difficulty of figuring out the private key, given the public key. The two keys each of which is a single, very large, number have a special relationship, but untangling it is enormously hard. It boils down to a mathematical technique called factorisation: given a huge number, you have to find which two unique prime numbers, when multiplied together, give the number.
One of the most popular public-key encryption methods today is the RSA system. The "S" of RSA is Adi Shamir, a computer scientist at the Weizmann Institute of Science in Israel. Ironically, Shamir has just devised a new kind of computer that undermines the security of the system he helped to invent. He calls his machine "Twinkle".
As Shamir says, Twinkle is by no means the first attempt to design a special machine for doing mathematics. In the early 1920s, number theorist Derrick Lehmer built a kind of numerical bicycle which activated a set of toothed wheels. All the mathematician had to do was pedal.
Noone's built a Twinkle yet, but Shamir has published detailed plans. The machine will look a bit like one of those cardboard tubes that the more expensive brands of malt whisky come in. On the inside base of a light-tight cylinder will be a single wafer containing a few hundred thousand processing cells. Each cell will house two small memories, a photoreceptor, and a gallium arsenide light-emitting diode (LED).
Twinkle clocks at 10 gigahertz, about 20,000 times faster than today's fastest PCs, and at speeds like this, electrical pulses simply can't travel around electrical circuits fast enough. Instead, Twinkle uses an optical clock: mounted on the inside top of the cylinder is a bright LED, shining down onto the wafer below. It flashes once every 10 thousand millionths of a second. The photoreceptor in each cell responds to the flash, and the cell performs a computation, trying to factor the number it's working on. The cell's LED flashes if it succeeds, and each flash is recorded by another photoreceptor mounted at the top of the cylinder. Twinkle can perform its special kind of factoring far faster than a conventional computer.
Does this mean that RSA is seriously undermined? No. RSA Data Security Inc responded rapidly, stating that Twinkle would only be capable of cracking the simpler versions of RSA coding. Increase the number of bits in the RSA codes, and Twinkle is quickly flummoxed.
Nevertheless, some experts think the writing is on the wall for conventional cryptography, which relies on mathematical problems which have proven extremely hard to solve so far. Researchers at Los Alamos National Labs are exploring new techniques based on the principles of quantum physics. This is encryption beyond the reach of mathematical trickery and novel computer designs. "To break quantum encryption a cracker will first have to break the laws of physics", says Dr Richard Hughes, director of the Los Alamos programme.
We don't have quantum encryption yet, but when we do, it really will be totally safe to send your credit card details across the Internet. Probably.
Toby Howard teaches at the University of Manchester.