[ISN] Math discovery rattles Net security

From: InfoSec News (isnat_private)
Date: Tue Nov 05 2002 - 04:08:14 PST

  • Next message: InfoSec News: "Re: [ISN] A New Cryptography Uses The Quirks of Photon Streams"

    Forwarded from: Elyn Wollensky <elynat_private>
    By Lee Gomes
    November 4, 2002
    Will Manindra Agrawal bring about the end of the Internet as we know
    it? The question is not as ridiculous as it was just two months ago.
    Prof. Agrawal is a 36-year old theoretical computer scientist at the
    Indian Institute of Technology in Kanpur, India. In August, he solved
    a problem that had eluded millennia of mathematicians: developing a
    method to determine with complete certainty if a number is prime.
    PRIME NUMBERS ARE those divisible only by themselves and 1. While
    small primes like 5 or 17 are easy to spot, for very large numbers,
    those hundreds of digits long, there never had been a formula of
    "primality testing" that didn't have a slight chance of error.
    Besides being a show-stopping bit of mathematics, the work was big
    news for the Internet. Very large prime numbers are the bedrock of
    Internet encryption, the sort your browser uses when you are shopping
    That encryption system takes two big, and secret, prime numbers and
    multiplies them. For a bad guy to decrypt your message, he'd need to
    take the product of that multiplication and figure out the two prime
    numbers used to generate it. It's called the "factoring problem," and
    fortunately it's something no one on Earth knows how to do quickly. A
    speedy method of factoring would make existing Internet security
    useless, not a pleasant thought in this Internet age.
    Prof. Agrawal's work involved only testing whether a number is prime,
    not the factoring problem. Still, there are enough connections and
    similarities between the two that mathematicians and computer
    scientists from all over the East Coast flew in to hear Prof. Agrawal
    on a whirlwind tour last week through the likes of M.I.T., Harvard and
    At Princeton, Prof. Agrawal's lecture was the sort of deep math that
    only the most beautiful minds could understand. In a subsequent, and
    more lay-friendly, interview he said he started his work three years
    ago. He was dealing with a different problem, called identity testing,
    when he noticed the solution hinted at a potential fresh assault on
    prime-number testing.
    It was a long three years. While no slouch in math, Prof. Agrawal said
    he sometimes had to use Google to find information on the more
    recondite aspects of number theory. His Eureka! moment came in July.
    As he was driving his daughter to school on his motor scooter, a
    particularly complicated mathematical set suddenly fell into place.
    The computer scientists who heard Prof. Agrawal speak said, with
    considerable pride, that he was obviously one of them, because of the
    way he proceeded purposely - "algorithmically" is the word they used -
    toward his goal. (As computer scientists tell it, mathematicians tend
    to be too showy and discursive about things.)
    Prof. Agrawal is the first to admit that his work, for all its elegant
    math, has no immediate practical application. He says the current
    tests for prime numbers, even with their slight chance of error, are
    good enough for most people, as well as extremely fast.
    Still, will he now move on to the factoring challenge? Yes, in due
    The best current method of factoring, he explains, is the Number Field
    Sieve. "Best" is a relative term, since all the computers in the world
    would still need untold trillions of years to use the system to factor
    just one big number.
    Prof. Agrawal writes the Number Field Sieve equation on a piece of
    paper, looks at it and winces. "Factoring is a natural problem. And
    natural problems should have a natural complexity to them. But this,"
    he says, pointing to the equation, "this is not natural complexity.
    This looks very strange. There must be something more natural than
    this out there."
    What he doesn't yet know, however, is whether a more "natural"
    approach to factoring also would be appreciably faster than current
    methods. And that, of course, is the $64 billion question.
    Most mathematicians say they don't lose any sleep about waking up and
    finding the factoring problem solved. It's just too hard, they say.
    (This difficulty was the very reason the method was chosen for
    Internet security in the first place.)
    But others, like Princeton math professor Peter Sarnak who hosted
    Prof. Agrawal on campus last week, aren't so convinced of the
    factoring problem's eternal intractability. The fact that one
    venerable mathematics problem has just been solved, said Prof. Sarnak,
    might inspire new assaults on factoring, possibly even using some of
    Prof. Agrawal's techniques.
    Prof. Agrawal said factoring will have to wait a few years; he wants
    to warm up with something easier, like "derandomizing polynomial time
    algorithms," for instance.
    The professor worked on primality testing with two of his graduate
    students: Neeraj Kayal and Nitin Saxena. They had planned to join him
    on his U.S. victory tour. But the American Embassy in New Delhi, the
    times being what they are, refused them visas. The two young geniuses
    had to stay home.
    ISN is currently hosted by Attrition.org
    To unsubscribe email majordomoat_private with 'unsubscribe isn'
    in the BODY of the mail.

    This archive was generated by hypermail 2b30 : Tue Nov 05 2002 - 06:32:10 PST