. 15
( 19 .)


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

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

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

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
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


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

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


The Impending Demise of RSA?

The increase in mw computing power during those
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-
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
cryptographic knowledge. Often these groups are
415/595-4126 (fax)
viewed as being somewhat exclusive of each other;
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-
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,
many others.

Page 60
Previous Page Home Next Page

The Impending Demise of RSA?

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-


. 15
( 19 .)