<<

. 11
( 19 .)



>>

implementational,
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)

<<

. 11
( 19 .)



>>