to the “instructions” contained in its time-stamp

scott.s@surety.com.

IN E W S L E T T E R OF RSA LABORATORIES

CRYPTOBYTES AUTUMN 1995 -THE TECHNICAL

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

situations.

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

References

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

El

THE TECHNICAL NEWSLETTER OF RSA LABORATORIES - AUTUMN 1995 CRYPTOBYTES

Page 41

Previous Page Home Next Page

A N N O U N C E M E N T S

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

l

Paranoids

cussions will be on electronic commerce and

doing business on the Internet. Meanwhile

The 1996 RSA Data Security Conference will Collisions

l

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

l

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

information,

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

FIRST CLASS

U.S. POSTAGE

100 MARINE PARKWAY

REDWOOCI C I T Y

CA. 94065-1031

T E L 415/595-7703

F A X 415/595-4126

rsa-labs@rsa.com

Copyright 0 1995 RSA Laboratories, a division of RSA Data Security, Inc. All rights reserved.

Page 42

Previous Page Home Next Page

VOLUME I, N U M B E R 2 - SUMMER 1995

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

Lang:

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

(imlal.ledonpageD

canbe˜at˜˜il.aubum.˜u.

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

munity.

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-

developments,

systems based on the discrete logarithm problem.

be they

Subscription Information

This article is nicely complemented by news that

cryptographic,

the IEEE P1363 standardization effort is moving

cryptanalytic or

CryptoBytesis published four times annually;

quickly towards standards for algorithms based