Independent Submission T. Pornin Request for Comments: 6979 August 2013 Category: Informational ISSN: 2070-1721 Deterministic Usage of the Digital Signature Algorithm (DSA) and Elliptic Curve Digital Signature Algorithm (ECDSA) Abstract This document defines a deterministic digital signature generation procedure. Such signatures are compatible with standard Digital Signature Algorithm (DSA) and Elliptic Curve Digital Signature Algorithm (ECDSA) digital signatures and can be processed with unmodified verifiers, which need not be aware of the procedure described therein. Deterministic signatures retain the cryptographic security features associated with digital signatures but can be more easily implemented in various environments, since they do not need access to a source of high-quality randomness. Status of This Memo This document is not an Internet Standards Track specification; it is published for informational purposes. This is a contribution to the RFC Series, independently of any other RFC stream. The RFC Editor has chosen to publish this document at its discretion and makes no statement about its value for implementation or deployment. Documents approved for publication by the RFC Editor are not a candidate for any level of Internet Standard; see Section 2 of RFC 5741. Information about the current status of this document, any errata, and how to provide feedback on it may be obtained at http://www.rfc-editor.org/info/rfc6979. Copyright Notice Copyright (c) 2013 IETF Trust and the persons identified as the document authors. All rights reserved. This document is subject to BCP 78 and the IETF Trust's Legal Provisions Relating to IETF Documents (http://trustee.ietf.org/license-info) in effect on the date of publication of this document. Please review these documents carefully, as they describe your rights and restrictions with respect to this document.

Table of Contents 1. Introduction ....................................................3 1.1. Requirements Language ......................................4 2. DSA and ECDSA Notations .........................................4 2.1. Key Parameters .............................................5 2.2. Key Pairs ..................................................5 2.3. Integer Conversions ........................................6 2.3.1. Bits and Octets .....................................6 2.3.2. Bit String to Integer ...............................6 2.3.3. Integer to Octet String .............................7 2.3.4. Bit String to Octet String ..........................7 2.3.5. Usage ...............................................8 2.4. Signature Generation .......................................8 3. Deterministic DSA and ECDSA ....................................10 3.1. Building Blocks ...........................................10 3.1.1. HMAC ...............................................10 3.2. Generation of k ...........................................10 3.3. Alternate Description of the Generation of k ..............12 3.4. Usage Notes ...............................................13 3.5. Rationale .................................................13 3.6. Variants ..................................................14 4. Security Considerations ........................................15 5. Intellectual Property Status ...................................17 6. References .....................................................17 6.1. Normative References ......................................17 6.2. Informative References ....................................18 Appendix A. Examples .............................................20 A.1. Detailed Example ..........................................20 A.1.1. Key Pair ..............................................20 A.1.2. Generation of k .......................................20 A.1.3. Signature .............................................23 A.2. Test Vectors ..............................................24 A.2.1. DSA, 1024 Bits ........................................25 A.2.2. DSA, 2048 Bits ........................................27 A.2.3. ECDSA, 192 Bits (Prime Field) .........................29 A.2.4. ECDSA, 224 Bits (Prime Field) .........................31 A.2.5. ECDSA, 256 Bits (Prime Field) .........................33 A.2.6. ECDSA, 384 Bits (Prime Field) .........................35 A.2.7. ECDSA, 521 Bits (Prime Field) .........................38 A.2.8. ECDSA, 163 Bits (Binary Field, Koblitz Curve) .........42 A.2.9. ECDSA, 233 Bits (Binary Field, Koblitz Curve) .........44 A.2.10. ECDSA, 283 Bits (Binary Field, Koblitz Curve) .........46 A.2.11. ECDSA, 409 Bits (Binary Field, Koblitz Curve) .........49 A.2.12. ECDSA, 571 Bits (Binary Field, Koblitz Curve) .........52 A.2.13. ECDSA, 163 Bits (Binary Field, Pseudorandom Curve) ....56 A.2.14. ECDSA, 233 Bits (Binary Field, Pseudorandom Curve) ....58 A.2.15. ECDSA, 283 Bits (Binary Field, Pseudorandom Curve) ....60

