http://www.nytimes.com/library/tech/99/05/biztech/articles/02encr.html
May 2, 1999
Israeli Scientist Reports Discovery of Advance in Code Breaking
By JOHN MARKOFF
An Israeli computer scientist is expected to shake up the world of
cryptography this week when he introduces a design for a device that could
quickly unscramble computer-generated codes that until now have been
considered secure enough for financial and government communications.
In a paper to be presented Tuesday in Prague, the computer scientist, Adi
Shamir, one of the world's foremost cryptographers, will describe a
machine, not yet built, that could vastly improve the ability of code
breakers to decipher codes thought to be unbreakable in practical terms.
They are used to protect everything from financial transactions on the
Internet to account balances stored in so-called smart cards.
Shamir's idea would combine existing technology into a special computer
that could be built for a reasonable cost, said several experts who have
seen the paper. It is scheduled to be presented at an annual meeting of
the International Association for Cryptographic Research, which begins on
Monday.
The name of Mr. Shamir, a computer scientist at Weizmann Institute of
Science in Rehovoth, Israel, is the "S" in R. S. A., the encryption design
that has become the international standard for secure transmissions. He is
a co-inventor of R.S.A. -- with Ronald Rivest of the Massachusetts
Institute of Technology and Leonard Adleman of the University of Southern
California.
R.S.A. is known as public-key cryptography. In this system, a person has a
public key and a private key. The public key is used to scramble a message
and may be used by anyone, so it can, even should, be made public. But the
private key that is needed to unscramble the message must be kept secret
by the person who holds it.
R.S.A., like many public-key systems, is based on the fact that it is
immensely difficult and time-consuming for even the most powerful
computers to factor large numbers. But Mr. Shamir's machine would make
factoring numbers as long as about 150 digits much easier, thus making it
much simpler to reveal messages scrambled with public-key encryption
methods.
A number of advances in factoring have been made in the last five years.
But most of them are the result of applying brute force to the problem.
When R.S.A. was created in 1977, Mr. Shamir and his colleagues challenged
anyone to break the code. Employing 1970's technology, they said, a
cryptographer would need 40 quadrillion years to factor a public key, and
they predicted that even with anticipated advances in computer science and
mathematics, no one would be able to break the code until well into the
next century.
In fact, a message the trio had encoded with a 129-digit key successfully
withstood attack for only 17 years. It was factored by an international
team of researchers in 1994.
Using Mr. Shamir's machine, cracking the 140-digit number would be reduced
to the difficulty of cracking a key about 80 digits long -- relatively
easy by today's standards.
Researchers said that if his machine worked it would mean that
cryptographic systems with keys of 512 bits or less -- that is, keys less
than about 150 digits long -- would be vulnerable in the future, an
exposure that would have seemed unthinkable only five years ago. The
longer 1,024-bit keys that are available today would not be vulnerable at
present.
-o-
Subscribe: mail majordomo@repsec.com with "subscribe isn".
Today's ISN Sponsor: Hacker News Network [www.hackernews.com]
Received on Mon May 3 08:06:34 1999