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 majordomoat_private with "subscribe isn". Today's ISN Sponsor: Hacker News Network [www.hackernews.com]
This archive was generated by hypermail 2b30 : Fri Apr 13 2001 - 13:22:57 PDT