A.2.16. ECDSA, 409 Bits (Binary Field, Pseudorandom Curve) ....63 A.2.17. ECDSA, 571 Bits (Binary Field, Pseudorandom Curve) ....66 A.3. Sample Code ...............................................70 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: o 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. o Key pair generation is not altered. Existing private keys can be used with deterministic DSA and ECDSA. o Using deterministic DSA and ECDSA implies no extra storage requirement of any secret or public value. o 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]. 2. DSA and ECDSA Notations In this section, we succinctly describe DSA and ECDSA and define our notations. The complete specifications for DSA and ECDSA can be found in [FIPS-186-4] and [X9.62], respectively.

2.1. Key Parameters DSA and ECDSA work over a large group of prime size, in which the group operation is easy to compute, but the discrete logarithm is computationally infeasible with existing and foreseeable technology. The definition of the group is called the "key parameters". Key parameters may be shared between different key pairs with no ill effect on security; this is the usual case with ECDSA in particular. DSA uses the following key parameters: p a large prime number (at least 1024 bits) q a sufficiently large prime number (at least 160 bits) that is also a divisor of p-1 g a generator for the multiplicative subgroup of order q of integers modulo p The group on which DSA will be computed consists of the values 'g^j mod p', where '^' denotes exponentiation and j ranges from 0 to q-1 (inclusive). The size of the group is q. ECDSA uses the following key parameters: E an elliptic curve, defined over a given finite field q a sufficiently large prime number (at least 160 bits) that is a divisor of the curve order G a point of E, of order q The group on which ECDSA will be computed consists of the curve points jG (multiplication of point G by integer j) where j ranges from 0 to q-1. G is such that qG = 0 (the "point at infinity" on the curve E). The size of the group is q. Note that these notations slightly differ from those described in [X9.62]; we use them in order to match those used for DSA. 2.2. Key Pairs A DSA or ECDSA private key is an integer x taken modulo q. The relevant standards prescribe that x shall not be 0; hence, x is an integer in the range [1, q-1].

A DSA or ECDSA public key is computed from the private key x and the key parameters: o For DSA, the public key is the integer: y = g^x mod p o For ECDSA, the public key is the curve point: U = xG 2.3. Integer Conversions Let qlen be the binary length of q. qlen is the smallest integer such that q is less than 2^qlen. This is the size of the binary representation of q without a sign bit (note that q, being a big prime, is odd, thus avoiding any ambiguity about the length of any integer equal to a power of 2). We define five conversion functions, which work on strings of bits, octets, and integers modulo q. qlen is the main parameter for these conversions. In the following subsections, we use two other lengths, called blen and rlen. rlen is equal to qlen, rounded up to the next multiple of 8 (if qlen is already a multiple of 8, then rlen equals qlen; otherwise, rlen is slightly larger, up to qlen+7). Note that rlen is unrelated to the value r, the first half of a generated signature. blen is the length (in bits) of an input sequence of bits and may vary between calls. blen may be smaller than, equal to, or larger than qlen. 2.3.1. Bits and Octets Formally, all operations are defined on sequences of bits. A sequence is ordered; the first bit is said to be leftmost, while the last bit is rightmost. On most software systems, bits are grouped into octets (sequences of eight bits). Binary data, e.g., the output of a hash function, is available as a sequence of octets. Whenever applicable, we consider that bits within an octet are ordered from most significant to least significant: the first (leftmost) bit within an octet has numerical value 128, while the last (rightmost) has numerical value 1. 2.3.2. Bit String to Integer The bits2int transform takes as input a sequence of blen bits and outputs a non-negative integer that is less than 2^qlen. It consists of the following steps:

