6
$\begingroup$

This document (page 27) says that:

The only significant difference between ECDSA and DSA is in the generation of $r$.

  • ECDSA $r = (kG)_x \bmod n$ and,
  • DSA: $r=g^k \bmod p$

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?

$\endgroup$
3
  • 1
    $\begingroup$ If you knew $k$ for any single DSA signature you could recover the private signature key. $\endgroup$
    – SEJPM
    Sep 4, 2016 at 7:47
  • $\begingroup$ @SEJPM that's a fact. However, if I know k then I also know kG and g^k so, my question is still valid. Why do we need a calculations? $\endgroup$
    – lontivero
    Sep 4, 2016 at 15:04
  • $\begingroup$ I got it! r cannot be any random number because in the verification process we have to be able to get it back. In ECDSA: R = k*G in verification V = u1*G + u2*Q and v=xcood(V)=r=xcood(R). Am I right? $\endgroup$
    – lontivero
    Sep 4, 2016 at 15:59

4 Answers 4

5
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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).

$\endgroup$
1
  • $\begingroup$ Sure, you have to be in the correct subgroup, but that's not the main argument. 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 do a dlog. $\endgroup$
    – tylo
    Sep 5, 2016 at 11:35
1
$\begingroup$

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 different numbers instead of using the unique $r$ during the two steps:

  • Arbitrary number $r_1$ for calculating the signature $s := (m + xr_1)k^{-1} ~ (mod~q)$ (where $m$ denotes the Hash of the message, which should be $H(m_0)$ for security concerns), and --
  • $r_2 := g^k ~(mod ~ p) $ derived from the secret number $k$, used only in the last comparing step of verification.

Thus the signature should contain all the three numbers: $<s, r_1, r_2>$, so that $r_2 = g^{ms^{-1}}y^{r_1 s^{-1}}~(mod~p)$ provides a plausible verification check for $m$.

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 "signature", as long as $r_2$ is deliberately chosen as:

  • $r_2 := g^{m s^{-1}} y^{r_1 s^{-1}}$ $mod~p$.

which makes the signature $<s, r_1, r_2>$ always indistinguishable from one derived from the secret key $k$ and $x$, unless the secret keys are made public for the third party to verify.

However, if $r_1 = r_2$ is required, only the honest signer using the true values of $x$ and $k$ can get the above result.

(The last step $mod ~ q$ in verification is omitted since it is just a unification step to make the compared values below $q$.)

$\endgroup$

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.