printed copies are available for an annual

around the use of elliptic curves.

can be brought

subscription fee of U.S. $90. To subscribe,

together for the

contact RSA Laboratories at:

Our second invited article, i%e Future of Integer

benefit of the

Factorization by A. Odlyzko, provides a valuable

cryptographic

RSA Laboratories

contemporary assessment of factoring ability. The

community.

100 Marine Parkway, Suite 500

article also provides some thoughts on possible

Redwood City, CA 94065

trends for the future and potential developments

415/595-7703

well into the next century. Because of the obvious

415/595-4126 (fax)

relevance of this article to the continuing safe use of

rsa-labs@rsa.com

the RSA cryptosystem, we conclude the article with

the current RSA Laboratories minimum key-size

Back issues in electronic form are available

recommendations for users of RSA.

via the World-Wide Web at

http://www.rsa.com/rsalabs/clyptobytes/.

Following on pieces in the last issue of CryptoBytes

we include an article providing details of an initial

analysis of the RC5 encryption algorithm. In addi-

tion, readers interested in last issue™s articleMessage

Authentication with MD5 will find a short letter by RSA Latwmtories ts the reseanb anddeoelopment division ofRsA

P. van Oorschot and B. Preneel essential reading. Da&z Security, Inc., the companyfounded by the inuznton oftbe

RSApubIic-keycr@xystem. RSA Laboratories reyiews, aligns

and implemat˜ssenr˜aande˜˜tct yprosystemsfal(˜nds. Its

We also include a short review of recent analysis clientsinclu&˜mentagencies, telecommunications˜ompa-

into the performance of MD5. Since one of the nies, computer manufacturers software ahelopeq cable TV

original aims of CryptBytes was to provide a basic, buoadcarre, inatiw video manufachlm, andsatellitebmzd-

cast companies, among others.

reliable cryptographic news service, we are hoping

that this item will be the first of an occasional but

ongoing feature, Algorithms Update. By providing a

suitable forum, we hope that reports on major

CRYPTOBYTES SUMMER 1 9 9 5 -THE TECHNICAL NEWSLETTER OF RSA LABORATORIES

Page 44

Previous Page Home Next Page

Elliptic Curve Cryptosystems

Continued from page 1

Comparing these two running times, one can multiplication and inversion) in the underlying There are many

conclude that with our current state of knowl- finite field F, and thus can be efficiently imple- cryptographic

edge, it is roughly as difficult to compute dis- mented. protocols whose

crete logarithms modulo a prime p as it is to fac- security is based

tor an integer n of the same size. The main attraction of elliptic curve cryptosys- on the discrete

terns arises because the analogue of the discrete logarithm prob-

