Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this community
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 ?
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:
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).
Why don't they just take $s = r d_A + z$
The equation that an ECDSA-like signature uses must satisfy these requirements:
It must be practical for the signer to compute
It must be impractical for someone who doesn't know the private key to compute
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.
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...
