13
$\begingroup$

I understand DH and ElGamal and RSA encryption/signatures. But when I look at ECDSA (or plain DSA), it seems like the formulas are just pulled out of thin air. I can verify that the algebra used in the verification formula does in fact work out, but I have no clue why forgeries are hard, why these formulas were used, why something simpler wouldn't work, and where the inventor(s) got all this stuff. Can someone explain the intuition behind ECDSA?

$\endgroup$
  • $\begingroup$ Asking for "intuition" makes it hard to know in advance exactly what kind of answer you are hoping for. Could you perhaps relate your question to exactly what you find unclear e.g. in the Wikipedia article en.wikipedia.org/wiki/Digital_Signature_Algorithm? $\endgroup$ – Henrick Hellström Mar 10 '16 at 2:12
  • $\begingroup$ @HenrickHellström The wikipedia article doesn't give any answers to the questions I gave above: why are forgeries hard? Where did the formulas come from? Why won't a simpler scheme work? What idea(s) did the inventor(s) use to come up with this? Wikipedia just gives what most sources give: a rote recapitulation of the formulas with no explanation. $\endgroup$ – Fixee Mar 10 '16 at 2:16
  • $\begingroup$ I'd suggest to remove/split away the parts on the how it works and why its hard as multiple questions in one will less likely be answered. $\endgroup$ – lathspell Mar 10 '16 at 6:31
16
$\begingroup$

It is possible to view DSA/ECDSA as an identification scheme (like Schnorr) but with a different variant of Fiat-Shamir. This gives the intuition that you are perhaps looking for. I will include an excerpt from Intro to Modern Cryptography 2nd edition (Section 12.5.2) which gives this explanation:

Begin Excerpt -- Section 12.5.2 DSA and ECDSA

The Digital Signature Algorithm (DSA) and Elliptic Curve Digital Signature Algorithm (ECDSA) are based on the discrete-logarithm problem in different classes of groups. They have been around in some form since 1991, and are both included in the current Digital Signature Standard (DSS) issued by NIST.

Both schemes follow a common template and can be viewed as being constructed from an underlying identification scheme (see the previous section). Let $ \mathbb{G}$ be a cyclic group of prime order $q$ with generator $g$. Consider the following identification scheme in which the prover's private key is $x$ and public key is $( \mathbb{G}, q, g, y)$ with $y=g^x$:

  1. The prover chooses uniform $k \in \mathbb{Z}_{q}^*$ and sends $I:=g^k$.
  2. The verifier chooses and sends uniform $\alpha, r \in \mathbb{Z}_{q}$ as the challenge.
  3. The prover sends $s:=[k^{-1} \cdot (\alpha+xr) \bmod q]$ as the response.
  4. The verifier accepts if $s\neq 0$ and $g^{\alpha s^{-1}} \!\cdot y^{r s^{-1}}=I$.

Note $s \neq 0$ unless $\alpha=-xr \bmod q$, which occurs with negligible probability. Assuming $s \neq 0$, the inverse $s^{-1} \bmod q$ exists and $$ g^{\alpha s^{-1}} \! \cdot y^{r s^{-1}} = g^{\alpha s^{-1}} \! \cdot g^{xrs^{-1}} = g^{(\alpha+xr) \cdot s^{-1}} = g^{(\alpha+xr) \cdot k \cdot (\alpha+xr)^{-1}} = I. $$ We thus see that correctness holds with all but negligible probability.

One can show that this identification scheme is secure if the discrete-logarithm problem is hard in the group. We merely sketch the argument, assuming familiarity with the results of the previous section (i.e., Schnorr and identification schemes). First of all, transcripts of honest executions can be simulated: to do so, simply choose uniform $\alpha, r \in \mathbb{Z}_{q}$ and $s \in \mathbb{Z}_{q}^*$, and then set $I:=g^{\alpha s^{-1}} \!\cdot y^{r s^{-1}}$. (This no longer gives a perfect simulation, but it is close enough.) Moreover, if an attacker outputs an initial message $I$ for which it can give correct responses $s_1, s_2 \in \mathbb{Z}_{q}^*$ to distinct challenges $(\alpha, r_1), (\alpha, r_2)$ then $$ g^{\alpha s_1^{-1}} \!\cdot y^{r_1 s_1^{-1}} = I = g^{\alpha s_2^{-1}} \!\cdot y^{r_2 s_2^{-1}}, $$ and so $g^{\alpha (s_1^{-1} - s_2^{-1})} = h^{r_1s_1^{-1} - r_2s_2^{-1}}$ and $\log_g h$ can be computed as in the previous section. The same holds if the attacker gives correct responses to distinct challenges $(\alpha_1, r), (\alpha_2, r)$.