There are many cryptographic protocols whose logarithm problem in these curves is apparently lem in ZI, [. ..I.

security is based on the discrete logarithm prob- much harder than the discrete logarithm prob- However, they

lem in Zk for example the ElGamal public-key lem in Z;, and the integer factorization problem. can equally well

encryption and signature schemes, the Digital More precisely, let E be an elliptic curve defined be described in

Signature Algorithm (DSA), and the Schnorr sig- over a finite field F4, where q is a prime or prime the setting of

nature scheme. Originally these protocols were power. Let n denote the number of points on E; any finite group.

all described in thealgebraic setting of the multi- it is always the case that n is roughly equal to q.

plicative group q. However, they can equally If n is a prime (or at least divisible by a large

well be described inthe setting of any finite prime) then the best method known for comput-

group, for example the multiplicative group of ing discrete logarithms in E are the fully expo-

the finite field Fy of characteristic 2. nential algorithms of Shanks and Pollard, which

have an expected running time of about 6 ellip-

Why consider other groups? tic curve operations. What should be noted here

There are two primary reasons for this. Firstly, is that the function 5 grows much faster than

other groups may be easier to implement in soft- the running time functions for discrete logs in Z;,

ware or hardware. Secondly, the discrete loga- (equation (1)) and factoring integers (equation

rithm problem in the group may be harder than (2)).

the discrete logarithm problem in 5. Conse-

quently, one can use a group G that is smaller As a concrete example, let E be an elliptic curve

than 5 while maintaining the same level of se- over the field Fa160. As an optimistic estimate,

curity. This results in cryptosystems with smaller suppose that a machine rated at 1 mips can per-

key-sizes, bandwidth savings, and possibly faster form 40,000 elliptic curve operations per second.

implementation. (This estimate is indeed very optimistic - an

ASIC built by MOBIUS Encryption Technologies

Elliptic curves for performing elliptic curve operations over the

In 1985, Neal Koblitz and Victor Miller indepen- field Fz155 has a 40 MHz clockrate and can per-

dently proposed using the group of points on an form roughly 40,000 elliptic operations per sec-

elliptic curve in existing discrete-log cryptosys- ond.) Then the computing power required to

terns. For an introduction to this subject, the compute a single discrete logarithm in E is about

reader is referred to the books by Koblitz [21 and lOI MY (mips-years). By contrast, based on the

Stinson [41. A more complete treatment is given most recent implementation of the number field

by Menezes 131. Without going into all the de- sieve for factoring by Dodson and Lenstra 111, the

tails, an elliptic curve over a finite field F is the computing power required to factor a 1024-bit

set of all solutions (also called points) (x,y), x F, integer is estimated to be about 3 * 101™ MY (see

y F, to an equation of a special form. For ex- Andrew Odlyzko™s article in this issue). Thus an

ample, if the finite field is F = Zp, the integers elliptic curve cryptosystem over the IbO-bit field

modulo a prime p, then the equation has the F2160 offers the same level of security as RSA or

form yz = x3 + ax + b, where a,b Z, and DSA with a modulus size of 1024 bits.

4˜3 + 27b2 1L 0 (modp). There is a simple group The advantage of the elliptic curve system is that

law for adding two points on the curve to pro- arithmetic in the field F2160 is far easier to imple-

duce a third point. The addition rule simply in- ment, both in hardware and software, than arith-

volves a few operations (addition, subtraction, metic modulo a 1024-bit integer. For example,

CRYPTOBYTES

1995

SUMMER

LABORATORIES -

NEWSLETTER OF RSA

THE TECHNICAL

Page 45 Previous Page Home Next Page

the ASIC mentioned above for performing ellip creases. The smaller key sizes result in smaller sys-

[,,.I elliptic curve

In addition, the encryption and signature tem parameters, smaller public-key certificates,

cryptosystems

schemes based on elliptic curves are an order of bandwidth savings, and faster implementations. El-

offer the most

security per bit liptic curve systems are particularly beneficial in

magnitude faster than 1024-bit DSA and RSA.

applications where computational power and inte-

of any known Similar speedups are now possible in software

grated circuit space is limited, such as smart cards,

public-key due to recent advances in the software imple-

PCMCIA cards, and wireless devices. b

scheme [. ..] mentation of elliptic curve cryptosystems over

Fp.

References

In summary, elliptic curve cryptosystems offer the

111 B. Dodson and A. Lenstra, “NFS with four large primes:

most security per bit of any known public-key

an explosive experiment”, Advances in Ctyptology-

scheme. This will tend to increase their attractive-

CRYpTO™95, to appear.

ness relative to other cryptosystems as computing

121 N. Koblitz, A Course in Number 7beory and Cryptog-

power improvements warrant general key size in-

raphy, Springer-Veriag, New York, 1994.

tic curve arithmetic over Fy55 has only 12,000

gates, and would occupy less than 5% of the area 131 A. Menezes, Elliptic Curue Public Key Ct3/ptosystems,

Kluwer Academic Publishers, Boston, 1993.

typically designated for a smart card processor.

I41 D. Stinson, Cryptography- 78eoty and Practice, CRC

Press, Boca Raton, 1995.

STANDARDS UPDATE

a standard for cryptography based on elliptic

Elliptic Curves in Draft IEEE Standard

curves.

Elliptic curve cryptosystems are taking another

For more information on P1363, contact the work-

step forward from theory to practice as part of a

ing group™s chair, Burt Kaliski of RSA Laborato-

draft standard being prepared by IEEE™s ˜I363

ries. Meeting notices and draft materials are avail-

working group, Standardfor RSA, DQfie-Hellman

able by anonymous ftp to ftp.rsa.com in the pub/

and Related Public-Key Cryptography.

˜1363 directory. The next meeting of P1363 will

review the elliptic curve material and is sched-

Four cryptographic mechanisms based on elliptic

uled for August 31-September 1 at the University

curves are currently being considered:

of California, Santa Barbara, following the

l Elliptic Curve Encryption Scheme (ECES), an

CRYPTO ˜95 conference.

analog of the ElGamal public-key crypto-

system;

S/MIME Standardized

Elliptic Curve Signature Scheme (ECSS), an

l

A group of leading networking and messaging

analog of a variant of the ElGamal signature

vendors, in conjunction with RSA Data Security,

scheme;

Inc., recently endorsed a specification that will

Elliptic Curve Digital Signature Algorithm

l

enable encrypted messages to be exchanged be-

(ECDSA), an analog of NIST™s Digital Signa-

tween E-mail applications from different vendors.

ture Algorithm; and

Vendors participating in the announcement in-

Elliptic Curve Key Establishment Protocol

l

cluded ConnectSoft, Frontier, FTP Software,

(ECKEP), an extension of Diffie-Hellman key

Elliptic curve

Qualcomm, Microsoft, Lotus, Wollongong, Ban-

agreement that provides implicit key authenti-

cryptosystems

yan, NCD, SecureWare, and VeriSign.

cation.

are taking

The specification - Secure/Multipurpose Internet

another step

Mail Extensions (S/MIME) - is based on the

Other algorithms to be included in the standard

forward from

popular Internet MIME standard (RFC 1521) with

are RSA, Diffie-Hellman and ElGamal. The stan-

theory to

the secure portion of the message defined by the

dard will also have sections on random number

practice.

public key cryptography standards PKCS #7 and

generation and hardware support for public-key

PKCS #lo.

cryptography.

Developers interested in S/MIME can get more

ISO/IEC JTC l/WG 2/SC 27 (Security Techniques

information in “What™s New” on RSA™s web page

- Techniques and Mechanisms) is also drafting

(http://www.rsa.com). h

CRYPTOBYTES SUMMER 1 9 9 5 -THE

ia TECHNICAL NEWSLETTER OF RSA LABORATORIES

Page 46

Previous Page Home Next Page

The Future of Integer Factorization

variety of other benchmarks are used in preference to

AndxewM.Odlyzko

mips measures. Still, given the uncertainty in any

AT&T Bell Laboratories

projection far into the future, this measure seems ad-

Murray Hill, NJ 07974 USA

equate.

Introduction

How large should be the moduli in public key crypt@ 43D will refer to an integer of 43 decimal digits.

systems such as RSA and DSS (the US Digital Sig-

nature Standard)? The answer depends on the an- Discussion will be restricted to integer factorization. There is a

ticipated threats. Even if those are known, there is Discrete logarithms are, with the present state of long record

no way to provide a definitive answer, since progress knowledge, slightly more difficult to compute modulo of estimates

in integer factorization and discrete logarithm algo- an appropriately chosen prime than it is to factor a of sizes of

rithms is not predictable. (Furthermore, there is still “hard” integer of the same size, but the difference is integers that

the possibility that RSA and DSS could be broken not large Ill]. Therefore to be on the safe side in could be

designing cryptosystems, one should assume that all

by other methods than factoring or discrete log ap- factored.

the projections about sizes of integers that it will be

proaches.) However, since choices of moduli have to They have

be made, it is necessary to make some estimates, and possible to factor will also apply to sizes of primes uniformly

this note attempts to do so, taking into account both modulo which one can compute discrete logarithms. turned out to

the increase in available computing power and fu- be too low.

Factorization records and

ture algorithmic developments. The projections

historical estimates

made below suggest that RSA and DSS moduli might

There is a long record (see Appendix A) of estimates

have to be unpleasantly large. In particular, the 512-

of sizes of integers that could be factored. They have

bit moduli that have been adopted in a variety of

uniformly turned out to be too low, primarily because

cryptosystems are already unsafe for all applications

of unanticipated algorithmic improvements. Faster

except those with very modest security requirements.

than expected growth in available computing resources

I would like to stress that while the assertion about also played a role, though. Table 1 summarizes the

insecurity of 512-bit moduli is easy to support with progress that has occurred in the last few decades. Table

solid technical evidence, the projections about the 2 shows how much the computing power available for

future are much less certain, and should not be treated integer factorizations has increased.

as firm forecasts, but as possible ways that computa-

tional number theory might develop. Table 1 (see Appendix B)