<<

. 6
( 19 .)



>>

Adi Shamir is professor at the Applied Math Department of the
toring 512 bit moduli in 10,000 to 15,000 MIPS-
Weizmann Institute of Science, Israel. He is a co-inventor of the
years (A. Lenstra, private communication). This is
RSA cryptosystem and can be contacted at shamir@wisdom.
(continued on page 3)
weizmann.ac.il.
Page 27
Previous Page Home Next Page

Editor™s Note

In this, the autumn edition of CryptoBytes, we have are of particular interest to our readers. In this issue,
decided to concentrate on issues related to the use of the question “How do digital time-stamps support
digital signatures?” is answered by Stuart Haber, Burt
the RSA cryptosystem.
Kaliski and Scott Stometta.
The main article in this issue is entitled The Secure
Use of RSA. Adapted from a seminar presented by The future success of CryptoBytes depends on input
Ron Rivest at the 1995 RSA Laboratories Seminar from all sectors of the cryptographic community
Series, this article considers the myths and realities and as usual we would very much like to thank the
of using the RSA cryptosystem. From low exponent writers who have contributed to this third issue. We
attacks to padding rules, this article provides the encourage any readers with comments, opposite
ground rules for avoiding a variety of potential at- opinions, suggestions, proposals for questions in our
tacks on RSA when used either to provide message Frequently Asked Questions column or proposals for
encryption or to digitally sign documents. items in future issues to contact the CryptoBytes edi-
tor by any of the methods given below. h
We also have a variety of reports on several recent
research results.
Contact and Subscription
Information
At most At most conferences, time is set aside for researchers
conferences, to present their latest results outside of the main pro-
CryptoBytes will be available by subscrip-
time is set aside gram, and consequently, outside of the conference
tion and individual annual subscription to
for researchers proceedings. This means that it is often hard to track
to present their four issues is U.S.$90. To subscribe, con-
down the essential details of what was said. As initial
latest results tact RSA Laboratories at:
steps to make information on rump session items more
outside of the widely available, we present reports on three items
main program.... RSA Laboratories
that were presented at recent rump sessions.
This means that 100 Marine Parkway, Suite 500
it is ofien hard Redwood City, CA 94065
A novel idea by Adi Shamir, leading to a rather un-
415/595-7703
to track down the conventional implementation of RSA, has some very
415/595-4126 (fax)
essential details intriguing properties. In this issue of CryptoBytes
of what was said. rsa-lubs@rsa . corn
we include an article by Adi Shamir which provides
more details on ideas that were originally presented
We are hoping that electronic subscrip-
at the rump session of Eurocrypt ˜95 earlier this year.
tion to CryptoBytes, via the World-Wide
Web, will be available soon. All back is-
We also have news of two items from the rump ses-
sues are available via the World-Wide Web
sion of the Crypto ˜95 conference. We report on a
at http://www.rsa.com/rsalabs/cryptobytes/.
new “protocol failure” when RSA is used with expo-
nent three and also on a new attack on the envelope
The CryptoBytes editor can be contacted
method of using a hash function for message authen-
by any of the above methods, or by E-mail
tication. (In one way or another, message authenti-
to bytes-ed@rsa.com.
cation with hash functions has featured in all issues
of CryptoBytes so far!) Also, as part of our ongoing
features, we provide an Algorithms Update on some
About RSA laboratories
very exciting new work in the analysis of hash func-
tions by Hans Dobbertin.
RSA Laboratories is the research and development division of RSA
Data Security, Inc., he company founded by the inventurs of the
Finally, in this issue, we introduce a new column: RSA public-key cryptosystem. RSA Laboratories reviews, designs
and implements secure and efficient cryptosystems of all kinds. Its
Frequently Asked Questions. Extracted from the ongo-
clients include government agencies, telecommunications compa-
ing enhancements to RSA Laboratories™ Answers to
nies, computer manufacturers, software developers, cable 7V
Frequently Asked Questions, this column will feature broadcasters, interactive video manufacturers, and satellite broad-
answers to new questions on today™s cryptography that cast companies, among others.


-- Eil
CRYPTOBYTES -THE TECHNICAL NEWSLETTER OF RSA LABORATORIES
AUTUMN 1995
Page 28
Previous Page Home Next Page

RSA for Paranoids
Continued from page 1

