5
$\begingroup$

According to Wikipedia, if Alice wants to sign some message, she computes $s = k^{-1} (z + r d_A)$ then sends $(r, s)$ to Bob.

I don't understand why they use this particular formula $s = k^{-1} (z + r d_A)$ for signing the message ? Why don't they just take $s = r d_A + z$ (i.e. $k = 1$) or $s = d_A + z$ or some other form ?

$\endgroup$
12
$\begingroup$

The main reason is historical (and a bit sad).

ECDSA can be seen as a repurposed authentication mechanism. The private key owner wants to prove knowledge of the private key $x$ that matches a given public key $Q = xG$, but without revealing that private key. Thus, this is organized as a three-step protocol:

  1. The prover makes a commitment on a newly generated random value $k$; the commitment is the point $kG$ (value $r$ is basically the X coordinate of that point).
  2. The verifier issues a challenge (let's call it $e$).
  3. The prover responds to the challenge with a value $s$, which is such that the verifier can check that the prover knew a value derived from $k$ and $x$, but without actually revealing $x$.

This authentication scheme is then turned into a signature scheme by making the signer play the protocol against himself: the challenge is computed deterministically from the commitment, making the physical presence of the verifier unnecessary. The signer can play the protocol by himself, and the transcript of the protocol (the pair $(r,s)$) can be verified non-interactively afterwards.

Now, in the 1980s, there was a nice protocol fitting that mechanism, known as Schnorr signatures. In a Schnorr signature, the challenge $e$ is computed as a hash value over the signed message and the commitment, and the response is computed as $s = k - xe$ (some variants make it $s = k + xe$). However, Schnorr had filed a patent on that algorithm. When the US federal government looked for an algorithm to standardize for all US federal organizations, they wanted to avoid patents as much as possible (otherwise, they would have used RSA, which was also patented). Thus, they looked for a more-or-less Schnorr-like protocol that would be nonetheless different enough so as not to infringe on the patent. They thus lifted the ElGamal signature scheme, which was not patented (at that time! Certicom filed patents afterwards, for ElGamal adapted to elliptic curves). It was ElGamal that introduced the modular inversion of $k$, which is cumbersome to implement. The result of the adaptation of ElGamal into a US standard was called DSA. ECDSA was later defined as DSA applied on elliptic curves.

Thus, you can say that the specific formula of DSA and ECDSA, with the $k^{-1}$, was chosen for patent avoidance reasons, not for any cryptographic advantage. Indeed, that formula sucks: it makes implementation more complicated, it prevents some security proofs, and it makes the signatures somewhat malleable (if $(r,s)$ is a valid ECDSA signature, then $(r,-s)$ is also a valid ECDSA signature on the same message with the same key), a property which has induced some occasional trouble (namely, transaction replay attacks in Bitcoin).

$\endgroup$
3
$\begingroup$

Why don't they just take $s = r d_A + z$

The equation that an ECDSA-like signature uses must satisfy these requirements:

  1. It must be practical for the signer to compute

  2. It must be impractical for someone who doesn't know the private key to compute

  3. It must not allow forgeries; someone who sees a number of valid signatures/message pairs must not be able to deduce the private key, or otherwise generate signatures to messages that the valid signer hasn't signed.

  4. It must yield a relation that the verifier can, well, verify

In this example, it does not satisfy (3); someone who sees one signature knows $r$, $s$ and the message gives him $z$; that is sufficient for him to recover $d_A$ the private key (and with that, he can sign anything)

$s = d_A + z$

Ditto, an adversary who sees $s$ and can compute $z$ can recover the private key $d_A$

or some other form ?

There are other forms that do meet all four of the requirements; however none I know are significantly simpler than the form that ECDSA uses...

$\endgroup$
  • $\begingroup$ Thanks for the answer. But I still don't know how ECDSA's inventors come up with the idea that $s = k^{-1} (z + r d_A)$ ? $\endgroup$ – HOANG GIANG Dec 13 '18 at 4:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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