Introduction
The ECDSA signature scheme requires fresh, high-quality entropy for each signature generation. This presents two problems:
1. The availability of a source of high-quality entropy for signing
2. The inability of automated tests to verify that a signature was created using sufficiently high-quality 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, non-deterministic ECDSA signing will be discussed, followed by the deterministic variant and some of its disadvantages.
Non-deterministic 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 x-coordinate 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 highly-random value (the secret) is technically easier to guess than 2 unknown highly-random 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 SHA-256, 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, secret-1]
(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/python-ecdsa/blob/c7b5e063447e5d67acc61ec35d9521fa0fce7a24/src/ecdsa/keys.py#L1346-L1407
medium.com/@simonwarta/signature-determinism-for-blockchain-developers-dbd84865a93e
datatracker.ietf.org/doc/html/rfc6979
billatnapier.medium.com/ecdsa-weakness-where-nonces-are-reused-2be63856a01a