Skip to main content

1. Introduction

DSA [FIPS-186-4] and ECDSA [X9.62] are two standard digital signature schemes. They provide data integrity and verifiable authenticity in various protocols.

One characteristic of DSA and ECDSA is that they need to produce, for each signature generation, a fresh random value (hereafter designated as k). For effective security, k must be chosen randomly and uniformly from a set of modular integers, using a cryptographically secure process. Even slight biases in that process may be turned into attacks on the signature schemes.

The need for a cryptographically secure source of randomness proves to be a hindrance to deployment of DSA and ECDSA signature schemes in some architectures in which secure random number generation is challenging, in particular, embedded systems such as smartcards. In those systems, the RSA signature algorithm, used as specified in Public-Key Cryptography Standards (PKCS) #1 [RFC3447] (with "type 1" padding, not the Probabilistic Signature Scheme (PSS)) and ISO 9796-2 [ISO-9796-2], is often preferred, even though it is computationally more expensive, because RSA (with such padding schemes) is deterministic and thus does not require a source of randomness.

The randomized nature of DSA and ECDSA also makes implementations harder to test. Automatic tests cannot reliably detect whether the implementation uses a source of randomness of high enough quality. This makes the implementation process more vulnerable to catastrophic failures, often discovered after the system has been deployed and successfully attacked.

It is possible to turn DSA and ECDSA into deterministic schemes by using a deterministic process for generating the "random" value k. That process must fulfill some cryptographic characteristics in order to maintain the properties of verifiability and unforgeability expected from signature schemes; namely, for whoever does not know the signature private key, the mapping from input messages to the corresponding k values must be computationally indistinguishable from what a randomly and uniformly chosen function (from the set of messages to the set of possible k values) would return.

This document describes such a procedure. It has the following features:

  • Produced signatures remain fully compatible with plain DSA and ECDSA. Entities that verify the signatures need not be changed or even be aware of the process used to generate k.

  • Key pair generation is not altered. Existing private keys can be used with deterministic DSA and ECDSA.

  • Using deterministic DSA and ECDSA implies no extra storage requirement of any secret or public value.

  • Deterministic DSA and ECDSA can be applied over the same inputs as plain DSA and ECDSA, namely a hash value computed over the message that is to be signed, with a cryptographically secure hash function.

Some relatively arbitrary choices were taken in the definition of deterministic (EC)DSA as specified in this document; this was done in order to make it as universally applicable as possible, so as to maximize usefulness of included test vectors. See Section 3.6 for a discussion of some possible variants.

It shall be noted that key pair generation still requires a source of randomness. In embedded systems where quality of randomness is an issue, it can often be arranged that key pair generation occurs within more controlled conditions (e.g., during a special smartcard initialization procedure or under physical control of sworn agents) or the key might even be generated elsewhere and imported in the device. Deterministic DSA and ECDSA only deal with the need for randomness at the time of signature generation.

1.1. Requirements Language​

The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this document are to be interpreted as described in RFC 2119 [RFC2119].