Path: gmdzi!unido!mcsun!uunet!caen!deccrl!bloom-beacon!
bloom-picayune.mit.edu!athena.mit.edu!burt
From: bu...@chirality.rsa.com (Burt Kaliski)
Newsgroups: sci.crypt
Subject: Comments on DSS
Message-ID: <BURT.91Nov19125427@chirality.rsa.com>
Date: 19 Nov 91 17:54:27 GMT
Sender: ne...@athena.mit.edu (News system)
Distribution: sci
Organization: RSA Data Security, Inc.
Lines: 529
Nntp-Posting-Host: 192.80.211.33
FYI --
A letter to NIST commenting on the proposed Digital Signature Standard
(DSS).
-- Burt Kaliski
RSA Data Security, Inc.
----------------------------------------------------------------------
November 4, 1991
Director, Computer Systems Laboratory
ATTN: Proposed FIPS for DSS
Technology Building, Room B-154
National Institute of Standards and Technology
Gaithersburg, MD 20899
Dear Director:
This letter is in response to your proposed Digital Signature
Standard (DSS). It addresses the speed of the proposed Digital
Signature Algorithm (DSA).
One of the ways to determine whether a given computational
technique is suitable for a wide range of applications and
environments is to ask whether that technique is fast enough for
typical use. Some techniques may be fast enough for specific
uses, but have a limited range of application. A nationally
standardized computational technique, it would seem, should have
a wide range of application.
What are some of the typical uses of digital signature
techniques? Here are some examples.
Privacy-enhanced electronic mail. A user can attach digital
signatures to outgoing electronic mail and verify digital
signatures on incoming mail. On the outgoing mail, the user
carries out a signature operation. On the incoming mail, he or
she carries out at least one verification operation. The user
must verify the sender's signature on the mail itself, and the
user may also verify signatures of the following kinds: a
certification authority's signature on the sender's public key; a
higher-level certification authority's signature on the first
certification authority's public key; and signatures on "hot
lists" of compromised keys. Signature and verification speed are
both important for privacy-enhanced mail, but verification speed
is critical, since verifications are carried out more often.
Software virus protection. One way to help "immunize" computers
against software viruses is for manufacturers to attach digital
signatures to their software. The digital signature acts as a
tamper-detection seal and allows users to determine whether
software is in its original condition before running it. The
manufacturer signs the software only once; users verify a digital
signature every time they run a program. Clearly, an overhead of
more than a second or so to verify a signature is unacceptable.
Electronic banking. A central bank verifies digital signatures on
thousands of banking transactions every hour. Every extra second
per verification means that the bank needs more special hardware
to assist the central computer.
So speed is very important, and verification speed is a critical
parameter.
Based on the verification speed measure, I claim that DSS is
unqualified as a national signature standard. Even NIST's own
measurements give a verification time of over 10 seconds for DSS
on a personal computer (see reference 1). This is much too long
for use in typical verification-intensive applications such as
those just described. Actual timings with a reference
implementation of cryptographic tools give times of five and 12
seconds, depending on the computer (see Appendix B). And even
though DSS's signing can be made very fast with certain
precomputation operations, those operations are not generally
applicable (see Appendix C), and DSS signing time remains in the
range of two to five seconds.
What about the smart-card applications described by NIST where
verification speed is not so important? The Federal Register
announcement on DSS states:
"The technique selected provides for efficient
implementation of the signature operations in smart
card applications. In these applications the signing
operations are performed in the computationally modest
environment of the smart card while the verification
process is implemented in a more computationally rich
environment such as a personal computer ... ."
It would appear from this statement that the smart card does not
need to verify any signatures. But is this true? Two industry-
proposed smart-card protocols (see references 2 and 3) involve
mutual authentication, where a terminal verifies the identity of
the smart card and vice versa. In those protocols the smart card
carries out verification operations as well as signature
operations, so verification speed on the smart card is critical.
Thus while DSS may be fast enough for NIST's smart-card
applications (assuming NIST's applications do not require mutual
authentication), DSS is not fast enough for the smart-card
applications planned by industry.
There is one digital signature technique whose verification is
fast enough for most applications, the RSA Digital Signature(TM).
It has long been known that RSA verification is a fast operation.
Indeed, calculations show that RSA verification is up to 130
times faster than DSS verification (for DSS's proposed parameters
versus a 512-bit RSA modulus; see Appendix A). Actual times for
RSA verification are in the tenths or hundredths of a second,
whereas times for DSS verification are several seconds, orders of
magnitude greater.
To summarize, signature verification speed is a critical
parameter for most applications. The proposed DSS, with
verification speed up to 130 times slower than the verification
speed of RSA, is not likely to be an acceptable alternative to
RSA for these applications. A national signature standard should
attempt to balance the requirements of a diversity of
applications. The claim that DSS is well-suited to smart-card
applications is an unbalanced rationale that is inconsistent with
the evidence.
On the basis of this analysis, I recommend strongly that you
withdraw the DSS from consideration, and reconsider alternatives
that have a much faster signature verification time.
Yours truly,
Burton S. Kaliski Jr., Ph.D.
Cryptographic Systems Scientist
RSA Labs
Encl.
References
[1] NIST publishes draft digital signature standard. Personal
Identification News, 7(9):1,8,7, September 1991.
[2] John C. Kennedy and Jim K. Omura. Advanced smart card
prototype with public key signature capability and biometric
unlock. Proceedings of Securetech/CardTech '91, 1991.
[3] M. Abadi, M. Burrows, C. Kaufman, and B. Lampson.
Authentication and Delegation with Smart Cards. Technical
Report 67. Digital Systems Research Center, 1990.
Appendix A. Comparison of DSS and RSA speeds
This appendix gives a theoretical comparison of DSS and RSA speeds.
Work is measured in terms of three operations:
Modular multiplication: Compute a = bc mod d where 0 <= b,c < d.
Modular squaring: Compute a = b^2 mod d where 0 <= b < d.
Modular inversion: Compute a = 1/b mod d where 0 <= b < d and the
inverse exists.
Some other operations, such as modular addition, integer
multiplication, and modular reduction are also involved in DSS and
RSA, but since the other operations are much less frequent than the
three operations just given, they are ignored in the analysis.
Let #x denote the number of bits in the binary representation of x.
Let us denote the amount of work to perform modular multiplication as
M(#d). Similarly, let us denote the amount of work to perform modular
squaring as S(#d), and the amount of work to perform modular
inversion as I(#d). To keep the analysis simple, let us will assume
the following relationships hold for M and S:
S(b) = .75 M(b) ;
M(b1)/b1^2 = M(b2)/b2^2 .
The first relationship states that the amount of work to perform
modular squaring is three-quarters that to perform modular
multiplication. This follows from the observation that half the work
in modular multiplication is due to modular reduction, and half the
remaining work (i.e., one quarter the total work) can be eliminated
when the operands being multiplied are known to be equal. As a result
of this relationship, it is possible to express all work in terms of
modular multiplication and modular inversion.
The second relationship states that the amount of work to perform
modular multiplication grows as the square of the number of bits.
While there are algorithms for modular multiplication whose amount of
work grows more slowly than the square of the number of bits, those
so-called "fast" algorithms are not practical until the number of
bits is quite large, say several thousand or more.
The following four sections analyze the amount of work to compute and
verify DSS and RSA signatures. In the analysis, the amount of time to
compute a hash value H(m) on the message m is ignored, as the time
depends on the length of the message and the hash function, but not
the digital signature scheme.
A.1 DSS signatures
Computing DSS signatures involves the following equations:
r = (g^k mod p) mod q ;
s = (H(m) + xr)/k mod q .
It is well known that one can compute the values r and s with the
following operations, on average:
.5#q modulo-p multiplications
#q modulo-p squarings
two modulo-q multiplications
one modulo-q inversion
(Note that a modulo-q reduction, a modulo-q addition, and the
computation of H(m) are ignored, for reasons given above.)
A simple improvement known as the 16-ary method (see Knuth vol. II,
for example), in which bits of the exponent k are processed in groups
of four, allows one to compute the values r and s with approximately
these operations, on average:
.25#q+7 modulo-p multiplications
#q+7 modulo-p squarings
two modulo-q multiplications
one modulo-q inversion
While there are slightly faster methods to compute the values r and
s, let us stay with the 16-ary method, which has the following amount
of work:
(.25#q+7)M(#p) + (#q+7)M(#p) + 2 M(#q) + I(#q) .
This result can be simplified under the relationships for M and S to
(#q+12.25+2(#q/#p)^2)M(#p) + I(#q) .
A.2 DSS verification
Verifying a DSS signature involves the following equations:
w = 1/s' mod q ,
u1 = H(m')w mod q ,
u2 = r'w mod q ,
v = (g^u1 y^u2 mod p) mod q ,
v =? r' .
One can compute the values w, u1, u2 and v with approximately the
following operations, on average, if the 16-ary method is employed:
.5#q+15 modulo-p multiplications
2#q+14 modulo-p squarings
two modulo-q multiplications
one modulo-q inversion
In the paper on the ElGamal cryptosystem, a technique attributed to
Shamir for computing values like v is described. This technique
allows one to compute the values w, u1, u2 and v with approximately
the following operations, on average:
.75#q+2 modulo-p multiplications
#q modulo-p squarings
two modulo-q multiplications
one modulo-q inversion
Staying with the Shamir method gives the following amount of work:
(1.5#q+2+2(#q/#p)^2)M(#p) + I(#q) .
A.3 RSA signatures
Computing an RSA signature involves the following equation:
s = H(m)^d mod n .
One can compute the value s with approximately the following operations,
on
average, if the 16-ary method is employed:
.25#d+7 modulo-n multiplications
#d+7 modulo-n squarings
RSA signatures can be computed much faster if one takes advantage of
the fact that the signer knows the prime factors p and q of n. (These
prime factors are not to be confused with the primes p and q in DSS.)
With such knowledge, one can compute the value s with approximately
the following operations, on average:
.5#p modulo-p multiplications
.5#q modulo-q multiplications
#p modulo-p squarings
#q modulo-q squarings
Staying with the prime-factors method gives the following amount of
work:
(1.25#p)M(#p) + (1.25#q)M(#q) .
Assuming that the prime factors have approximately the same number of
bits, this result can be simplified to
(2.5#p)M(#q) ,
which can be further simplified under the relationships for M and S
to
(.31#n)M(#n) .
This is about three times faster than the 16-ary non-prime-factors
method. There are slightly faster methods.
A.4 RSA verification
Verifying an RSA signature involves the following equations:
v = s'^e mod n ,
H(m') =? v .
Let us consider the special cases e = 3 and e = 2^16+1, which are
commonly suggested for applications of RSA. (The X.509 directory
authentication framework and Internet Privacy-Enhanced Mail make such
suggestions.)
For e = 3, one can compute the value v with approximately the
following operations:
one modulo-n multiplication
one modulo-n squaring
Thus the amount of work for e = 3 is
1.75 M(#n) .
For e = 2^16+1, one can compute the value v with:
one modulo-n multiplication
16 modulo-n squarings
Thus the amount of work for e = 2^16+1 is
13 M(#n).
A.5 Comparison for recommended key lengths
It has been shown that the amount of work to compute and verify DSS
and RSA signatures, expressed in terms of modular multiplication and
inversion operations, is as follows:
Signatures.
DSS: (#q+12.25+2(#q/#p)^2)M(#p) + I(#q)
RSA: (.31#n) M(#n)
Verification.
DSS: (1.5#q+2+2(#q/#p)^2)M(#p) + I(#q)
RSA (e = 3): 1.75 M(#n)
RSA (e = 2^16+1): 13 M(#n)
With DSS's proposed 512-bit prime p and 160-bit prime q, and a 512-bit
RSA modulus n, the amount of work becomes:
Signatures. Verification.
DSS: 172.5 M(512) + I(160) DSS: 242.2 M(512) + I(160)
RSA: 160 M(512) RSA (e = 3): 1.75 M(512)
RSA (e = 2^16+1): 13 M(512)
The amount of work to compute a DSS signature is roughly the same as
the amount of work to compute an RSA signature.
On the other hand, the amount to work to verify a DSS signature is
more than 130 times as much as that to verify an RSA signature when e
= 3, and more than 18 times as much when e = 2^16+1. (The 130-to-1
ratio is likely to be a little more than one can achieve in practice,
given that there is some computational overhead common to RSA and
DSS, such as moving keys in and out of memory, that is not sped up at
all.)
It is also clear that the amount of work to verify a DSS signature is
nearly 50 percent more than the amount of work to compute a DSS
signature.
Some researchers have suggested that a 512-bit prime p is not large
enough. With a 640-bit prime p and 160-bit prime q for DSS, and a
640-bit modulus n for RSA, the amount of work becomes:
Signatures. Verification.
DSS: 172.4 M(640) + I(160) DSS: 242.1 M(640) + I(160)
RSA: 200 M(640) RSA (e = 3): 1.75 M(640)
RSA (e = 2^16+1): 13 M(640)
For the larger p and n, the amount of work to compute a DSS signature
is less than the amount of work to compute an RSA signature, but the
amount of work to verify a DSS signature is still up to two orders of
magnitude more than the amount of work to verify an RSA signature.
If DSS's prime p is shared by a large group of users then the
assumption that equal-length DSS p and RSA n means equal security no
longer holds, since DSS's prime p is worth more to a potential
attacker. Such a condition would further increase the ratio between
DSS and RSA verification times, since the DSS's p would have to be
larger than RSA's n.
A.6 Summary
The theoretical comparison of DSS and RSA signatures has shown that
with well-known implementation techniques, DSS and RSA signing have
roughly the same speed, and RSA verification is 18 to 130 times
faster than DSS verification. For larger DSS and RSA keys, DSS
signing becomes slightly faster than RSA signing, but RSA
verification remains up to two orders of magnitude faster than DSS
verification.
Appendix B. Times from actual implementations
The calculations given in Appendix A are shown to be accurate by
actual implementations of DSS and RSA. Three implementations were
considered:
I. 20MHz '386 computer running RSA-REF, a free cryptographic toolkit
now being prepared by RSA Data Security. RSA-REF is written
entirely in C.
II. Sparcstation I computer running RSA-REF.
III. SUN 3/160 PC running NIST software, as given in the September
1991 issue of Personal Identification News. It is not specified
in what language the NIST software is written.
The signature and verification times are as follows:
PLATFORM I.
RSA-REF.
20MHz Intel '386, MS-DOS.
Microsoft C 6.0, large memory model, optimization on.
Signatures. Verification.
DSS: 5.6 seconds. DSS: 12.0 seconds.
RSA: 5.2 seconds. RSA (e = 3): 0.06 seconds.
RSA (e = 2^16+1): 0.50 seconds.
PLATFORM II.
RSA-REF.
Sparcstation I, UNIX.
Sun C, optimization on.
Signatures. Verification.
DSS: 2.19 seconds. DSS: 4.74 seconds.
RSA: 2.35 seconds. RSA (e = 3): 0.02 seconds.
RSA (e = 2^16+1): 0.19 seconds.
PLATFORM III.
NIST software.
SUN 3/160 PC.
Language not specified.
Signatures. Verification.
DSS: 6.10 seconds. DSS: 12.3 seconds.
RSA: 6.98 seconds. RSA (e not spec.): 1.00 seconds.
The signature and verification times do not match the theoretical
calcuations exactly because not all the speedups discussed in
Appendix A are implemented, and because some implementation overhead
is ignored in the calculations. For example, RSA-REF does not speed
up squaring; it uses the 2-ary method for exponentiation, not the
4-ary method; and it does not employ the "Shamir method" for DSS
verification. Consequently, the times for RSA-REF can probably be
improved a little for RSA and a little more for DSS verification,
though not enough to change any of the conclusions. It is not
specified what speedups NIST's software includes, and it seems likely
that the exponent e for RSA is neither 3 nor 2^16+1, given the
relatively large time for RSA verification.
The signature and verification times could be improved significantly
by rewriting parts of RSA-REF and (perhaps) NIST's software in
assembly language, and a factor of five to 10 improvement in speed
can be expected. On the other hand, the computers considered above
are faster than what most users have. Thus the assembly speedup is
counterbalanced by the users' slower computers, and the general sense
of an operation taking a few seconds or a few tenths of a second for
in a typical environment remains accurate.
Appendix C. About precomputation
One feature of DSS signatures is that it is possible to precompute
the value r before receiving a message m to be signed, since the
value r does not depend on the message m. The value s depends on the
message m, and the amount of work to compute the value s is only:
two modulo-q multiplications
one modulo-q inversion
Only in special applications, however, is such precomputation
effective. For precomputation of the value r to be effective it must
be possible to store the values r and k securely until the message m
is received. While secure storage may be possible in a smart card, it
is likely to be more difficult on a computer workstation. A
workstation has short-term secure storage in the sense that as long
as the user is at the workstation no one can examine the
workstation's memory, assuming that there are no "back doors" to the
workstation's memory. As soon as the user leaves the workstation,
however, the memory becomes vulnerable, and the only means for secure
storage (other than smart cards) is via encryption with a
user-supplied password. It does not seem likely that the value r and
k could be maintained securely in all circumstances. Indeed, if an
attacker can obtain the value k for even one signature, then the
attacker can derive the user's private key and break the user's
security permanently. Therefore it seems that applications would not
always take advantage of precomputation in a workstation environment.
Some other precomputation is possible for both DSS and RSA. Indeed,
any value that depends only on p, g or q in DSS, or on n and its
factors in RSA, can be precomputed. In DSS the precomputed values can
be made public, since p, g and q are public, whereas in RSA the
values can only be made public if they do not depend on the factors
of n. They must be kept private if they depend on the factors. Taking
additional precomputation into account would affect the comparison of
DSS and RSA.