A team of mathematicians has set a new record for factoring a large number into primes, breaking a massive 307-digit number into its three indivisible factors and besting the previous mark by 30 digits. Written as a binary string of zeros and ones, the number is 1017 places or "bits" long--nearly as long as the 1024-bit numbers currently used to encode electronic messages--and the researchers' method of using a network of computers raises the prospect of hijacking PC and video-game systems to try to crack codes. However, security experts say they're confident they can stay ahead of would-be hackers.
To keep financial transactions or military intelligence under wraps, these secret messages are transformed into strings of numbers, which are then multiplied or otherwise mixed up with other large numbers that serve as "keys" for scrambling and decoding the message. For example, the widely used RSA encryption scheme uses two keys. A public key is essentially a very large number that is the product of two prime numbers and is available to everyone. A private key consists of the two prime numbers. The public key allows anyone to send an encrypted message, but only the holder of the private key can read it, using the two prime numbers to unlock the original message. The only known way to crack RSA is to factor the public key, which requires long, brute-force calculation. Nevertheless, in 1999 researchers mustered enough computing power to show that 512-bit public keys then commonly used in Europe could be factored into the primes (Science, 3 September 1999, p. 1472). That result led to an increased adoption of 1024-bit keys.
To factor the 1017-bit behemoth, Thorsten Kleinjung of Bonn University and colleagues distributed the number crunching over hundreds of computers that among them tallied a total of 95 years of processing time. Previously, one important step in the computation, called the matrix step, had to be performed by a large cluster of computers in a single location. "What is a really new aspect of this work is that we have been able to distribute this matrix step over [computers at] different locations," says Arjen Lenstra of the Swiss Federal Institute of Technology in Lausanne. The team reported the result in an open memo to their fellow mathematicians.
The result raises the possibility that criminals might someday commandeer computers on the Internet to crack codes, Lenstra says. In fact, Play Station 3 video-game systems, which are optimized for number crunching and typically connected to the Internet, could provide a useful resource for such chicanery. Kleinjung and his colleagues are now trying to get their hands on a substantial number of Play Stations. "We want to have thousands of them, or ten thousands, and see what analytic potential they may have," says Lenstra.
Ronald Rivest, a cryptographer at the Massachusetts Institute of Technology in Cambridge and one of the developers of the RSA code, says that a real breakthrough in the basic mathematics of factoring large numbers might cause a problem, but meanwhile he is confident that RSA encryption will remain secure. "There are already recommendations to switch to keys of 2048 bits; ... the software is flexible," he says.