Digital Signature Algorithm


The Digital Signature Algorithm (DSA) is a standard for digital signatures proposed by the NIST in August 1991 for use in their Digital Signature Standard (DSS).

Key generation

Keys are generated in two phases: the first one consists of a choice of parameters for the algorithm which can be publicly shared between users of the system, while the second one is the usual computation of public and private keys for a single user.

Algorithm parameters generation

  • Choose a cryptographic hash function (SHA-2 for the current DSS). The output can be truncated to the size of a key pair.
  • Decide on a key length and an integer , which represent the main measure of the cryptographic strength of the key. For instance, NIST recommends . Moreover, has to be less than or equal to the hash output.
  • Choose an -bit prime .
  • Choose an -bit prime such that , i.e. is a multiple of .
  • Choose a number such that is the smallest integer that satisfies
The algorithm parameters may now be shared between different users of the system which generated them.

Keys computation

  • Choose a private key by some random method, such that .
  • Compute the public key .
In order to efficiently compute the modular exponentiations, it could be convenient to use algorithms such as exponentiation by squaring.

Message signing

If is the hash function we've chosen and the message, then:

  • Choose a random such that for each message.
  • Compute .
  • In the rare case that , go back and choose a new random .
  • Compute .
  • In the rare case that , go back and choose a new random .
  • The signature is: .

Message verifying

  • If one between or is not satisfied, reject the message.
  • Compute .
  • Compute
  • Compute .
  • Compute .
  • The signature is considered valid if and only if .
In some aspects, DSA is very similar to the ElGamal signature scheme.

Correctness