only 2-3 times harder than the factorization of RSA- A well known way of speeding up the RSA encryp- In this paper . . .
tion process c = me (mod n) is to use a small encryp
129 achieved (by a different algorithm) in early 1994, [we] propose
and is likely to be demonstrated within a year. tion exponent e. Since m is only one tenth the size a new variant
of n, encryption exponents which are smaller than of the RSA
Since the inception of the RSA cryptosystem, all the 10 do not provide any wraparound during the modu- cryptosystem,
record breaking factorizations of RSA keys were based lar reduction, and should be avoided. When e is which we co//
around 20, the size of me is about twice the size of n,
on algorithms of the second type, and it is reasonable “unbalcmced
to assume that this trend will continue in the foresee- and thus the wraparound effect is similar to the squar- RSA”. its goal
able future. If this is the case, there is no need to in- ing operation of full size numbers in Rabin™s scheme. is to provide
crease the sizes of n and its prime factors at the same Note that for such an e, most of the multiplications much higher
rate. In this paper we use this observation in order to in the computation of me (mod n) are non modular security at
multiplications of relatively small numbers, and only
propose a new variant of the RSA cryptosystem, which essentially
we call “unbalanced RSA”. Its goal is to provide much the last squaring is likely to be a full size modular no extra cost.
higher security at essentially no extra cost. multiplication. The recommended range of e is 20-
100, which makes the encryption time with a 5,000
Unbalanced RSA bit modulus comparable to the decryption time with
As a typical example of the new RSA variant, we a 500 bit modulus (i.e., less than a second).
describe an “ultimate security” implementation,
The other operation we have to consider is the de-
which is likely to provide long term security even to
cryption process m = cd (mod n) in which c, n and d
professional paranoids. In this version we increase
the overall size of n by a factor of 10 (to 5,000 bits), are 5,000 bit numbers. If we use the Chinese remain-
and the size of its prime factor p by a factor of 2 (to der theorem, we can easily compute mt =cd (mod p)
500 bits). The size of the other factor 4 of n is 4,500 via a 500 bit exponentiation, by reducing c modulo
bits, and the name of this variant reflects the un- p and d modulo p-1 at the beginning of the compu-
equal sizes of the two prime factors of n. tation. However, we then have to carry out the 4,500
bit exponentiation mZ = cd (mod q), which is 93=729
Such a modulus is way out of reach of today™s factor- times slower.
ing algorithms, and is likely to remain secure even if
factoring algorithms of the first type will become The main purpose of this note is to show that there
much better, and factoring algorithms of the second is no need to carry out this expensive computation.
type will become enormously better. Only a major By definition, ml is equal to m (mod p). However,
breakthrough in factoring (such as a practical polyno- the cleartext m is known to be smaller than p, and
thus m (mod p) is simply m itself. By combining these
mial time factoring algorithm, which will completely
kill the RSA scheme) can possibly threaten it. observations, we conclude that ml is the original
cleartext m, and thus it is just a waste of time to
carry out the computation of m2 modulo 4, which
The main problem in using such a modulus n is the
fact that standard RSA implementations become will yield the same result.
about 1000 times slower: A typical 500 bit exponen-
Other optimizations
tiation which required 1 second on a microprocessor
would now require 16 minutes, which is unacceptable. While the unbalanced RSA variant has about the
same time complexity as the original variant, its
Since RSA encryption is typically used only in order space complexity and public key size are 10 times
to exchange session keys for fast secret key crypto- larger. We now show how to use additional optimi-
systems, the cleartexts are usually quite short: even zation techniques to avoid these extra overheads.
three independent keys for triple DES require only
168 bits, and it is unlikely that anyone would use Consider first the issue of RAM size. On personal
the RSA cryptosystem to exchange secret keys which computers the lo-fold increase in the size of the reg
are larger than p. We can thus assume that the isters is meaningless, but smart cards contain very
cleartext is in the range [0, p), and that it is padded small RAMS and their cost is directly proportional
with random bits to make sure that it is not much to the size of their memory. In addition, many smart
shorter than p. card manufacturers have already designed RSA


EZI -._. .
THE TECHNICAL NEWSLETTER OF RSA LABORATORIES - AUTUMN 1995 CRYPTOBYTES
Page 29
Previous Page Home Next Page




