3
$\begingroup$

Formula for calculating an ECDSA signature (r, s) is:

s = k-1(z + qr)

k - private key for a random point R
z - hash of a message
q - original private key
r - x(R)

I am interested in why do we need two secret values (k and q) in a formula for calculating ECDSA signature? In other words, why we need one additional secret value k (and its public key - point on a curve) in additional to already existing one secret value q (and its public key)? Couldn't it be realized with only one unknown value (q)?

I found some answer here.

The reason nonce is used is because you need to create two unknowns so that people cannot reverse engineer the private key from the public key.

It seems to me that this is so that we have one equation with two unknowns (which is unsolvable). If only the original private key q is present in the equation, i.e. if it is the only unknown (without the additional secret k), we would have one equation with one unknown, which is solvable. However, I'm not sure. Is that the reason or something else/additional?

Also, why is it used as k-1 in equation and not just k? Some special security reason or just a "design detail" of the algorithm creators?

$\endgroup$
6
  • $\begingroup$ Probabilistic signature! Otherwise, one can distinguished that the message signed again. $\endgroup$
    – kelalaka
    Nov 26, 2023 at 17:06
  • $\begingroup$ @kelalaka Can you explain in a little more detail what exactly you mean? $\endgroup$
    – LeaBit
    Nov 26, 2023 at 17:16
  • 1
    $\begingroup$ First of all, what is your definition of $k$-less ECDSA? See this What is the intuition for ECDSA? $\endgroup$
    – kelalaka
    Nov 26, 2023 at 17:36
  • $\begingroup$ @kelalaka I am not from the world of cryptographic and mathematic, so I can't give you an concrete answer to your question. I was just like if we have one secret value (original private key q), why is there a need for another one k? Could we just make an algorithm with that one secret value and what is the base reason of introducing one additional? I found some logical answer in the link I posted in a question where it says that we need two unknowns in equation to make it unsolvable and it makes full sense to me. $\endgroup$
    – LeaBit
    Nov 26, 2023 at 17:53
  • 1
    $\begingroup$ @kelalaka: your observation is correct that if there was no secret value $k$, then ECDSA would necessarily be a deterministic signature scheme (that is, such that the same signature is obtained if we sign again the same message with the same private key). However this is not why we need an additional secret value $k$: we can make $k$ a deterministic pseudo-random function of message and private key, and then ECDSA becomes a deterministic secure signature scheme. There's RFC6979 codifying that. But still, $k$ needs to exist and be secret. $\endgroup$
    – fgrieu
    Nov 26, 2023 at 18:09

1 Answer 1

7
$\begingroup$

First, why does $k$ need to be secret in ECDSA?

With the question's notation, in ECDSA, $s=k^{-1}(z+q\,r)\bmod n$ where $n$ is the public prime order of the elliptic curve group, $z$ is public since it's the hash of the message, $r\bmod n$ is public since that's the first component of the signature, and $q$ is the private key with $0<q<n$. It follows that knowledge of $k$ would allow to compute $q$ as $q=(r\bmod n)^{-1}(s\,k-z)\bmod n$, allowing to sign any message and breaking the signature's security.


But that does not tell why we need $k$ and the corresponding point $k\,G$ on the curve, which the question also asks.

Attempt at a high-level explanation: for construction of a signature scheme using as sole building block an arbitrary group in which we define scalar multiplication by repeated addition and a generator $G$ (as in ECDSA), all the methods we know require (at least, and for those in practical use, exactly)

  • One public group element (the public key) that is a multiple of $G$ by a secret integer (the private key $q$ in the question).
  • And, for each message, another public group element that is a multiple of $G$ by another secret integer ($k$ in the question) unique to each signature.

For a more detailed explanation, I recommend this answer to what is the intuition for ECDSA?.


As to why the modular inverse $k^{-1}$ must be computed when it is not the case for other signature schemes using the same kind of groups as ECDSA (e.g. Schnorr signature adapted to elliptic curve group): this is because ECDSA evolved from DSA that also requires a modular inverse. ECDSA differs from DSA only by the choice of the group, and loosing one bit in the representation of a group element (with the consequence that there are two valid signatures, easily derived one from the other, for each choice of $k$ all other things being equal).

As to why DSA has this modular inverse, there are at least two theories (not exclusive):

  • DSA was inspired by the ElGamal signature scheme, which uses a modular inverse in the equation $s=k^{-1}(m-q\,r)\bmod(p-1)$, where $m$ is the message. DSA differs by:

    1. Hashing the message (which is necessary for avoiding existential forgery).
    2. Using a generator of a subgroup with prime and relatively small order $n$ instead of $p-1$, which allows a much smaller signature and faster computation.
    3. A sign change in the private key, which is minor.
  • DSA was published after Schnorr signature, which does 1/2/3 above and does not require computation of a modular inverse (a clear advantage), by using an extra input to the hash. For wide adoption without royalty issues, it was desirable that the design of DSA distinguish itself most clearly from the claims in this patent for Schnorr signature (later US version)

And: when we try to remove the modular inversion from the formulas in ElGamal signature, DSA or ECDSA, it seems that for the signature verification to work, another modular inversion must be added elsewhere. As far as I know, all methods to get entirely rid of the modular inversion in these schemes add an additional input to the existing hash (as in Schnorr signature), or an additional hash.

$\endgroup$
5
  • $\begingroup$ Great explanation. Just one question about needs for secret values. You said that for each message we need one additional secret value. Since we are signing one message in ECDSA we need one additional secret value (k). However, if we have, for example, 3 messages, in theory we would need 3 ks, that is 3 secret values k + q. Right? $\endgroup$
    – LeaBit
    Nov 26, 2023 at 20:25
  • 2
    $\begingroup$ Yes, that's what happens in ECDSA, either $k$ is randomly generated for each message or - for deterministic ECDSA - it is calculated from the hash & the private key to keep it secret. $\endgroup$
    – Maarten Bodewes
    Nov 26, 2023 at 20:34
  • 1
    $\begingroup$ @MaartenBodewes So, in both cases (deterministic and non-deterministic) for each message I need one additional secret value k and the only question is how we will get its value. For non-deterministic: k is random and for deterministic is what you wrote above. Did I get it right? $\endgroup$
    – LeaBit
    Nov 26, 2023 at 20:52
  • 2
    $\begingroup$ Yes, that's exactly what I meant to say. $\endgroup$
    – Maarten Bodewes
    Nov 26, 2023 at 21:26
  • 1
    $\begingroup$ Yes to the above comments, understood as stated for distinct messages. The number of (hopefully distinct) $k$ is: the number of signatures made, for random choice of $k$; or the number of distinct messages signed, for deterministic choice of $k$. $\endgroup$
    – fgrieu
    Nov 26, 2023 at 21:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.