Introduction
The ECDSA signature scheme requires fresh, highquality entropy for each signature generation. This presents two problems:
1. The availability of a source of highquality entropy for signing
2. The inability of automated tests to verify that a signature was created using sufficiently highquality entropy
The solution is to use a deterministic method of the producing the required entropy. That is, an entropy value that is a pure function of the data to be signed. The required value for each signing operation is commonly known as
k
.Firstly, nondeterministic ECDSA signing will be discussed, followed by the deterministic variant and some of its disadvantages.
Nondeterministic signing
Signature generation begins with a randomly chosen point on an elliptic curve. This point is calculated by using a random value
k
, starting from a known generator point
G
. The first part of the signature
r
is simply:
r = kG
This equation relies on elliptic curve arithmetic.
r
represents the xcoordinate of the resulting point on the curve. The second part of the signature
s
is calculated as follows:
s = (k^1) * (H(M) + r * secret)
Where:
1.
H(M)
is the hash of the message
M
converted to an integer2.
secret
is the secret key of the signerThe concatenation of the two values
r
and
s
is the signature.Given two messages signed using the same secret key and the same nonce
k
(hence the same
r
), the secret key can be recovered as follows:
h1 = H(M1)
h2 = H(M2)
secret = (s2 * h1 + s1 * h2) / [r * (s1 + s2)]
h2 = H(M2)
secret = (s2 * h1 + s1 * h2) / [r * (s1 + s2)]
It is therefore imperative that a different nonce
k
be used for each signature.Deterministic signing
The objective of deterministic signing is to avoid the need to generate a new value
k
for each operation. In short, the means of doing this involves combining the secret key with the hash of the message, yielding a value that cannot be known unless the secret key is known.Note: This does provide less security than using a fresh value for
k
. 1 unknown highlyrandom value (the secret) is technically easier to guess than 2 unknown highlyrandom values (the secret and the random k value).Algorithm
According to RFC6979, the steps to generate a value
k
from the message and secret are as follows:1. Hash the message
h1 = H(M)
2. Begin first initialisation of
V
and
K
parameters Initialise
V
to all 1s equal to the length of the hash
V = 0x01 0x01 0x01 ... 0x01
For SHA256, this equates to 32 octets set to 1.
 Initialise
K
to all 0s equal to the length of the hash
K = 0x00 0x00 0x00 ... 0x00
3. Begin second initialisation
 Set the value of
K = HMAC_K(V  0x00  int2octets(secret)  bits2octets(h1))
Where:


HMAC_K
is the HMAC function using the same hash as step (1) with key
K


denotes concatenation
 Set the value of
V = HMAC_K(V)
4. Begin third initialisation
 Set the value of
K = HMAC_K(V  0x01  int2octets(secret)  bits2octets(h1))
Only the second concatenation,
0x01
has changed. Set the value of
V = HMAC_K(V)
5. Begin main loop
 Set
T
to an empty sequence such that the length of
T
is 0 While
length(T) < length(secret)
:


V = HMAC_K(V)

T = T  V
6. Finally,
k = bits2int(T)
7. If the value of
k
is not within the range
[1, secret1]
(i.e. the value of
r
is 0), the following should be run:
K = HMAC_K(V  0x00)

V = HMAC_K(V)
 Return to step (4)
It should be noted that, while possible, this scenario is vanishingly unlikely to occur.
Conclusion
The deterministic signing scheme can be used in place of the normal signing schema for ECDSA.
Sources
github.com/tlsfuzzer/pythonecdsa/blob/c7b5e063447e5d67acc61ec35d9521fa0fce7a24/src/ecdsa/keys.py#L1346L1407
medium.com/@simonwarta/signaturedeterminismforblockchaindevelopersdbd84865a93e
datatracker.ietf.org/doc/html/rfc6979
billatnapier.medium.com/ecdsaweaknesswherenoncesarereused2be63856a01a