NIST's Digital Signature Proposal
A Technical Review

Burt Kaliski, RSA Laboratories
Dennis Branstad, NIST

Outline
  Introduction
  Definition
  Performance
  Security
  Trap doors
  Conclusions

Introduction
  Digital signatures
    public key, private key
    signing
    verification
  History
    1976 Diffie-Hellman
    1984 Elgamal
    1989 Schnorr
    August 1991 DSS proposal
    August 1991 - November 1991 first comment period
    November 1991 - February 1992 second comment period
    revised proposal in preparation

Definition
  Parameters
    public key
    private key
  Algorithm
    signing
    verification
      why it works
  vs. other systems
    Diffie-Hellman
    Elgamal
    Schnorr
    RSA

Performance
    in multiplications
  Signing
    off-line
    on-line
    with precomputed values
  Verification
    without precomputed values
    with precomputed values
  Key generation
    common modulus
    unique modulus
  vs. other systems (table)
    Elgamal
    RSA

Security
  Problem
    given message, find signature
    given public key, find private key
  Solutions
    discrete logarithms
      index calculus
      number field sieve
      baby-step/giant-step
      unexplored q-based attacks
      cost (table)
    random number recovery
  vs. RSA

Trap doors
  What is a trap door?
  "Trapped" primes
    definition
    properties
  Revised key generation

Conclusions
  Digital signature scheme based on discrete logarithms
  Signing speed good, verification speed fair
  Generally strong, some parts unexplored
  Trap doors possible, but avoidable