Gavin writes:
>Wirt writes:
>> As they say in big-time lawyerly circles, the whole question may be moot [or
>> as they say in military circles: OBE ("overcome by events")]. The NY Times
>> reported this story a few days ago on May 2:
>>
>> =======================================
>>
>> Israeli Scientist Reports Discovery of
>> Advance in Code Breaking
>
>Shamir's proposed machine is interesting, but does not fundamentally
>change anything. He's got a way to factor numbers up to about 512
>bits in size relatively quickly, but this method does not scale well,
>and 1024 bit numbers still appear unfactorable up until the Sun burns
>out.
Two things make me less confident than Gavin. First, 23 years ago, Ron
Rivest (the R in RSA) offered a design for a machine to mount a
brute-force attack on DES that could find a truly random key in a few
hours, and some keys (keys likely to be seen within a typical commercial
cryptosystem) within a few seconds. The machine was derided as
impractical: it was too complex, the MTBF for its chips would preclude
any successful solutions, and so on. But at least one such machine exists
today, built last year entirely with private funds, which no doubt means
that most governments have had such machines for many years. Technology
increases exponentially, not linearly.
Second, the field of quantum computing is advancing a lot more rapidly
than even its most optimistic supporters were predicting five years ago.
There are now few theoretical problems remaining, and the practical
problems are being solved at an increasing rate. An article in this
week's _Nature_ (sorry, last week's now) describes a unit quantum cell
built by NEC that, unlike previous quantum computer experiments, lives on
a chip rather than in a large laboratory. (It still needs to be cooled to
liquid-helium temperatures.) For a quantum computer, factoring a 1024-bit
number will take twice as long as factoring a 512-bit number, rather than
the factor of 2^512 required by a classical computer.
The quantum computing approach merits special attention because it's so
early on its development curve, and theoretical work is still being done.
I liken the state of quantum computing today to the state of DNA
sequencing in 1992, when the Human Genome Initiative was first proposed.
In 1992, the project was expected to take 20 years and absorb the
energies of many thousands of people worldwide. In fact, one objection to
the project was that it would soak up so much laboratory capacity that
nothing else would get done. But when actual sequencing was begun a
couple of years later, it was expected to take 15 years, with work done
at just a few major centers. Today, several companies are proposing to do
the job (starting over from scratch) in under two years with a staff of
about 250.
Human beings are supremely lousy at predicting the course of events that
evolve exponentially. If I had a secret I needed to keep for 10 years,
I'd be quite uncomfortable trusting that secret the the difficulty of
factoring a 1024-bit number.
-- Bruce
--------------------------------------------------------------------------
Bruce Toback Tel: (602) 996-8601| My candle burns at both ends;
OPT, Inc. (800) 858-4507| It will not last the night;
11801 N. Tatum Blvd. Ste. 142 | But ah, my foes, and oh, my friends -
Phoenix AZ 85028 | It gives a lovely light.
btoback AT optc.com | -- Edna St. Vincent Millay
Mail sent to [log in to unmask] will be inspected for a
fee of US$250. Mailing to said address constitutes agreement to
pay, including collection costs.
|