The DSA/ECDSA signature schemes are constructed by ``collapsing'' the above identification scheme into a non-interactive algorithm run by the signer. In contrast to the Fiat--Shamir transform, however, the transformation here is carried out as follows:

  • Set $\alpha:=H(m)$, where $m$ is the message being signed and $H$ is a cryptographic hash function.
  • Set $r:=F(I)$ for a (specified) function $F: \mathbb{G}\rightarrow \mathbb{Z}_{q}$. Here, $F$ is a ``simple'' function that is not intended to act like a random oracle.

The function $F$ depends on the group $ \mathbb{G}$, which in turn depends on the scheme. In DSA, $ \mathbb{G}$ is taken to be an order-$q$ subgroup of $\mathbb{Z}_{p}^*$, for $p$ prime, and $F(I) =[I \bmod q]$. In ECDSA, $ \mathbb{G}$ is an order-$q$ subgroup of an elliptic-curve group $E({\mathbb Z}_p)$, for $p$ prime. (ECDSA also allows elliptic curves over other fields.) Any element of such a group can be represented as a pair $(x, y) \in {\mathbb Z}_p \times {\mathbb Z}_p$. The function $F$ in this case is defined as $F((x,y)) = [x \bmod q]$.

DSA and ECDSA - abstractly: Let $\cal G$ be a group -generator algorithm.

  • $\sf gen$: on input $1^n$, run ${\cal G}(1^n)$ to obtain $( \mathbb{G}, q, g)$. Choose uniform $x \in \mathbb{Z}_{q}$ and set $y:=g^x$. The public key is $(\mathbb{G}, q, g, y)$ and the private key is $x$.

    As part of key generation, two functions $H: \{0,1\}^* \rightarrow \mathbb{Z}_{q}$ and $F: \mathbb{G}\rightarrow \mathbb{Z}_{q}$ are specified, but we leave this implicit.

  • $\sf sign$: on input the private key $x$ and a message $m \in \{0,1\}^*$, choose uniform $k \in \mathbb{Z}_{q}^*$ and set $r:=F(g^k)$. Then compute $s:= [k^{-1} \cdot (H(m) + xr) \bmod q]$. (If $r=0$ or $s=0$ then start again with a fresh choice of $k$.) Output the signature \mbox{$(r, s)$}.
  • $\sf vrfy$: on input a public key $(\mathbb{G}, q, g, y)$, a message $m \in \{0,1\}^*$, and a signature $(r,s)$ with $r, s \neq 0 \bmod q$, output 1 if and only if $$ r = F\left(g^{H(m) \cdot s^{-1}} y^{r \cdot s^{-1}}\right). $$

Assuming hardness of the discrete-logarithm problem, DSA and ECDSA can be proven secure if $H$ and $F$ are modeled as random oracles. As we have discussed above, however, while the random-oracle model may be reasonable for $H$, it is not an appropriate model for $F$. No proofs of security are known for the specific choices of $F$ in the standard. Nevertheless, DSA and ECDSA have been used and studied for decades without any attacks being found.

Proper generation of $k$. The DSA/ECDSA schemes specify that the signer should choose a uniform $k \in \mathbb{Z}_{q}^*$ when computing a signature. Failure to choose $k$ properly (e.g., due to poor random-number generation) can lead to catastrophic results. For starters, if an attacker can predict the value of $k$ used to compute a signature $(r, s)$ on a message $m$, then they can compute the signer's private key. This is true because $s = k^{-1} \cdot (H(m)+xr) \bmod q$, and if $k$ is known then the only unknown is the private key $x$.

Even if $k$ is unpredictable, the attacker can compute the signer's private key if the same $k$ is ever used to generate two different signatures. The attacker can easily tell when this happens because then $r$ repeats as well. Say $(r, s_1)$ and $(r, s_2)$ are signatures on messages $m_1$ and $m_2$, respectively. Then \begin{eqnarray*} s_1 & = & k^{-1} \cdot (H(m_1)+ x r) \bmod q \\ s_2 & = & k^{-1} \cdot (H(m_2) + x r) \bmod q. \end{eqnarray*} Subtracting gives $s_1-s_2 = k^{-1} \left(H(m_1)-H(m_2)\right) \bmod q$, from which $k$ can be computed; given $k$, the attacker can determine the private key $x$ as in the previous paragraph. This very attack was used by hackers to extract the master private key from the Sony PlayStation (PS3) in 2010.

$\endgroup$
  • 1
    $\begingroup$ This is very helpful, but without the underlying material (ie, Schnorr signatures and identification scheme discussion) it still requires some work. But perhaps the most useful thing about your answer is that you show that ECDSA is the result of an evolution (from FS, FFS, Schnorr, DSA, then ECDSA) and that helps me know what legwork I need to undertake. Thanks Yehuda! $\endgroup$ – Fixee Mar 10 '16 at 20:01
-2
$\begingroup$

EC-Schnorr or ECDSA, there is no important difference. The addition of $k$ (Schnorr) or the muliplication with $k^{-1}$ an can be seen as encryption of message and private key. That's why it's secure.

$\endgroup$

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.