THE TECHNICAL NEWSLETTER OF RSA LABORATORIES - SiiMMER CRYPTOBYTES

1995

Page 57

Previous Page Home Next Page

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

RSA Laboratories Technical tion are reports on the hardware implementa- In this issue:

Reports tions of RSA, an overview of electronic pay- Elliptic curve

l

The RSA Laboratories Technical Reports are ment systems and an internal assessment of the cryptosystems

now available via a subscription service. These security of the new RC5 encryption algorithm. The future of

l

reports offer detailed summaries of current integer

research on a variety of topics and they bring Contact RSA Laboratories for more infor- factorization

together information from a wide variety of mation about the RSA Laboratories Technical On the security

l

sometimes obscure sources. Subscription to the Report subscription service. of the RC5

Technical Reports will be at one of two levels: enryption

The 1996 RSA Data Security

individual or corporate. As well as receiving algorithm

Conference

all previously written reports, subscribers will

The 1996 RSA Data Security Conference will

receive new reports as they appear as well as

be held January 17-19 in the Fairmont Hotel,

current research notes on items of major sig-

nificance. San Francisco. In addition to daily keynote

speeches, the conference will include separate

strategic, development and cryptography tracks

Technical reports that are currently available

include recently updated surveys of block ci- which the expected 800-1000 attendees will

phers, stream ciphers and the MD family of hash be able to mix and match at will. More infor- For subscription

functions. Other reports offer substantial infor- mation can be found on RSA™s web page information,

