Re: Bellcore cracks 129-digit RSA encryption code (RISKS-16.03) [some insight .. djf]

[David Farber <farber () central cis upenn edu>]

Date: Mon, 9 May 1994 18:04:54 +0100
From: pcl () foo oucs ox ac uk (Paul C Leyland)
Subject: Re: Bellcore cracks 129-digit RSA encryption code (RISKS-16.03)


>   predicted would take "40 quadrillion years" to break.  ...


>   This mathematically arduous task was accomplished in eight months by
>   600 volunteers in 24 countries who used their organizations' spare
>   computing capacity.  ...


There are two risks, one amusing.  Ron Rivest now regrets ever making that 40
quadrillion years estimate.  It was silly when he made it; his papers in the
scientific literature from that era give estimates which are within an order
of magnitude of how much computation we actually used.  From those estimates,
and the observation that way back then it wasn't feasible to hook together
hundreds of computers, we can deduce that a late 70's supercomputer using the
best algorithms available then would have taken a few decades, maybe a
century.  Certainly much less than the 40 quadrillion years.  The risk is:
making predictions about the runtime of computer programs can sometimes make
you look silly 8-)


The other risk is more serious.  RSA is widely used to protect commercially
significant information.  512-bit keys are widely used for this.  Most, if not
all, smart-card implementations are restricted to 512-bit keys.  RSA-129 has
425 bits.  I estimate (taking a risk 8-) that 512-bit keys are only about 20
times harder to break than 425-bit keys.  Readers are left to draw their own
conclusions.  However, it is not by chance that I have a 1024-bit PGP key.


Oh yes, as Arjen Lenstra had pointed out: if you had used RSA-129 as
the modulus in a digital signature for a 15-year mortgage, you would
have been cutting it pretty fine.  It is the use of RSA for long-lived
signatures which needs to be examined with a very critical eye.


Paul Leyland (one of four RSA-129 project coordinators)


------------------------------


Date: Fri, 6 May 1994 02:45:26 +0200
From: Dik.Winter () cwi nl
Subject: Re: Bellcore cracks 129-digit RSA encryption code


Perhaps because there is no risk beyond the known ones?  Bob Silverman of
MITRE (well known in number factoring circles) has publicly predicted already
some time ago that it would require about 5000 MIPS years to factor the
number.  Reasonably close to the actual figure.


That the team was led by Bell Communications Research is untrue.  It is a team
led by four people from Bellcore (Arjen Lenstra), MIT (Derek Atkins), Iowa
State University (Michael Graff) and Oxford University (Paul Leyland).


dik t. winter, cwi, kruislaan 413, 1098 sj  amsterdam, nederland, +31205924098
home: bovenover 215, 1025 jn  amsterdam, nederland; e-mail: dik () cwi nl