0
$\begingroup$

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

  1. $e = H(M)$
  2. $w = s^{-1 }\mod p$
  3. $u = ew \mod p$ and $v=rw \mod p$
  4. $Z=(z_1,z_2)=uG+v\cdot pk = uG+v\cdot xG$
  5. 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.

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

  2. $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?

$\endgroup$
2
$\begingroup$

Your second point is the correct interpretation.

Due to the negation map automorphism on (Weierstrass form) Elliptic Curves we have for all affine points that if $P = (x,y)$ belongs to the curve then also $-P = (x,-y)$ belongs to the curve.

This is due the curve's symmetry with the respect to the $x$ axis, as you said.

You can view it as $-k \cdot G = k \cdot (-G)$ but you can also see it as $k\cdot G$ and $-k\cdot G$ are symmetric with respect to the $x$ axis just like $G$ and $-G$. In fact, how would think of the negation of $(k\cdot G)$ if not with $-(k\cdot G)=(-k)\cdot G$ ?

Now the two point differs. But in the ECDSA verification only the x coordinate is checked, and this will be the same for $k\cdot G$ and $-k\cdot G$

$\endgroup$
  • $\begingroup$ I understand why the second point has to be correct. However, I still do not know what hampers me from a mathematical point of view to interpret G * (-k) just like I did in the first way? EC-DSA are basically some operations in F_p and -k mod p does exist. $\endgroup$ – null Jan 3 '18 at 10:24
  • $\begingroup$ Wrong! Coordinates work in F_p but scalars work modulo the order of the curve (which is different from p). Futhermore you CAN treat negative integers in finite field! E.g. -k mod p = -k + p mod p. If |k| < 0 then p-k is positive and is congruent to -k mod p $\endgroup$ – Ruggero Jan 3 '18 at 11:40

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.