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$
  • 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 Jun 26 '18 at 7:35
  • 1
    $\begingroup$ Correct comment, I changed the scheme to be still simpler than ECDSA, but incorporating z. $\endgroup$ – Jimmy Song Jun 27 '18 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 Jun 27 '18 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 Jun 27 '18 at 14:40
  • $\begingroup$ Inverse calculation isn't that slow. It works in O(logn) time. $\endgroup$ – Mayank Jun 28 '18 at 5:05
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$
  • $\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 Jun 27 '18 at 4:05

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.