is the smallest integer greater than or equal to r/p.
coprocessors which can handle 512 bit moduli, and
Since the prime numbers are relatively dense, such a
would be reluctant to redesign them in order to ac-
4 almost certainly exists, and n = ˜4 is very close to
commodate much larger moduli. However, in most
the target value t (the difference s = n - t is expected
applications the smart card is talking to a powerful
to be about 550 bits long). Each user u publishes this
PC or workstation, and we can choose to implement
either the encryption or the decryption side of the 550-bit s as his public key, and anyone can recover
the user™s 5,000-bit modulus n by computing G(u) + s.
RSA key exchange on the smart card. It turns out
to be easier to let the powerful machine choose and
encrypt the session key. The arbitrarily long cipher- It is important to note that this approach does not
make n easy to factor: the only difference between
text is sent to the smart card in a bit serial mode,
our n and standard n is that we start the search for q
and the smart card reduces it on-the-fly modulo p by
at a point which is the ratio of a random number and
clocking it through the 512 bit input register of its
a prime number, rather than at a random number.
coprocessor. The resultant value is then exponent-
Since the distribution of prime numbers p is not
iated by the 5 12 bit coprocessor to obtain the ses-
completely uniform, the choice of a is not completely
sion key. The advantage of this approach is that
uniform. We smooth this slight nonuniformity by
today™s coprocessors would be able to handle vari-
specifying a fairly large range of size 250 in which 4
able length moduli (dictated by the changing state
can be chosen, which makes the exact location of
of the art of factoring algorithms) without expensive
. . . the technique the range™s endpoints irrelevant. Once n is chosen,
periodic replacements of millions of smart cards in
described in this it makes no difference whether we specify it by its
large-scale consumer applications.
paper can also bits or by its distance s from another number t, and
be used to double the fact that t is a pseudo random rather than a truly
Another potential drawback of the new variant is
the speed and random number cannot change this fact.
the lo-fold increase in the size of the public key di-
halve the key rectory. However, the unbalanced construction of the
Finally, we note that the technique described in this
size of standard new public keys makes it possible to eliminate this
implementations paper can also be used to double the speed and halve
problem. Let G be a publicly known pseudo random
of the RSA the key size of standard implementations of the RSA
bit generator which maps each user identity u (name,
cryptosystem in which p and q have similar sizes.
email address, etc.) into a unique 5,000 bit pseudo
cryptosystem
in which random target value t. Each user picks a random 500- The optimization does not apply to the RSA signa-
p and q have bit prime p, and defines the other prime 4 as a ran- ture scheme, since the verifier cannot carry out com-
similar sizes. dom prime number in the range [a, a + 250] where a putations modulo the unknown p. b




U P D A T E
A 1 G 0 R I T H M S

Collisions in MD4 rithm SHA and its more recent revision SHA- 1 fol-
low the same design approach that was pioneered by
Recent work by Hans Dobbertin has discovered that Rivest with MD4. Rivest also designed an extended
version of MD4 with a 256-bit rather than 128-bit
collisions for MD4 can be found within a few min-
hash value which was considered to be much more
utes on a typical PC. Even more impressive is the
fact that collisions can be constructed, in around an secure than MD4. It appears, however, that these new
techniques will also compromise extended-MD4.
hour, so that the text they represent makes sense. For
an example, see how Alf swindles Ann opposite.
While MD4 remained secure until now, it was felt
MD4 was among the first of a new generation of that MD4 made little allowance for potential crypt-
what are termed dedicated hash functions, designed analytic developments. Consequently, the use of
from first principles to be hash functions rather than MD4 has been discouraged for some considerable
being based around some other primitive such as a time, and instead the usual recommendation was to
block cipher. MD5, RIPEMD, the secure hash algo- replace MD4 with the more conservatively designed


CRYPTOBYTES ™ AUTUMN 1995 -THE TECHNICAL NEWSLETTER OF RSA LABORATORIES
H
Page 30
Previous Page Home Next Page




SHA- 1, the task facing the cryptanalyst is much more
MD5. Dobbertin™s work clearly confirms that if MD4
involved. Initial review of those algorithms suggests a
is still being used anywhere, then it should be imme-
limited opportunity for new developments (except on
diately replaced.
reduced-round versions of RIPEMD which have al-
ready succumbed to this type of analysis) and Crypto-
As for the applicability of Dobbertin™s techniques to
Bytes will report on any further developments. h
other hash functions such as MD5, RIPEMD and



Alf Swindles Ann M. = Ox9074449b Ms = 0x68742074
MI = Ox1089fc26 M9 = Ox72702065

<<

. 6
( 19 .)



>>