ñòð. 1 |

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 |