What is the intuition for ECDSA?

Question

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?

Answer 1

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.

Answer 2

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.