(http:/www.rsa.com> or by contacting the

mation on such topics as the RSA Factoring see page 2 of

Challenge, fair cryptography and the software conference organizer, Iayne Kaplan Events, at this newsletter.

implementation of RSA. In immediate prepara- 415/340-9300. h

I

FIRST CLASS

U.S. POSTAGE

100 MARINE PARKWAY

REDWOOD CITY

CA. 94065-1031

T E L 415/595-7703

F A X 415/595-4126

rsa-labsQrsa.com

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

Page 58

Previous Page Home Next Page

I, N U M B E R I - SPRING 1995

VOLUME

Cont.ents

The Impending Demise of RSA?

The increase in mw computing power during those

GilksBrassard

years cannot be discounted, nor can the fact that

DCpartement d™informatique et de R.O.

hundreds of workstations around the world spent

Universite de Montreal

all their otherwise idle cycles on the task for the

C.P. 6128, Succursale Centre-Ville

better part of one year. Indeed, the several thou-

Montreal (Qu&ec>

sand Mrps-years that were spent on the calculation

C A N A D A H3C 357

might not have been available to poor academics

In August 1977, Rivest, Shamir and Adleman is- back in 1977. But in the Preface of my new text-

sued a ciphertext challenge woith one hundred dol- bookFundamentulofA&˜˜bgorithmics; soon to be released

lars to Scientific American readers when Martin by Prentice-Hall with Paul Bratley as coauthor, I

Gardner described their revolutionary RSA cryp- am quick to point out that far more significant was

tographic system in his monthly “Mathematical the discovery of more sophisticated factorization

Games” column. This sounded very safe because it algorithms. When I put on my hat as teacher of

was estimated at the time that the fastest existing algorithmics, I like to use this example to illustrate

computer using the most efficient known algorithm that more efficient algorithms can produce much

could not earn the award until it had run without more dramatic results than better hardware. To

interruption for millions of times the age of the Uni- make life more interesting, however, I am wearing

verse. This particular challenge involved the fac- quite a different hat as I write this essay!

torization of a 129figure number r, which appeared

to be so out-of-reach at the time that Martin Even though the “double large prime multiple poly-

Gardner reported: “Rivest and his associates have nomial variation of the quadratic sieve” algorithm

no proof that at some future time no one will dis- was successful in factoring the 129-figure number

cover a fast algorithm for factoring composites as relevant to the RSA challenge, the age of the Uni-

large as r [...I. They consider [the] possibility ex- verse would still not suffice to factor a 500-figure

tremely remote.” Nevertheless, the $100 reward was number by this or any other known classical algo-

cashed last year-and donated to the Free Software rithm (such as the number field sieve) even if all

Foundation-after a mere eight months of inten- the world™s computers were put to contribution.

sive computation led by Derek Atkins and Arjen Therefore, one should not infer from the fate of the

Lenstra. What happened? 1977 challenge that RSA has been broken: the les-

son is that bigger numbers should be used and that

overconfident claims should be avoided. Clearly,

Professor Gilks Brzzsani, lJnit,e&tide Mont&al, is intemsted

even more remarkable advances in algorithmics will

in all aqxcis of cgpology b˜Uperb˜ his beskrwwn contribu-

tionisaraco˜˜˜of˜n˜mC˜t˜˜by.Hec be required if RSA is to fail completely or even if it

contactedatbuassard@ilo.umont˜. i%s esay was writ-

is to fail on keys merely twice the size used in the

ten while the author was on sabbatical at the University of

Scienttfic American challenge. Progress in hardware

Wolkmgong, Austmlia. Research supnkzd inp? by Canada™s

Ns˜˜cand Qu6bec™sFcAR.

Page 59

Previous Page Home Next Page

Welcome to CryptoBytes

Much of the future success of CyptoByteswill depend

Welcome to the first issue of CryptoBytes, the

on input from outside of RSA Laboratories. Such

technical newsletter on cryptography from RSA

input might range from invited articles and research-

Laboratories.

ers providing notification of recent results and

One of the nicest features of cryptographic research developments, through letters and opposite opinions

is the speed with which developments occur. This is from readers. While RSA Laboratories will coordi-

a primary reason why so many nate CryptoBytes, the intention is for it to become

researchers find working in the field a useful resource for the whole cryptographic com-

so rewarding. More often than not, munity. To help in this process, back issues of

however, new results or second- CryptoByteswill be available free of charge via the

World-Wide Web.

hand accounts of someone™s valued

opinion circulate for months by

word of mouth or by E-mail before We hope that you™ll agree that this first issue of

appearing in journals or in con- CryptoBytesis a step towards our goals. We would

ference proceedings. In fact, very much like to thank the writers who have

it might be convincingly argued contributed to this first issue, and we welcome any

comments, suggestions or proposals for future issues.

that a great deal of interesting

information is never actually -Ron Rivest Q

published, never cited, and never properly referred

Edhr™s note: Suggestions and contributions for future issues

to by other researchers.

of CryptoBytes can be sent to bytes-ed@rsa.com or to RSA

Laboratories by any of the methods given below.

A newsletter can alleviate this situation. The aim

would be to circulate interesting news as it happens,

thereby providing a reliable distribution method for Subscription Information

substantial ˜bites of Crypto™. In addition, a newsletter

might provide a forum for results or opinions that, CryptoBytesis published four times annually;

while of great cryptographic interest, would not ap-

printed copies are available for an annual

pear at any of the more classical outlets because of

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

their format. contact RSA Laboratories at:

Such a newsletter should be of interest to all those

RSA Laboratories

involved in cryptography; from those implementing

100 Marine Parkway, Suite 500

cryptographic techniques and designing cryptographic Redwood City, CA 94065

products to those in the academic development of

415/595-7703

cryptographic knowledge. Often these groups are

415/595-4126 (fax)

viewed as being somewhat exclusive of each other;

rsa-labs@rsa.com

instead we suggest that there is an impoitant symbio-

sis. One goal of a newsletter on cryptography must be

Back issues in electronic form are available

the transfer of information across these artificial di-

via the World-Wide Web at

vides. In this way researchers will hear about con-

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

tinuing efforts to implement the fruits of their research

efforts and implementers can keep track of the latest

cryptographic innovations.

RSA Laboratories is the research division ofRSA Data Security,

With the first issue of CryptoBytes in your hands, Inc., tbewmpanyjnmukdby the intxmtolsoftbe RSApublic-@

we are hoping to achieve some of these goals. We clyptosysrem. RS4 Ldwratodes rxzdem, &&sand tmplemenls

secure and eflcient cryptosystems of all kinds. Its clients include

are also hoping to provide a complement to current

gozernmentagencies, teL2wmmuniuztkm.s wmpanles, computer

newsletters such as IEEE™s Cipher, the IACR manufacturers sofnuaredevelopeq cable Tvbroadcasters,

newsletter and the ˜ITS Data Security Letter, among imuidaomanufma, andsatellire broadcast companits,

anwnptkws.

many others.

CSYPTOBYTES SPRING 1975 - THE TECHNICAL NEWSLETTER LABORATORIES

OF RSA

Page 60

Previous Page Home Next Page

The Impending Demise of RSA?

-˜P%Fl

subject to )a? + )py = 1. The coefficients O! and fi

will at best be a minor factor in the eventual success

of future attacks against RSA. Right? Wrong! are called the amplitudes of POS and )l@, respectively.