1. The sequence is first truncated or expanded to length qlen: * if qlen < blen, then the qlen leftmost bits are kept, and subsequent bits are discarded; * otherwise, qlen-blen bits (of value zero) are added to the left of the sequence (i.e., before the input bits in the sequence order). 2. The resulting sequence is then converted to an integer value using the big-endian convention: if input bits are called b_0 (leftmost) to b_(qlen-1) (rightmost), then the resulting value is: b_0*2^(qlen-1) + b_1*2^(qlen-2) + ... + b_(qlen-1)*2^0 The bits2int transform can also be described in the following way: the input bit sequence (of length blen) is transformed into an integer using the big-endian convention. Then, if blen is greater than qlen, the resulting integer is divided by two to the power blen-qlen (Euclidian division: the remainder is discarded); in many software implementations of arithmetics on big integers, that division is equivalent to a "right shift" by blen-qlen bits. 2.3.3. Integer to Octet String An integer value x less than q (and, in particular, a value that has been taken modulo q) can be converted into a sequence of rlen bits, where rlen = 8*ceil(qlen/8). This is the sequence of bits obtained by big-endian encoding. In other words, the sequence bits x_i (for i ranging from 0 to rlen-1) are such that: x = x_0*2^(rlen-1) + x_1*2^(rlen-2) + ... + x_(rlen-1) We call this transform int2octets. Since rlen is a multiple of 8 (the smallest multiple of 8 that is not smaller than qlen), then the resulting sequence of bits is also a sequence of octets, hence the name. 2.3.4. Bit String to Octet String The bits2octets transform takes as input a sequence of blen bits and outputs a sequence of rlen bits. It consists of the following steps: 1. The input sequence b is converted into an integer value z1 through the bits2int transform: z1 = bits2int(b)

2. z1 is reduced modulo q, yielding z2 (an integer between 0 and q-1, inclusive): z2 = z1 mod q Note that since z1 is less than 2^qlen, that modular reduction can be implemented with a simple conditional subtraction: z2 = z1-q if that value is non-negative; otherwise, z2 = z1. 3. z2 is transformed into a sequence of octets (a sequence of rlen bits) by applying int2octets. 2.3.5. Usage It is worth noting that int2octets is not the reverse of bits2int, even for input sequences of length qlen: int2octets will add some bits on the left, while bits2int will discard some bits on the right. int2octets is the reverse of bits2int only when qlen is a multiple of 8 and bit sequences already have length qlen. bits2int is used during signature generation and verification in standard DSA and ECDSA to transform a hash value (computed over the input message) into an integer modulo q. That is, the integer obtained through bits2int is further reduced modulo q; since that integer is less than 2^qlen, that reduction can be performed with at most one subtraction. int2octets is defined under the name "Integer-to-OctetString" in Section 2.3.7 of SEC 1 [SEC1]. It is used in the specification of the encoding of an ECDSA private key (x) within an ASN.1-based structure. bits2octets is not used in standard DSA or ECDSA. We will use it in the specification of deterministic (EC)DSA. 2.4. Signature Generation Signature generation uses a cryptographic hash function H and an input message m. The message is first processed by H, yielding the value H(m), which is a sequence of bits of length hlen. Normally, H is chosen such that its output length hlen is roughly equal to qlen, since the overall security of the signature scheme will depend on the smallest of hlen and qlen; however, the relevant standards support all combinations of hlen and qlen.

The following steps are then applied: 1. H(m) is transformed into an integer modulo q using the bits2int transform and an extra modular reduction: h = bits2int(H(m)) mod q As was noted in the description of bits2octets, the extra modular reduction is no more than a conditional subtraction. 2. A random value modulo q, dubbed k, is generated. That value shall not be 0; hence, it lies in the [1, q-1] range. Most of the remainder of this document will revolve around the process used to generate k. In plain DSA or ECDSA, k should be selected through a random selection that chooses a value among the q-1 possible values with uniform probability. 3. A value r (modulo q) is computed from k and the key parameters: * For DSA: r = g^k mod p mod q (The exponentiation is performed modulo p, yielding a number between 0 and p-1, which is then further reduced modulo q.) * For ECDSA: the point kG is computed; its X coordinate (a member of the field over which E is defined) is converted to an integer, which is reduced modulo q, yielding r. If r turns out to be zero, a new k should be selected and r computed again (this is an utterly improbable occurrence). 4. The value s (modulo q) is computed: s = (h+x*r)/k mod q The pair (r, s) is the signature. How a signature is to be encoded is not covered by the DSA and ECDSA standards themselves; a common way is to use a DER-encoded ASN.1 structure (a SEQUENCE of two INTEGERs, for r and s, in that order).

