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
This document (page 27) says that:
The only significant difference between ECDSA and DSA is in the generation of $r$.
Why is it necessary to have a function that takes a random number $k$? Why do we cannot use the random $k$ directly as our $r$ value in the signatures?
First an important warning: DSA and ECDSA are in no way proven to be secure. This is the lot of most cryptographic algorithms, so, at best, we can only have some intuition about why they ensure security.
DSA (and then ECDSA) is a loose derivative from Schnorr signature (in fact, it was not exactly Schnorr's algorithm for the avowed purpose of not falling within the scope of Schnorr's patent, which did not prevent some litigation to happen). It can be thus understood as a proof of knowledge. In this case, the value $k$ is a value that MUST NOT be revealed in the end; the signer commits to that value by computing and revealing $g^k$ ($kG$ for ECDSA).
Indeed, if you consider the signature verification algorithm, the value $g^k$ is rebuilt by the verifier, who only knows the public key: $$ \begin{eqnarray*} w &=& s^{-1} \mod q \\ u_1 &=& wH(m) \mod q \\ u_2 &=& rw \mod q \\ v &=& (g^{u_1} y^{u_2} \mod p) \mod q \\ \end{eqnarray*} $$
The value $g^{u_1}y^{u_2} \pmod p$ is indeed $g^k$ in its entirety.
However, if $k$ is revealed, then since the signature is $(r,s)$ where $$r = (H(m)+xr)/k \pmod q$$ then $x$ (the secret key) can be easily recomputed: $$x = r - k^{-1}H(m) \pmod q$$
To sum up, we need to use $g^k$ (or $kG$) and not directly $k$ because that is where the magic of the signature algorithm resides: in a commitment to a random value $k$, which is hidden behind the discrete logarithm, and still bound by algebraic relations to the (revealed) $g^k$, which allows its validation.
The DSA signing algorithm involves the value $k$ not only at the step $r=g^k$, but also when calculating $s = k^{-1} (H(m)+rx)$.
So if you assign $r$ randomly, then you would need to calculate $k$ for the calculation of $s$, which is the dlog of $r$ to base $g$.
The argument of Biv's answer is of course valid too: If you choose $r$ randomly, you can't be sure that it is actually in the subgroup generated by $g$. In the verification process you need this fact, so that different powers of $g$ cancel each other out.
Considering ECDSA: Actually, it is exactly the same algorithm, just the additive notation instead of multiplicative. And of course, that the actual addition in elliptic curves have their own unique definition. For example, to calculate modular exponentiations, usually square-and-multiply is used. In additive notation, this is just called "double-and-add", as noted in the Wiki article as well.
The simplest reason why we have to compute $r = kG$ or $r = g^k$ instead of directly using $k$ is to make sure that the random number you are using is actually in the cyclic group used by the verification.
Consider $g \in \mathbb{Z}_p^*$, pick a random $k$. How can you be sure that $k$ is in $<g,g^2, g^3, \ldots>$ ? This is a Discrete log problem by the way.
In the case of ECC, you want to work with numbers in $<G, 2G, 3G, \ldots>$, in the same way, if you do not compute $r = kG$, how can you be sure that $k$ is included in the cyclic group of generated numbers ?
The idea here is to have a random number included in the cyclic group, not any random number.
Also as Tylo noted:
The reason is simply that you also need $k$ at another step in the signing process. If you choose $r$ randomly and then have to get $k$, you would have to compute a discrete log (in the case of DSA).
That's an essential question! In fact, the DSA would be totally invalid if $r = g^k$ was not imposed.
Suppose that Eve is allowed to pick two arbitrary numbers:
Thus the signature should contain all the three numbers: $<s, r_1, r_2>$, so that $r_2 = g^{m\omega}y^{r_1 \omega}~(mod~p)$ provides a plausible verification check for $m$ (where $\omega := s^{-1} ~(mod~q)$).
However, the freedom of choosing $r_1, r_2$ without imposing $r_1 = r_2$ makes the algorithm vulnerable against attacks.
Without the private key $x$, and even without bothering to choose $k$, a dishonest signer Eve can freely pick up ANY two random lucky numbers $s$ and $r_1$ as the claimed "signagure", as long as $r_2$ is deliberately chosen as:
which makes the signature $<s, r_1, r_2>$ always valid for $m$ unless $k$ or $x$ is made public.
The essential principle is that only the honest signer using the true values of $x$ and $k$ can get the above result with $r_1 = r_2$ satisfied.
(The last step $mod ~ q$ in verification is omitted since its just a unification step to make the compared values below $q$. Also the signature $<s, r>$ is equivalent to $<\omega, r>$ where $\omega := s^{-1} ~(mod ~ q)$ since the calculation of the reverse number is also trifle)