A qubit is best visualized as a point on the surface of

Quantum computing, an emerging branch of computer a unit sphere whose North and South poles corre-

science, may well prove the above conventional wis- spond to the classical values. If state y/ is observedin

dom false. For the first time, revolutionary new con- the sense that the qubit is asked to assume a classical

cepts may hold the key to a computer that would go value, it will collapseonto PS with probability b}2

e2ponentially faster than conventional computers, at and onto )l 8 with complementary probability )pp.

least for some computational tasks. This means that So far, it looks as if we have but nzinvented analogue

the speed-up would be increasingly spectacular as the computation. Things become more interesting when

size of the input gets larger, which is precisely the we consider quantum reg&z&scomposed of n qubits.

type of claim that had been the prerogative of algo- Such registers can be set to an arbitrary quantum su-

rithmic improvements until now. In particular, build- perposition of states ˜-I™ = 9Qx ax}&3 subject to

ing on the work of David Deutsch and Richard Jozsa, ˜%x x b}” = 1, where X denotes the set of all classi-

cal n-bit strings. If this register is asked to assume a

Ethan Bernstein and Umesh Vazirani, Daniel Simon,

and Don Coppersmith, Peter Shor has discovered that classical value, each x in Xwill be obtained with prob-

ability @x p, and the register will collapse onto the

quantum computers can factor an n-figure number

in a time asymptotically proportional to n*+& for afbi- observed value.

trarily small 6. This means that it would take about

the same time to crack an RSA key as to use it legiti- In principle, it is possible to compute on such regis-

mately! In other words, quantum computers spell ters. If a quantum computer is programmed to com-

pute some functionf : X 0 Y and if it is started with

complete disaster on RSA. This has not (yet) forced

RSA Laboratories to file for Chapter 11 because there superposition y = mzx ax}333 in its input register,

are formidable technological difficulties before the then it will produce superposition Y™ = %,, a$&$@

first quantum computer can be built, but the possi- in its output register in the time needed to compute f on

bility should not be underestimated. a single input. In other words, this provides for exp

nentially many computations to take place simulta-

What is a quantum computer? This theoretical neously in a single piece of hardware, a phenomenon

notion emerged from the work of Paul Benioff, Rich- known as quantumparallelkm. We are far from ana-

ard Feynman and David Deutsch in the first half of logue computing now. The good news is that we have

the eighties. I cannot say much in this short essay obtained exponentially many answers for the price Revolutionary

but I shall try to sketch the basic principles. For more of one. The bad news is that Heisenberg™s uncertainty flew concepts

detail and references to the work mentioned here- principle forbids us from looking at the output regis- may tJotd the

such as Peter Shor™s quantum factorization algo- ter for fear of spoiling it! More precisely, if we ask key to a

rithm-1 invite you to read my forthcoming paper in the output register to assume a classical value, it will computer that

Cunzmt Trends in Com&&rScience, Jan van Ieeuwen collapse to the value of f6.9 for an 3c randomly cho- would go

(Ed.), Lecture Notes in Computer Science, Volume sen in X with probability bxy, and the quantum exponentially

1000 (special anniversary volume), Springer-Verlag, superposition Y™ will be destroyed by the measure- faster than

ment. So far, it looks as if quantum computing is not

195. Until this volume has appeared, you may wish conventional

to read my earlier account insigact News, Volume only impractical but useless as well. computers.

25, number 4, December 194, pp. 15 - 21.

What makes quantum computing interesting is the

notion of quantum inte$knce, which is exactly the

Let us begin with a quantum bit, or qubit (a word

coined by Benjamin Schumacher). In classical digi- principle behind Young™s celebrated double-slit ex-

periment. In a classical probabilistic calculation, it

tal computing, a bit can take either value 0 or value

1. Nothing in between is allowed. In quantum com- is possible to program the computer to select one of

puting, a qubit can be in linearsuperposition of the several possible computation paths according to the

laws of probability. In any specific instance of the

two classical states. If we denote the classical states

by p 8 and ) 18, then a qubit can be in state w = a calculation, however, only one of the potential paths

POS + p )l 8 for arbitrary complex numbers a and p is actually taken, and what-could-have-happened-