Technology and Trends
 USENET Archives
  
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.