. 1
( 2 .)



>>

Previous Page Home Next Page




Security Estimates for 512-bit RSA .................................... 1
Abstract .............................................................................. 1
1 Introduction ....................................................................... 2
2 Three projections .............................................................. 2
2.1 Dollar investment ......................................................... 2
Table 1: The estimated time in years required to factor a .......... 3
2.2 Well positioned adversary ............................................ 3
Table 2: The estimated time in years required to factor a .......... 4
2.3 Network attack ............................................................. 4
Table 3: The number of people that might be required to ........... 4

3 New techniques ................................................................. 5
4 Conclusions ....................................................................... 5
References ............................................................................ 7
Previous Page Home Next Page




Security Estimates for 512-bit RSA
M.J.B. Robshaw
RSA Laboratories
100 Marine Parkway
Redwood City, CA 94065-1031
matt@rsa. corn

June 29, 1995


Abstract

In this note we address the short-term security offered by the use of a 512-bit
RSA modulus. Following recent tremendous improvements to the practicality of the
generalized number field sieve, it must be expected that by the end of next year, a
512-bit RSA number will have been factored. However, for those fielded systems which
use 512-bit RSA, what are the implications? Some systems may well continue using
512-bit RSA long after one particular 512-bit RSA number has been factored. In this
note, we present data which might provide answers to questions about the continuing
use of a 512-bit RSA modulus.




Copyright @ 1995 RSA Laboratories, a division of RSA Data Security, Inc. RSA Data
Security Inc. part number oo3-SO3O5S-˜OO-OOO-OOO


1
Previous Page Home Next Page




1 Introduction
It is well known that the security of the RSA cryptosystem [4] relies on the
continuing impracticality of factoring large numbers of a particular type It is
also well known that advances in factoring techniques, together with contin-
ual improvements in hardware performance, mean that increasingly large and
˜difficult™ numbers can be factored as time goes by.
Using a variety of techniques it is possible to estimate, with reasonable ac-
curacy in the short term, the size of the modulus that should be used in an
implementation of RSA to attain some desired security level. However, there
are few estimates which provide information on the increasing vulnerability of
systems with a specific, and perhaps fixed, size of modulus.
For some considerable time a 512-bit RSA modulus has been considered as
offering relatively good security. However, recent improvements in factoring
techniques force us to closely consider the increasing vulnerability of a 512-
bit RSA modulus. In this note we try to estimate the likely risks involved in
continuing to use a 512-bit modulus over the next ten years.


2 Three projections
Throughout this note we will make some basic assumptions. Foremost among
them is that when using the generalized number field sieve [2] (which is at
present the most effective algorithm for tackling larger RSA numbers) then the
number of MIPS-years™ (abbreviated to MY) required to factor a 512-bit RSA
modulus is roughly 3 x lo4 [3].
Additionally we will assume that the computing power per dollar doubles
every 18 months (a common assumption) and that a 10 MIPS machine (or the
parts thereof) can currently be bought for U.S.$500.
In this note we have taken no account of potential algorithmic improvement.
However, it is worth noting that a number with special form and a length of
162 decimal digits was recently factored using the special number field sieve
[3]. While a number of 162 decimal digits is longer than one of 512 bits, this
factorization required a particularly modest 200 MY. If anywhere near this kind
of algorithm performance can be delivered on numbers without this special form,
then 512-bit RSA numbers will be truly weak.

2.1 Dollar investment
In this section we consider adversaries who are buying and setting up equipment
exclusively to factor 512-bit RSA numbers. The estimates that follow can easily
˜The number of operations completed in a year by a machine operating at one million
instructions per second.




2
Previous Page Home Next Page




be adjusted if it is felt that the cost of buying powerful computing equipment
is quite different from our presumed figure in 1995 of 10 MIPS for U.S.$500.
In the table that follows, we estimate the time in years required to factor a
512-bit RSA number with an investment of the dollar amount shown. We assume
that the increase in computing power translates into a drop in purchasing cost.
Note that in this table and others following, some numbers appear to remain
unchanged between successive years due to rounding.