3. Deterministic DSA and ECDSA Deterministic (EC)DSA is the process of generating an (EC)DSA signature over an input message m by using the standard (EC)DSA signature generation process (discussed in the previous section), except that the value k, instead of being randomly generated, is obtained through the process described in this section. We use the notations described in Section 2. 3.1. Building Blocks 3.1.1. HMAC HMAC [RFC2104] is a construction of a Message Authentication Code using a hash function and a secret key. Here, we use HMAC with the same hash function H as the one used to process the input message prior to signature generation or verification. We denote the process of applying HMAC with key K over data V by: HMAC_K(V) which returns a sequence of bits of length hlen (the output length of the underlying hash function H). 3.2. Generation of k Given the input message m, the following process is applied: a. Process m through the hash function H, yielding: h1 = H(m) (h1 is a sequence of hlen bits). b. Set: V = 0x01 0x01 0x01 ... 0x01 such that the length of V, in bits, is equal to 8*ceil(hlen/8). For instance, on an octet-based system, if H is SHA-256, then V is set to a sequence of 32 octets of value 1. Note that in this step and all subsequent steps, we use the same H function as the one used in step 'a' to process the input message; this choice will be discussed in more detail in Section 3.6.

c. Set: K = 0x00 0x00 0x00 ... 0x00 such that the length of K, in bits, is equal to 8*ceil(hlen/8). d. Set: K = HMAC_K(V || 0x00 || int2octets(x) || bits2octets(h1)) where '||' denotes concatenation. In other words, we compute HMAC with key K, over the concatenation of the following, in order: the current value of V, a sequence of eight bits of value 0, the encoding of the (EC)DSA private key x, and the hashed message (possibly truncated and extended as specified by the bits2octets transform). The HMAC result is the new value of K. Note that the private key x is in the [1, q-1] range, hence a proper input for int2octets, yielding rlen bits of output, i.e., an integral number of octets (rlen is a multiple of 8). e. Set: V = HMAC_K(V) f. Set: K = HMAC_K(V || 0x01 || int2octets(x) || bits2octets(h1)) Note that the "internal octet" is 0x01 this time. g. Set: V = HMAC_K(V) h. Apply the following algorithm until a proper value is found for k: 1. Set T to the empty sequence. The length of T (in bits) is denoted tlen; thus, at that point, tlen = 0. 2. While tlen < qlen, do the following: V = HMAC_K(V) T = T || V

3. Compute: k = bits2int(T) If that value of k is within the [1,q-1] range, and is suitable for DSA or ECDSA (i.e., it results in an r value that is not 0; see Section 3.4), then the generation of k is finished. The obtained value of k is used in DSA or ECDSA. Otherwise, compute: K = HMAC_K(V || 0x00) V = HMAC_K(V) and loop (try to generate a new T, and so on). Please note that when k is generated from T, the result of bits2int is compared to q, not reduced modulo q. If the value is not between 1 and q-1, the process loops. Performing a simple modular reduction would induce biases that would be detrimental to signature security. 3.3. Alternate Description of the Generation of k The process described in the previous section is actually derived from the "HMAC_DRBG" pseudorandom number generator, described in [SP800-90A] and Annex D of [X9.62]. Using the terminology from [SP800-90A], the generation of k can be described as such: a. Instantiate HMAC_DRBG using HMAC parameterized with the same hash function H as the one used for processing the message that is to be signed. Instantiation parameters are: requested_instantiation_security_strength Set this parameter to any value that the HMAC_DRBG implementation will accept, when using H as base hash function. prediction_resistance_flag Set this parameter to "false". personalization_string Set this parameter to "Null" (the empty bit sequence). entropy_input Use int2octets(x) as entropy string. nonce Use bits2octets(H(m)) as nonce.

