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