year
2000
1998 1999
1996 1997
Investment
1.5
3.8 2.4
9.5 6.0
$100,000
0.2
0.4 0.2
0.9 0.6
$l,OOO,OOO
$10,000,000 0.1 < < < <
2004 2005
2003
2001 2002
0.2
0.4 0.2
0.9 0.6
$100,000
<.
< <
0.1 <
$1,000,000
$10,000,000 < < < < <

Table 1: The estimated time in years required to factor a 512-bit
RSA number with a given investment of 1996-2005 technology. The
symbol < is used to denote less than one month.

2.2 Well positioned adversary
In this section we consider the role of a systems administrator or some other
individual with access to a considerable amount of computing power within a
company. Such an individual might obtain factoring software from the Internet
and use the spare cycles on company machines to attack the keys used by
other employees. This consideration was motivated by calculations performed
by Odlyzko [3].
While an individual might attack one of the workers™ keys chosen at random;
the key used by a finance or policy director would most likely be the key under
threat.
In the following table we give the time required in years to attack a 512-bit
RSA modulus. We assume that each machine in the company has an effective
rating of 10 MIPS in 1995 ( since spare cycles are being used in the illicit factor-
ization). Machines that are considerably faster may well be available and would
alter the predictions accordingly. The number of workstations were chosen to
represent a small company, a large company and a very large company.




3
Previous Page Home Next Page




Table 2: The estimated time in years required to factor a 512-bit
RSA number, with a given number of workstations, for the years
1996-2005. The symbol < is used to denote less than one month.

2.3 Network attack
The increasing use of the Internet to network together computers is an important
feature in contemporary factoring efforts. In this section we try to estimate the
number of people required to participate in some widely publicized factoring
effort.
We shall assume that each person has access, and is willing to offer, 10 MIPS
worth of processing power in 1995 and an increasing amount in successive years
in line with improving hardware performance. In this third table we present the
number of people (or workstations) which are needed to factor a single 512-bit
RSA modulus in the time shown.

year
2000
time 1 996 1998 1999
1997
2 years 150
380 240
950 600
1 year 300
750 470
1900 1200
600
1500 950
3800 2400
6 months
2004 2005
2003
2001 2002
15
37 23
94 59
2 years
30
1 year 74 47
190 120
59
150 94
380 240
6 months

Table 3: The number of people that might be required to collaborate
on achieving the factorization of a 512-bit RSA number in a given time
period, for the years 1996-2005.




4
Previous Page Home Next Page




3 New techniques
In our analysis we have made no allowance for any potential algorithmic im-
provement. How much might this undermine the figures we have presented?
We have restricted our attention to a specific lo-year span, and it is unclear
how much algorithmic improvement should be allowed for within this period.
Perhaps there will be no substantial improvements within the next 10 years,
or perhaps any improvements will only be significant when applied to numbers
much longer than 512 bits.
It is unlikely, however, that this will in fact be the case. Already it is known
that the work effort required in April 1994 for the landmark factorization of
RSA-129 [l] could now be considerably reduced using the newer generalized
number field sieve.
We must stress that significant improvements to the number field sieve will
dramatically undermine any security offered by 512-bit moduli. Even if the best
improvements to the generalized number field were to make it only three times
more efficient than today2, then
$l,OOO,OOO could be spent next year to factor a 512-bit modulus in under
l

four months rather than almost a year,
a company with 5,000 workstations next year would have sufficient re-
l

sources to factor a 512-bit modulus in under six weeks rather than around
five months, and
a team of fewer than twice the number of people involved in the factoriza-
l

tion of RSA-129 could factor a 512-bit modulus in about six months next
year.
These should be serious considerations.


4 Conclusions
The figures in this report represent important implications for the use of 512-bit
RSA moduli, even in the short term.
Considering the effort required to factor a 512-bit RSA modulus, we have
observed that for an investment in 1997 of $l,OOO,OOO, an attacker might be

. 1
( 2 .)



>>