Israeli Scientist Reports Discovery of Advance in Code Breaking

Dan Kohn (dan@teledesic.com)
Sun, 2 May 1999 23:42:45 -0700


This message is in MIME format. Since your mail reader does not understand
this format, some or all of this message may not be legible.

------ =_NextPart_000_01BE952F.0C944E00
Content-Type: text/plain

> http://www.nytimes.com/library/tech/99/05/biztech/articles/02encr.html
>
> Copyright 1999 The New York Times Company
>
>
> May 2, 1999
>
> Israeli Scientist Reports Discovery of Advance in Code Breaking
>
> By JOHN MARKOFF n 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.

------ =_NextPart_000_01BE952F.0C944E00
Content-Type: application/ms-tnef
Content-Transfer-Encoding: base64

eJ8+IjUGAQaQCAAEAAAAAAABAAEAAQeQBgAIAAAA5AQAAAAAAADoAAEIgAcAGAAAAElQTS5NaWNy
b3NvZnQgTWFpbC5Ob3RlADEIAQWAAwAOAAAAzwcFAAIAFwAqAC0AAABLAQEIAAUABAAAAAAAAAAA
AAEJAAQAAgAAAAAAAAABIIADAA4AAADPBwUAAgAXACIANAAAAEoBAQmAAQAhAAAAMDUyOEIxREJG
NTAwRDMxMUFDNTcwMDgwQzc0MjNBNzIA8QYBBIABAEAAAABJc3JhZWxpIFNjaWVudGlzdCBSZXBv
cnRzIERpc2NvdmVyeSBvZiBBZHZhbmNlIGluIENvZGUgQnJlYWtpbmcAIhcBDYAEAAIAAAACAAIA
AQOQBgC4DwAAMQAAAAsAAgABAAAACwArAAAAAAADAC4AAAAAAAIBMQABAAAAUgEAAFBDREZFQjA5
AAEAAgB2AAAAAAAAADihuxAF5RAaobsIACsqVsIAAEVNU01EQi5ETEwAAAAAAAAAABtV+iCqZhHN
m8gAqgAvxFoMAAAAVERNQUlMAC9vPVRFTEVERVNJQy9vdT1LSVJLTEFORC9jbj1SZWNpcGllbnRz
L2NuPWpvcmRhbm5lAC4AAAAAAAAAhQ1coicR0hGVsgCAX+ZzvwEA710bL/JT0RGVqgCAX+ZzvwAA
AGBF4QAAAAAAAC4AAAAAAAAAhQ1coicR0hGVsgCAX+ZzvwEA710bL/JT0RGVqgCAX+ZzvwAAAGBF
4gAAEAAAAGWepaoLAdMRlcEAgF/mc79LAAAARlc6IFtQR1BdOiBJc3JhZWxpIFNjaWVudGlzdCBS
ZXBvcnRzIERpc2NvdmVyeSBvZiBBZHZhbmNlIGluIENvZGUgQnJlYWtpbmcAAABAADkAYNaLJjCV
vgEDAF1AAAAAAB4AcAABAAAARwAAAFtQR1BdOiBJc3JhZWxpIFNjaWVudGlzdCBSZXBvcnRzIERp
c2NvdmVyeSBvZiBBZHZhbmNlIGluIENvZGUgQnJlYWtpbmcAAAIBcQABAAAAIAAAAAG+lOqLDvJk
o6b/eBHSik4AgF+t1OUAC9NgMAACgNUwCwAXDAAAAAAeADFAAQAAAAQAAABEQU4AAwAaQAAAAAAe
ADBAAQAAAAQAAABEQU4AAwAZQAAAAAACAQkQAQAAAIAJAAB8CQAAzhAAAExaRnXvkXPWAwAKAHJj
cGcxMjXiMgNDdGV4BUEBAwH3/wqAAqQD5AcTAoAP8wBQBFY/CFUHshElDlEDAQIAY2jhCsBzZXQy
BgAGwxEl9jMERhO3MBIsETMI7wn3tjsYHw4wNREiDGBjAFAzCwkBZDM2FlALpiA+BCBoAkBwOi8v
d6EdgC5ueXQHci4FoEBtL2xpYnIKwHkGLw6wE9AvOTkvMOA1L2Jpeh8DCsAd4GxjbAeQH3AyCfAF
AC7dHRBtGAAKsQqAPiF1EiGUcHkFEGcdECAxH1CgOSBUaGUHs1kFsO5rI0AHcwhQbQqwHcAhfIEh
5k1heSAyLCLz0yF9J+BJcx6wZR6ABgAeYwiQAjAEAAVAUmVw2xfBBCBEBAAFoHYEkCZwpG9mEMBk
dgBwYyNwJwuAEiEBACBCGCBhaxULgGchfUImcEpPSAJOBdBBUktPRkbPJ+ADoCgWHkFwdQ6wBcDX
BPAotgQAIA7AcAWQDrCwZCB0by8gE+BrI3BUdXAneHQjYXcFsGxXMHAqUQUAeQUwbwnAYdxwaCZw
MeAv0XcJ4CQAXncjYAOgI2ELgHQDYGSzGtAHkWEgAQAAkGcDoO0CEHIh5jVSdg3gI3Ax4JZhBUAF
oHUyUXF1DeC0a2wmcHUAgAUAYQbQ8yCALpctZwnwBJA3QDBhfwWgNXE3EyHmOFAd4AMgbs5vB+AT
4CoAIGIJ4S6R7wCBBIEwYRQQYwhwI3AJ8P8IYCLANdI10AuAKrEHMTVA1m4LMSIEZynybgeAAjBd
LpJtOFAN4DdAaTyhLv0hfUkDoDVQCrAwIAXAMJG/PEBCgBggFBACMDBhVApQrHNkJmErAVAesGcK
UOcmoDHiLq90LCd4KoAocfET4G1pciagAiAjcCpR7THnJwQgNeFlBGApATK57QSQcyagA/BsIWY1
YgUB/0MhNVAAwTOQObAmoDuwBUDueRQgPDA34GxGcDcaKqD/KQA4IQdwQ1Ap8THSNhcfsP0egHQq
MzoyPDArkkphMIL/BYEFIEpROic90gVAQvQ4UP9Q8wGgIIAh5isBQ1AA0CBR+z7RLvFtHiAjQiZw
CsAxAf8UEDBzTuEfAQVANsAqETOB/yvgNdADYSHmPmg0wABxVQL/PKFH4THTQkAu8TmwUwMA0Ps3
cUAxYgdAKrIEICkASTHHMHALgSH1c28tVUEggP89IQDAACBFUAsRQT4h5kd0/0jxPNE1UDIgN5Ie
QR+wSAG/DsAo8VfyHwI7sBewZ0RS/1tiLyAwIQcxIeZFZzcpQyH/TTM+EzVQK5FdsD6AOMRGYf8v
IAtwPSIqAWQ4MAIpcjQgfzCgO/MUEDRBMeJCk1XQSf8vswTwI2A08F4SQv46uAOR+QBwbnU+0QeA
FCBX8kg111rUQOM+0UEEEG8+sUDy/T4TQzLIDeAh5ikwFBAKwN8T0EqRchE+ADxAZwuAWkP+TQIg
RDFBTifgI1I+gAeA/SpCTWsxR3Y1UEVvBUA3QXxXZR/AA4EuAQCAHeB0fy7hIeYqUSiTKtQpMFKw
dj9MwHMxKBQmoC/RMeIiU84ieyN2wVXQQS5FA2jX/yDxMtFw8jV1NyMT4AQgPED/HkFPIzSSb8kp
AD8BCxE12p89RVmTR6AEEEEDIEgq4fs1MgWgLQuAKgBjgQXAKlHHfWB9kH3AIC0tSqEx4OcH8XAx
PydSaSoAKQFINf8mUAQQTDFWgQJABCB5dypCxlRi2D8BIExlZ0ELIt8iBCqAIIADgkg1VQMAKgH7
AJBQRFMIYDHhEgIHQAaQuwWwAwBhdM+F9i/Razux30JRBCAu0AJgDeAtMPAmcO8yumtBWnJrknkp
AElQd0L/QrFnMSd4gCJCcZGjkPBWEv+LIUJxBRAqoIoBkgFV05Wa/y/RVoVdNziGTAEHkFnQOZBf
iwMAwCZwU1JWkmKK8nnfR/Fn8TCgUDBeoW4moFeB/wOgMMA3gkaJQyEAwCtRkZT9VdBCLuBqpJbI
NxQv0Tmw/wmAMGQ4WU9JJ+CaRkCQKQH/QyEw8AUxPUEYIE0RM2JDMf+UU2nEBvBe4JyRj0+F9Sag
/x6AMPEDgSZwkZmTpEqBL9H3XBBWklplZlUBoLU6xy/R/wdwQBEUEDghR0ABIA3gN5DfeJGLIR3i
XdA8oXVHoFgCPwWxnSMx4kljKVAz0HJmvzeQZF5RY6tCBbELYHKakf9uUAbQSmGfZHaoSPFMJWFE
/yHmAMAw8bIUV/Ky5ZFSF7DPWAGVUgbgn5ExNRZQR0D/c+ApgUCQc5FnEQiRRQJWgP+1WVfynKG5
AwCQJKAggELT/xggKgBuc5pja6I4lDBwhqP/kZh+PwOgB4BSoV7vRwKy1f8qQp7AKqNg4TXBtjc7
+J6z/ysBMeILYCkBPmAqACHmTPDvE/GfZEljSDRtVjMx4kNh662ywhJwC1B5V/IeoInyvzXhNvIw
oKKbTuE4wW3Ab/d40DQyhgV3gDGk0TnjKwH5IwA3NyagdqiLAzOSF5H/IIBEwroHE9FeASvgbTKc
A19sUyuSRRUBAFXQRbuhb/vI885BMEjxYshGhzHhqZGfaCF3Q0nKYUWhQiA0FlD/N9CewAUQStBw
8sYTsdg2GP+VqHdBrgJWAkNRR0AwRDcy/50jhqMAcCBRBSA548JGVDnfd4wq0ZrEx0JA4WNKgTuw
/0fjYVRL0qJT0iXVCVCUO1T/M9BK0GNkMeI5sA7RKtACMP8IcHS/J/HC5HdCmkYx4jTA/0EAO+Ew
cCDhBHG9tTVQDiB8OS24k5YCXTca0DURc/+wkTghhqJcoQRwbVEBkDgA5z4TAiA4ITE3xgZrYc1S
/7IUm5NtiYEcDrA4oCpCQ2LncwJRQs4TOTTmP40gAJB/WAGzv0xjOIE4AGKDI2Ex/9fg6nXBpeHG
IeYYITUBMHN/MeKtV1BU9fY1UJYTuAM4/7h3t3OGcPhIC2Ad4CoAOCH/ZxGbITNhBHAmYEjxgfbA
X/+QQfHpaBOgxCpgM5K0iCPw/1zi7rE3gweAbgE6mjK5leHfqbWGlJIBWkEqYDUOIDww/7jCslKa
UYZioMUmoAbiwOa/CCM3IUJRuA78heG4djeQ/zmyOMLElbCQ5fFE8MDobgH/MAFJcINjNzJhVGoW
dkAwcH87UUxRU+PtpMVS2MVEwG9PQUYjQ7dyFsExLCDANP4tB6EG1DcjVkI8ABuAXDD/4mREMtc1
TMH4KAy5N0FDVQVBRX0Z0AMA3j+vbwAAAwABbiAAAAADAAGACCAGAAAAAADAAAAAAAAARgAAAABS
hQAA4xUAAB4AAIAIIAYAAAAAAMAAAAAAAABGAAAAAFSFAAABAAAABAAAADguNQADAAKACCAGAAAA
AADAAAAAAAAARgAAAAABhQAAAAAAAAsAA4AIIAYAAAAAAMAAAAAAAABGAAAAAAOFAAAAAAAACwAE
gAggBgAAAAAAwAAAAAAAAEYAAAAADoUAAAAAAAADAAWACCAGAAAAAADAAAAAAAAARgAAAAAQhQAA
AAAAAAMABoAIIAYAAAAAAMAAAAAAAABGAAAAABGFAAAAAAAAAwAHgAggBgAAAAAAwAAAAAAAAEYA
AAAAGIUAAAAAAAAeAAiACCAGAAAAAADAAAAAAAAARgAAAAA2hQAAAQAAAAEAAAAAAAAAHgAJgAgg
BgAAAAAAwAAAAAAAAEYAAAAAN4UAAAEAAAABAAAAAAAAAB4ACoAIIAYAAAAAAMAAAAAAAABGAAAA
ADiFAAABAAAAAQAAAAAAAAADACYAAAAAAAMANgAAAAAACwBDgAggBgAAAAAAwAAAAAAAAEYAAAAA
BoUAAAAAAAADAPE/CQQAAAMA/T/kBAAAAwCAEP////8CAUcAAQAAAC8AAABjPVVTO2E9IDtwPVRF
TEVERVNJQztsPVRETUFJTC05OTA1MDMwNjQyNDVaLTY3AAAeADhAAQAAAAQAAABEQU4AHgA5QAEA
AAAEAAAAREFOAEAABzCKGdklMJW+AUAACDAATpQML5W+AR4APQABAAAAAQAAAAAAAAAeAB0OAQAA
AEAAAABJc3JhZWxpIFNjaWVudGlzdCBSZXBvcnRzIERpc2NvdmVyeSBvZiBBZHZhbmNlIGluIENv
ZGUgQnJlYWtpbmcAHgA1EAEAAABAAAAAPEVGNUQxQjJGRjI1M0QxMTE5NUFBMDA4MDVGRTY3M0JG
MDEyMTA5ODVAdGRtYWlsLnRlbGVkZXNpYy5jb20+AAsAKQAAAAAACwAjAAAAAAADAAYQZfOzRQMA
BxA2CwAAAwAQEAEAAAADABEQAQAAAB4ACBABAAAAZQAAAEhUVFA6Ly9XV1dOWVRJTUVTQ09NL0xJ
QlJBUlkvVEVDSC85OS8wNS9CSVpURUNIL0FSVElDTEVTLzAyRU5DUkhUTUxDT1BZUklHSFQxOTk5
VEhFTkVXWU9SS1RJTUVTQ09NUEEAAAAAAgF/AAEAAABAAAAAPEVGNUQxQjJGRjI1M0QxMTE5NUFB
MDA4MDVGRTY3M0JGMDEyMTA5ODVAdGRtYWlsLnRlbGVkZXNpYy5jb20+ANnT

------ =_NextPart_000_01BE952F.0C944E00--