. 10
( 19 .)


can be contacted at stuart@belkore.com, burt@rsa.com and
to the “instructions” contained in its time-stamp

Page 40
Previous Page Home Next Page

certificate, to this widely witnessed summary num- serve the non-rep&ability desired of digital signatures
for important documents.
ber; this is how the particular record is tied to a par-
ticular moment in time. The verification procedure
takes a particular record and a putative time-stamp The statement that private keys cannot be derived
from public keys is an over-simplification of a more
certificate for that record and a particular time, and
uses this information to validate whether that record complicated situation. In fact, this claim depends on
the computational difficulty of certain mathemati-
was indeed certified at the time claimed by checking
it against the widely available summary number for cal problems. As the state of the art advances-both
that moment. the current state of algorithmic knowledge, as well
as the computational speed and memory available in
Two features of a digital time-stamping system are currently available computers-the maintainers of a
particularly helpful in enhancing the integrity of a digital signature system will have to make sure that
digital signature system. First, a time-stamping sys- Time-stamping
signers use longer and longer keys. But what is to
tem cannot be compromised by the disclosure of a become of documents that were signed using key strengthens
key. This is because digital time-stamping systems lengths that are no longer considered secure? If the non-repudiation
do not rely on keys, or any other secret information, signed document is digitally time-stamped, then its of digital
integrity can be maintained even after a particular
for that matter. Second, following the technique signatures.
introduced in [I], digital time-stamp certificates can key-length is no longer considered secure.
be renewed so as to remain valid indefinitely.
Of course, digital time-stamp certificates also depend
With these features in mind, consider the following for their security on the difficulty of certain compu-
tational tasks concerned with so-called one-way hash
functions. (All practical digital-signature systems de-
It sometimes happens that the connection between pend on these functions as well.) Those who main-
a person and his or her public signature key must be tain a secure digital time-stamping service will have
revoked-for example, if the user™s secure access to to remain abreast of the state of the art in building
the private key is accidently compromised; or when and in attacking one-way hash functions. Over time,
the key belongs to a job or role in an organization they will need to upgrade their implementation of
that the person no longer holds. Therefore the per- these functions, as part of the process of renewal [ 11.
son-key connection must have time limits, and the This will allow time-stamp certificates to remain
signature verification procedure should check that valid indefinitely.
the record was signed at a time when the signer™s
public key was indeed in effect. And thus when a
user signs a record that may be checked some time [l] D. Bayer, S. Haber, and W.S. Stometta. Improving the
later-perhaps after the user™s key is no longer in efficiency and reliability of digital time-stamping. In R.M.
effect-the combination of the record and its signa- Capocelli, A. De Santis, U. Vaccaro, editors, Sequences
ture should be certified with a secure digital time- II: Methods in Communication, Security, and Computer Sci-
stamping service. ence, pp. 329-334, Springer-Verlag, New York (1993).
[2] W. Diffie and M.E. Hellman. New directions in cryptog
There is another situation in which a user™s public raphy. IEEE Transactions on Information Theory, IT-22:
key may be revoked. Consider the case of the signer 644-654, 1976.
of a particularly important document who later [3] S. Haber and W.S. Stornetta. How to time-stamp a
wishes to repudiate his signature. By dishonestly re- digital document. Journal of Cryptology, Vol. 3, No. 2,
porting the compromise of his private key, so that all pp. 99-111 (1991).
his signatures are called into question, the user is [4] National Institute of Standards and Technology (NIST).
able to disavow the signature he regrets. However, if FIPS Publication 186: Digital Signature Standard, May
the document in question was digitally time-stamped 19, 1994.
together with its signature (and key-revocation re- [5] R.L. Rivest, A. Shamir, and L. Adleman. A method
ports are time-stamped as well), then the signature for obtaining digital signatures and public-key crypto-
cannot easily be disavowed in this way. This is the systems. Communications of the ACM, 2 l(2): 120- 126,
recommended procedure, therefore, in order to pre- February 1978. b

Page 41
Previous Page Home Next Page


The 1996 RSA Data Security There are plans for several open panel discus- in this issue:
Conference sions. On the final day, the focus of these dis- RSA for

cussions will be on electronic commerce and
doing business on the Internet. Meanwhile
The 1996 RSA Data Security Conference will Collisions

Washington will be the topic for discussion on
be held January 17-19 in the Fairmont Hotel, in MD4
the second day, with issues ranging from CLIP-
San Francisco. First held in 1991, this annual The Secure

PER, FORTEZZA and key escrow, to export
conference is expected to attract more than Use of RSA
Digital Time
control. Following the keynote address and
1,000 participants and provides an excellent l

company announcements on the first morning,
opportunity for business people, academic cryp- Stamps
a cryptographer™s expert panel will provide an
tographers and representatives of government
excellent opportunity for attendees to direct
to gather and debate the technology and busi-
their questions directly to some of the leading
ness issues facing the industry.
figures in cryptographic research.
Spread over three days, there will be a wide
Over the years, the RSA Data Security Confer-
range of seminars, tutorials and presentations.
ence has proved to be a great opportunity for
Many of the presentations will be focused on
vendors, developers and specialists to meet, and
the commercial applications of modem crypto-
like previous years it is expected to be filled to
graphic technology, with an emphasis on Public For subscription
capacity very soon. More information can be
Key Cryptosystems, but there will also be simul-
found on RSA™s web page (http:llwww.rsa.coml)
taneous tracks for developers, cryptographers see page 2 of
or by contacting the conference organizer,
and analysts from which attendees can pick and this newsletter.
Layne Kaplan Events, at 415/340-9300.
choose the talks they wish to attend. I


CA. 94065-1031
T E L 415/595-7703
F A X 415/595-4126

Copyright 0 1995 RSA Laboratories, a division of RSA Data Security, Inc. All rights reserved.
Page 42
Previous Page Home Next Page

The technical newsletter of RSA Laboratories, a division of %A Data Security, Inc.

Elliptic Curve Cryptosystems

col, which allows two parties Alice and Bob to
Alfred Menezes
establish a secret key through an exchange of
120 Math Annex
public messages, works as follows. Let p be a
Auburn University
large prime number, and let a be a generator of
Auburn, AL 36849 USA
the multiplicative group q; in layman™s terms
Elliptic curves have been intensively studied in this means that the powers o!˜, a™, d, . , OP
number theory and algebraic geometry for over of a, each reduced modulop, yield all the inte-
100 years and there is an enormous literature on gers between 1 andp-1. The parametersp and
the subject. To quote the mathematician Serge a are public knowledge. Alice then generates
a random integer a, 0 I a I p-2, and transmits
aa mod p to Bob. Bob similarly generates a
It is possible to write endlessly on elliptic curves.
random integer b, 0 I b I p-2, and transmits clb
(This is not a threat.)
modp to Alice. Both parties can now compute
the number aab mod p, which serves as their
Elliptic curves also figured prominently in the
secret key.
recent proof of Fermat™s Last Theorem by Andrew
Wiles. Originally pursued for purely aesthetic
reasons, elliptic curves have recently been utilized The security of the Diffie-Hellman key agree-
in devising algorithms for factoring integers, ment protocol is based on the apparent intrac-
primality proving, and in public-key cryptogra- tability of the discrete logarithm problem in q:
phy. Although the high security per bit ratio for given a prime p, a generator a of q, and an
elliptic curve cryptosystems has been known for
element /? Z&determine the integer a, 0 I a .5
10 years, it is only recently that high speed
p-2, such that CP - p (mod p). The best algo-
implementations have been available.
rithm known for this problem is the general
number field sieve by Dan Gordon, and has an
Discrete-log cryptosystems
asymptotic running time of
In their landmark 1976 paper, Whit Diffie and
Martin Hellman invented the notion of public-
exp((1.923 + o(l>>(log p)*/3(log log p)z/3>. (0
key cryptography, and introduced the Dt$e-
Hellman key agreement protocol. This proto-
The security of the RSA public-key cryptosystem
is based upon the difficulty of the problem of
D1: Al&d Mentzes is as.Wantprof&sor in the “Department
factoring integers. The number field sieve is
of Discrete and Statistical ScienceVat Auburn University,
the best algorithm known for this problem, and
Alabama. His main nztzavch intenzxtsan?pu.blz&&y ctyptogra-
phy, e&tic tune c?yprosystems, anda&oritbmic number theory. has an asymptotic running time of
Dr. Menezes also consults on a regular basis for M˜BIi7.S
expW.923 + dl))(log n)“3(log log n>U3) (2)
Encryption Technologies, Mississauga, Ontario, Canada. He
Page 43
Previous Page Home Next Page
Editor™s Note

algorithm developments, be they cryptographic,
Welcome to the second issue of CryptBytes. Dur-
cryptanalytic or implementational, can be brought
ing May of this year, we launched this newsletter
together for the benefit of the cryptographic com-
with the aim of providing a forum for “results and
opnions that, while of great cryptographic interest,
would not appear at any of the more classical out-
To include all these items, we have already had to
lets because of their format.” The initial response
increase the number of pages in CryptoBytes. We
to the general idea of a technical newsletter has
would very much like to thank all the writers who
been very encouraging, and we are pleased to bring
have contributed to this second issue, and since the
a second issue which further fulfills the aims set out
in the first. future success of CryptoBytesdepends on input from
all sectors of the cryptographic community, we
In this second issue of CryptoBytes, we are present- encourage any readers with comments, opposite
By providing a
ing two invited articles. opinions, suggestions or proposals for future issues
suitable forum,
to contact the CryptoBytes editor at RSA Laborato-
we hope that
The first, Elliptic Curue Cqbtosystems by A. Menezes, ries or by E-mail to bytes-ed@rsa.com. m
reports on
provides us with an intriguing glimpse at what are
major algorithm
potentially very efficient alternatives to crypto-
systems based on the discrete logarithm problem.
be they
Subscription Information
This article is nicely complemented by news that
the IEEE P1363 standardization effort is moving
cryptanalytic or
CryptoBytesis published four times annually;
quickly towards standards for algorithms based


. 10
( 19 .)