1
$\begingroup$

The verification algorithm for ECDSA is:

$P=e\times G$,
$(r,y)=k\times G$, and
$s=(z+re)\times k^{-1} \bmod n$,

where $P$ is the public curve point, $G$ is the generator point, $e$ is the private key, $n$ is the order of $G$, $z$ is the message hash and $k\in [1,n-1]$.

$u = z\times s^{-1}$ and
$v = r\times s^{-1} \bmod n$.

If $u\times G+v\times P=(r,y)$, then signature is valid.

The math works for this, but why isn't something much easier done?

$P=e\times G$, $(r,y)=k\times G$ and $s=(k-rz)\times e^{-1}$

$rz\times G+s\times P=rz\times G+((k-rz)\times e^{-1})\times P=rz\times G+((k-rz)\times e^{-1})\times e\times G)=rz\times G+(k-rz)\times G=rz\times G+k\times G-rz\times G=k\times G=(r,y)$

So $r,s$ can be used almost directly in the $u\times G+v\times P$ equation and the same condition be used to check that the signature is valid. In addition, the formulation does not use as much division, which is computationally the most expensive part.

I'm sure there's some vulnerability with this more naive signature scheme. What is that vulnerability?

$\endgroup$
5
  • 3
    $\begingroup$ The point of ECDSA is to sign a message. In the original formula, the hash of the message is represented by z. In your idea, there is no message involved, so the operation is pointless. $\endgroup$
    – Faulst
    Commented Jun 26, 2018 at 7:35
  • 1
    $\begingroup$ Correct comment, I changed the scheme to be still simpler than ECDSA, but incorporating z. $\endgroup$
    – Jimmy Song
    Commented Jun 27, 2018 at 4:04
  • 1
    $\begingroup$ There are several variants of ECDSA (e.g. see airccj.org/CSCP/vol4/csit42111.pdf). Probably you have invented a further variant. $\endgroup$
    – user27950
    Commented Jun 27, 2018 at 6:13
  • 1
    $\begingroup$ But why is ECDSA so popular? The calculation of the inverse is so expensive compared to something like I explain above. At the very least, we can transmit s^-1 instead of s and make it a multiplication instead. $\endgroup$
    – Jimmy Song
    Commented Jun 27, 2018 at 14:40
  • $\begingroup$ Inverse calculation isn't that slow. It works in O(logn) time. $\endgroup$
    – Mayank
    Commented Jun 28, 2018 at 5:05

1 Answer 1

1
$\begingroup$

In the actual ECDSA, $(r,s)$ is called the signature of the message $m$ whose hash is $z$ i.e. $z=H(m)$.
By removing $z$ from the equation, you have completely eliminated any correlation of this "new incorrect signature" (which isn't even a signature) with the message, which is completely against the notion of a digital signature being a representative of the message which has been signed. If digital signatures did not depend on the messages, then anyone could just strip off a signature by someone, say $A$, from one message and use this signature to sign any document of their choice without $A$ even knowing.
In ECDSA, it is the $s$ value which is coupled with the message hash $z$, so if the $s$ value is completely independent of $z$ (and therefore $m$), then (r,s) is not at all a signature. It is then just a random linear equation between 2 points on an elliptic curve.

$\endgroup$
1
  • $\begingroup$ Sorry about that, I should have caught this. I changed the signature scheme to incorporate z. I'm wondering why we go through the hard work of division, which is very expensive. $\endgroup$
    – Jimmy Song
    Commented Jun 27, 2018 at 4:05

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.