- News Home
5 December 2013 11:26 am ,
Vol. 342 ,
At age 30, Dutch biologist Freek Vonk has built up a respectable career as a snake scientist. But in his home country,...
Since arriving on the island of Guam in the 1940s, the brown tree snake ( Boiga irregularis ) has extirpated native...
An animal rights group known as the Nonhuman Rights Project filed lawsuits in three New York courts this week in an...
Researchers have been hot on the trail of the elusive Denisovans, a type of ancient human known only by their DNA and...
Thousands of scientists in the Russian Academy of Sciences (RAS) are about to lose their jobs as a result of the...
Dyslexia, a learning disability that hinders reading, hasn't been associated with deficits in vision, hearing, or...
Exotic, elusive, and dangerous, snakes have fascinated humankind for millennia. They can be hard to find, yet their...
Researchers have sequenced and analyzed the first two snake genomes, which represent two evolutionary extremes. The...
- 5 December 2013 11:26 am , Vol. 342 , #6163
- About Us
23 May 2007 (All day)
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.