Another Nail in the RSA coffin.

[Matthew X]

Prime efforts may boost encryption

Ram Ram Bam Bam.
By Sandeep Junnarkar
Staff Writer, CNET News.com
August 9, 2002, 11:39 AM PT
Computer scientists in India have cracked an age-old mathematical problem 
by designing a method for computers to quickly prove whether a figure is a 
prime number--a vital step in cryptography.
RSA, a popular encryption algorithm used in securing Internet commerce, is 
built on the assumption that when prime numbers--those evenly divisible 
only by themselves and the number one--are large enough, they're nearly 
impossible to generate and determine.
To create encryption keys, RSA uses two huge prime numbers and multiplies 
them together to produce another number that is considered the "key."
Testing then confirms whether the initial numbers were in fact prime. The 
current algorithms used in so-called primality tests are speedy but have a 
miniscule probability of producing a wrong answer.
But a new algorithm, developed at the Indian Institute of Technology in 
Kanpur by Manindra Agrawal and his students Neeraj Kayal and Nitin Saxena, 
is believed to generate correct results each and every time.
"The most glaring weakness in the current cryptographic software is that we 
can't prove with a guarantee that a number is prime," said Eric Allender, a 
professor of computer science at the State University of New Jersey at 
Rutgers. "This new algorithm answers a fundamental question that has been 
open for some centuries and studied intensely for several decades."
Although Agrawal's paper on the subject, titled "Primes is in P," has yet 
to be published, it is causing a stir in the field because of the way it 
handles a math problem that has captivated mathematicians as far back as 
the ancient Chinese and Greeks. Several leading computer scientists and 
mathematicians have studied the paper.
"Some of the preceding work was quite complex," Allender said. "This is 
really a lovely, crisp and elegant algorithm."
Practical uses for the algorithm, computer scientists admit, are still far 
off.
"Our algorithm is slower than the fastest-known primality testing 
algorithms," Agrawal said. "The satisfying part of our algorithm is that it 
is completely deterministic as opposed to earlier ones that may make an 
error--even though rarely."
Computers scientists said that in many areas, people are often willing to 
live with that small probability of error. But with the increasing reliance 
on encryption in fields such as banking and secure communications, a 
greater priority is being placed on strengthening cryptography.
"The greatest import of this (algorithm) is as a theoretical result and as 
a first step," Allender said. "It opens the door. There will be subsequent 
refinements and improvements in the techniques to make it more practical."
E-mail story  Print story  Send us news tips
Related News
Critical hole found in encryption program June 27, 2002
Security company drops PGP encryption March 8, 2002
Distributed computing strikes gold December 13, 2001
Get this story's "Big Picture" FROM
http://news.com.com/2100-1001-949170.html?tag=fd_top