Note that the last two parameters are not parameters to the HMAC_DRBG instantiation function per se; instead, those values are requested from the internal Get_entropy_input function during instantiation. For deterministic (EC)DSA, we want HMAC_DRBG to run with the entropy string and nonce that we specify, without accessing an actual entropy source. b. Generate a candidate value for k by requesting qlen bits from HMAC_DRBG and converting the resulting bits into an integer with the bits2int transform. Repeat this step until a value is obtained, which is non-zero, less than q, and suitable for (EC)DSA (see Section 3.4). Note that we instantiate a new HMAC_DRBG instance for each signature generation process. There is no "personalization string" and no "additional input" when generating bits. The reseed function of HMAC_DRBG is never invoked, neither externally nor as a consequence of the internal HMAC_DRBG processing. As shown above, we use the encoding of the private key as "entropy string" and the hashed message (truncated and expanded by bits2octets) as "nonce". In HMAC_DRBG, the entropy string and nonce are simply concatenated into the initial seed; hence, the split between "entropy" and "nonce" is quite arbitrary. Using qlen bits for each ought to be compatible with most HMAC_DRBG implementation input requirements. 3.4. Usage Notes With DSA or ECDSA, the value k is used to compute the first half of the signature, dubbed r (see Section 2.4). The DSA and ECDSA standards mandate that, if r is zero, then a new k should be selected. In that situation, this document specifies that the value k is "unsuitable", and the generation process shall keep on looping. This occurrence is utterly improbable. Actually, it would require considerable computational effort (similar to breaking preimage resistance of the hash function) to find a private key and a message that lead to a zero value for r; hitting such a case by pure chance is thus deemed implausible, and an attacker cannot force it with carefully crafted messages. In practice, such a code path will not be triggered and thus can be implemented with little optimization. 3.5. Rationale The process described in the previous sections mimics the "Approved" generation process of k described in Annex D of [X9.62], with the "HMAC_DRBG" pseudorandom number generator. The main difference is

