A computer scientist from the Wiezmann Institute in Israel has designed a light-based computer capable of cracking encrypted messages with key lengths previously thought to be uncrackable. Professor Adi Shamir, one of the founders of RSA Data Security Inc, showcased his design of the device which he calls TWINKLE (The Wiezmann Institute Key Locating Engine) yesterday at the Eurocrypt ’99 conference in Prague.
Shamir estimates that the device, based on an opto-electronic design which uses a combination of the photons that make up light and the electrons that make up electricity, to transmit digital information, would be as powerful as around 1000 PCs when performing the factoring process, called sieving. Sieving is the first of two stages involved in the breaking an encrypted message. It results in a set of linear equations which must then be solved in order to find the key.
In a recent test attempt to crack a 465-bit key, the sieving took 200 computers four weeks to complete. A Cray supercomputer, equipped with 810Mbytes of memory, then solved the resulting system of equations in 100 hours. Shamir’s computational device would not be able to perform the process of solving the equations that result from sieving because it has no memory capabilities, and simply outputs the equations it finds to another computer that collects them. Shamir estimates that just seven of his devices would be able to collect the complete set of equations associated with a 465-bit key in a mere six days, a thousand times faster than the system of 200 ordinary computers. However, he does warn that a bottleneck would then form at the second phase, which would still take four days to complete.
According to RSA, the largest key length that has so far been cracked is 450-bit, but the breakthrough makes the cracking of even 512-bit keys realistic, the company says. The device has yet to be built and Shamir says there is still a fair amount of engineering that would need to be done before one could be built. However, Shamir claims device would cost only around $5,000 to build once the engineering difficulties had been overcome.
