Assuming we have a valid EC-DSA signature $\sigma = (r,s)$. We can then easily create another valid signature without the knowledge of the secret key by negating $s$. That is, $\sigma' = (r, -s)$ can still be verified. The verification algorithm of ECDSA works the following
- $e = H(M)$
- $w = s^{-1 }\mod p$
- $u = ew \mod p$ and $v=rw \mod p$
- $Z=(z_1,z_2)=uG+v\cdot pk = uG+v\cdot xG$
- If $z_1=r\mod p$ return TRUE, otherwise FALSE
I'd like to understand mathematically why $\sigma'$ is still valid. If we fully extend the forth step of the verification algorithm, we get the following:
$Z = (x,y) = uG+v\cdot xG=G\cdot(ew+rwx)=G\cdot (e\cdot s^{-1}+r\cdot s^{-1}x)=G\cdot s^{-1}(e+rx)=G\cdot k\cdot(e+xr)^{-1}\cdot(e+xr)=G\cdot k $
Negating $s$ in $\sigma'$ essentially means, that we compute $Z = G\cdot (-k)$ instead of $Z = G\cdot k$. However, I see two ways to interpret $Z = G\cdot (-k)$, but obviously only one can be correct.
Recall that EC-DSA is applied on a finite field $\mathbb{F}_p$ with $p$ prime. $Z=G\cdot (-k) \mod p $ means that we first set $h = -k \mod p$. This is $h=p-k \mod p$ (For instance, $-3 \mod 17 = 14$.). We then calculate $Z = G\cdot h$. However, $G\cdot h$ does not equal $G\cdot k$ and thus, $\sigma \neq \sigma'$. This contradicts the assumption.
$Z=G\cdot (-k)$ can be written as $Z=-G\cdot k$. We then compute $Y=G\cdot k$ and eventually get $Z=-Y$. We simply have to negate the point $Y$. As $Y = (y_1, y_2)$ is a point on an elliptic curve, we get $Z = -Y = (y_1, -y_2) = (z_1, -z_2)$. The negation only affects the second point component and thus $\sigma = \sigma'$.
Question
Obviously, the first interpretation is not correct. But why? Is $\sigma = (r, -s)$ a valid signature, because it is only mirrored at the x-axis? The fifth step of the verification algorithm would still return true, because it takes only the x component of $Z$ into consideration? What prevents me to interpret $G\cdot (-k)$ like in the first way?