that we use the concatenation of the private key x and the hashed message H(m) as the pseudorandom number generator (PRNG) seed. If using a "security level" of n bits, then HMAC_DRBG should be used with seed entropy at least n+64 bits; however, the key x should also have been generated with that much entropy, and the length of x is qlen, which is at least equal to 2*n and thus larger than n+64 (DSA and ECDSA, as specified by the standards, require qlen >= 160). It can then be argued that deterministic ECDSA fulfills the entropy requirements of Annex D of [X9.62]. We use bits2octets(H(m)) instead of H(m) in order to ease integration. Indeed, many existing signature systems offload the message hashing; the signature engine (which has access to the private key) receives only H(m). In some applications, where data bandwidth is constrained, only the first qlen bits of H(m) are transferred to the signature engine, on the basis that the bits2int transform will ignore subsequent bits anyway. Possibly, in some systems, the truncated H(m) could be externally reduced modulo q, since that is the first thing that (EC)DSA performs on the hashed message. With the definition of bits2octets, deterministic (EC)DSA can be applied with the same input. 3.6. Variants Many parts of the specification of deterministic (EC)DSA are quite arbitrary. It is possible to define variants that are NOT "deterministic (EC)DSA" but that may nonetheless be useful in some contexts: o It is possible to use H(m) directly, instead of bits2octets(H(m)), as part of the HMAC input. As explained in Section 3.5, we use bits2octets(H(m)) in order to ease integration into systems that already use an (EC)DSA signature engine by sending it an already- truncated hash value. Using the whole H(m) does not introduce any vulnerability. o Additional data may be added to the input of HMAC, concatenated after bits2octets(H(m)): K = HMAC_K(V || 0x00 || int2octets(x) || bits2octets(h1) || k') A use case may be a protocol that requires a non-deterministic signature algorithm on a system that does not have access to a high-quality random source. It suffices that the additional data k' is non-repeating (e.g., a signature counter or a monotonic clock) to ensure "random-looking" signatures are indistinguishable, in a cryptographic way, from plain (EC)DSA signatures. In [SP800-90A] terminology, k' is the "additional

input" that can be set as a parameter when generating pseudorandom bits. This variant can be thought of as a "strengthening" of the randomness of the source of the additional data k'. o Instead of using x (the private key) as input to HMAC, it is possible to use additional secret data, stored along with the private key with the same security measures. The entropy of that additional data SHALL be at least n bits, preferably n+64 bits or more, where n is the target security level. Having additional secret data may help in formally proving the security of derandomization, but it implies an extra storage cost and incompatibility with already-generated (EC)DSA private keys. o Similarly, the private key could be a value z, from which both x (the "private key" in the plain (EC)DSA sense) and another value x', to be used as input to HMAC in the generation of k, would be derived through a suitable Pseudorandom Function (PRF) (such as HMAC_DRBG). This would keep private key storage requirements to a minimum while providing a more easily proven security, but it would impact private key generation and would not be compatible with already-generated key pairs. o In this document, we use the same hash function H for processing the input message and as a parameter to HMAC. Two distinct hash functions could be used, provided that both are adequately secure. The overall security will be limited by the weaker of the two hash functions, i.e., the one with the smaller output. Using a specific, constant hash function for HMAC may be useful for constrained implementations that accept externally hashed messages, regardless of what hash function was used for that, but have resources for implementing only one hash function for HMAC. The main disadvantage of any variant is that it ceases to be verifiable against the test vectors published in this document. 4. Security Considerations Proper implementation and usage of a cryptographic signature algorithm require taking into account many parameters. In particular, private key generation, storage, access control, and disposal are sensitive operations, which this document does not address in any way. Deterministic (EC)DSA shows how to achieve the security characteristics of a standard DSA or ECDSA signature scheme while removing the need for a source of strong randomness, or even any source of randomness, during signature generation.

Private key generation, however, absolutely requires such a strongly random source. In situations where deterministic (EC)DSA is to be used due to the lack of an appropriate source of randomness, one must assume that the private key has been generated externally and imported into the signature generation system or was generated in a context where randomness was available. For instance, one can imagine a smartcard that generates its private key while still in the factory under controlled environmental conditions, but for which random data generation cannot be guaranteed once deployed in the field, when physically in the hands of potential attackers. Both removal of the random source requirement and the ability to test an implementation against test vectors enhance security of DSA and ECDSA signer implementations, in that they help avoid hard-to-test failure conditions. Deterministic signature schemes may also help in other situations, e.g., to avoid spurious duplicates, when the same data element is signed several times with the same key: with a deterministic signature scheme, the same signature is generated every time, making duplicate detection much easier. Conversely, lack of randomization may have adverse effects in some advanced protocols, e.g., related to anonymity in some voting schemes. As a rule of thumb, deterministic DSA or ECDSA can be used in lieu of the genuine DSA or ECDSA, with no additional security issues, if the overall protocol would tolerate another deterministic signature scheme, in particular RSA as specified in PKCS #1 [RFC3447] (with "type 1" padding, not PSS) or ISO 9796-2 [ISO-9796-2]. The list of protocols in which deterministic DSA or ECDSA is appropriate includes Transport Layer Security (TLS) [RFC5246], the Secure SHell (SSH) Protocol [RFC4251], Cryptographic Message Syntax (CMS) [RFC5652] and derivatives, X.509 public key infrastructures [RFC5280], and many others. The construction described in this document is known as a "derandomization". This has been proposed for various signature schemes. Security relies on whether the generation of k is indistinguishable from the output of a random oracle. Roughly speaking, HMAC_DRBG is secure in that role as long as HMAC behaves as a PRF (Pseudorandom Function). For details on the security of HMAC and HMAC_DRBG, please refer to [H2008] and [B2006]. For a more formal treatment of derandomization, see [LN2009]. One remaining issue with deterministic (EC)DSA, as presented in this document, is the "double use" of the private key x, both as the private key in the signature generation algorithm itself and as input to the HMAC_DRBG-based pseudorandom oracle for producing the k value. This requires HMAC_DRBG to keep on being a random oracle, even when

the public key (which is computed from x) is also known. Given the lack of common structure between HMAC and discrete logarithms, this seems a reasonable assumption. Side-channel attacks are an important consideration whenever an attacker can accurately measure aspects of an implementation such as the length of time that it takes to perform a signing operation or the power consumed at each point of a signing operation. The determinism of the algorithms described in this note may be useful to an attacker in some forms of side-channel attacks, so implementations SHOULD use defensive measures to avoid leaking the private key through a side channel. 5. Intellectual Property Status To the best of our knowledge, deterministic (EC)DSA is not covered by any active patent. The paper [BDLSY2011] points to two independent publications of the idea of derandomization by Barwood and Wigley, both in early 1997, and also to a patent application by Naccache, M'Raihi, and Levy-dit-Vehel a few months later [NML1997], but the application was withdrawn in 2003. We are not aware of any other patent on the subject.